b311480e |
1 | -- Created on: 1992-12-24 |
2 | -- Created by: Denis PASCAL |
3 | -- Copyright (c) 1992-1999 Matra Datavision |
4 | -- Copyright (c) 1999-2012 OPEN CASCADE SAS |
5 | -- |
6 | -- The content of this file is subject to the Open CASCADE Technology Public |
7 | -- License Version 6.5 (the "License"). You may not use the content of this file |
8 | -- except in compliance with the License. Please obtain a copy of the License |
9 | -- at http://www.opencascade.org and read it completely before using this file. |
10 | -- |
11 | -- The Initial Developer of the Original Code is Open CASCADE S.A.S., having its |
12 | -- main offices at: 1, place des Freres Montgolfier, 78280 Guyancourt, France. |
13 | -- |
14 | -- The Original Code and all software distributed under the License is |
15 | -- distributed on an "AS IS" basis, without warranty of any kind, and the |
16 | -- Initial Developer hereby disclaims all such warranties, including without |
17 | -- limitation, any warranties of merchantability, fitness for a particular |
18 | -- purpose or non-infringement. Please see the License for the specific terms |
19 | -- and conditions governing the rights and limitations under the License. |
20 | |
7fd59977 |
21 | |
22 | |
23 | generic class TopologicalSortFromIterator from GraphTools |
24 | (Graph as any; |
25 | Vertex as any; |
26 | VHasher as any; |
27 | VIterator as any) |
28 | |
29 | --generic class TopologicalSortFromIterator from GraphTools |
30 | -- (Graph as any; |
31 | -- Vertex as any; |
32 | -- VHasher as MapHasher from TCollection (Vertex); |
33 | -- VIterator as VertexIterator (Graph,Vertex)) |
34 | |
35 | ---Purpose: This generic class defines an iterator to visit |
36 | -- each vertex of the underlying graph, in such an |
37 | -- order that noone vertex is reach before any vertex |
38 | -- that point to it. In general the order produced by |
39 | -- topological sort is not unique. Usefull for DAG |
40 | -- Topological Sort. The option <ignoreSelfLoop> |
41 | -- allows the user to ignore (or not) any vertex wich |
42 | -- contains a self loop. The option <processCycle> |
43 | -- allows the user to visit (or not> vertices which |
44 | -- are in a cycle. |
45 | |
46 | |
47 | uses SequenceOfInteger from TColStd |
48 | |
49 | raises NoSuchObject from Standard, |
50 | NoMoreObject from Standard, |
51 | DomainError from Standard |
52 | |
53 | private class TSMap instantiates IndexedDataMap from TCollection |
54 | (Vertex,TSNode from GraphTools,VHasher); |
55 | |
56 | is |
57 | |
58 | Create |
59 | ---Purpose: Create an empty algorithm. |
60 | returns TopologicalSortFromIterator from GraphTools; |
61 | |
62 | FromVertex (me : in out; V : Vertex); |
63 | ---Purpose: Add <V> as initial condition. This method is |
64 | -- cumulative. Use Perform method before visting the |
65 | -- result of the algorithm. |
66 | ---Level: Public |
67 | |
68 | Reset (me : in out); |
69 | ---Purpose: Reset the algorithm. It may be reused with new |
70 | -- initial conditions. |
71 | ---Level: Public |
72 | |
73 | Perform (me : in out; G : Graph; |
74 | ignoreSelfLoop : Boolean from Standard; |
75 | processCycle : Boolean from Standard); |
76 | ---Purpose: Peform the algorithm in <G> from initial setted |
77 | -- conditions according to the two following flags. |
78 | -- * <ignoreSelfLoop> allows the user to ignore (or |
79 | -- not) any vertex wich contains a self loop. |
80 | -- * <processCycle> allows the user to visit (or not> |
81 | -- vertex which is in a cycle. |
82 | ---Level: Public |
83 | |
84 | More (me) |
85 | returns Boolean from Standard; |
86 | ---Level: Public |
87 | |
88 | Next (me : in out) |
89 | raises NoMoreObject from Standard; |
90 | ---Level: Public |
91 | |
92 | Value (me) |
93 | returns any Vertex |
94 | ---Level: Public |
95 | ---C++: return const & |
96 | raises NoSuchObject from Standard; |
97 | |
98 | IsInCycle (me) |
99 | returns Boolean from Standard |
100 | ---Purpose: Returns TRUE if the current vertex is in a cycle. |
101 | ---Level: Public |
102 | raises NoSuchObject from Standard; |
103 | |
104 | |
105 | fields |
106 | |
107 | -- conditions |
108 | myVertices : TSMap from GraphTools; |
109 | myIgnoreSelfLoop : Boolean from Standard; |
110 | myProcessCycle : Boolean from Standard; |
111 | -- result |
112 | mySort : SequenceOfInteger from TColStd; |
113 | myCycles : Integer from Standard; |
114 | myCurrent : Integer from Standard; |
115 | |
116 | end TopologicalSortFromIterator; |
117 | |
118 | |
119 | |
120 | |