Index for fast arc lookup by its endpoint nodes. More...

#include <tpl_indexArc.H>

Inheritance diagram for Aleph::IndexArc< GT, Tree, SA >:

Collaboration diagram for Aleph::IndexArc< GT, Tree, SA >:

Classes
struct	Cmp_Arc

Public Member Functions
GT_Arc *	insert (GT_Arc *e)
	Insert an arc pointer into the index.

GT_Arc *	search (void src, void tgt) const
	Search an arc that connects two nodes.

GT_Arc *	search_directed (void src, void tgt) const
	Search an arc that connects two nodes as a directed pair.

GT_Arc *	search (GT_Arc *a) const
	Search an arc by using its endpoint pointers.

GT_Arc *	insert_in_graph (GT_Node src, GT_Node tgt, const GT_Arc_Type &info)
	Create a new arc between two nodes, insert it into the graph and index it.

GT_Arc *	insert_in_graph (GT_Node src, GT_Node tgt, GT_Arc_Type &&info=GT_Arc_Type())

void	remove (GT_Arc *e)
	Remove an arc from the index.

void	remove_from_graph (GT_Arc *a)
	Remove an arc from both index and graph.

void	clear_index ()
	Remove all arcs from the index.

void	build_index ()
	Insert into the index all arcs currently present in the graph.

	IndexArc (GT &__g, bool with_init=true, SA &&__sa=SA())
	Construct an arc index for a graph.

	IndexArc (GT &__g, bool with_init, SA &__sa)
	Construct an arc index for a graph (lvalue filter overload).

size_t	size () const
	Return the number of arcs currently stored in the index.

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 Member Functions
void	init ()

Private Attributes
GT &	g

DynSetTree< GT_Arc *, Tree, Cmp_Arc >	index

SA	sa

Detailed Description

template<class GT, template< class, class > class Tree = Rand_Tree, class SA = Dft_Show_Arc<GT>>
class Aleph::IndexArc< GT, Tree, SA >

Index for fast arc lookup by its endpoint nodes.

IndexArc indexes the arcs of a graph by the pair of endpoint nodes the arc connects.

For directed graphs, the key is the ordered pair (src, tgt).
For non-directed graphs, the key is the unordered pair {src, tgt} (so (src, tgt) and (tgt, src) refer to the same indexed arc).

Main operations are:

search(src, tgt): find an arc between two nodes.
insert(arc): insert an already existing arc into the index.
insert_in_graph(src, tgt, info): create an arc in the graph and index it.

Template Parameters

GT	Graph type (typically `List_Graph` or `List_Digraph`).
Tree	Binary-search-tree type used internally by `DynSetTree`.
SA	Arc filter type used by iterators when building the index.

Note: IndexArc assumes a simple graph for correctness of the “one key -> one arc” mapping (no parallel arcs connecting the same endpoints). If the underlying graph contains parallel arcs, only one of them can be indexed.

See also: IndexNode Index_Graph

Definition at line 119 of file tpl_indexArc.H.

Member Typedef Documentation

◆ GT_Arc

template<class GT , template< class, class > class Tree = Rand_Tree, class SA = Dft_Show_Arc<GT>>

typedef GT::Arc Aleph::IndexArc< GT, Tree, SA >::GT_Arc

private

Definition at line 123 of file tpl_indexArc.H.

◆ GT_Arc_Type

template<class GT , template< class, class > class Tree = Rand_Tree, class SA = Dft_Show_Arc<GT>>

typedef GT::Arc_Type Aleph::IndexArc< GT, Tree, SA >::GT_Arc_Type

private

Definition at line 125 of file tpl_indexArc.H.

◆ GT_Node

template<class GT , template< class, class > class Tree = Rand_Tree, class SA = Dft_Show_Arc<GT>>

typedef GT::Node Aleph::IndexArc< GT, Tree, SA >::GT_Node

private

Definition at line 124 of file tpl_indexArc.H.

◆ GT_Node_Type

template<class GT , template< class, class > class Tree = Rand_Tree, class SA = Dft_Show_Arc<GT>>

typedef GT::Node_Type Aleph::IndexArc< GT, Tree, SA >::GT_Node_Type

private

Definition at line 126 of file tpl_indexArc.H.

Constructor & Destructor Documentation

◆ IndexArc() [1/2]

template<class GT , template< class, class > class Tree = Rand_Tree, class SA = Dft_Show_Arc<GT>>

Aleph::IndexArc< GT, Tree, SA >::IndexArc	(	GT &	__g,
		bool	with_init = `true`,
		SA &&	__sa = `SA()`
	)

inline

Construct an arc index for a graph.

Parameters

