smtrat::CycleEnumerator< FHG, Collector > Struct Template Reference

This class encapsulates an algorithm for enumerating all cycles. More...

#include <ForwardHyperGraph.h>

Collaboration diagram for smtrat::CycleEnumerator< FHG, Collector >:

Public Member Functions
	CycleEnumerator (const FHG &fhg, Collector &c)
	Constructor from a graph and a collector object. More...
bool	findAll ()
	Start the search for all cycles. Returns whether the search was finished (true) or aborted (false). More...

Private Types
using	Vertex = typename FHG::Vertex
	Type of a vertex. More...

Private Member Functions
void	unblock (Vertex v)
	Unblocks the given vertex and all vertices that depend on it. More...
bool	enumerate (Vertex src, Vertex v)
	Recursively enumerate all cycles that start in src and are currently in v. More...

Private Attributes
const FHG &	mGraph
	Reference to the graph we search cycles in. More...
std::vector< bool >	mBlocked
	Stores whether a vector is currently blocked. More...
std::vector< std::vector< Vertex > >	mBlockDependencies
	Stores vertex dependencies when vertices are blocked. More...
std::vector< typename FHG::Vertex >	mVertexStack
	Stores the current list of vertices. More...
std::vector< typename FHG::Edge >	mEdgeStack
	Stores the current list of edges. More...
Collector &	mCollector
	The callback object. More...
bool	mAborted
	Whether this search has been aborted by the collector. More...

Detailed Description

template<typename FHG, typename Collector>
struct smtrat::CycleEnumerator< FHG, Collector >

This class encapsulates an algorithm for enumerating all cycles.

This class implements an adaption of the algorithm described in [Johnson75]. Unlike the algorithm described there, this version works on forward hypergraphs as implemented by ForwardHyperGraph.

Although the algorithm works recursively, this implementation can be used somewhat iteratively. The cycles are given to the caller using an collector functor. If this functor returns true, the search for more cycles is aborted immediately. Due to this pattern, there is no need to store the cycles within this class and thus the memory usage is minimized.

Definition at line 152 of file ForwardHyperGraph.h.

Member Typedef Documentation

Vertex

template<typename FHG , typename Collector >

using smtrat::CycleEnumerator< FHG, Collector >::Vertex = typename FHG::Vertex

private

Type of a vertex.

Definition at line 155 of file ForwardHyperGraph.h.

Constructor & Destructor Documentation

CycleEnumerator()

template<typename FHG , typename Collector >

smtrat::CycleEnumerator< FHG, Collector >::CycleEnumerator ( const FHG &  fhg, Collector &  c  )

inline

Constructor from a graph and a collector object.

Definition at line 173 of file ForwardHyperGraph.h.

Member Function Documentation

enumerate()

template<typename FHG , typename Collector >

bool smtrat::CycleEnumerator< FHG, Collector >::enumerate ( Vertex  src, Vertex  v  )

private

Recursively enumerate all cycles that start in src and are currently in v.

findAll()

template<typename FHG , typename Collector >

bool smtrat::CycleEnumerator< FHG, Collector >::findAll

(

)

Start the search for all cycles. Returns whether the search was finished (true) or aborted (false).

unblock()

template<typename FHG , typename Collector >

void smtrat::CycleEnumerator< FHG, Collector >::unblock ( Vertex  v )

inlineprivate

Unblocks the given vertex and all vertices that depend on it.

Definition at line 187 of file ForwardHyperGraph.h.

Field Documentation

mAborted

template<typename FHG , typename Collector >

bool smtrat::CycleEnumerator< FHG, Collector >::mAborted

private

Whether this search has been aborted by the collector.

Definition at line 170 of file ForwardHyperGraph.h.

mBlockDependencies

template<typename FHG , typename Collector >

std::vector<std::vector<Vertex> > smtrat::CycleEnumerator< FHG, Collector >::mBlockDependencies

private

Stores vertex dependencies when vertices are blocked.

Definition at line 162 of file ForwardHyperGraph.h.

mBlocked

template<typename FHG , typename Collector >

std::vector<bool> smtrat::CycleEnumerator< FHG, Collector >::mBlocked

private

Stores whether a vector is currently blocked.

Definition at line 160 of file ForwardHyperGraph.h.

mCollector

template<typename FHG , typename Collector >

Collector& smtrat::CycleEnumerator< FHG, Collector >::mCollector

private

The callback object.

Definition at line 168 of file ForwardHyperGraph.h.

mEdgeStack

template<typename FHG , typename Collector >

std::vector<typename FHG::Edge> smtrat::CycleEnumerator< FHG, Collector >::mEdgeStack

private

Stores the current list of edges.

Definition at line 166 of file ForwardHyperGraph.h.

mGraph

template<typename FHG , typename Collector >

const FHG& smtrat::CycleEnumerator< FHG, Collector >::mGraph

private

Reference to the graph we search cycles in.

Definition at line 157 of file ForwardHyperGraph.h.

mVertexStack

template<typename FHG , typename Collector >

std::vector<typename FHG::Vertex> smtrat::CycleEnumerator< FHG, Collector >::mVertexStack

private

Stores the current list of vertices.

Definition at line 164 of file ForwardHyperGraph.h.

---

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

• smtrat-modules/ICEModule/ForwardHyperGraph.h