src/GraphTools/GraphTools_ReducedGraph.gxx

   1 // Created on: 1991-10-23
   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 <GraphTools_RGNode.hxx>
  22 #include <GraphTools_ListIteratorOfSCList.hxx>
  23
  24 static Standard_Boolean ContainsBack (const Handle(GraphTools_SC)& SC1,
  25                                const Handle(GraphTools_SC)& SC2)
  26 {
  27   GraphTools_ListIteratorOfSCList it (SC1->GetBackSC());
  28   for (;it.More();it.Next()) {
  29     if (it.Value() == SC2) return Standard_True;
  30   }
  31   return Standard_False;
  32 }
  33
  34 static Standard_Boolean ContainsFront (const Handle(GraphTools_SC)& SC1,
  35                                 const Handle(GraphTools_SC)& SC2)
  36 {
  37   GraphTools_ListIteratorOfSCList it (SC1->GetFrontSC());
  38   for (;it.More();it.Next()) {
  39     if (it.Value() == SC2) return Standard_True;
  40   }
  41   return Standard_False;
  42 }
  43
  44 //=======================================================================
  45 //function : GraphTools_ReducedGraph
  46 //purpose  :
  47 //=======================================================================
  48
  49 GraphTools_ReducedGraph::GraphTools_ReducedGraph ()
  50 {
  51   performed = Standard_False;
  52 }
  53
  54
  55 //=======================================================================
  56 //function : GraphTools_ReducedGraph
  57 //purpose  :
  58 //=======================================================================
  59
  60 GraphTools_ReducedGraph::GraphTools_ReducedGraph
  61   (const Graph& G)
  62 {
  63   FromGraph(G);
  64   Perform(G);
  65 }
  66
  67
  68 //=======================================================================
  69 //function : FromGraph
  70 //purpose  :
  71 //=======================================================================
  72
  73 void GraphTools_ReducedGraph::FromGraph (const Graph& G)
  74 {
  75   performed = Standard_False;
  76   for (GIterator itG (G); itG.More(); itG.Next() ) {
  77     GraphTools_RGNode newnode;
  78     myVertices.Add (itG.Value(),newnode);
  79   }
  80 }
  81
  82
  83 //=======================================================================
  84 //function : FromVertex
  85 //purpose  :
  86 //=======================================================================
  87
  88 void GraphTools_ReducedGraph::FromVertex (const Vertex& V)
  89 {
  90   performed = Standard_False;
  91   GraphTools_RGNode newnode;
  92   myVertices.Add(V,newnode);
  93 }
  94
  95 //=======================================================================
  96 //function : Perform
  97 //purpose  :
  98 //=======================================================================
  99
 100 void GraphTools_ReducedGraph::Perform (const Graph& G)
 101 {
 102   performed = Standard_True;
 103   myNowIndex = 0;
 104   myStack.Clear();
 105   mySort.Clear();
 106   Standard_Integer visited;
 107   Standard_Integer index = 1;
 108   while  (index <= myVertices.Extent()) {
 109     visited = myVertices(index).GetVisited();
 110     if (visited == 0) Visit(index,G);
 111     index++;
 112   }
 113   // front and back strong components  of a given one : Update
 114   Standard_Integer curV,nbV,adjV,nbadjV;
 115   Handle(GraphTools_SC) curSC,adjSC;
 116   GraphTools_ListIteratorOfSCList it;
 117   for (it.Initialize(mySort); it.More(); it.Next()) {
 118     curSC = it.Value();
 119     nbV   = curSC->NbVertices();
 120     for (Standard_Integer j = 1; j <= nbV; j++) {
 121       curV  = curSC->GetVertex(j);
 122       nbadjV = myVertices(curV).NbAdj();
 123       for (Standard_Integer k = 1; k <= nbadjV; k++) {
 124         adjV  = myVertices(curV).GetAdj(k);
 125         adjSC = myVertices(adjV).GetSC();
 126         if (adjSC != curSC) {
 127           if (!ContainsFront(curSC,adjSC)) curSC->AddFrontSC (adjSC);
 128           if (!ContainsBack(adjSC,curSC))  adjSC->AddBackSC  (curSC);
 129         }
 130       }
 131     }
 132   }
 133 }
 134
 135
 136 //=======================================================================
 137 //function : Reset
 138 //purpose  :
 139 //=======================================================================
 140
 141 void GraphTools_ReducedGraph::Reset ()
 142 {
 143   performed = Standard_False;
 144   myVertices.Clear();
 145   myNowIndex = 0;
 146   myStack.Clear();
 147   mySort.Clear();
 148 }
 149
 150
 151 //=======================================================================
 152 //function : IsRoot
 153 //purpose  :
 154 //=======================================================================
 155 Standard_Boolean GraphTools_ReducedGraph::IsRoot
 156   (const Handle(GraphTools_SC)& SC) const
 157 {
 158   return (SC->GetBackSC().IsEmpty());
 159 }
 160
 161
 162 //=======================================================================
 163 //function : IsLeaf
 164 //purpose  :
 165 //=======================================================================
 166 Standard_Boolean GraphTools_ReducedGraph::IsLeaf
 167   (const Handle(GraphTools_SC)& SC) const
 168 {
 169   return (SC->GetFrontSC().IsEmpty());
 170 }
 171
 172
 173 //=======================================================================
 174 //function : NbVertices
 175 //purpose  :
 176 //=======================================================================
 177
 178 Standard_Integer GraphTools_ReducedGraph::NbVertices
 179   (const Handle(GraphTools_SC)& SC) const
 180 {
 181   return SC->NbVertices();
 182 }
 183
 184
 185 //=======================================================================
 186 //function : GetVertex
 187 //purpose  :
 188 //=======================================================================
 189
 190 const Vertex& GraphTools_ReducedGraph::GetVertex
 191   (const Handle(GraphTools_SC)& SC,
 192    const Standard_Integer index) const
 193 {
 194   return myVertices.FindKey(SC->GetVertex(index));
 195 }
 196
 197
 198 //=======================================================================
 199 //function : GetSC
 200 //purpose  :
 201 //=======================================================================
 202 Handle(GraphTools_SC) GraphTools_ReducedGraph::GetSC
 203        (const Vertex& V) const
 204 {
 205   if (!performed) Standard_DomainError::Raise();
 206   return myVertices.FindFromKey(V).GetSC();
 207 }
 208
 209
 210 //=======================================================================
 211 //function : Visit
 212 //purpose  :
 213 //=======================================================================
 214
 215 Standard_Integer GraphTools_ReducedGraph::Visit
 216   (const Standard_Integer k, const Graph& G)
 217 {
 218   Standard_Integer MIN;
 219   Standard_Integer M;
 220   myNowIndex++;
 221   myVertices(k).SetVisited(myNowIndex);
 222   MIN = myNowIndex;
 223   myStack.Prepend(k);
 224   Standard_Integer currentVisited;
 225   currentVisited = myVertices(k).GetVisited();
 226   Standard_Integer adjacentIndex;
 227   Standard_Integer adjacentVisited;
 228   for (VIterator itV (G,myVertices.FindKey(k)); itV.More(); itV.Next()) {
 229     adjacentIndex = myVertices.FindIndex(itV.Value());
 230     if (adjacentIndex == 0) {
 231       GraphTools_RGNode newnode;
 232       adjacentIndex   = myVertices.Add (itV.Value(),newnode);
 233       adjacentVisited = 0;
 234     }
 235     else  adjacentVisited = myVertices(adjacentIndex).GetVisited();
 236     myVertices(k).AddAdj(adjacentIndex);
 237     if (adjacentVisited == 0) M = Visit (adjacentIndex,G);
 238     else M = adjacentVisited;
 239     if (M < MIN) MIN = M;
 240   }
 241   if (MIN == currentVisited) {
 242     Handle(GraphTools_SC) SC = new GraphTools_SC();
 243     Standard_Boolean more;
 244     do {
 245       SC->AddVertex(myStack.First());
 246       myVertices(myStack.First()).SetVisited(IntegerLast());
 247       myVertices(myStack.First()).SetSC(SC);
 248       more = myStack.First() != k;
 249       myStack.RemoveFirst() ;
 250     }
 251     while (more);
 252     mySort.Prepend(SC);
 253   }
 254   return MIN;
 255 }
 256
 257
 258
 259
 260
 261