[in]	__g	Graph to be indexed.
[in]	with_init	If `true`, all current arcs of `__g` are inserted into the index at construction time.
[in]	__sa	Arc filter used when iterating arcs.

Exceptions

std::bad_alloc if there is not enough memory.

Definition at line 324 of file tpl_indexArc.H.

References Aleph::IndexArc< GT, Tree, SA >::init(), and Aleph::maps().

◆ IndexArc() [2/2]

template<class GT , template< class, class > class Tree = Rand_Tree, class SA = Dft_Show_Arc<GT>>

Aleph::IndexArc< GT, Tree, SA >::IndexArc	(	GT &	__g,
		bool	with_init,
		SA &	__sa
	)

inline

Construct an arc index for a graph (lvalue filter overload).

Parameters

[in]	__g	Graph to be indexed.
[in]	with_init	If `true`, all current arcs of `__g` are inserted into the index at construction time.
[in]	__sa	Arc filter used when iterating arcs.

Exceptions

std::bad_alloc if there is not enough memory.

Definition at line 339 of file tpl_indexArc.H.

References Aleph::IndexArc< GT, Tree, SA >::init(), and Aleph::maps().

Member Function Documentation

◆ build_index()

template<class GT , template< class, class > class Tree = Rand_Tree, class SA = Dft_Show_Arc<GT>>

void Aleph::IndexArc< GT, Tree, SA >::build_index ( )

inline

Insert into the index all arcs currently present in the graph.

Definition at line 299 of file tpl_indexArc.H.

References Aleph::IndexArc< GT, Tree, SA >::g, Aleph::IndexArc< GT, Tree, SA >::insert(), Aleph::Filter_Iterator< Container, It, Show_Item >::next_ne(), Aleph::IndexArc< GT, Tree, SA >::sa, and Aleph::IndexArc< GT, Tree, SA >::search().

Referenced by TEST().

◆ clear_index()

template<class GT , template< class, class > class Tree = Rand_Tree, class SA = Dft_Show_Arc<GT>>

void Aleph::IndexArc< GT, Tree, SA >::clear_index ( )

inline

Remove all arcs from the index.

Definition at line 293 of file tpl_indexArc.H.

References Aleph::IndexArc< GT, Tree, SA >::index.

Referenced by TEST().

◆ init()

template<class GT , template< class, class > class Tree = Rand_Tree, class SA = Dft_Show_Arc<GT>>

void Aleph::IndexArc< GT, Tree, SA >::init ( )

inlineprivate

Definition at line 308 of file tpl_indexArc.H.

References Aleph::IndexArc< GT, Tree, SA >::g, Aleph::IndexArc< GT, Tree, SA >::insert(), Aleph::Filter_Iterator< Container, It, Show_Item >::next_ne(), and Aleph::IndexArc< GT, Tree, SA >::sa.

Referenced by Aleph::IndexArc< GT, Tree, SA >::IndexArc(), and Aleph::IndexArc< GT, Tree, SA >::IndexArc().

◆ insert()

template<class GT , template< class, class > class Tree = Rand_Tree, class SA = Dft_Show_Arc<GT>>

GT_Arc * Aleph::IndexArc< GT, Tree, SA >::insert ( GT_Arc * e )

inline

Insert an arc pointer into the index.

If an arc with the same endpoints already exists in the index, then no insertion is performed and the already indexed arc is returned.

Parameters

[in] e Arc pointer to index.

Returns: The indexed arc pointer (either e or the already indexed one).

Definition at line 179 of file tpl_indexArc.H.

References Aleph::IndexArc< GT, Tree, SA >::index.

Referenced by Aleph::IndexArc< GT, Tree, SA >::build_index(), Aleph::IndexArc< GT, Tree, SA >::init(), Aleph::IndexArc< GT, Tree, SA >::insert_in_graph(), Aleph::IndexArc< GT, Tree, SA >::insert_in_graph(), TEST(), TEST(), and TEST().

◆ insert_in_graph() [1/2]

template<class GT , template< class, class > class Tree = Rand_Tree, class SA = Dft_Show_Arc<GT>>

Aleph::IndexArc< GT, Tree, SA >::insert_in_graph	(	GT_Node *	src,
		GT_Node *	tgt,
		const GT_Arc_Type &	info
	)

inline

Create a new arc between two nodes, insert it into the graph and index it.

This method enforces the simple-graph constraint: if an arc between these endpoints already exists (according to the index), a std::domain_error is thrown.

Parameters

[in]	src	Source node.
[in]	tgt	Target node.
[in]	info	Arc payload to copy/move into the new arc.

Returns: Pointer to the created arc.

Exceptions

std::bad_alloc	if there is not enough memory.
std::domain_error	if there is already an arc between these nodes.

