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
33class ctkDependencyGraphPrivate;
34
38class CTK_CORE_EXPORT ctkDependencyGraph
39{
40public:
41 ctkDependencyGraph(int nvertices);
43
45 void printGraph()const;
46
48 int numberOfVertices()const;
49
51 int numberOfEdges()const;
52
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
100protected:
101 ctkDependencyGraphPrivate* d_ptr;
102
103private:
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