tpl_indexArc_example.cc File Reference

Educational examples for arc indexing (fast arc lookup) More...

#include <iostream>
#include <tpl_indexArc.H>
#include <tpl_graph.H>

Include dependency graph for tpl_indexArc_example.cc:

Go to the source code of this file.

Functions
int	main ()

Detailed Description

Educational examples for arc indexing (fast arc lookup)

WHAT IS ARC INDEXING?

Maintains a binary search tree of arcs indexed by (source, target) pair Enables O(log m) arc search instead of O(degree) iteration Essential for dense graphs where degree is large

TYPICAL PROBLEM:

"Does arc exist from node A to node B?" Without index: Iterate through all arcs of A - O(degree) With index: Binary search tree lookup - O(log m)

WHEN TO USE?

• Dense graphs (many arcs per node)
• Frequent arc existence queries
• Need fast arc weight/data lookup
• Building adjacency-matrix-like behavior

COMPILE & RUN:

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

Definition in file tpl_indexArc_example.cc.

Function Documentation

main()

int main

(

)

Definition at line 37 of file tpl_indexArc_example.cc.

References Aleph::DynList< T >::append(), Aleph::List_Graph< _Graph_Node, _Graph_Arc >::insert_node(), log2(), Aleph::maps(), N, and nodes.