CTK  0.1.0
The Common Toolkit is a community effort to provide support code for medical image analysis, surgical navigation, and related projects.
ctkDependencyGraph.h
Go to the documentation of this file.
1 /*=========================================================================
2 
3  Library: CTK
4 
5  Copyright (c) Kitware Inc.
6 
7  Licensed under the Apache License, Version 2.0 (the "License");
8  you may not use this file except in compliance with the License.
9  You may obtain a copy of the License at
10 
11  http://www.apache.org/licenses/LICENSE-2.0.txt
12 
13  Unless required by applicable law or agreed to in writing, software
14  distributed under the License is distributed on an "AS IS" BASIS,
15  WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
16  See the License for the specific language governing permissions and
17  limitations under the License.
18 
19 =========================================================================*/
20 
21 #ifndef __ctkDependencyGraph_h
22 #define __ctkDependencyGraph_h
23 
24 // CTK includes
25 #if !defined(NO_SYMBOL_EXPORT)
26 #include "ctkCoreExport.h"
27 #else
28 #define CTK_CORE_EXPORT
29 #endif
30 
31 #include <list>
32 
33 class ctkDependencyGraphPrivate;
34 
38 class CTK_CORE_EXPORT ctkDependencyGraph
39 {
40 public:
41  ctkDependencyGraph(int nvertices);
43 
44  void printAdditionalInfo()const;
45  void printGraph()const;
46 
48  int numberOfVertices()const;
49 
51  int numberOfEdges()const;
52 
54  bool checkForCycle();
55 
57  bool cycleDetected()const;
58 
60  int cycleOrigin()const;
61 
63  int cycleEnd()const;
64 
65  // The traverse of the tree will print information on standard output
66  void setVerbose(bool verbose);
67 
71  void insertEdge(int from, int to);
72 
75  void findPaths(int from, int to, std::list<std::list<int>* >& paths);
76 
78  void findPath(int from, int to, std::list<int>& path);
79 
82  void setEdgeListToExclude(const std::list<int>& list);
83 
86  virtual bool shouldExcludeEdge(int edge)const;
87 
89  virtual void processEdge(int /*from*/, int /*to*/){}
90 
95  bool topologicalSort(std::list<int>& sorted, int rootId = -1);
96 
98  void sourceVertices(std::list<int>& sources);
99 
100 protected:
101  ctkDependencyGraphPrivate* d_ptr;
102 
103 private:
104 
105  // Intentionally disable copy semantics
107  ctkDependencyGraph &operator=(const ctkDependencyGraph &);
108 };
109 
110 #endif
111 
Class to implement a dependency graph, converted to STL instead of Qt.
void setEdgeListToExclude(const std::list< int > &list)
bool topologicalSort(std::list< int > &sorted, int rootId=-1)
int numberOfEdges() const
Get the number of edges associated with current graph.
void printAdditionalInfo() const
virtual bool shouldExcludeEdge(int edge) const
void sourceVertices(std::list< int > &sources)
Retrieve all vertices with indegree 0.
bool cycleDetected() const
Return true if there is at least one cycle.
ctkDependencyGraph(int nvertices)
int numberOfVertices() const
Get the number of vertices associated with current graph.
void insertEdge(int from, int to)
int cycleOrigin() const
If a cycle has been detected, return the origin of the cycle otherwise 0.
virtual void processEdge(int, int)
Called each time an edge is visited.
virtual ~ctkDependencyGraph()
void findPaths(int from, int to, std::list< std::list< int > * > &paths)
void findPath(int from, int to, std::list< int > &path)
Retrieve the path between two vertices.
void printGraph() const
void setVerbose(bool verbose)
int cycleEnd() const
If a cycle has been detected, return the end of the cycle otherwise 0.
bool checkForCycle()
Traverse graph and check for cycle.
ctkDependencyGraphPrivate * d_ptr