Tulip  4.1.0
Better Visualization Through Research
 All Classes Files Functions Variables Enumerations Enumerator Properties Groups Pages
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 ()
 
Observableoperator= (const Observable &)
 
void sendEvent (const Event &message)
 
virtual void treatEvents (const std::vector< Event > &events)
 
- Static Private Member Functions inherited from tlp::Observable
static ObservablegetObject (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
graphthe graph to test for acyclicity
obstructionEdgesIf 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
graphThe 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
graphThe graph to make acyclic.
reversedThe edges that were reversed during the process.
selfLoopsSets of two nodes and three edges that were added in stead of self loops.
Returns
void