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
6 // This file is part of Open CASCADE Technology software library.
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.
14 // Alternatively, this file may be used under the terms of Open CASCADE
15 // commercial license or contractual agreement.
19 #include <Standard_NoMoreObject.hxx>
20 #include <Standard_NoSuchObject.hxx>
21 #include <GraphTools_RGNode.hxx>
22 #include <GraphTools_ListIteratorOfSCList.hxx>
24 static Standard_Boolean ContainsBack (const Handle(GraphTools_SC)& SC1,
25 const Handle(GraphTools_SC)& SC2)
27 GraphTools_ListIteratorOfSCList it (SC1->GetBackSC());
28 for (;it.More();it.Next()) {
29 if (it.Value() == SC2) return Standard_True;
31 return Standard_False;
34 static Standard_Boolean ContainsFront (const Handle(GraphTools_SC)& SC1,
35 const Handle(GraphTools_SC)& SC2)
37 GraphTools_ListIteratorOfSCList it (SC1->GetFrontSC());
38 for (;it.More();it.Next()) {
39 if (it.Value() == SC2) return Standard_True;
41 return Standard_False;
44 //=======================================================================
45 //function : GraphTools_ReducedGraph
47 //=======================================================================
49 GraphTools_ReducedGraph::GraphTools_ReducedGraph ()
51 performed = Standard_False;
55 //=======================================================================
56 //function : GraphTools_ReducedGraph
58 //=======================================================================
60 GraphTools_ReducedGraph::GraphTools_ReducedGraph
68 //=======================================================================
69 //function : FromGraph
71 //=======================================================================
73 void GraphTools_ReducedGraph::FromGraph (const Graph& G)
75 performed = Standard_False;
76 for (GIterator itG (G); itG.More(); itG.Next() ) {
77 GraphTools_RGNode newnode;
78 myVertices.Add (itG.Value(),newnode);
83 //=======================================================================
84 //function : FromVertex
86 //=======================================================================
88 void GraphTools_ReducedGraph::FromVertex (const Vertex& V)
90 performed = Standard_False;
91 GraphTools_RGNode newnode;
92 myVertices.Add(V,newnode);
95 //=======================================================================
98 //=======================================================================
100 void GraphTools_ReducedGraph::Perform (const Graph& G)
102 performed = Standard_True;
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);
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()) {
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);
136 //=======================================================================
139 //=======================================================================
141 void GraphTools_ReducedGraph::Reset ()
143 performed = Standard_False;
151 //=======================================================================
154 //=======================================================================
155 Standard_Boolean GraphTools_ReducedGraph::IsRoot
156 (const Handle(GraphTools_SC)& SC) const
158 return (SC->GetBackSC().IsEmpty());
162 //=======================================================================
165 //=======================================================================
166 Standard_Boolean GraphTools_ReducedGraph::IsLeaf
167 (const Handle(GraphTools_SC)& SC) const
169 return (SC->GetFrontSC().IsEmpty());
173 //=======================================================================
174 //function : NbVertices
176 //=======================================================================
178 Standard_Integer GraphTools_ReducedGraph::NbVertices
179 (const Handle(GraphTools_SC)& SC) const
181 return SC->NbVertices();
185 //=======================================================================
186 //function : GetVertex
188 //=======================================================================
190 const Vertex& GraphTools_ReducedGraph::GetVertex
191 (const Handle(GraphTools_SC)& SC,
192 const Standard_Integer index) const
194 return myVertices.FindKey(SC->GetVertex(index));
198 //=======================================================================
201 //=======================================================================
202 Handle(GraphTools_SC) GraphTools_ReducedGraph::GetSC
203 (const Vertex& V) const
205 if (!performed) Standard_DomainError::Raise();
206 return myVertices.FindFromKey(V).GetSC();
210 //=======================================================================
213 //=======================================================================
215 Standard_Integer GraphTools_ReducedGraph::Visit
216 (const Standard_Integer k, const Graph& G)
218 Standard_Integer MIN;
221 myVertices(k).SetVisited(myNowIndex);
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);
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;
241 if (MIN == currentVisited) {
242 Handle(GraphTools_SC) SC = new GraphTools_SC();
243 Standard_Boolean more;
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() ;