tlp::AcyclicTest Class Reference

#include <AcyclicTest.h>

Inherits tlp::Observable.

Static Public Member Functions
static bool	acyclicTest (const Graph *graph, std::vector< edge > *obstructionEdges=NULL)
static bool	isAcyclic (const Graph *graph)
static void	makeAcyclic (Graph *graph, std::vector< edge > &reversed, std::vector< tlp::SelfLoops > &selfLoops)

Additional Inherited Members
Private Member Functions inherited from tlp::Observable
void	addListener (Observable *const listener) const
void	addObserver (Observable *const observer) const
unsigned int	countListeners () const
unsigned int	countObservers () const
unsigned int	getReceived () const
unsigned int	getSent () const
void	removeListener (Observable *const listener) const
void	removeObserver (Observable *const observerver) const
	Observable (const Observable &)
tlp::Iterator< tlp::Observable * > *	getObservables () const
bool	hasOnlookers () const
void	notifyObservers ()
void	observableDeleted ()
Observable &	operator= (const Observable &)
void	sendEvent (const Event &message)
virtual void	treatEvents (const std::vector< Event > &events)
Static Private Member Functions inherited from tlp::Observable
static Observable *	getObject (tlp::node n)
static const tlp::VectorGraph &	getObservableGraph ()
static void	holdObservers ()
static bool	isAlive (tlp::node n)
static unsigned int	observersHoldCounter ()
static void	unholdObservers ()

Detailed Description

This class provides tests for acyclicity on a graph. Results are cached in a map of graphs and result. This class observes the graphs that have been tested to remove the result from this graph if it is modified. This forces the use of the singleton pattern instead of simply using static functions/members.

Definition at line 58 of file AcyclicTest.h.

Member Function Documentation

static bool tlp::AcyclicTest::acyclicTest ( const Graph *  graph, std::vector< edge > *  obstructionEdges = NULL  )

static

Returns whether the graph is acyclic. Collection of obstruction edges takes a bit of time, as iteration over the graph must continue even when it has been found cyclic.

Parameters

graph	the graph to test for acyclicity
obstructionEdges	If not null, will be filled with edges that cause the graph to be cyclic. Defaults to 0.

Returns

bool

static bool tlp::AcyclicTest::isAcyclic ( const Graph *  graph )

static

Checks whether the graph is acyclic or not. The result is cached so subsequent calls are in O(1).

Parameters

graph

The graph on which to perform the acyclicity test.

Returns

bool True if the graph is acyclic, false otherwise.

static void tlp::AcyclicTest::makeAcyclic ( Graph *  graph, std::vector< edge > &  reversed, std::vector< tlp::SelfLoops > &  selfLoops  )

static

Makes the graph acyclic by removing edges.

Parameters

graph	The graph to make acyclic.
reversed	The edges that were reversed during the process.
selfLoops	Sets of two nodes and three edges that were added in stead of self loops.

Returns

void