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
|
// File: GraphTools_BFSIterator.gxx
// Created: Mon Oct 12 16:34:41 1992
// Author: Denis PASCAL
// <dp@bravox>
#include <Standard_NoMoreObject.hxx>
#include <Standard_NoSuchObject.hxx>
#include <TColStd_QueueOfInteger.hxx>
//=======================================================================
//function : GraphTools_BFSIterator
//purpose :
//=======================================================================
GraphTools_BFSIterator::GraphTools_BFSIterator () {}
//=======================================================================
//function : Perform
//purpose :
//=======================================================================
void GraphTools_BFSIterator::Perform
(const Graph& G, const Vertex& V)
{
Standard_Integer index;
myVisited.Clear();
TColStd_QueueOfInteger myReady;
index = myVisited.Add(V);
myReady.Push(index);
while (!myReady.IsEmpty()) {
Vertex w1 = myVisited (myReady.Front());
myReady.Pop();
for (VIterator it(G,w1); it.More(); it.Next()) {
Vertex w2 = it.Value();
if (!myVisited.Contains(w2)) {
index = myVisited.Add(w2);
myReady.Push(index);
}
}
}
myCurrentIndex = 1;
}
//=======================================================================
//function : More
//purpose :
//=======================================================================
Standard_Boolean GraphTools_BFSIterator::More () const
{
return myCurrentIndex <= myVisited.Extent();
}
//=======================================================================
//function : Next
//purpose :
//=======================================================================
void GraphTools_BFSIterator::Next ()
{
myCurrentIndex++;
}
//=======================================================================
//function : Value
//purpose :
//=======================================================================
const Vertex& GraphTools_BFSIterator::Value () const
{
return myVisited(myCurrentIndex);
}
|
