1 // Copyright (c) 1999-2014 OPEN CASCADE SAS
3 // This file is part of Open CASCADE Technology software library.
5 // This library is free software; you can redistribute it and/or modify it under
6 // the terms of the GNU Lesser General Public License version 2.1 as published
7 // by the Free Software Foundation, with special exception defined in the file
8 // OCCT_LGPL_EXCEPTION.txt. Consult the file LICENSE_LGPL_21.txt included in OCCT
9 // distribution for complete text of the license and disclaimer of any warranty.
11 // Alternatively, this file may be used under the terms of Open CASCADE
12 // commercial license or contractual agreement.
15 #include <IFGraph_Articulations.hxx>
16 #include <Interface_EntityIterator.hxx>
17 #include <Interface_Graph.hxx>
18 #include <Interface_InterfaceModel.hxx>
19 #include <Standard_Transient.hxx>
21 // Points d'Articulation d'un Graphe : ce sont les "passages obliges" du graphe
22 // Algorithme tire du Sedgewick, p 392
23 IFGraph_Articulations::IFGraph_Articulations
24 (const Interface_Graph& agraph, const Standard_Boolean whole)
26 { if (whole) thegraph.GetFromModel(); }
29 void IFGraph_Articulations::GetFromEntity
30 (const Handle(Standard_Transient)& ent)
31 { thegraph.GetFromEntity(ent,Standard_True); }
33 void IFGraph_Articulations::GetFromIter(const Interface_EntityIterator& iter)
34 { thegraph.GetFromIter(iter,0); }
37 void IFGraph_Articulations::ResetData ()
38 { Reset(); thegraph.Reset(); thelist = new TColStd_HSequenceOfInteger(); }
40 void IFGraph_Articulations::Evaluate ()
42 // Algorithme, cf Sedgewick "Algorithms", p 392
43 thelist = new TColStd_HSequenceOfInteger();
44 // Utilisation de Visit
45 Standard_Integer nb = thegraph.Size();
46 for (Standard_Integer i = 1; i <= nb; i ++) {
48 if (thegraph.IsPresent(i)) Visit(i);
50 // Resultat dans thelist
52 Standard_Integer nbres = thelist->Length();
53 for (Standard_Integer ires = 1; ires <= nbres; ires ++) {
54 Standard_Integer num = thelist->Value(ires);
55 GetOneItem(thegraph.Model()->Value(num));
59 Standard_Integer IFGraph_Articulations::Visit (const Standard_Integer num)
62 thegraph.SetStatus(num,thenow);
63 Standard_Integer min = thenow;
65 for (Interface_EntityIterator iter = thegraph.Shareds(thegraph.Entity(num));
66 iter.More(); iter.Next()) {
67 Handle(Standard_Transient) ent = iter.Value();
68 Standard_Integer nument = thegraph.EntityNumber(ent);
69 if (!thegraph.IsPresent(num)) {
70 thegraph.GetFromEntity(ent,Standard_False);
71 nument = thegraph.EntityNumber(ent);
73 Standard_Integer statent = thegraph.Status(nument); // pas reevalue
75 Standard_Integer mm = Visit(nument);
76 if (mm < min) min = mm;
77 if (mm > thegraph.Status(num)) thelist->Append(num); // ON EN A UN : num
79 else if (statent < min) min = statent;