tpl_indexGraph_example.cc File Reference

Educational examples for indexed graphs (fast O(log n) lookups) More...

#include <iostream>
#include <chrono>
#include <tpl_indexGraph.H>
#include <tpl_graph.H>

Include dependency graph for tpl_indexGraph_example.cc:

Go to the source code of this file.

Functions
int	main ()

Detailed Description

Educational examples for indexed graphs (fast O(log n) lookups)

WHAT IS AN INDEXED GRAPH?

A graph wrapper that maintains search trees for:

• Nodes: Indexed by node value for O(log n) search
• Arcs: Indexed by endpoint pair for O(log n) search

Standard graph operations are O(n) linear search Indexed graphs provide O(log n) search - HUGE speedup for large graphs!

WHY USE INDEX_GRAPH?

• Fast node lookup by value: O(log n) vs O(n)
• Fast arc search: O(log n) vs O(degree)
• Prevents duplicate nodes automatically
• Essential for large graphs (n > 1000 nodes)

TRADE-OFFS:

• Much faster searches O(log n)
• Automatic duplicate prevention
• Slightly slower insertions O(log n) vs O(1)
• Extra memory for indices

COMPILE & RUN:

g++ -std=c++20 -I.. -o tpl_indexGraph_example tpl_indexGraph_example.cc ./tpl_indexGraph_example

Definition in file tpl_indexGraph_example.cc.

Function Documentation

main()

int main

(

)

Definition at line 43 of file tpl_indexGraph_example.cc.

References GraphCommon< GT, Node, Arc >::get_num_nodes(), Aleph::Index_Graph< GT, Compare, Tree >::insert_arc(), Aleph::Index_Graph< GT, Compare, Tree >::insert_node(), log2(), Aleph::maps(), N, Aleph::Index_Graph< GT, Compare, Tree >::search_arc(), and Aleph::Index_Graph< GT, Compare, Tree >::search_node().