Builds node and arc indices for fast lookup and retrieval. More...

#include <tpl_indexGraph.H>

Collaboration diagram for Aleph::Index_Graph< GT, Compare, Tree >:

Public Member Functions
	Index_Graph (GT &g)
	Creates an index of the graph: nodes and arcs are indexed.

GT_Node *	insert_node (const GT_Node_Type &info)
	Creates a new node and inserts it into the graph and the index.

GT_Arc *	insert_arc (GT_Node src, GT_Node tgt, const GT_Arc_Type &info=GT_Arc_Type())
	Creates a new arc between two nodes and inserts it into the graph and the index.

GT_Node *	search_node (GT_Node *p)
	Looks up a node in the index.

GT_Node *	search_node (const GT_Node_Type &info)
	Looks up a node in the index.

GT_Arc *	search_arc (GT_Node src, GT_Node tgt)
	Looks up an arc in the index given its two nodes.

void	remove_node (GT_Node *p)
	Removes node p from the graph and from the index.

void	remove_arc (GT_Arc *a)
	Removes arc a from the graph and from the index.

size_t	get_num_arcs () const
	Returns the number of arcs the index contains.

size_t	get_num_nodes () const
	Returns the number of nodes the index contains.

Private Types
typedef GT::Arc	GT_Arc

typedef GT::Node	GT_Node

typedef GT::Arc_Type	GT_Arc_Type

typedef GT::Node_Type	GT_Node_Type

Private Attributes
IndexNode< GT, Compare, Tree >	idx_node

IndexArc< GT, Tree >	idx_arc

Detailed Description

template<class GT, class Compare = Dft_Node_Cmp<GT>, template< class, class > class Tree = Treap>
class Aleph::Index_Graph< GT, Compare, Tree >

Builds node and arc indices for fast lookup and retrieval.

Index_Graph indexes nodes and arcs for the sake of their fast retrieval.

To make it easier and safer to use, Index_Graph offers the classic topological operations of a graph: insert_node(), insert_arc(), etc.

The class takes the following type parameters:

GT: the graph type, based on List_Graph
Compare: comparison class for the nodes' indexing key. This class's contract is to implement operator () like this:
template <class GT>

struct Dft_Node_Cmp

{

bool

operator () (typename GT::Node * p1, typename GT::Node * p2) const

{

// access the nodes and compare according to the desired field

}

};

Aleph::Dft_Node_Cmp
Default node comparison class for Nodes_Index.
Definition tpl_graph_indexes.H:59

Aleph::Graph_Node< Node_Info >

By default this class is programmed to compare the value returned by get_info() on each node. For that, the < operator of type GT::Node_Type must be implemented

Tree: the type of binary search tree used internally to index the keys. Treaps are used by default

See also: IndexArc IndexNode

Author: Leandro Rabindranath León (lrleon at ula dot ve); Alejandro Mujica (aledrums at gmail dot com)

Definition at line 118 of file tpl_indexGraph.H.

Member Typedef Documentation

◆ GT_Arc

template<class GT , class Compare = Dft_Node_Cmp<GT>, template< class, class > class Tree = Treap>

typedef GT::Arc Aleph::Index_Graph< GT, Compare, Tree >::GT_Arc

private

Definition at line 122 of file tpl_indexGraph.H.

◆ GT_Arc_Type

template<class GT , class Compare = Dft_Node_Cmp<GT>, template< class, class > class Tree = Treap>

typedef GT::Arc_Type Aleph::Index_Graph< GT, Compare, Tree >::GT_Arc_Type

private

Definition at line 124 of file tpl_indexGraph.H.

◆ GT_Node

template<class GT , class Compare = Dft_Node_Cmp<GT>, template< class, class > class Tree = Treap>

typedef GT::Node Aleph::Index_Graph< GT, Compare, Tree >::GT_Node

private

Definition at line 123 of file tpl_indexGraph.H.

◆ GT_Node_Type

template<class GT , class Compare = Dft_Node_Cmp<GT>, template< class, class > class Tree = Treap>

typedef GT::Node_Type Aleph::Index_Graph< GT, Compare, Tree >::GT_Node_Type

private

Definition at line 125 of file tpl_indexGraph.H.

Constructor & Destructor Documentation

◆ Index_Graph()

template<class GT , class Compare = Dft_Node_Cmp<GT>, template< class, class > class Tree = Treap>

Aleph::Index_Graph< GT, Compare, Tree >::Index_Graph ( GT & g )

inline

Creates an index of the graph: nodes and arcs are indexed.

Definition at line 133 of file tpl_indexGraph.H.

Member Function Documentation

◆ get_num_arcs()

template<class GT , class Compare = Dft_Node_Cmp<GT>, template< class, class > class Tree = Treap>

size_t Aleph::Index_Graph< GT, Compare, Tree >::get_num_arcs ( ) const

inline

Returns the number of arcs the index contains.

Definition at line 229 of file tpl_indexGraph.H.

