src/GraphTools/GraphTools_TopologicalSortFromIterator.gxx

   1 // Created on: 1991-05-29
   2 // Created by: Denis PASCAL
   3 // Copyright (c) 1991-1999 Matra Datavision
   4 // Copyright (c) 1999-2014 OPEN CASCADE SAS
   5 //
   6 // This file is part of Open CASCADE Technology software library.
   7 //
   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.
  13 //
  14 // Alternatively, this file may be used under the terms of Open CASCADE
  15 // commercial license or contractual agreement.
  16
  17 //              <dp>
  18
  19 #include <Standard_NoMoreObject.hxx>
  20 #include <Standard_NoSuchObject.hxx>
  21 #include <Standard_DomainError.hxx>
  22 #include <TColStd_ListOfInteger.hxx>
  23 #include <GraphTools_TSNode.hxx>
  24
  25 //=======================================================================
  26 //function : GraphTools_TopologicalSortFromIterator
  27 //purpose  :
  28 //=======================================================================
  29
  30 GraphTools_TopologicalSortFromIterator::GraphTools_TopologicalSortFromIterator () {}
  31
  32
  33
  34 //=======================================================================
  35 //function : FromVertex
  36 //purpose  :
  37 //=======================================================================
  38
  39 void GraphTools_TopologicalSortFromIterator::FromVertex (const Vertex& V)
  40 {
  41   GraphTools_TSNode newnode;
  42   myVertices.Add(V,newnode);
  43 }
  44
  45
  46 //=======================================================================
  47 //function : Perform
  48 //purpose  :
  49 //=======================================================================
  50
  51 void GraphTools_TopologicalSortFromIterator::Perform
  52   (const Graph& G,
  53    const Standard_Boolean ignoreSelfLoop,
  54    const Standard_Boolean processCycle)
  55 {
  56   myIgnoreSelfLoop = ignoreSelfLoop;
  57   myProcessCycle   = processCycle;
  58   myCurrent        = 1;
  59   mySort.Clear();
  60   // algorithm DS
  61   Standard_Integer i, indexcurrent, indexadjacent, nbadjacent;
  62   indexcurrent = 1;
  63   while (indexcurrent <= myVertices.Extent()) {
  64     VIterator itV (G,myVertices.FindKey(indexcurrent));
  65     for ( ; itV.More(); itV.Next()) {
  66       indexadjacent = myVertices.FindIndex(itV.Value());
  67       if (indexadjacent == 0) {
  68         GraphTools_TSNode newnode;
  69         indexadjacent = myVertices.Add(itV.Value(),newnode);
  70       }
  71       if (! (indexcurrent == indexadjacent && myIgnoreSelfLoop)) {
  72         myVertices(indexcurrent).AddSuccessor(indexadjacent);
  73         myVertices(indexadjacent).IncreaseRef();
  74       }
  75     }
  76     indexcurrent++;
  77   }
  78   // current root vertices queue
  79   TColStd_ListOfInteger processQueue;
  80   Standard_Integer nbVertices = myVertices.Extent();
  81   for (i = 1 ; i <= nbVertices; i++) {
  82     if (myVertices(i).NbRef() == 0) processQueue.Append(i);
  83   }
  84   // acyclic processing
  85   while (!processQueue.IsEmpty()) {
  86     indexcurrent = processQueue.First();
  87     mySort.Append(indexcurrent);
  88     nbadjacent = myVertices(indexcurrent).NbSuccessors();
  89     for (i = 1; i <= nbadjacent; i++) {
  90       indexadjacent = myVertices(indexcurrent).GetSuccessor(i);
  91       myVertices(indexadjacent).DecreaseRef();
  92       if (myVertices(indexadjacent).NbRef() == 0) {
  93         processQueue.Append(indexadjacent);
  94       }
  95     }
  96     processQueue.RemoveFirst();
  97   }
  98   // cyclic processing
  99   myCycles = mySort.Length() + 1;
 100   if (myProcessCycle) {
 101     for (i = 1 ; i <= nbVertices; i++) {
 102       if (myVertices(i).NbRef() != 0) mySort.Append(i);
 103     }
 104   }
 105 }
 106
 107
 108 //=======================================================================
 109 //function : Reset
 110 //purpose  :
 111 //=======================================================================
 112
 113 void GraphTools_TopologicalSortFromIterator::Reset ()
 114 {
 115    myVertices.Clear();
 116 //   myIgnoreSelfLoop : Boolean from Standard;
 117 //   myProcessCycle   : Boolean from Standard;
 118    mySort.Clear();
 119 //   myCycles         : Integer from Standard;
 120    myCurrent = 1;
 121 }
 122
 123
 124 //=======================================================================
 125 //function : More
 126 //purpose  :
 127 //=======================================================================
 128
 129 Standard_Boolean GraphTools_TopologicalSortFromIterator::More () const
 130 {
 131   return myCurrent <= mySort.Length();
 132 }
 133
 134
 135 //=======================================================================
 136 //function : Next
 137 //purpose  :
 138 //=======================================================================
 139
 140 void GraphTools_TopologicalSortFromIterator::Next ()
 141 {
 142   if (!More()) Standard_NoMoreObject::Raise();
 143   myCurrent ++;
 144 }
 145
 146
 147 //=======================================================================
 148 //function : Value
 149 //purpose  :
 150 //=======================================================================
 151
 152 const Vertex& GraphTools_TopologicalSortFromIterator::Value () const {
 153   if (!More()) Standard_NoSuchObject::Raise();
 154   return myVertices.FindKey (mySort(myCurrent));
 155 }
 156
 157
 158 //=======================================================================
 159 //function : IsInCycle
 160 //purpose  :
 161 //=======================================================================
 162
 163 Standard_Boolean GraphTools_TopologicalSortFromIterator::IsInCycle () const
 164 {
 165   if (!More()) Standard_NoSuchObject::Raise();
 166   return myCurrent >= myCycles;
 167 }
 168
 169
 170
 171
 172
 173
 174
 175
 176
 177
 178
 179
 180
 181
 182
 183
 184
 185
 186
 187
 188
 189
 190
 191
 192
 193
 194
 195
 196
 197
 198
 199
 200
 201
 202
 203
 204
 205
 206
 207
 208
 209
 210
 211
 212
 213
 214
 215
 216
 217
 218
 219
 220
 221
 222
 223
 224
 225