src/IFGraph/IFGraph_Articulations.cxx

   1 // Copyright (c) 1999-2014 OPEN CASCADE SAS
   2 //
   3 // This file is part of Open CASCADE Technology software library.
   4 //
   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.
  10 //
  11 // Alternatively, this file may be used under the terms of Open CASCADE
  12 // commercial license or contractual agreement.
  13
  14
  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>
  20
  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)
  25       :  thegraph (agraph)
  26       {  if (whole) thegraph.GetFromModel();  }
  27
  28
  29    void  IFGraph_Articulations::GetFromEntity
  30   (const Handle(Standard_Transient)& ent)
  31       {  thegraph.GetFromEntity(ent,Standard_True);  }
  32
  33    void  IFGraph_Articulations::GetFromIter(const Interface_EntityIterator& iter)
  34       {  thegraph.GetFromIter(iter,0);  }
  35
  36
  37    void  IFGraph_Articulations::ResetData ()
  38 {  Reset();  thegraph.Reset(); thelist = new TColStd_HSequenceOfInteger();  }
  39
  40    void  IFGraph_Articulations::Evaluate ()
  41 {
  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 ++) {
  47     thenow = 0;
  48     if (thegraph.IsPresent(i)) Visit(i);
  49   }
  50 //  Resultat dans thelist
  51   Reset();
  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));
  56   }
  57 }
  58
  59     Standard_Integer IFGraph_Articulations::Visit (const Standard_Integer num)
  60 {
  61   thenow ++;
  62   thegraph.SetStatus(num,thenow);
  63   Standard_Integer min = thenow;
  64
  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);
  72     }
  73     Standard_Integer statent = thegraph.Status(nument);     // pas reevalue
  74     if (statent == 0) {
  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
  78     }
  79     else if (statent < min) min = statent;
  80   }
  81   return min;
  82 }