mo_on_trees_example.cc File Reference

Three creative scenarios demonstrating Mo's algorithm on trees. More...

#include <tpl_mo_on_trees.H>
#include <tpl_graph.H>
#include <tpl_sgraph.H>
#include <tpl_agraph.H>
#include <tpl_dynListStack.H>
#include <tpl_dynSetHash.H>
#include <cassert>
#include <cstdio>

Include dependency graph for mo_on_trees_example.cc:

Go to the source code of this file.

Functions
template<class GT >
static size_t	brute_subtree_distinct (const GT &g, typename GT::Node *tree_root, typename GT::Node *subtree_root)
template<class GT >
static size_t	brute_path_distinct (const GT &g, typename GT::Node *root, typename GT::Node *u, typename GT::Node *v)
static void	rainforest_biodiversity ()
static void	network_latency ()
static void	org_chart ()
static void	filesystem_inodes ()
int	main ()

Detailed Description

Three creative scenarios demonstrating Mo's algorithm on trees.

SCENARIO 1 — "Rainforest Biodiversity" (List_Graph, subtree queries)

A botanist catalogues plant species in a hierarchical forest canopy. Each node represents a canopy section labelled by its dominant species. Subtree queries count how many distinct species appear in each section and all sub-sections beneath it.

SCENARIO 2 — "Network Latency Analysis" (List_SGraph, path queries)

A tree-shaped data-centre network has routers labelled by latency class. Path queries between pairs of routers count the number of distinct latency classes along the route.

SCENARIO 3 — "Corporate Org Chart" (Array_Graph, path + subtree)

An org chart tree stores department IDs. Subtree queries find distinct departments under a VP; path queries count distinct departments between two employees. Demonstrates Array_Graph.

Definition in file mo_on_trees_example.cc.

Function Documentation

brute_path_distinct()

template<class GT >

static size_t brute_path_distinct ( const GT &  g, typename GT::Node *  root, typename GT::Node *  u, typename GT::Node *  v  )

static

Definition at line 123 of file mo_on_trees_example.cc.

References Aleph::divide_and_conquer_partition_dp(), Aleph::DynMapHashTable< Key, Data, HashTable, Cmp >::find(), GraphCommon< GT, Node, Arc >::get_connected_node(), Aleph::DynHashTable< Key, HashTable, Cmp >::insert(), Aleph::DynMapHashTable< Key, Data, HashTable, Cmp >::insert(), Aleph::DynListStack< T >::push(), and root().

Referenced by network_latency(), org_chart(), TEST(), TEST(), TEST(), TYPED_TEST(), and TYPED_TEST().

brute_subtree_distinct()

template<class GT >

static size_t brute_subtree_distinct ( const GT &  g, typename GT::Node *  tree_root, typename GT::Node *  subtree_root  )

static

Definition at line 76 of file mo_on_trees_example.cc.

References Aleph::divide_and_conquer_partition_dp(), Aleph::DynMapHashTable< Key, Data, HashTable, Cmp >::find(), GraphCommon< GT, Node, Arc >::get_connected_node(), Aleph::DynMapHashTable< Key, Data, HashTable, Cmp >::insert(), and Aleph::DynListStack< T >::push().

Referenced by org_chart(), rainforest_biodiversity(), TEST(), TEST(), TYPED_TEST(), and TYPED_TEST().

filesystem_inodes()

static void filesystem_inodes ( )

static

Definition at line 386 of file mo_on_trees_example.cc.

References Aleph::destroy_tree(), Aleph::divide_and_conquer_partition_dp(), and root().

Referenced by main().

main()

int main

(

)

Definition at line 471 of file mo_on_trees_example.cc.

References Aleph::divide_and_conquer_partition_dp(), filesystem_inodes(), network_latency(), org_chart(), and rainforest_biodiversity().

network_latency()

static void network_latency ( )

static

Definition at line 236 of file mo_on_trees_example.cc.

References brute_path_distinct(), Aleph::divide_and_conquer_partition_dp(), GraphCommon< GT, Node, Arc >::esize(), Aleph::List_Graph< _Graph_Node, _Graph_Arc >::insert_arc(), Aleph::List_Graph< _Graph_Node, _Graph_Arc >::insert_node(), and GraphCommon< GT, Node, Arc >::vsize().

Referenced by main().

org_chart()

static void org_chart ( )

static

Definition at line 307 of file mo_on_trees_example.cc.

References brute_path_distinct(), brute_subtree_distinct(), Aleph::divide_and_conquer_partition_dp(), GraphCommon< GT, Node, Arc >::esize(), Aleph::List_Graph< _Graph_Node, _Graph_Arc >::insert_arc(), Aleph::List_Graph< _Graph_Node, _Graph_Arc >::insert_node(), and GraphCommon< GT, Node, Arc >::vsize().

Referenced by main().

rainforest_biodiversity()

static void rainforest_biodiversity ( )

static

Definition at line 171 of file mo_on_trees_example.cc.

References brute_subtree_distinct(), Aleph::divide_and_conquer_partition_dp(), GraphCommon< GT, Node, Arc >::esize(), h, Aleph::List_Graph< _Graph_Node, _Graph_Arc >::insert_arc(), Aleph::List_Graph< _Graph_Node, _Graph_Arc >::insert_node(), r, and GraphCommon< GT, Node, Arc >::vsize().

Referenced by main().