References Aleph::Index_Graph< GT, Compare, Tree >::idx_arc.

Referenced by TEST_F(), TEST_F(), TEST_F(), TEST_F(), TEST_F(), TEST_F(), TEST_F(), TEST_F(), TEST_F(), TEST_F(), TEST_F(), TEST_F(), TEST_F(), TEST_F(), and TEST_F().

◆ get_num_nodes()

template<class GT , class Compare = Dft_Node_Cmp<GT>, template< class, class > class Tree = Treap>

size_t Aleph::Index_Graph< GT, Compare, Tree >::get_num_nodes ( ) const

inline

Returns the number of nodes the index contains.

Definition at line 232 of file tpl_indexGraph.H.

References Aleph::Index_Graph< GT, Compare, Tree >::idx_node.

Referenced by TEST_F(), TEST_F(), TEST_F(), TEST_F(), TEST_F(), TEST_F(), TEST_F(), TEST_F(), TEST_F(), TEST_F(), TEST_F(), TEST_F(), TEST_F(), TEST_F(), TEST_F(), TEST_F(), TEST_F(), TEST_F(), TEST_F(), TEST_F(), TEST_F(), TEST_F(), TEST_F(), TEST_F(), and TEST_F().

◆ insert_arc()

template<class GT , class Compare = Dft_Node_Cmp<GT>, template< class, class > class Tree = Treap>

GT_Arc * Aleph::Index_Graph< GT, Compare, Tree >::insert_arc	(	GT_Node *	src,
		GT_Node *	tgt,
		const GT_Arc_Type &	info = `GT_Arc_Type()`
	)

inline

Creates a new arc between two nodes and inserts it into the graph and the index.

Parameters

[in]	src	source node.
[in]	tgt	target node.
[in]	info	information to be copied into the arc. By default it is whatever the GT_Arc_Type() constructor gives.

Returns: pointer to the new arc.

Exceptions

bad_alloc if there is not enough memory.

Definition at line 159 of file tpl_indexGraph.H.

References ah_domain_error_if, Aleph::blossom_maximum_cardinality_matching(), Aleph::Index_Graph< GT, Compare, Tree >::idx_arc, and Aleph::Index_Graph< GT, Compare, Tree >::idx_node.

Referenced by main(), TEST_F(), TEST_F(), TEST_F(), TEST_F(), TEST_F(), TEST_F(), TEST_F(), TEST_F(), TEST_F(), TEST_F(), TEST_F(), TEST_F(), TEST_F(), TEST_F(), TEST_F(), TEST_F(), TEST_F(), TEST_F(), TEST_F(), and TEST_F().

◆ insert_node()

template<class GT , class Compare = Dft_Node_Cmp<GT>, template< class, class > class Tree = Treap>

GT_Node * Aleph::Index_Graph< GT, Compare, Tree >::insert_node ( const GT_Node_Type & info )

inline

Creates a new node and inserts it into the graph and the index.

Parameters

[in] info information to be copied into the node.

Returns: pointer to the new node.

Exceptions

bad_alloc if there is not enough memory.

Definition at line 144 of file tpl_indexGraph.H.

References Aleph::blossom_maximum_cardinality_matching(), and Aleph::Index_Graph< GT, Compare, Tree >::idx_node.

Referenced by main(), TEST_F(), TEST_F(), TEST_F(), TEST_F(), TEST_F(), TEST_F(), TEST_F(), TEST_F(), TEST_F(), TEST_F(), TEST_F(), TEST_F(), TEST_F(), TEST_F(), TEST_F(), TEST_F(), TEST_F(), TEST_F(), TEST_F(), TEST_F(), TEST_F(), TEST_F(), TEST_F(), TEST_F(), TEST_F(), TEST_F(), TEST_F(), TEST_F(), TEST_F(), TEST_F(), TEST_F(), TEST_F(), TEST_F(), TEST_F(), TEST_F(), TEST_F(), TEST_F(), TEST_F(), TEST_F(), TEST_F(), TEST_F(), TEST_F(), TEST_F(), TEST_F(), TEST_F(), and TEST_F().

◆ remove_arc()

template<class GT , class Compare = Dft_Node_Cmp<GT>, template< class, class > class Tree = Treap>

void Aleph::Index_Graph< GT, Compare, Tree >::remove_arc ( GT_Arc * a )

inline

Removes arc a from the graph and from the index.

Definition at line 223 of file tpl_indexGraph.H.

References Aleph::Index_Graph< GT, Compare, Tree >::idx_arc.

Referenced by TEST_F(), TEST_F(), and TEST_F().

◆ remove_node()

template<class GT , class Compare = Dft_Node_Cmp<GT>, template< class, class > class Tree = Treap>

void Aleph::Index_Graph< GT, Compare, Tree >::remove_node ( GT_Node * p )

inline

Removes node p from the graph and from the index.

Parameters

[in] p pointer to the node to remove

