src/GraphTools/GraphTools_DFSIterator.gxx

   1 // Created on: 1992-10-12
   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
  21
  22 #include <Standard_NoMoreObject.hxx>
  23 #include <Standard_NoSuchObject.hxx>
  24 #include <TColStd_StackOfInteger.hxx>
  25
  26 //=======================================================================
  27 //function : GraphTools_DFSIterator
  28 //purpose  :
  29 //=======================================================================
  30
  31 GraphTools_DFSIterator::GraphTools_DFSIterator () {}
  32
  33
  34 //=======================================================================
  35 //function : Perform
  36 //purpose  :
  37 //=======================================================================
  38
  39 void GraphTools_DFSIterator::Perform
  40   (const Graph& G, const Vertex& V)
  41 {
  42   Standard_Integer index;
  43   myVisited.Clear();
  44   TColStd_StackOfInteger myReady;
  45
  46   index = myVisited.Add(V);
  47   myReady.Push(index);
  48   while (!myReady.IsEmpty()) {
  49     Vertex w1 = myVisited (myReady.Top());
  50     myReady.Pop();
  51     for (VIterator it(G,w1); it.More(); it.Next()) {
  52       Vertex w2 = it.Value();
  53       if (!myVisited.Contains(w2)) {
  54         index = myVisited.Add(w2);
  55         myReady.Push(index);
  56       }
  57     }
  58   }
  59   myCurrentIndex = 1;
  60 }
  61
  62
  63 //=======================================================================
  64 //function : More
  65 //purpose  :
  66 //=======================================================================
  67
  68 Standard_Boolean GraphTools_DFSIterator::More () const
  69 {
  70   return myCurrentIndex <= myVisited.Extent();
  71 }
  72
  73
  74 //=======================================================================
  75 //function : Next
  76 //purpose  :
  77 //=======================================================================
  78
  79 void GraphTools_DFSIterator::Next ()
  80 {
  81   myCurrentIndex++;
  82 }
  83
  84
  85 //=======================================================================
  86 //function : Value
  87 //purpose  :
  88 //=======================================================================
  89
  90 const Vertex& GraphTools_DFSIterator::Value () const
  91 {
  92   return myVisited(myCurrentIndex);
  93 }
  94