blob: f5eb94b7d08ba92d779b7df5940ec1d94ae5dce2 (
plain)
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
|
-- File: GraphTools_SortedStrgCmptsFromIterator.cdl
-- Created: Wed Oct 23 12:07:20 1991
-- Author: Denis PASCAL
-- <dp@topsn2>
---Copyright: Matra Datavision 1991, 1992
generic class SortedStrgCmptsFromIterator from GraphTools
(Graph as any;
Vertex as any;
VHasher as any;
VIterator as any)
---Purposes: This generic class implements the Strong Components
-- Research algorithm from a set of vertices. An
-- iterator on adjacent vertices of a given one, are
-- requested. Each Strong Component encapsulates
-- vertices which are part of a cycle, in the underlying
-- graph. The interface of this algorithm is made as an
-- iterator. A each step it is possible to know the
-- number of vertices, which are members of the current
-- Strong Components, and to visit each one. Strong
-- Components are visited in such an order than noone is
-- returned before an other which point to it.
uses StackOfInteger from TColStd,
ListOfSequenceOfInteger from GraphTools,
ListIteratorOfListOfSequenceOfInteger from GraphTools
raises NoMoreObject from Standard,
NoSuchObject from Standard,
DomainError from Standard
private class SCMap instantiates IndexedDataMap from TCollection
(Vertex,Integer,VHasher);
is
Create
---Purpose: Create an empty algorithm.
returns SortedStrgCmptsFromIterator from GraphTools;
FromVertex (me : in out; V : Vertex)
---Purpose: Add <V> as initial condition. This method is
-- cumulative. Use Perform method before visting the
-- result of the algorithm.
---Level: Public
raises DomainError from Standard;
Reset (me : in out);
---Purpose: Reset the algorithm. It may be reused with new
-- conditions.
---Level: Public
Perform (me : in out; G : Graph);
---Purpose: Peform the algorithm in <G> from initial setted
-- conditions.
---Level: Public
More(me)
returns Boolean from Standard;
---Purpose: returns True if there are others strong
-- components.
---Level: Public
Next(me : in out)
---Purpose: Set the iterator to the next strong component.
---Level: Public
raises NoMoreObject from Standard;
NbVertices (me)
returns Integer from Standard
---Purpose: Returns number of vertices of the current Strong
-- Components.
---Level: Public
raises NoSuchObject from Standard;
Value(me; index : Integer from Standard)
returns any Vertex
---Purpose: returns the vertex of index <I> of the current
-- Strong Component.
---Level: Public
---C++: return const &
raises NoSuchObject from Standard;
Visit (me : in out; k : Integer from Standard;
G : Graph)
---Level: Internal
returns Integer from Standard;
fields
-- conditions
myVertices : SCMap from GraphTools;
-- algorithm
myNowIndex : Integer from Standard;
myStack : StackOfInteger from TColStd;
-- result
mySort : ListOfSequenceOfInteger from GraphTools;
myIterator : ListIteratorOfListOfSequenceOfInteger from GraphTools;
end SortedStrgCmptsFromIterator;
|
