1 -- Created on: 1993-01-06
2 -- Created by: Denis PASCAL
3 -- Copyright (c) 1993-1999 Matra Datavision
4 -- Copyright (c) 1999-2014 OPEN CASCADE SAS
6 -- This file is part of Open CASCADE Technology software library.
8 -- This library is free software; you can redistribute it and/or modify it under
9 -- the terms of the GNU Lesser General Public License version 2.1 as published
10 -- by the Free Software Foundation, with special exception defined in the file
11 -- OCCT_LGPL_EXCEPTION.txt. Consult the file LICENSE_LGPL_21.txt included in OCCT
12 -- distribution for complete text of the license and disclaimer of any warranty.
14 -- Alternatively, this file may be used under the terms of Open CASCADE
15 -- commercial license or contractual agreement.
17 generic class ReducedGraph from GraphTools
24 --signature class ReducedGraph from GraphTools
27 -- VHasher as MapHasher from TCollection (Vertex);
28 -- VIterator as VertexIterator (Graph,Vertex);
29 -- GIterator as GraphIterator (Graph,Vertex))
31 ---Purpose: this generic class defines an algorithm to build and
32 -- visit the reduced graph of a given directed graph.
34 -- A reduced graph is defined itself as a graph where
35 -- each vertex represents a strong component. Each
36 -- strong component is a subset of vertices of the
37 -- underlying graph which are mutually dependant in the
38 -- way that there is always a path to go from a given
39 -- vertex to another vertex and back (Definition of a
40 -- cycle) . Of course the Reduced Graph (or Condensed
41 -- Graph) is a DAG (Directed Acyclic Graph).
43 -- After initialisation conditions (methods FromXXX) the
44 -- user has to build the reduced graph using the method
45 -- Perfrom. So each vertex of the underlying graph will
46 -- be encapsulated in a strong component (class SC of the
47 -- package). The algorithm may be reused using the
50 -- nested iterators and methods provides services to
51 -- visit the reduced graph:
53 -- * class SortedSCIterator defines an iterator to visit
54 -- each strong component. This visit is done according
55 -- to topologiacl sort of the reduced graph (which is a
58 -- * class AdjSCIterator defines an iterator to visit
59 -- each adjacent StrongComponent of a given one.
61 -- * The methods NbVertices and GetVertex of the reduced
62 -- graph returned the number and each vertex member of a
63 -- strong component. The method GetSC returned for a
64 -- given vertex its strong component.e
66 -- Warning: Noone method may be used on SC class. This class is only
67 -- here to identify a StrongComponent.
69 uses SC from GraphTools,
70 SCList from GraphTools,
71 ListIteratorOfSCList from GraphTools,
72 ListOfInteger from TColStd
74 raises NoSuchObject from Standard,
75 NoMoreObject from Standard,
76 OutOfRange from Standard
78 private class RGMap instantiates IndexedDataMap from TCollection
80 RGNode from GraphTools,
83 class SortedSCIterator from GraphTools
85 uses SC from GraphTools,
86 ListIteratorOfSCList from GraphTools
88 raises NoMoreObject from Standard,
89 NoSuchObject from Standard
93 Create returns SortedSCIterator from GraphTools;
95 Create (RG : ReducedGraph from GraphTools)
96 returns SortedSCIterator from GraphTools;
98 Initialize (me : in out; RG : ReducedGraph from GraphTools);
101 More (me) returns Boolean from Standard;
102 ---Purpose: Returns True if there are others Strong
107 raises NoMoreObject from Standard;
110 Value (me) returns SC from GraphTools
111 raises NoSuchObject from Standard;
116 myIterator : ListIteratorOfSCList;
118 end SortedSCIterator;
121 class AdjSCIterator from GraphTools
123 uses SC from GraphTools,
124 ListIteratorOfSCList from GraphTools
126 raises NoMoreObject from Standard,
127 NoSuchObject from Standard,
128 OutOfRange from Standard
132 Create returns AdjSCIterator from GraphTools;
134 Create (RG : ReducedGraph from GraphTools;
135 SC : SC from GraphTools)
136 returns AdjSCIterator from GraphTools;
138 Initialize (me : in out; RG : ReducedGraph from GraphTools;
139 SC : SC from GraphTools);
142 More (me) returns Boolean from Standard;
146 raises NoMoreObject from Standard;
149 Value (me) returns SC from GraphTools
151 raises NoSuchObject from Standard;
155 myIterator : ListIteratorOfSCList;
162 ---Purpose: Create an empty algorithm
163 returns ReducedGraph from GraphTools;
167 ---Purpose: Create the algorithm, set each vertex of <G>
168 -- reached by GIterator, as research conditions, and
169 -- perform the algorithm. User may directly visit
170 -- (nested class xxxIterator) the result of the
172 returns ReducedGraph from GraphTools;
174 FromGraph (me : in out; G : Graph);
175 ---Purpose: Add each vertex of <G> reached by GIterator tool
176 -- as research conditions. User must used Perform
177 -- method before visiting the result of the algorithm.
180 FromVertex (me : in out; V : Vertex);
181 ---Purpose: Add <V> as research condition. This method is
182 -- cumulative. User must used Perform method before
183 -- visting the result of the algorithm.
186 Perform (me : in out; G : Graph);
187 ---Purpose: Perform the algorithm IN <G> FROM previous
188 -- initialisation condition(s).
192 ---Purpose: Clear initialisation conditions. The algorithm may
193 -- be initialized and performed again from new
194 -- conditions. In that case new nested SCIterator and
195 -- AdjSCIterator may be reinitialized.
198 IsRoot (me; SC : SC from GraphTools)
199 returns Boolean from Standard;
202 IsLeaf (me; SC : SC from GraphTools)
203 returns Boolean from Standard;
206 NbVertices (me; SC : SC from GraphTools)
207 ---Purpose: returns number of vertices, members of <me>.
209 returns Integer from Standard;
211 GetVertex (me; SC : SC from GraphTools;
212 index : Integer from Standard)
214 ---C++: return const&
216 raises OutOfRange from Standard;
218 GetSC (me; V : Vertex)
219 ---Purpose: Returns the SC which contains <V>.
221 returns SC from GraphTools;
223 Visit (me : in out; k : Integer from Standard;
226 returns Integer from Standard
232 myVertices : RGMap from GraphTools;
234 performed : Boolean from Standard;
235 myNowIndex : Integer from Standard;
236 myStack : ListOfInteger from TColStd;
238 mySort : SCList from GraphTools;
242 class SortedSCIterator from GraphTools