summaryrefslogtreecommitdiff
path: root/inc/GraphTools_BFSIterator.gxx
blob: 9d5dee88281905f1e62f699d7b397787bd09a7f7 (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
// 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);
}