tpl_indexArc.H File Reference

Arc indexing for fast lookup by endpoint nodes. More...

#include <cassert>
#include <functional>
#include <stdexcept>
#include <utility>
#include <tpl_dynSetTree.H>
#include <tpl_graph.H>
#include <ah-errors.H>

Include dependency graph for tpl_indexArc.H:

This graph shows which files directly or indirectly include this file:

Go to the source code of this file.

Classes
class	Aleph::IndexArc< GT, Tree, SA >
	Index for fast arc lookup by its endpoint nodes. More...
struct	Aleph::IndexArc< GT, Tree, SA >::Cmp_Arc

Namespaces
namespace	Aleph
	Main namespace for Aleph-w library functions.

Detailed Description

Arc indexing for fast lookup by endpoint nodes.

Example: Fast arc search between nodes

using GT = List_Graph<Graph_Node<string>, Graph_Arc<int>>;
GT g;
IndexArc<GT> arc_index(g);
 
auto a = g.insert_node("A");
auto b = g.insert_node("B");
auto c = g.insert_node("C");
 
// Insert and index arcs
auto ab = arc_index.insert_in_graph(a, b, 10);
auto bc = arc_index.insert_in_graph(b, c, 20);
 
// O(log n) search for arc between two nodes
auto found = arc_index.search(a, b);
if (found)
  cout << "Arc weight: " << found->get_info() << endl;

Example: Road network queries

// Quickly find road between two cities
auto road = arc_index.search(city1, city2);
if (road)
  cout << "Distance: " << road->get_info() << " km" << endl;

Author

Leandro Rabindranath León

Definition in file tpl_indexArc.H.