1 -- Created on: 1992-12-24
2 -- Created by: Denis PASCAL
3 -- Copyright (c) 1992-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 TopologicalSortFromIterator from GraphTools
23 --generic class TopologicalSortFromIterator from GraphTools
26 -- VHasher as MapHasher from TCollection (Vertex);
27 -- VIterator as VertexIterator (Graph,Vertex))
29 ---Purpose: This generic class defines an iterator to visit
30 -- each vertex of the underlying graph, in such an
31 -- order that noone vertex is reach before any vertex
32 -- that point to it. In general the order produced by
33 -- topological sort is not unique. Usefull for DAG
34 -- Topological Sort. The option <ignoreSelfLoop>
35 -- allows the user to ignore (or not) any vertex wich
36 -- contains a self loop. The option <processCycle>
37 -- allows the user to visit (or not> vertices which
41 uses SequenceOfInteger from TColStd
43 raises NoSuchObject from Standard,
44 NoMoreObject from Standard,
45 DomainError from Standard
47 private class TSMap instantiates IndexedDataMap from TCollection
48 (Vertex,TSNode from GraphTools,VHasher);
53 ---Purpose: Create an empty algorithm.
54 returns TopologicalSortFromIterator from GraphTools;
56 FromVertex (me : in out; V : Vertex);
57 ---Purpose: Add <V> as initial condition. This method is
58 -- cumulative. Use Perform method before visting the
59 -- result of the algorithm.
63 ---Purpose: Reset the algorithm. It may be reused with new
64 -- initial conditions.
67 Perform (me : in out; G : Graph;
68 ignoreSelfLoop : Boolean from Standard;
69 processCycle : Boolean from Standard);
70 ---Purpose: Peform the algorithm in <G> from initial setted
71 -- conditions according to the two following flags.
72 -- * <ignoreSelfLoop> allows the user to ignore (or
73 -- not) any vertex wich contains a self loop.
74 -- * <processCycle> allows the user to visit (or not>
75 -- vertex which is in a cycle.
79 returns Boolean from Standard;
83 raises NoMoreObject from Standard;
89 ---C++: return const &
90 raises NoSuchObject from Standard;
93 returns Boolean from Standard
94 ---Purpose: Returns TRUE if the current vertex is in a cycle.
96 raises NoSuchObject from Standard;
102 myVertices : TSMap from GraphTools;
103 myIgnoreSelfLoop : Boolean from Standard;
104 myProcessCycle : Boolean from Standard;
106 mySort : SequenceOfInteger from TColStd;
107 myCycles : Integer from Standard;
108 myCurrent : Integer from Standard;
110 end TopologicalSortFromIterator;