CTK  0.1.0
The Common Toolkit is a community effort to provide support code for medical image analysis, surgical navigation, and related projects.
Public Member Functions | Protected Attributes | List of all members
ctkDependencyGraph Class Reference

Class to implement a dependency graph, converted to STL instead of Qt. More...

#include <Libs/Core/ctkDependencyGraph.h>

Public Member Functions

bool checkForCycle ()
 Traverse graph and check for cycle. More...
 
 ctkDependencyGraph (int nvertices)
 
bool cycleDetected () const
 Return true if there is at least one cycle. More...
 
int cycleEnd () const
 If a cycle has been detected, return the end of the cycle otherwise 0. More...
 
int cycleOrigin () const
 If a cycle has been detected, return the origin of the cycle otherwise 0. More...
 
void findPath (int from, int to, std::list< int > &path)
 Retrieve the path between two vertices. More...
 
void findPaths (int from, int to, std::list< std::list< int > * > &paths)
 
void insertEdge (int from, int to)
 
int numberOfEdges () const
 Get the number of edges associated with current graph. More...
 
int numberOfVertices () const
 Get the number of vertices associated with current graph. More...
 
void printAdditionalInfo () const
 
void printGraph () const
 
virtual void processEdge (int, int)
 Called each time an edge is visited. More...
 
void setEdgeListToExclude (const std::list< int > &list)
 
void setVerbose (bool verbose)
 
virtual bool shouldExcludeEdge (int edge) const
 
void sourceVertices (std::list< int > &sources)
 Retrieve all vertices with indegree 0. More...
 
bool topologicalSort (std::list< int > &sorted, int rootId=-1)
 
virtual ~ctkDependencyGraph ()
 

Protected Attributes

ctkDependencyGraphPrivate * d_ptr
 

Detailed Description

Class to implement a dependency graph, converted to STL instead of Qt.

Definition at line 38 of file ctkDependencyGraph.h.

Constructor & Destructor Documentation

◆ ctkDependencyGraph()

ctkDependencyGraph::ctkDependencyGraph ( int  nvertices)

◆ ~ctkDependencyGraph()

virtual ctkDependencyGraph::~ctkDependencyGraph ( )
virtual

Member Function Documentation

◆ checkForCycle()

bool ctkDependencyGraph::checkForCycle ( )

Traverse graph and check for cycle.

◆ cycleDetected()

bool ctkDependencyGraph::cycleDetected ( ) const

Return true if there is at least one cycle.

◆ cycleEnd()

int ctkDependencyGraph::cycleEnd ( ) const

If a cycle has been detected, return the end of the cycle otherwise 0.

◆ cycleOrigin()

int ctkDependencyGraph::cycleOrigin ( ) const

If a cycle has been detected, return the origin of the cycle otherwise 0.

◆ findPath()

void ctkDependencyGraph::findPath ( int  from,
int  to,
std::list< int > &  path 
)

Retrieve the path between two vertices.

◆ findPaths()

void ctkDependencyGraph::findPaths ( int  from,
int  to,
std::list< std::list< int > * > &  paths 
)

Retrieve the paths between two vertices Caller is responsible to clear paths list

◆ insertEdge()

void ctkDependencyGraph::insertEdge ( int  from,
int  to 
)

Insert edge (from, to) indicate a relation between two vertices Note also that vertex id should be >= 1

◆ numberOfEdges()

int ctkDependencyGraph::numberOfEdges ( ) const

Get the number of edges associated with current graph.

◆ numberOfVertices()

int ctkDependencyGraph::numberOfVertices ( ) const

Get the number of vertices associated with current graph.

◆ printAdditionalInfo()

void ctkDependencyGraph::printAdditionalInfo ( ) const

◆ printGraph()

void ctkDependencyGraph::printGraph ( ) const

◆ processEdge()

virtual void ctkDependencyGraph::processEdge ( int  ,
int   
)
inlinevirtual

Called each time an edge is visited.

Definition at line 89 of file ctkDependencyGraph.h.

◆ setEdgeListToExclude()

void ctkDependencyGraph::setEdgeListToExclude ( const std::list< int > &  list)

List of edge to exclude An edge is specified using its extremity

◆ setVerbose()

void ctkDependencyGraph::setVerbose ( bool  verbose)

◆ shouldExcludeEdge()

virtual bool ctkDependencyGraph::shouldExcludeEdge ( int  edge) const
virtual

The default implementation check if 'edge' is in the list of edge to exclude See setEdgeListToExclude

◆ sourceVertices()

void ctkDependencyGraph::sourceVertices ( std::list< int > &  sources)

Retrieve all vertices with indegree 0.

◆ topologicalSort()

bool ctkDependencyGraph::topologicalSort ( std::list< int > &  sorted,
int  rootId = -1 
)

Perform a topological sort Return false if the graph contains cycles If a rootId is given, the subgraph starting at the root id is sorted See cycleDetected, cycleOrigin, cycleEnd

Member Data Documentation

◆ d_ptr

ctkDependencyGraphPrivate* ctkDependencyGraph::d_ptr
protected

Definition at line 101 of file ctkDependencyGraph.h.


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