Aleph::Compute_Cycle_In_Digraph< GT, Itor, SA > Class Template Reference

Determines if a digraph contains a cycle and constructs it. More...

#include <Tarjan.H>

Public Member Functions
	Compute_Cycle_In_Digraph (SA __sa=SA())
	Constructs a cycle computation instance with an arc filter.
bool	operator() (const GT &g, Path< GT > &path) const
	Invokes the computation of a cycle in a digraph.
Path< GT >	operator() (const GT &g) const
	Computes and returns a cycle in the digraph.
Path< GT >	operator() (const GT &g, typename GT::Node *src) const
	Computes and returns a cycle starting from a specific node.

Private Attributes
SA	sa_

Detailed Description

template<AlephGraph GT, template< typename, class > class Itor = Out_Iterator, ArcFilter< GT > SA = Dft_Show_Arc<GT>>
class Aleph::Compute_Cycle_In_Digraph< GT, Itor, SA >

Determines if a digraph contains a cycle and constructs it.

Compute_Cycle_In_Digraph() takes a digraph g, determines if it contains a cycle, and if so, constructs a path containing the cycle in question.

The class is based on Tarjan's algorithm.

The function uses two type parameters:

1. GT: the digraph class.
2. SA: the arc filter used by the internal iterator.

The class delegates to Tarjan_Connected_Components, which marks traversal progress with the Aleph::Depth_First and Aleph::Min node bits.

Note

This class is intended for directed graphs. Behavior on undirected graphs is undefined.

Definition at line 999 of file Tarjan.H.

Constructor & Destructor Documentation

Compute_Cycle_In_Digraph()

template<AlephGraph GT, template< typename, class > class Itor = Out_Iterator, ArcFilter< GT > SA = Dft_Show_Arc<GT>>

Aleph::Compute_Cycle_In_Digraph< GT, Itor, SA >::Compute_Cycle_In_Digraph ( SA  __sa = SA() )

inline

Constructs a cycle computation instance with an arc filter.

Parameters

[in]

__sa

Arc filter functor. Defaults to Dft_Show_Arc<GT>.

Definition at line 1009 of file Tarjan.H.

Member Function Documentation

operator()() [1/3]

template<AlephGraph GT, template< typename, class > class Itor = Out_Iterator, ArcFilter< GT > SA = Dft_Show_Arc<GT>>

Path< GT > Aleph::Compute_Cycle_In_Digraph< GT, Itor, SA >::operator() ( const GT &  g ) const

inline

Computes and returns a cycle in the digraph.

Parameters

[in]

g

The graph to search for cycles.

Returns

A Path containing the cycle if found, empty path otherwise.

Exceptions

bad_alloc

if there is not enough memory.

Definition at line 1034 of file Tarjan.H.

References Aleph::blossom_maximum_cardinality_matching(), and Aleph::Compute_Cycle_In_Digraph< GT, Itor, SA >::sa_.

operator()() [2/3]

template<AlephGraph GT, template< typename, class > class Itor = Out_Iterator, ArcFilter< GT > SA = Dft_Show_Arc<GT>>

bool Aleph::Compute_Cycle_In_Digraph< GT, Itor, SA >::operator() ( const GT &  g, Path< GT > &  path  ) const

inline

Invokes the computation of a cycle in a digraph.

Parameters

[in]	g	the graph on which to compute its blocks.
[out]	path	path that defines the cycle.

Returns

true if the graph contains a cycle; false otherwise. In the latter case the value of path is indeterminate.

Exceptions

bad_alloc

if there is not enough memory.

Definition at line 1021 of file Tarjan.H.

References Aleph::blossom_maximum_cardinality_matching(), and Aleph::Compute_Cycle_In_Digraph< GT, Itor, SA >::sa_.

operator()() [3/3]

template<AlephGraph GT, template< typename, class > class Itor = Out_Iterator, ArcFilter< GT > SA = Dft_Show_Arc<GT>>

Path< GT > Aleph::Compute_Cycle_In_Digraph< GT, Itor, SA >::operator() ( const GT &  g, typename GT::Node *  src  ) const

inline

Computes and returns a cycle starting from a specific node.

Parameters

[in]	g	The graph to search for cycles.
[in]	src	The source node to start the search from (must not be null).

Returns

A Path containing the cycle if found, empty path otherwise.

Exceptions

domain_error	if src is null.
bad_alloc	if there is not enough memory.

Definition at line 1049 of file Tarjan.H.

References Aleph::blossom_maximum_cardinality_matching(), Aleph::Tarjan_Connected_Components< GT, Itor, SA >::compute_cycle(), and Aleph::Compute_Cycle_In_Digraph< GT, Itor, SA >::sa_.

Member Data Documentation

sa_

template<AlephGraph GT, template< typename, class > class Itor = Out_Iterator, ArcFilter< GT > SA = Dft_Show_Arc<GT>>

SA Aleph::Compute_Cycle_In_Digraph< GT, Itor, SA >::sa_

private

Definition at line 1001 of file Tarjan.H.

Referenced by Aleph::Compute_Cycle_In_Digraph< GT, Itor, SA >::operator()(), Aleph::Compute_Cycle_In_Digraph< GT, Itor, SA >::operator()(), and Aleph::Compute_Cycle_In_Digraph< GT, Itor, SA >::operator()().

---

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

• Tarjan.H