This is an overloaded member function, provided for convenience. It differs from the above function only in what argument(s) it accepts.

Definition at line 250 of file tpl_indexArc.H.

References ah_domain_error_if, Aleph::IndexArc< GT, Tree, SA >::g, Aleph::IndexArc< GT, Tree, SA >::insert(), Aleph::List_Graph< _Graph_Node, _Graph_Arc >::insert_arc(), Aleph::maps(), and Aleph::IndexArc< GT, Tree, SA >::search().

Referenced by TEST().

◆ insert_in_graph() [2/2]

template<class GT , template< class, class > class Tree = Rand_Tree, class SA = Dft_Show_Arc<GT>>

GT_Arc * Aleph::IndexArc< GT, Tree, SA >::insert_in_graph	(	GT_Node *	src,
		GT_Node *	tgt,
		GT_Arc_Type &&	info = `GT_Arc_Type()`
	)

inline

Definition at line 265 of file tpl_indexArc.H.

References ah_domain_error_if, Aleph::IndexArc< GT, Tree, SA >::g, Aleph::IndexArc< GT, Tree, SA >::insert(), Aleph::List_Graph< _Graph_Node, _Graph_Arc >::insert_arc(), Aleph::maps(), and Aleph::IndexArc< GT, Tree, SA >::search().

◆ remove()

template<class GT , template< class, class > class Tree = Rand_Tree, class SA = Dft_Show_Arc<GT>>

void Aleph::IndexArc< GT, Tree, SA >::remove ( GT_Arc * e )

inline

Remove an arc from the index.

Definition at line 280 of file tpl_indexArc.H.

References Aleph::IndexArc< GT, Tree, SA >::index.

Referenced by Aleph::IndexArc< GT, Tree, SA >::remove_from_graph(), and TEST().

◆ remove_from_graph()

template<class GT , template< class, class > class Tree = Rand_Tree, class SA = Dft_Show_Arc<GT>>

void Aleph::IndexArc< GT, Tree, SA >::remove_from_graph ( GT_Arc * a )

inline

Remove an arc from both index and graph.

Definition at line 286 of file tpl_indexArc.H.

References Aleph::IndexArc< GT, Tree, SA >::g, Aleph::IndexArc< GT, Tree, SA >::remove(), and Aleph::List_Graph< _Graph_Node, _Graph_Arc >::remove_arc().

Referenced by TEST().

◆ search() [1/2]

template<class GT , template< class, class > class Tree = Rand_Tree, class SA = Dft_Show_Arc<GT>>

GT_Arc * Aleph::IndexArc< GT, Tree, SA >::search ( GT_Arc * a ) const

inline

Search an arc by using its endpoint pointers.

Parameters

[in] a Arc whose endpoints are used as search key.

Returns: A pointer to the indexed arc if it exists; nullptr otherwise.

Definition at line 232 of file tpl_indexArc.H.

References Aleph::IndexArc< GT, Tree, SA >::search(), GTArcCommon< ArcInfo >::src_node, and GTArcCommon< ArcInfo >::tgt_node.

◆ search() [2/2]

template<class GT , template< class, class > class Tree = Rand_Tree, class SA = Dft_Show_Arc<GT>>

GT_Arc * Aleph::IndexArc< GT, Tree, SA >::search	(	void *	src,
		void *	tgt
	)		const

inline

Search an arc that connects two nodes.

For directed graphs, only the arc (src, tgt) is searched. For non-directed graphs, (src, tgt) and (tgt, src) refer to the same indexed arc.

Parameters

[in]	src	Source node pointer.
[in]	tgt	Target node pointer.

Returns: A pointer to the indexed arc if it exists; nullptr otherwise.

Definition at line 195 of file tpl_indexArc.H.

References Aleph::IndexArc< GT, Tree, SA >::index, Aleph::maps(), GTArcCommon< ArcInfo >::src_node, and GTArcCommon< ArcInfo >::tgt_node.

Referenced by Aleph::IndexArc< GT, Tree, SA >::build_index(), Aleph::IndexArc< GT, Tree, SA >::insert_in_graph(), Aleph::IndexArc< GT, Tree, SA >::insert_in_graph(), Aleph::IndexArc< GT, Tree, SA >::search(), TEST(), TEST(), and TEST().

◆ search_directed()

template<class GT , template< class, class > class Tree = Rand_Tree, class SA = Dft_Show_Arc<GT>>

GT_Arc * Aleph::IndexArc< GT, Tree, SA >::search_directed	(	void *	src,
		void *	tgt
	)		const

inline

Search an arc that connects two nodes as a directed pair.

In directed graphs this is equivalent to search(src, tgt). In non-directed graphs, direction is not meaningful and this method behaves like search(src, tgt).

Parameters