Definition at line 212 of file tpl_indexGraph.H.

References Aleph::Index_Graph< GT, Compare, Tree >::idx_arc, and Aleph::Index_Graph< GT, Compare, Tree >::idx_node.

Referenced by TEST_F(), TEST_F(), TEST_F(), TEST_F(), TEST_F(), TEST_F(), TEST_F(), TEST_F(), and TEST_F().

◆ search_arc()

template<class GT , class Compare = Dft_Node_Cmp<GT>, template< class, class > class Tree = Treap>

GT_Arc * Aleph::Index_Graph< GT, Compare, Tree >::search_arc	(	GT_Node *	src,
		GT_Node *	tgt
	)

inline

Looks up an arc in the index given its two nodes.

Parameters

[in]	src	pointer to the source node.
[in]	tgt	pointer to the target node.

Returns: pointer to the arc if it is found in the index; nullptr otherwise.

Definition at line 203 of file tpl_indexGraph.H.

References Aleph::Index_Graph< GT, Compare, Tree >::idx_arc.

Referenced by main(), TEST_F(), TEST_F(), TEST_F(), TEST_F(), TEST_F(), TEST_F(), and TEST_F().

◆ search_node() [1/2]

template<class GT , class Compare = Dft_Node_Cmp<GT>, template< class, class > class Tree = Treap>

GT_Node * Aleph::Index_Graph< GT, Compare, Tree >::search_node ( const GT_Node_Type & info )

inline

Looks up a node in the index.

Parameters

[in] info information by which the node will be searched for.

Returns: pointer to the node if it is found in the index; nullptr otherwise.

Warning: Keep in mind that the lookup is performed according to the implementation of the Compare comparison class passed at instantiation time.

Definition at line 191 of file tpl_indexGraph.H.

References Aleph::blossom_maximum_cardinality_matching(), and Aleph::Index_Graph< GT, Compare, Tree >::idx_node.

◆ search_node() [2/2]

template<class GT , class Compare = Dft_Node_Cmp<GT>, template< class, class > class Tree = Treap>

GT_Node * Aleph::Index_Graph< GT, Compare, Tree >::search_node ( GT_Node * p )

inline

Looks up a node in the index.

Parameters

[in] p pointer to the node.

Returns: pointer to the node if it is found in the index; nullptr otherwise.

Definition at line 177 of file tpl_indexGraph.H.

References Aleph::Index_Graph< GT, Compare, Tree >::idx_node.

Referenced by main(), TEST_F(), TEST_F(), TEST_F(), TEST_F(), TEST_F(), TEST_F(), TEST_F(), TEST_F(), TEST_F(), TEST_F(), TEST_F(), TEST_F(), TEST_F(), TEST_F(), TEST_F(), TEST_F(), and TEST_F().

Member Data Documentation

◆ idx_arc

template<class GT , class Compare = Dft_Node_Cmp<GT>, template< class, class > class Tree = Treap>

IndexArc<GT, Tree> Aleph::Index_Graph< GT, Compare, Tree >::idx_arc

private

Definition at line 128 of file tpl_indexGraph.H.

Referenced by Aleph::Index_Graph< GT, Compare, Tree >::get_num_arcs(), Aleph::Index_Graph< GT, Compare, Tree >::insert_arc(), Aleph::Index_Graph< GT, Compare, Tree >::remove_arc(), Aleph::Index_Graph< GT, Compare, Tree >::remove_node(), and Aleph::Index_Graph< GT, Compare, Tree >::search_arc().

◆ idx_node

template<class GT , class Compare = Dft_Node_Cmp<GT>, template< class, class > class Tree = Treap>

IndexNode<GT, Compare, Tree> Aleph::Index_Graph< GT, Compare, Tree >::idx_node

private

Definition at line 127 of file tpl_indexGraph.H.

Referenced by Aleph::Index_Graph< GT, Compare, Tree >::get_num_nodes(), Aleph::Index_Graph< GT, Compare, Tree >::insert_arc(), Aleph::Index_Graph< GT, Compare, Tree >::insert_node(), Aleph::Index_Graph< GT, Compare, Tree >::remove_node(), Aleph::Index_Graph< GT, Compare, Tree >::search_node(), and Aleph::Index_Graph< GT, Compare, Tree >::search_node().

The documentation for this class was generated from the following file:

tpl_indexGraph.H

Public Member Functions

Private Types

Private Attributes

Detailed Description

Member Typedef Documentation

◆ GT_Arc

◆ GT_Arc_Type

◆ GT_Node

◆ GT_Node_Type

Constructor & Destructor Documentation

◆ Index_Graph()

Member Function Documentation

◆ get_num_arcs()

◆ get_num_nodes()

◆ insert_arc()

◆ insert_node()

◆ remove_arc()

◆ remove_node()

◆ search_arc()

◆ search_node() [1/2]

◆ search_node() [2/2]

Member Data Documentation

◆ idx_arc

◆ idx_node