From d1c0148483f8807b31fd868800b4be1a28cdd1b0 Mon Sep 17 00:00:00 2001 From: dln Date: Tue, 6 May 2014 09:57:53 +0400 Subject: [PATCH] 0024885: Getting rid of "TKAdvTools" toolkit "TKAdvTools" toolkit was deleted. And packages from this toolkit were: - GraphDS -> deleted - GraphTools -> moved to WOK - Dynamic -> deleted - Materials -> deleted - Expr -> moved to TKMath - ExprIntrp -> moved to TKMath - TKAdvTools -> deleted All references of the "TKAdvTools" toolkit were removed --- adm/UDLIST | 1 + collect_binary.bat | 3 - collect_binary.sh | 5 - src/GraphTools/GraphTools.cdl | 107 +++++++ src/GraphTools/GraphTools_AdjSCIterator.gxx | 91 ++++++ src/GraphTools/GraphTools_BFSIterator.cdl | 73 +++++ src/GraphTools/GraphTools_BFSIterator.gxx | 97 +++++++ ...aphTools_ConnectedVerticesFromIterator.cdl | 101 +++++++ ...aphTools_ConnectedVerticesFromIterator.gxx | 211 ++++++++++++++ .../GraphTools_ConnectedVerticesIterator.cdl | 102 +++++++ .../GraphTools_ConnectedVerticesIterator.gxx | 143 ++++++++++ src/GraphTools/GraphTools_DFSIterator.cdl | 82 ++++++ src/GraphTools/GraphTools_DFSIterator.gxx | 89 ++++++ src/GraphTools/GraphTools_GraphIterator.cdl | 69 +++++ src/GraphTools/GraphTools_GraphIterator.gxx | 15 + src/GraphTools/GraphTools_RGNode.cdl | 53 ++++ src/GraphTools/GraphTools_RGNode.cxx | 117 ++++++++ src/GraphTools/GraphTools_ReducedGraph.cdl | 253 +++++++++++++++++ src/GraphTools/GraphTools_ReducedGraph.gxx | 261 ++++++++++++++++++ src/GraphTools/GraphTools_SC.cdl | 67 +++++ src/GraphTools/GraphTools_SC.cxx | 116 ++++++++ .../GraphTools_SortedSCIterator.gxx | 90 ++++++ ...GraphTools_SortedStrgCmptsFromIterator.cdl | 129 +++++++++ ...GraphTools_SortedStrgCmptsFromIterator.gxx | 200 ++++++++++++++ .../GraphTools_SortedStrgCmptsIterator.cdl | 117 ++++++++ .../GraphTools_SortedStrgCmptsIterator.gxx | 140 ++++++++++ src/GraphTools/GraphTools_TSNode.cdl | 49 ++++ src/GraphTools/GraphTools_TSNode.cxx | 104 +++++++ ...GraphTools_TopologicalSortFromIterator.cdl | 114 ++++++++ ...GraphTools_TopologicalSortFromIterator.gxx | 225 +++++++++++++++ .../GraphTools_TopologicalSortIterator.cdl | 107 +++++++ .../GraphTools_TopologicalSortIterator.gxx | 154 +++++++++++ src/GraphTools/GraphTools_VertexIterator.cdl | 69 +++++ src/GraphTools/GraphTools_VertexIterator.gxx | 15 + src/TKWOK/EXTERNLIB | 1 - src/TKWOK/PACKAGES | 1 + src/WOKLibs/EXTERNLIB | 1 - src/WOKSH/EXTERNLIB | 1 - 38 files changed, 3562 insertions(+), 11 deletions(-) create mode 100644 src/GraphTools/GraphTools.cdl create mode 100644 src/GraphTools/GraphTools_AdjSCIterator.gxx create mode 100644 src/GraphTools/GraphTools_BFSIterator.cdl create mode 100644 src/GraphTools/GraphTools_BFSIterator.gxx create mode 100644 src/GraphTools/GraphTools_ConnectedVerticesFromIterator.cdl create mode 100644 src/GraphTools/GraphTools_ConnectedVerticesFromIterator.gxx create mode 100644 src/GraphTools/GraphTools_ConnectedVerticesIterator.cdl create mode 100644 src/GraphTools/GraphTools_ConnectedVerticesIterator.gxx create mode 100644 src/GraphTools/GraphTools_DFSIterator.cdl create mode 100644 src/GraphTools/GraphTools_DFSIterator.gxx create mode 100644 src/GraphTools/GraphTools_GraphIterator.cdl create mode 100644 src/GraphTools/GraphTools_GraphIterator.gxx create mode 100644 src/GraphTools/GraphTools_RGNode.cdl create mode 100644 src/GraphTools/GraphTools_RGNode.cxx create mode 100644 src/GraphTools/GraphTools_ReducedGraph.cdl create mode 100644 src/GraphTools/GraphTools_ReducedGraph.gxx create mode 100644 src/GraphTools/GraphTools_SC.cdl create mode 100644 src/GraphTools/GraphTools_SC.cxx create mode 100644 src/GraphTools/GraphTools_SortedSCIterator.gxx create mode 100644 src/GraphTools/GraphTools_SortedStrgCmptsFromIterator.cdl create mode 100644 src/GraphTools/GraphTools_SortedStrgCmptsFromIterator.gxx create mode 100644 src/GraphTools/GraphTools_SortedStrgCmptsIterator.cdl create mode 100644 src/GraphTools/GraphTools_SortedStrgCmptsIterator.gxx create mode 100644 src/GraphTools/GraphTools_TSNode.cdl create mode 100644 src/GraphTools/GraphTools_TSNode.cxx create mode 100644 src/GraphTools/GraphTools_TopologicalSortFromIterator.cdl create mode 100644 src/GraphTools/GraphTools_TopologicalSortFromIterator.gxx create mode 100644 src/GraphTools/GraphTools_TopologicalSortIterator.cdl create mode 100644 src/GraphTools/GraphTools_TopologicalSortIterator.gxx create mode 100644 src/GraphTools/GraphTools_VertexIterator.cdl create mode 100644 src/GraphTools/GraphTools_VertexIterator.gxx diff --git a/adm/UDLIST b/adm/UDLIST index 621352e..7ca776c 100644 --- a/adm/UDLIST +++ b/adm/UDLIST @@ -26,6 +26,7 @@ p WOKTools p WOKUnix p WOKUtils p WOKernel +p GraphTools r WOKBuilderDef r WOKEntityDef r WOKStepsDef diff --git a/collect_binary.bat b/collect_binary.bat index f471177..9c6e808 100644 --- a/collect_binary.bat +++ b/collect_binary.bat @@ -114,9 +114,6 @@ if exist "%CASROOT%\win%ARCH%\%VCVER%\bin%CASDEB%" ( goto :eof ) -xcopy "%CASROOT%\%preOCCDLLPath%\TKAdvTools.dll" "%installPath%\lib\wnt\" -if not %errorlevel%. == 0. (set "doNotCopyForeignFileList=%doNotCopyForeignFileList%;TKAdvTools.dll") - xcopy "%CASROOT%\%preOCCDLLPath%\TKernel.dll" "%installPath%\lib\wnt\" if not %errorlevel%. == 0. (set "doNotCopyForeignFileList=%doNotCopyForeignFileList%;TKernel.dll") diff --git a/collect_binary.sh b/collect_binary.sh index 33b8e08..3a0ad48 100644 --- a/collect_binary.sh +++ b/collect_binary.sh @@ -30,11 +30,6 @@ if [ -e "$preOCCTLibPath/libTKernel.so" ]; then else echo "$preOCCTLibPath/libTKernel.so does not exist" fi -if [ -e "$preOCCTLibPath/libTKAdvTools.so" ]; then - cp -f "$preOCCTLibPath/libTKAdvTools.so" $installRelatePath/lib/lin/ -else - echo "$preOCCTLibPath/libTKAdvTools.so does not exist" -fi #wok libs checking preWOKLibPath="./lin${ARCH}/${cmdArg2}/lib${CASDEB}" diff --git a/src/GraphTools/GraphTools.cdl b/src/GraphTools/GraphTools.cdl new file mode 100644 index 0000000..425b0d5 --- /dev/null +++ b/src/GraphTools/GraphTools.cdl @@ -0,0 +1,107 @@ +-- Created on: 1991-03-07 +-- Created by: Denis Pascal +-- Copyright (c) 1991-1999 Matra Datavision +-- Copyright (c) 1999-2014 OPEN CASCADE SAS +-- +-- This file is part of Open CASCADE Technology software library. +-- +-- This library is free software; you can redistribute it and/or modify it under +-- the terms of the GNU Lesser General Public License version 2.1 as published +-- by the Free Software Foundation, with special exception defined in the file +-- OCCT_LGPL_EXCEPTION.txt. Consult the file LICENSE_LGPL_21.txt included in OCCT +-- distribution for complete text of the license and disclaimer of any warranty. +-- +-- Alternatively, this file may be used under the terms of Open CASCADE +-- commercial license or contractual agreement. + +package GraphTools + + ---Purpose: This package provides algorithms working + -- on a directed graph. Those algorithms are generic for + -- user (Graph and Vertex) data, and tool classes. + + +uses Standard, + MMgt, + TCollection, + TColStd + +is + + + class ListOfSequenceOfInteger instantiates List from TCollection + (SequenceOfInteger from TColStd); + +-- Requirements +-- ============ + +-- Data +-- Vertex +-- Graph +-- Tools + generic class GraphIterator; + generic class VertexIterator; + +-- Services (Algorithms) +-- ===================== + + + ---Purpose: Depth First Search (DFS) + + generic class DFSIterator, + DFSMap; + + + ---Purpose: Breath First Search (BFS) + + generic class BFSIterator, + BFSMap; + + + ---Purpose: Sorted Strong Components (SC) + + generic class SortedStrgCmptsFromIterator, + SCMap; + + generic class SortedStrgCmptsIterator; + + + ---Purpose: Topological Sort (TS) + + class TSNode; + + generic class TopologicalSortFromIterator, + TSMap; + + generic class TopologicalSortIterator; + + + ---Purpose: Connected Vertices (CV) + + generic class ConnectedVerticesFromIterator, + CVMap, + ConnectMap; + + generic class ConnectedVerticesIterator; + + + ---Purpose: Reduced Graph (RG) + + class RGNode; + + class SC; + + class SCList instantiates List from TCollection + (SC from GraphTools); + + generic class ReducedGraph, + RGMap, + SortedSCIterator, + AdjSCIterator; + +end GraphTools; + + + + + diff --git a/src/GraphTools/GraphTools_AdjSCIterator.gxx b/src/GraphTools/GraphTools_AdjSCIterator.gxx new file mode 100644 index 0000000..662764a --- /dev/null +++ b/src/GraphTools/GraphTools_AdjSCIterator.gxx @@ -0,0 +1,91 @@ +// Created on: 1991-10-23 +// Created by: Denis PASCAL +// Copyright (c) 1991-1999 Matra Datavision +// Copyright (c) 1999-2014 OPEN CASCADE SAS +// +// This file is part of Open CASCADE Technology software library. +// +// This library is free software; you can redistribute it and/or modify it under +// the terms of the GNU Lesser General Public License version 2.1 as published +// by the Free Software Foundation, with special exception defined in the file +// OCCT_LGPL_EXCEPTION.txt. Consult the file LICENSE_LGPL_21.txt included in OCCT +// distribution for complete text of the license and disclaimer of any warranty. +// +// Alternatively, this file may be used under the terms of Open CASCADE +// commercial license or contractual agreement. + +// + +#include +#include + + +//======================================================================= +//function : GraphTools_AdjSCIterator +//purpose : +//======================================================================= +GraphTools_AdjSCIterator::GraphTools_AdjSCIterator () +{ +} + + +//======================================================================= +//function : GraphTools_AdjSCIterator +//purpose : +//======================================================================= +GraphTools_AdjSCIterator::GraphTools_AdjSCIterator + (const GraphTools_ReducedGraph& RG, + const Handle(GraphTools_SC)& SC) +{ + Initialize (RG,SC); +} + + +//======================================================================= +//function : Initialize +//purpose : +//======================================================================= +void GraphTools_AdjSCIterator::Initialize + (const GraphTools_ReducedGraph& RG, + const Handle(GraphTools_SC)& SC) +{ + myIterator.Initialize(SC->GetFrontSC()); +} + + +//======================================================================= +//function : More +//purpose : +//======================================================================= +Standard_Boolean GraphTools_AdjSCIterator::More() const +{ + return myIterator.More(); +} + + +//======================================================================= +//function : Next +//purpose : +//======================================================================= +void GraphTools_AdjSCIterator::Next() +{ + myIterator.Next(); +} + + +//======================================================================= +//function : Value +//purpose : +//======================================================================= +Handle(GraphTools_SC) GraphTools_AdjSCIterator::Value () const +{ + return myIterator.Value(); +} + + + + + + + + diff --git a/src/GraphTools/GraphTools_BFSIterator.cdl b/src/GraphTools/GraphTools_BFSIterator.cdl new file mode 100644 index 0000000..2c4a256 --- /dev/null +++ b/src/GraphTools/GraphTools_BFSIterator.cdl @@ -0,0 +1,73 @@ +-- Created on: 1992-10-12 +-- Created by: Denis PASCAL +-- Copyright (c) 1992-1999 Matra Datavision +-- Copyright (c) 1999-2014 OPEN CASCADE SAS +-- +-- This file is part of Open CASCADE Technology software library. +-- +-- This library is free software; you can redistribute it and/or modify it under +-- the terms of the GNU Lesser General Public License version 2.1 as published +-- by the Free Software Foundation, with special exception defined in the file +-- OCCT_LGPL_EXCEPTION.txt. Consult the file LICENSE_LGPL_21.txt included in OCCT +-- distribution for complete text of the license and disclaimer of any warranty. +-- +-- Alternatively, this file may be used under the terms of Open CASCADE +-- commercial license or contractual agreement. + +generic class BFSIterator from GraphTools + (Graph as any; + Vertex as any; + VHasher as any; + VIterator as any) + +--generic class BFSIterator from GraphTools +-- (Graph as any; +-- Vertex as any; +-- VHasher as MapHasher from TCollection (Vertex); +-- VIterator as VertexIterator (Graph,Vertex)) + +---Purpose: This generic class implement the Breadth First Search + -- algorithm from a Vertex with an iterator to reached + -- adjacent vertices of a given one. The interface of + -- this algorithm is made as an iterator. + +raises NoMoreObject from Standard, + NoSuchObject from Standard + + class BFSMap instantiates IndexedMap from TCollection (Vertex,VHasher); + +is + + Create + returns BFSIterator; + ---Purpose: Create an empty iterator. + + Perform (me : in out; G : Graph; V : Vertex); + ---Purpose: Initializes the research from member vertex of . + ---Level: Public + + More (me) returns Boolean from Standard; + ---Purpose: Returns True if there are other vertices. + ---Level: Public + + Next(me : in out) + ---Purpose: Set the iterator to the next vertex. + ---Level: Public + raises NoMoreObject from Standard; + + Value(me) returns any Vertex + ---Purpose: returns the vertex value for the current + -- position of the iterator. + ---Level: Public + ---C++: return const & + raises NoSuchObject from Standard; + +fields + + myVisited : BFSMap from GraphTools; + myCurrentIndex : Integer from Standard; + +end BFSIterator; + + + diff --git a/src/GraphTools/GraphTools_BFSIterator.gxx b/src/GraphTools/GraphTools_BFSIterator.gxx new file mode 100644 index 0000000..55718b2 --- /dev/null +++ b/src/GraphTools/GraphTools_BFSIterator.gxx @@ -0,0 +1,97 @@ +// Created on: 1992-10-12 +// Created by: Denis PASCAL +// Copyright (c) 1992-1999 Matra Datavision +// Copyright (c) 1999-2014 OPEN CASCADE SAS +// +// This file is part of Open CASCADE Technology software library. +// +// This library is free software; you can redistribute it and/or modify it under +// the terms of the GNU Lesser General Public License version 2.1 as published +// by the Free Software Foundation, with special exception defined in the file +// OCCT_LGPL_EXCEPTION.txt. Consult the file LICENSE_LGPL_21.txt included in OCCT +// distribution for complete text of the license and disclaimer of any warranty. +// +// Alternatively, this file may be used under the terms of Open CASCADE +// commercial license or contractual agreement. + +#include +#include +#include + +//======================================================================= +//function : GraphTools_BFSIterator +//purpose : +//======================================================================= + +GraphTools_BFSIterator::GraphTools_BFSIterator () {} + + +//======================================================================= +//function : Perform +//purpose : +//======================================================================= + +void GraphTools_BFSIterator::Perform + (const Graph& G, const Vertex& V) +{ + Standard_Integer index; + myVisited.Clear(); + TColStd_QueueOfInteger myReady; + + index = myVisited.Add(V); + myReady.Push(index); + while (!myReady.IsEmpty()) { + Vertex w1 = myVisited (myReady.Front()); + myReady.Pop(); + for (VIterator it(G,w1); it.More(); it.Next()) { + Vertex w2 = it.Value(); + if (!myVisited.Contains(w2)) { + index = myVisited.Add(w2); + myReady.Push(index); + } + } + } + myCurrentIndex = 1; +} + + +//======================================================================= +//function : More +//purpose : +//======================================================================= + +Standard_Boolean GraphTools_BFSIterator::More () const +{ + return myCurrentIndex <= myVisited.Extent(); +} + + +//======================================================================= +//function : Next +//purpose : +//======================================================================= + +void GraphTools_BFSIterator::Next () +{ + myCurrentIndex++; +} + + +//======================================================================= +//function : Value +//purpose : +//======================================================================= + +const Vertex& GraphTools_BFSIterator::Value () const +{ + return myVisited(myCurrentIndex); +} + + + + + + + + + diff --git a/src/GraphTools/GraphTools_ConnectedVerticesFromIterator.cdl b/src/GraphTools/GraphTools_ConnectedVerticesFromIterator.cdl new file mode 100644 index 0000000..bffc839 --- /dev/null +++ b/src/GraphTools/GraphTools_ConnectedVerticesFromIterator.cdl @@ -0,0 +1,101 @@ +-- Created on: 1992-10-16 +-- Created by: Arnaud BOUZY +-- Copyright (c) 1992-1999 Matra Datavision +-- Copyright (c) 1999-2014 OPEN CASCADE SAS +-- +-- This file is part of Open CASCADE Technology software library. +-- +-- This library is free software; you can redistribute it and/or modify it under +-- the terms of the GNU Lesser General Public License version 2.1 as published +-- by the Free Software Foundation, with special exception defined in the file +-- OCCT_LGPL_EXCEPTION.txt. Consult the file LICENSE_LGPL_21.txt included in OCCT +-- distribution for complete text of the license and disclaimer of any warranty. +-- +-- Alternatively, this file may be used under the terms of Open CASCADE +-- commercial license or contractual agreement. + +generic class ConnectedVerticesFromIterator from GraphTools + (Graph as any; + Vertex as any; + VIterator as any) + + + ---Purpose: In a graph, returns subsets of a list of vertices in + -- which all vertices are connected. + +uses HArray1OfInteger from TColStd + + class CVMap instantiates IndexedMap from TCollection + (Vertex, + MapTransientHasher from TColStd); + + class ConnectMap instantiates DataMap from TCollection + (Vertex, + Integer from Standard, + MapTransientHasher from TColStd); + + +is + + Create + ---Purpose: Create an empty algorithm. + returns ConnectedVerticesFromIterator; + + FromVertex (me : in out; V : Vertex); + ---Purpose: Add as initial condition. This method is + -- cumulative. Use Perform method before visting the + -- result of the algorithm. + ---Level: Public + + Reset (me : in out); + ---Purpose: Reset the algorithm. It may be reused with new + -- conditions. + ---Level: Public + + Perform (me : in out; G : Graph); + ---Purpose: Peform the algorithm in from initial setted + -- conditions. + ---Level: Public + + More(me) + ---Purpose: Returns TRUE if there are others subset of + -- connected vertices. + ---Level: Public + returns Boolean from Standard; + + Next (me : in out); + ---Purpose: Set the iterator to the next subset of connected + -- vertices. + ---Level: Public + + NbVertices (me) + returns Integer from Standard; + ---Purpose: Returns number of vertices of the current subset + -- of connected vertices. + ---Level: Public + + Value (me; index : Integer from Standard) + returns any Vertex; + ---Purpose: Returns a vertex member of the current subset of + -- connected vertices. + ---Level: Public + ---C++: return const& + + Visit (me : in out; V : Vertex; + G : Graph; + visited : in out ConnectMap from GraphTools) + ---Purpose: Recursively called to visit the vertices connected to + -- in , with already visited vertices + -- . + ---Level: Internal + is private; + +fields + + initMap : CVMap from GraphTools; + tab : HArray1OfInteger from TColStd; + myCurrent : Integer from Standard; + +end ConnectedVerticesFromIterator; + + diff --git a/src/GraphTools/GraphTools_ConnectedVerticesFromIterator.gxx b/src/GraphTools/GraphTools_ConnectedVerticesFromIterator.gxx new file mode 100644 index 0000000..162babf --- /dev/null +++ b/src/GraphTools/GraphTools_ConnectedVerticesFromIterator.gxx @@ -0,0 +1,211 @@ +// Created on: 1992-10-19 +// Created by: Arnaud BOUZY +// Copyright (c) 1992-1999 Matra Datavision +// Copyright (c) 1999-2014 OPEN CASCADE SAS +// +// This file is part of Open CASCADE Technology software library. +// +// This library is free software; you can redistribute it and/or modify it under +// the terms of the GNU Lesser General Public License version 2.1 as published +// by the Free Software Foundation, with special exception defined in the file +// OCCT_LGPL_EXCEPTION.txt. Consult the file LICENSE_LGPL_21.txt included in OCCT +// distribution for complete text of the license and disclaimer of any warranty. +// +// Alternatively, this file may be used under the terms of Open CASCADE +// commercial license or contractual agreement. + +#include +#include + + +//======================================================================= +//function : GraphTools_ConnectedVerticesFromIterator +//purpose : +//======================================================================= + +GraphTools_ConnectedVerticesFromIterator::GraphTools_ConnectedVerticesFromIterator() +{ + myCurrent = 0; +} + + +//======================================================================= +//function : FromVertex +//purpose : +//======================================================================= + +void GraphTools_ConnectedVerticesFromIterator::FromVertex(const Vertex& avert) +{ + initMap.Add(avert); +} + + +//======================================================================= +//function : Reset +//purpose : +//======================================================================= + +void GraphTools_ConnectedVerticesFromIterator::Reset () +{ + myCurrent = 0; + initMap.Clear(); +} + + +//======================================================================= +//function : Perform +//purpose : +//======================================================================= + +void GraphTools_ConnectedVerticesFromIterator::Perform (const Graph& aGraph) +{ + Standard_Integer nbvert = initMap.Extent(); + GraphTools_ConnectMap visited; + Standard_Integer i; + for (i=1;i<=nbvert; i++) { + visited.Bind(initMap(i),i); + } + for (i=1;i<=nbvert; i++) { + if (visited(initMap(i)) == i) { + myCurrent = i; + VIterator vit(aGraph,initMap(i)); + while (vit.More()) { + Visit(vit.Value(),aGraph,visited); + vit.Next(); + } + } + } + + tab = new TColStd_HArray1OfInteger(1,nbvert,0); + for (i=1; i<= nbvert; i++) { + tab->SetValue(i,visited(initMap(i))); + } + myCurrent = 0; + Next(); +} + + +//======================================================================= +//function : More +//purpose : +//======================================================================= + +Standard_Boolean GraphTools_ConnectedVerticesFromIterator::More() const +{ + for (Standard_Integer i=1; i<= tab->Upper(); i++) { + if (tab->Value(i) >= myCurrent) { + return Standard_True; + } + } + return Standard_False; +} + + +//======================================================================= +//function : Next +//purpose : +//======================================================================= + +void GraphTools_ConnectedVerticesFromIterator::Next() +{ + Standard_Boolean found=Standard_False; + myCurrent++; + Standard_Integer nbv = tab->Upper(); + Standard_Integer i; + while (!found && (myCurrent <= nbv)) { + for (i=1; (i<= nbv) && !found; i++) { + if (tab->Value(i) == myCurrent) { + found = Standard_True; + } + } + if (!found) { + myCurrent++; + } + } +} + + +//======================================================================= +//function : NbVertices +//purpose : +//======================================================================= + +Standard_Integer GraphTools_ConnectedVerticesFromIterator::NbVertices() const +{ + if (!More()) { + Standard_NoSuchObject::Raise(); + } + Standard_Integer res = 0; + for (Standard_Integer i=1; i<= tab->Upper(); i++) { + if (tab->Value(i) == myCurrent) { + res++; + } + } + return res; +} + +//======================================================================= +//function : Value +//purpose : +//======================================================================= + +const Vertex& GraphTools_ConnectedVerticesFromIterator::Value + (const Standard_Integer index) const +{ + if (!More()) { + Standard_NoSuchObject::Raise(); + } + Standard_Integer current=0; + for (Standard_Integer i=1; i<= tab->Upper(); i++) { + if (tab->Value(i) == myCurrent) { + current++; + if (current == index) { + return initMap(i); + } + } + } +} + +//======================================================================= +//function : Visit +//purpose : +//======================================================================= + +void GraphTools_ConnectedVerticesFromIterator::Visit + (const Vertex& avert, + const Graph& agraph, + GraphTools_ConnectMap& visited) +{ + Standard_Boolean godown = Standard_False; + if (!visited.IsBound(avert)) { + visited.Bind(avert,myCurrent); + godown = Standard_True; + } + else { + Standard_Integer thebound = visited(avert); + if (thebound > myCurrent) { + visited(avert) = myCurrent; + godown = Standard_True; + } + else if (thebound < myCurrent) { + Standard_Integer rebind = visited(initMap(thebound)); + for (Standard_Integer i=1; i <= initMap.Extent(); i++) { + if ((visited(initMap(i)) == thebound) || + (visited(initMap(i)) == rebind)) { + visited(initMap(i)) = myCurrent; + } + } + } + } + if (godown) { + VIterator vit(agraph,avert); + while (vit.More()) { + Visit(vit.Value(),agraph,visited); + vit.Next(); + } + } +} + + + + diff --git a/src/GraphTools/GraphTools_ConnectedVerticesIterator.cdl b/src/GraphTools/GraphTools_ConnectedVerticesIterator.cdl new file mode 100644 index 0000000..d38b4e5 --- /dev/null +++ b/src/GraphTools/GraphTools_ConnectedVerticesIterator.cdl @@ -0,0 +1,102 @@ +-- Created on: 1993-03-18 +-- Created by: Denis PASCAL +-- Copyright (c) 1993-1999 Matra Datavision +-- Copyright (c) 1999-2014 OPEN CASCADE SAS +-- +-- This file is part of Open CASCADE Technology software library. +-- +-- This library is free software; you can redistribute it and/or modify it under +-- the terms of the GNU Lesser General Public License version 2.1 as published +-- by the Free Software Foundation, with special exception defined in the file +-- OCCT_LGPL_EXCEPTION.txt. Consult the file LICENSE_LGPL_21.txt included in OCCT +-- distribution for complete text of the license and disclaimer of any warranty. +-- +-- Alternatively, this file may be used under the terms of Open CASCADE +-- commercial license or contractual agreement. + +generic class ConnectedVerticesIterator from GraphTools + (Graph as any; + Vertex as any; + GIterator as any; + CVIterator as any) + +--generic class ConnectedVerticesIterator from GraphTools +-- (Graph as any; +-- Vertex as any; +-- GIterator as GraphIterator (Graph,Vertex)) +-- CVIterator as ConnectedVerticesFromIterator + + ---Purpose: In a graph, returns subsets of a list of vertices in + -- which all vertices are connected. + +is + + Create + ---Purpose: Create an empty algorithm. + returns ConnectedVerticesIterator from GraphTools; + + Create (G : Graph) + ---Purpose: Create the algorithm setting each vertex of + -- reached by GIterator tool, as initial conditions. + -- Use Perform method before visting the result of + -- the algorithm. + returns ConnectedVerticesIterator from GraphTools; + + FromGraph (me : in out; G : Graph); + ---Purpose: Add each vertex of reached by GIterator tool + -- as initial conditions. Use Perform method + -- before visiting the result of the algorithm. + ---Level: Public; + + FromVertex (me : in out; V : Vertex); + ---Purpose: Add as research condition. This method is + -- cumulative. User must used Perform method before + -- visting the result of the algorithm. + ---Level: Public + + Reset (me : in out); + ---Purpose: Reset the algorithm. It may be reused with new + -- initial conditions. + ---Level: Public + + Perform (me : in out; G : Graph); + ---Purpose: Peform the algorithm in from initial setted + -- conditions. + ---Level: Public + + More(me) + ---Purpose: Returns TRUE if there are others subset of + -- connected vertices. + ---Level: Public + returns Boolean from Standard; + + Next (me : in out); + ---Purpose: Set the iterator to the next subset of connected + -- vertices. + ---Level: Public + + NbVertices (me) + returns Integer from Standard; + ---Purpose: Returns number of vertices of the current subset + -- of connected vertices. + ---Level: Public + + Value (me; index : Integer from Standard) + returns any Vertex; + ---Purpose: Returns a vertex member of the current subset of + -- connected vertices. + ---Level: Public + ---C++: return const& + +fields + + myIterator : CVIterator; + +end ConnectedVerticesIterator; + + + + + + + diff --git a/src/GraphTools/GraphTools_ConnectedVerticesIterator.gxx b/src/GraphTools/GraphTools_ConnectedVerticesIterator.gxx new file mode 100644 index 0000000..2fb2b3d --- /dev/null +++ b/src/GraphTools/GraphTools_ConnectedVerticesIterator.gxx @@ -0,0 +1,143 @@ +// Created on: 1991-05-29 +// Created by: Denis PASCAL +// Copyright (c) 1991-1999 Matra Datavision +// Copyright (c) 1999-2014 OPEN CASCADE SAS +// +// This file is part of Open CASCADE Technology software library. +// +// This library is free software; you can redistribute it and/or modify it under +// the terms of the GNU Lesser General Public License version 2.1 as published +// by the Free Software Foundation, with special exception defined in the file +// OCCT_LGPL_EXCEPTION.txt. Consult the file LICENSE_LGPL_21.txt included in OCCT +// distribution for complete text of the license and disclaimer of any warranty. +// +// Alternatively, this file may be used under the terms of Open CASCADE +// commercial license or contractual agreement. + +// + + +//======================================================================= +//function : GraphTools_ConnectedVerticesIterator +//purpose : +//======================================================================= + +GraphTools_ConnectedVerticesIterator::GraphTools_ConnectedVerticesIterator () +{} + + +//======================================================================= +//function : GraphTools_TopologicalSortIterator +//purpose : +//======================================================================= + +GraphTools_ConnectedVerticesIterator::GraphTools_ConnectedVerticesIterator + (const Graph& G) +{ + FromGraph (G); +} + +//======================================================================= +//function : FromVertex +//purpose : +//======================================================================= + +void GraphTools_ConnectedVerticesIterator::FromVertex + (const Vertex& V) +{ + myIterator.FromVertex(V); +} + + +//======================================================================= +//function : GraphTools_ConnectedVerticesIterator +//purpose : +//======================================================================= +void GraphTools_ConnectedVerticesIterator::FromGraph (const Graph& G) +{ + for ( GIterator it (G); it.More(); it.Next() ) { + myIterator.FromVertex(it.Value()); + } +} + + +//======================================================================= +//function : Perform +//purpose : +//======================================================================= + +void GraphTools_ConnectedVerticesIterator::Perform + (const Graph& G) +{ + myIterator.Perform(G); +} + + +//======================================================================= +//function : Reset +//purpose : +//======================================================================= + +void GraphTools_ConnectedVerticesIterator::Reset () +{ + myIterator.Reset(); +} + +//======================================================================= +//function : More +//purpose : +//======================================================================= +Standard_Boolean GraphTools_ConnectedVerticesIterator::More () const +{ + return myIterator.More(); +} + +//======================================================================= +//function : Next +//purpose : +//======================================================================= +void GraphTools_ConnectedVerticesIterator::Next () +{ + myIterator.Next(); +} + + +//======================================================================= +//function : NbVertices +//purpose : +//======================================================================= + +Standard_Integer GraphTools_ConnectedVerticesIterator::NbVertices() const +{ + return myIterator.NbVertices(); +} + + +//======================================================================= +//function : Value +//purpose : +//======================================================================= +const Vertex& GraphTools_ConnectedVerticesIterator::Value + (const Standard_Integer I) const +{ + return myIterator.Value(I); +} + + + + + + + + + + + + + + + + + + + diff --git a/src/GraphTools/GraphTools_DFSIterator.cdl b/src/GraphTools/GraphTools_DFSIterator.cdl new file mode 100644 index 0000000..066b9ae --- /dev/null +++ b/src/GraphTools/GraphTools_DFSIterator.cdl @@ -0,0 +1,82 @@ +-- Created on: 1992-09-24 +-- Created by: Denis PASCAL +-- Copyright (c) 1992-1999 Matra Datavision +-- Copyright (c) 1999-2014 OPEN CASCADE SAS +-- +-- This file is part of Open CASCADE Technology software library. +-- +-- This library is free software; you can redistribute it and/or modify it under +-- the terms of the GNU Lesser General Public License version 2.1 as published +-- by the Free Software Foundation, with special exception defined in the file +-- OCCT_LGPL_EXCEPTION.txt. Consult the file LICENSE_LGPL_21.txt included in OCCT +-- distribution for complete text of the license and disclaimer of any warranty. +-- +-- Alternatively, this file may be used under the terms of Open CASCADE +-- commercial license or contractual agreement. + +generic class DFSIterator from GraphTools + (Graph as any; + Vertex as any; + VHasher as any; + VIterator as any) + + ---Purpose: This generic class implement the Depth First Search + -- algorithm from a Vertex with an iterator to reached + -- adjacent vertices of a given one. The interface of + -- this algorithm is made as an iterator. + +--generic class DFSIterator from GraphTools +-- (Graph as any; +-- Vertex as any; +-- VHasher as MapHasher from TCollection (Vertex); +-- VIterator as VertexIterator (Graph,Vertex)) + +raises NoMoreObject from Standard, + NoSuchObject from Standard + + class DFSMap instantiates IndexedMap from TCollection (Vertex,VHasher); + +is + + Create + returns DFSIterator; + ---Purpose: Create an empty iterator. + + Perform (me : in out; G : Graph; V : Vertex); + ---Purpose: Initializes the research from member vertex of + -- . + ---Level: Public + + More (me) returns Boolean from Standard; + ---Purpose: Returns True if there are other vertices. + ---Level: Public + + Next(me : in out) + ---Purpose: Set the iterator to the next vertex. + ---Level: Public + raises NoMoreObject from Standard; + + Value (me) returns any Vertex + ---Purpose: returns the vertex value for the current position + -- of the iterator. + ---C++: return const & + ---Level: Public + raises NoSuchObject from Standard; + + +fields + + myVisited : DFSMap from GraphTools; + myCurrentIndex : Integer from Standard; + +end DFSIterator; + + + + + + + + + + diff --git a/src/GraphTools/GraphTools_DFSIterator.gxx b/src/GraphTools/GraphTools_DFSIterator.gxx new file mode 100644 index 0000000..3356eda --- /dev/null +++ b/src/GraphTools/GraphTools_DFSIterator.gxx @@ -0,0 +1,89 @@ +// Created on: 1992-10-12 +// Created by: Denis PASCAL +// Copyright (c) 1992-1999 Matra Datavision +// Copyright (c) 1999-2014 OPEN CASCADE SAS +// +// This file is part of Open CASCADE Technology software library. +// +// This library is free software; you can redistribute it and/or modify it under +// the terms of the GNU Lesser General Public License version 2.1 as published +// by the Free Software Foundation, with special exception defined in the file +// OCCT_LGPL_EXCEPTION.txt. Consult the file LICENSE_LGPL_21.txt included in OCCT +// distribution for complete text of the license and disclaimer of any warranty. +// +// Alternatively, this file may be used under the terms of Open CASCADE +// commercial license or contractual agreement. + +#include +#include +#include + +//======================================================================= +//function : GraphTools_DFSIterator +//purpose : +//======================================================================= + +GraphTools_DFSIterator::GraphTools_DFSIterator () {} + + +//======================================================================= +//function : Perform +//purpose : +//======================================================================= + +void GraphTools_DFSIterator::Perform + (const Graph& G, const Vertex& V) +{ + Standard_Integer index; + myVisited.Clear(); + TColStd_StackOfInteger myReady; + + index = myVisited.Add(V); + myReady.Push(index); + while (!myReady.IsEmpty()) { + Vertex w1 = myVisited (myReady.Top()); + myReady.Pop(); + for (VIterator it(G,w1); it.More(); it.Next()) { + Vertex w2 = it.Value(); + if (!myVisited.Contains(w2)) { + index = myVisited.Add(w2); + myReady.Push(index); + } + } + } + myCurrentIndex = 1; +} + + +//======================================================================= +//function : More +//purpose : +//======================================================================= + +Standard_Boolean GraphTools_DFSIterator::More () const +{ + return myCurrentIndex <= myVisited.Extent(); +} + + +//======================================================================= +//function : Next +//purpose : +//======================================================================= + +void GraphTools_DFSIterator::Next () +{ + myCurrentIndex++; +} + + +//======================================================================= +//function : Value +//purpose : +//======================================================================= + +const Vertex& GraphTools_DFSIterator::Value () const +{ + return myVisited(myCurrentIndex); +} + diff --git a/src/GraphTools/GraphTools_GraphIterator.cdl b/src/GraphTools/GraphTools_GraphIterator.cdl new file mode 100644 index 0000000..3a5d272 --- /dev/null +++ b/src/GraphTools/GraphTools_GraphIterator.cdl @@ -0,0 +1,69 @@ +-- Created on: 1991-03-06 +-- Created by: Denis Pascal +-- Copyright (c) 1991-1999 Matra Datavision +-- Copyright (c) 1999-2014 OPEN CASCADE SAS +-- +-- This file is part of Open CASCADE Technology software library. +-- +-- This library is free software; you can redistribute it and/or modify it under +-- the terms of the GNU Lesser General Public License version 2.1 as published +-- by the Free Software Foundation, with special exception defined in the file +-- OCCT_LGPL_EXCEPTION.txt. Consult the file LICENSE_LGPL_21.txt included in OCCT +-- distribution for complete text of the license and disclaimer of any warranty. +-- +-- Alternatively, this file may be used under the terms of Open CASCADE +-- commercial license or contractual agreement. + +generic class GraphIterator from GraphTools (Graph as any; + Vertex as any) + +-- template class GraphIterator from GraphTools (Graph as any; +-- Vertex as any) + + ---Purpose: Template class which defines signatures of an + -- iterator to visit each vertex, member of the + -- underlying graph. + + +raises NoMoreObject from Standard, + NoSuchObject from Standard + +is + + Create (G : Graph) returns GraphIterator; + + More (me) returns Boolean; + ---Purpose: Returns TRUE if there are other vertices. + ---Level: Public + + Next (me : in out) + --- Purpose : Set the iterator to the next Vertex. + ---Level: Public + raises NoMoreObject from Standard; + + Value (me) returns Vertex + --- Purpose: Returns the vertex value for the current position + -- of the iterator + ---Level: Public + raises NoSuchObject from Standard; + +end GraphIterator; + + + + + + + + + + + + + + + + + + + diff --git a/src/GraphTools/GraphTools_GraphIterator.gxx b/src/GraphTools/GraphTools_GraphIterator.gxx new file mode 100644 index 0000000..b628db6 --- /dev/null +++ b/src/GraphTools/GraphTools_GraphIterator.gxx @@ -0,0 +1,15 @@ +// Created on: 1993-09-27 +// Created by: Denis PASCAL +// Copyright (c) 1993-1999 Matra Datavision +// Copyright (c) 1999-2014 OPEN CASCADE SAS +// +// This file is part of Open CASCADE Technology software library. +// +// This library is free software; you can redistribute it and/or modify it under +// the terms of the GNU Lesser General Public License version 2.1 as published +// by the Free Software Foundation, with special exception defined in the file +// OCCT_LGPL_EXCEPTION.txt. Consult the file LICENSE_LGPL_21.txt included in OCCT +// distribution for complete text of the license and disclaimer of any warranty. +// +// Alternatively, this file may be used under the terms of Open CASCADE +// commercial license or contractual agreement. diff --git a/src/GraphTools/GraphTools_RGNode.cdl b/src/GraphTools/GraphTools_RGNode.cdl new file mode 100644 index 0000000..2ee5827 --- /dev/null +++ b/src/GraphTools/GraphTools_RGNode.cdl @@ -0,0 +1,53 @@ +-- Created on: 1993-09-29 +-- Created by: Denis PASCAL +-- Copyright (c) 1993-1999 Matra Datavision +-- Copyright (c) 1999-2014 OPEN CASCADE SAS +-- +-- This file is part of Open CASCADE Technology software library. +-- +-- This library is free software; you can redistribute it and/or modify it under +-- the terms of the GNU Lesser General Public License version 2.1 as published +-- by the Free Software Foundation, with special exception defined in the file +-- OCCT_LGPL_EXCEPTION.txt. Consult the file LICENSE_LGPL_21.txt included in OCCT +-- distribution for complete text of the license and disclaimer of any warranty. +-- +-- Alternatively, this file may be used under the terms of Open CASCADE +-- commercial license or contractual agreement. + +class RGNode from GraphTools + +uses SC from GraphTools, + SequenceOfInteger from TColStd + +is + + Create returns RGNode; + + Reset (me : in out); + + SetVisited (me : in out; v : Integer from Standard); + + GetVisited (me) + returns Integer from Standard; + + AddAdj (me : in out; adj : Integer from Standard); + + NbAdj (me) + returns Integer from Standard; + + GetAdj (me; index : Integer from Standard) + returns Integer from Standard; + + SetSC (me : in out; SC : SC from GraphTools); + + GetSC (me) + returns SC from GraphTools; + +fields + + visited : Integer from Standard; + myAdj : SequenceOfInteger from TColStd; + mySC : SC from GraphTools; + +end RGNode; + diff --git a/src/GraphTools/GraphTools_RGNode.cxx b/src/GraphTools/GraphTools_RGNode.cxx new file mode 100644 index 0000000..f45e917 --- /dev/null +++ b/src/GraphTools/GraphTools_RGNode.cxx @@ -0,0 +1,117 @@ +// Created on: 1993-09-29 +// Created by: Denis PASCAL +// Copyright (c) 1993-1999 Matra Datavision +// Copyright (c) 1999-2014 OPEN CASCADE SAS +// +// This file is part of Open CASCADE Technology software library. +// +// This library is free software; you can redistribute it and/or modify it under +// the terms of the GNU Lesser General Public License version 2.1 as published +// by the Free Software Foundation, with special exception defined in the file +// OCCT_LGPL_EXCEPTION.txt. Consult the file LICENSE_LGPL_21.txt included in OCCT +// distribution for complete text of the license and disclaimer of any warranty. +// +// Alternatively, this file may be used under the terms of Open CASCADE +// commercial license or contractual agreement. + +#include + + +//======================================================================= +//function : GraphTools_RGNode +//purpose : +//======================================================================= + +GraphTools_RGNode::GraphTools_RGNode() +{ + visited = 0; +} + +//======================================================================= +//function : Reset +//purpose : +//======================================================================= + +void GraphTools_RGNode::Reset() +{ + visited = 0; + myAdj.Clear(); + mySC.Nullify(); +} + +//======================================================================= +//function : SetVisited +//purpose : +//======================================================================= + +void GraphTools_RGNode::SetVisited(const Standard_Integer v) +{ + visited = v; +} + + +//======================================================================= +//function : GetVisited +//purpose : +//======================================================================= + +Standard_Integer GraphTools_RGNode::GetVisited() const +{ + return visited; +} + + +//======================================================================= +//function : AddAdj +//purpose : +//======================================================================= + +void GraphTools_RGNode::AddAdj (const Standard_Integer adj) +{ + myAdj.Append(adj); +} + + +//======================================================================= +//function : NbAdj +//purpose : +//======================================================================= + +Standard_Integer GraphTools_RGNode::NbAdj() const +{ + return myAdj.Length(); +} + + +//======================================================================= +//function : GetAdj +//purpose : +//======================================================================= + +Standard_Integer GraphTools_RGNode::GetAdj + (const Standard_Integer index) const +{ + return myAdj(index); +} + + +//======================================================================= +//function : SetSC +//purpose : +//======================================================================= + +void GraphTools_RGNode::SetSC (const Handle(GraphTools_SC)& SC) +{ + mySC = SC; +} + + +//======================================================================= +//function : GetSC +//purpose : +//======================================================================= + +Handle(GraphTools_SC) GraphTools_RGNode::GetSC () const +{ + return mySC; +} diff --git a/src/GraphTools/GraphTools_ReducedGraph.cdl b/src/GraphTools/GraphTools_ReducedGraph.cdl new file mode 100644 index 0000000..7d43c64 --- /dev/null +++ b/src/GraphTools/GraphTools_ReducedGraph.cdl @@ -0,0 +1,253 @@ +-- Created on: 1993-01-06 +-- Created by: Denis PASCAL +-- Copyright (c) 1993-1999 Matra Datavision +-- Copyright (c) 1999-2014 OPEN CASCADE SAS +-- +-- This file is part of Open CASCADE Technology software library. +-- +-- This library is free software; you can redistribute it and/or modify it under +-- the terms of the GNU Lesser General Public License version 2.1 as published +-- by the Free Software Foundation, with special exception defined in the file +-- OCCT_LGPL_EXCEPTION.txt. Consult the file LICENSE_LGPL_21.txt included in OCCT +-- distribution for complete text of the license and disclaimer of any warranty. +-- +-- Alternatively, this file may be used under the terms of Open CASCADE +-- commercial license or contractual agreement. + +generic class ReducedGraph from GraphTools + (Graph as any; + Vertex as any; + VHasher as any; + VIterator as any; + GIterator as any) + +--signature class ReducedGraph from GraphTools +-- Graph as any; +-- Vertex as any; +-- VHasher as MapHasher from TCollection (Vertex); +-- VIterator as VertexIterator (Graph,Vertex); +-- GIterator as GraphIterator (Graph,Vertex)) + + ---Purpose: this generic class defines an algorithm to build and + -- visit the reduced graph of a given directed graph. + -- + -- A reduced graph is defined itself as a graph where + -- each vertex represents a strong component. Each + -- strong component is a subset of vertices of the + -- underlying graph which are mutually dependant in the + -- way that there is always a path to go from a given + -- vertex to another vertex and back (Definition of a + -- cycle) . Of course the Reduced Graph (or Condensed + -- Graph) is a DAG (Directed Acyclic Graph). + -- + -- After initialisation conditions (methods FromXXX) the + -- user has to build the reduced graph using the method + -- Perfrom. So each vertex of the underlying graph will + -- be encapsulated in a strong component (class SC of the + -- package). The algorithm may be reused using the + -- method Reset. + -- + -- nested iterators and methods provides services to + -- visit the reduced graph: + -- + -- * class SortedSCIterator defines an iterator to visit + -- each strong component. This visit is done according + -- to topologiacl sort of the reduced graph (which is a + -- DAG). + -- + -- * class AdjSCIterator defines an iterator to visit + -- each adjacent StrongComponent of a given one. + -- + -- * The methods NbVertices and GetVertex of the reduced + -- graph returned the number and each vertex member of a + -- strong component. The method GetSC returned for a + -- given vertex its strong component.e + -- + -- Warning: Noone method may be used on SC class. This class is only + -- here to identify a StrongComponent. + +uses SC from GraphTools, + SCList from GraphTools, + ListIteratorOfSCList from GraphTools, + StackOfInteger from TColStd + +raises NoSuchObject from Standard, + NoMoreObject from Standard, + OutOfRange from Standard + + private class RGMap instantiates IndexedDataMap from TCollection + (Vertex, + RGNode from GraphTools, + VHasher); + + class SortedSCIterator from GraphTools + + uses SC from GraphTools, + ListIteratorOfSCList from GraphTools + + raises NoMoreObject from Standard, + NoSuchObject from Standard + + is + + Create returns SortedSCIterator from GraphTools; + + Create (RG : ReducedGraph from GraphTools) + returns SortedSCIterator from GraphTools; + + Initialize (me : in out; RG : ReducedGraph from GraphTools); + ---Level: Public + + More (me) returns Boolean from Standard; + ---Purpose: Returns True if there are others Strong + -- Components. + ---Level: Public + + Next (me : in out) + raises NoMoreObject from Standard; + ---Level: Public + + Value (me) returns SC from GraphTools + raises NoSuchObject from Standard; + ---Level: Public + + fields + + myIterator : ListIteratorOfSCList; + + end SortedSCIterator; + + + class AdjSCIterator from GraphTools + + uses SC from GraphTools, + ListIteratorOfSCList from GraphTools + + raises NoMoreObject from Standard, + NoSuchObject from Standard, + OutOfRange from Standard + + is + + Create returns AdjSCIterator from GraphTools; + + Create (RG : ReducedGraph from GraphTools; + SC : SC from GraphTools) + returns AdjSCIterator from GraphTools; + + Initialize (me : in out; RG : ReducedGraph from GraphTools; + SC : SC from GraphTools); + ---Level: Public + + More (me) returns Boolean from Standard; + ---Level: Public + + Next (me : in out) + raises NoMoreObject from Standard; + ---Level: Public + + Value (me) returns SC from GraphTools + ---Level: Public + raises NoSuchObject from Standard; + + fields + + myIterator : ListIteratorOfSCList; + + end AdjSCIterator; + +is + + Create + ---Purpose: Create an empty algorithm + returns ReducedGraph from GraphTools; + + + Create (G : Graph) + ---Purpose: Create the algorithm, set each vertex of + -- reached by GIterator, as research conditions, and + -- perform the algorithm. User may directly visit + -- (nested class xxxIterator) the result of the + -- algorithm. + returns ReducedGraph from GraphTools; + + FromGraph (me : in out; G : Graph); + ---Purpose: Add each vertex of reached by GIterator tool + -- as research conditions. User must used Perform + -- method before visiting the result of the algorithm. + ---Level: Public + + FromVertex (me : in out; V : Vertex); + ---Purpose: Add as research condition. This method is + -- cumulative. User must used Perform method before + -- visting the result of the algorithm. + ---Level: Public + + Perform (me : in out; G : Graph); + ---Purpose: Perform the algorithm IN FROM previous + -- initialisation condition(s). + ---Level: Public + + Reset (me : in out); + ---Purpose: Clear initialisation conditions. The algorithm may + -- be initialized and performed again from new + -- conditions. In that case new nested SCIterator and + -- AdjSCIterator may be reinitialized. + ---Level: Public + + IsRoot (me; SC : SC from GraphTools) + returns Boolean from Standard; + ---Level: Public + + IsLeaf (me; SC : SC from GraphTools) + returns Boolean from Standard; + ---Level: Public + + NbVertices (me; SC : SC from GraphTools) + ---Purpose: returns number of vertices, members of . + ---Level: Public + returns Integer from Standard; + + GetVertex (me; SC : SC from GraphTools; + index : Integer from Standard) + returns any Vertex + ---C++: return const& + ---Level: Public + raises OutOfRange from Standard; + + GetSC (me; V : Vertex) + ---Purpose: Returns the SC which contains . + ---Level: Public + returns SC from GraphTools; + + Visit (me : in out; k : Integer from Standard; + G : Graph) + ---Level: Public + returns Integer from Standard + is private; + +fields + +-- conditions + myVertices : RGMap from GraphTools; +-- algorithm + performed : Boolean from Standard; + myNowIndex : Integer from Standard; + myStack : StackOfInteger from TColStd; +-- result + mySort : SCList from GraphTools; + +friends + + class SortedSCIterator from GraphTools + +end ReducedGraph; + + + + + + + + + diff --git a/src/GraphTools/GraphTools_ReducedGraph.gxx b/src/GraphTools/GraphTools_ReducedGraph.gxx new file mode 100644 index 0000000..4529a22 --- /dev/null +++ b/src/GraphTools/GraphTools_ReducedGraph.gxx @@ -0,0 +1,261 @@ +// Created on: 1991-10-23 +// Created by: Denis PASCAL +// Copyright (c) 1991-1999 Matra Datavision +// Copyright (c) 1999-2014 OPEN CASCADE SAS +// +// This file is part of Open CASCADE Technology software library. +// +// This library is free software; you can redistribute it and/or modify it under +// the terms of the GNU Lesser General Public License version 2.1 as published +// by the Free Software Foundation, with special exception defined in the file +// OCCT_LGPL_EXCEPTION.txt. Consult the file LICENSE_LGPL_21.txt included in OCCT +// distribution for complete text of the license and disclaimer of any warranty. +// +// Alternatively, this file may be used under the terms of Open CASCADE +// commercial license or contractual agreement. + +// + +#include +#include +#include +#include + +static Standard_Boolean ContainsBack (const Handle(GraphTools_SC)& SC1, + const Handle(GraphTools_SC)& SC2) +{ + GraphTools_ListIteratorOfSCList it (SC1->GetBackSC()); + for (;it.More();it.Next()) { + if (it.Value() == SC2) return Standard_True; + } + return Standard_False; +} + +static Standard_Boolean ContainsFront (const Handle(GraphTools_SC)& SC1, + const Handle(GraphTools_SC)& SC2) +{ + GraphTools_ListIteratorOfSCList it (SC1->GetFrontSC()); + for (;it.More();it.Next()) { + if (it.Value() == SC2) return Standard_True; + } + return Standard_False; +} + +//======================================================================= +//function : GraphTools_ReducedGraph +//purpose : +//======================================================================= + +GraphTools_ReducedGraph::GraphTools_ReducedGraph () +{ + performed = Standard_False; +} + + +//======================================================================= +//function : GraphTools_ReducedGraph +//purpose : +//======================================================================= + +GraphTools_ReducedGraph::GraphTools_ReducedGraph + (const Graph& G) +{ + FromGraph(G); + Perform(G); +} + + +//======================================================================= +//function : FromGraph +//purpose : +//======================================================================= + +void GraphTools_ReducedGraph::FromGraph (const Graph& G) +{ + performed = Standard_False; + for (GIterator itG (G); itG.More(); itG.Next() ) { + GraphTools_RGNode newnode; + myVertices.Add (itG.Value(),newnode); + } +} + + +//======================================================================= +//function : FromVertex +//purpose : +//======================================================================= + +void GraphTools_ReducedGraph::FromVertex (const Vertex& V) +{ + performed = Standard_False; + GraphTools_RGNode newnode; + myVertices.Add(V,newnode); +} + +//======================================================================= +//function : Perform +//purpose : +//======================================================================= + +void GraphTools_ReducedGraph::Perform (const Graph& G) +{ + performed = Standard_True; + myNowIndex = 0; + myStack.Clear(); + mySort.Clear(); + Standard_Integer visited; + Standard_Integer index = 1; + while (index <= myVertices.Extent()) { + visited = myVertices(index).GetVisited(); + if (visited == 0) Visit(index,G); + index++; + } + // front and back strong components of a given one : Update + Standard_Integer curV,nbV,adjV,nbadjV; + Handle(GraphTools_SC) curSC,adjSC; + GraphTools_ListIteratorOfSCList it; + for (it.Initialize(mySort); it.More(); it.Next()) { + curSC = it.Value(); + nbV = curSC->NbVertices(); + for (Standard_Integer j = 1; j <= nbV; j++) { + curV = curSC->GetVertex(j); + nbadjV = myVertices(curV).NbAdj(); + for (Standard_Integer k = 1; k <= nbadjV; k++) { + adjV = myVertices(curV).GetAdj(k); + adjSC = myVertices(adjV).GetSC(); + if (adjSC != curSC) { + if (!ContainsFront(curSC,adjSC)) curSC->AddFrontSC (adjSC); + if (!ContainsBack(adjSC,curSC)) adjSC->AddBackSC (curSC); + } + } + } + } +} + + +//======================================================================= +//function : Reset +//purpose : +//======================================================================= + +void GraphTools_ReducedGraph::Reset () +{ + performed = Standard_False; + myVertices.Clear(); + myNowIndex = 0; + myStack.Clear(); + mySort.Clear(); +} + + +//======================================================================= +//function : IsRoot +//purpose : +//======================================================================= +Standard_Boolean GraphTools_ReducedGraph::IsRoot + (const Handle(GraphTools_SC)& SC) const +{ + return (SC->GetBackSC().IsEmpty()); +} + + +//======================================================================= +//function : IsLeaf +//purpose : +//======================================================================= +Standard_Boolean GraphTools_ReducedGraph::IsLeaf + (const Handle(GraphTools_SC)& SC) const +{ + return (SC->GetFrontSC().IsEmpty()); +} + + +//======================================================================= +//function : NbVertices +//purpose : +//======================================================================= + +Standard_Integer GraphTools_ReducedGraph::NbVertices + (const Handle(GraphTools_SC)& SC) const +{ + return SC->NbVertices(); +} + + +//======================================================================= +//function : GetVertex +//purpose : +//======================================================================= + +const Vertex& GraphTools_ReducedGraph::GetVertex + (const Handle(GraphTools_SC)& SC, + const Standard_Integer index) const +{ + return myVertices.FindKey(SC->GetVertex(index)); +} + + +//======================================================================= +//function : GetSC +//purpose : +//======================================================================= +Handle(GraphTools_SC) GraphTools_ReducedGraph::GetSC + (const Vertex& V) const +{ + if (!performed) Standard_DomainError::Raise(); + return myVertices.FindFromKey(V).GetSC(); +} + + +//======================================================================= +//function : Visit +//purpose : +//======================================================================= + +Standard_Integer GraphTools_ReducedGraph::Visit + (const Standard_Integer k, const Graph& G) +{ + Standard_Integer MIN; + Standard_Integer M; + myNowIndex++; + myVertices(k).SetVisited(myNowIndex); + MIN = myNowIndex; + myStack.Push(k); + Standard_Integer currentVisited; + currentVisited = myVertices(k).GetVisited(); + Standard_Integer adjacentIndex; + Standard_Integer adjacentVisited; + for (VIterator itV (G,myVertices.FindKey(k)); itV.More(); itV.Next()) { + adjacentIndex = myVertices.FindIndex(itV.Value()); + if (adjacentIndex == 0) { + GraphTools_RGNode newnode; + adjacentIndex = myVertices.Add (itV.Value(),newnode); + adjacentVisited = 0; + } + else adjacentVisited = myVertices(adjacentIndex).GetVisited(); + myVertices(k).AddAdj(adjacentIndex); + if (adjacentVisited == 0) M = Visit (adjacentIndex,G); + else M = adjacentVisited; + if (M < MIN) MIN = M; + } + if (MIN == currentVisited) { + Handle(GraphTools_SC) SC = new GraphTools_SC(); + Standard_Boolean more; + do { + SC->AddVertex(myStack.Top()); + myVertices(myStack.Top()).SetVisited(IntegerLast()); + myVertices(myStack.Top()).SetSC(SC); + more = myStack.Top() != k; + myStack.Pop() ; + } + while (more); + mySort.Prepend(SC); + } + return MIN; +} + + + + + + diff --git a/src/GraphTools/GraphTools_SC.cdl b/src/GraphTools/GraphTools_SC.cdl new file mode 100644 index 0000000..6c10e18 --- /dev/null +++ b/src/GraphTools/GraphTools_SC.cdl @@ -0,0 +1,67 @@ +-- Created on: 1993-09-30 +-- Created by: Denis PASCAL +-- Copyright (c) 1993-1999 Matra Datavision +-- Copyright (c) 1999-2014 OPEN CASCADE SAS +-- +-- This file is part of Open CASCADE Technology software library. +-- +-- This library is free software; you can redistribute it and/or modify it under +-- the terms of the GNU Lesser General Public License version 2.1 as published +-- by the Free Software Foundation, with special exception defined in the file +-- OCCT_LGPL_EXCEPTION.txt. Consult the file LICENSE_LGPL_21.txt included in OCCT +-- distribution for complete text of the license and disclaimer of any warranty. +-- +-- Alternatively, this file may be used under the terms of Open CASCADE +-- commercial license or contractual agreement. + +class SC from GraphTools inherits TShared from MMgt + + ---Purpose: This class is used to identify a Strong Component. + -- The user has not to used its methods. + +uses SCList from GraphTools, + SequenceOfInteger from TColStd + +raises OutOfRange from Standard, + NoSuchObject from Standard + +is + + Create returns mutable SC; + + Reset (me : mutable); + ---Level: Public + + AddVertex (me : mutable; V : Integer from Standard); + ---Level: Public + + NbVertices (me) returns Integer from Standard; + ---Level: Public + + GetVertex (me; index: Integer from Standard) + ---Level: Public + returns Integer from Standard; + + AddFrontSC (me : mutable; SC : SC from GraphTools); + ---Level: Public + + GetFrontSC (me) returns SCList from GraphTools; + ---Level: Public + ---C++: return const & + + AddBackSC (me : mutable; SC : SC from GraphTools); + ---Level: Public + + GetBackSC (me) returns SCList from GraphTools; + ---Level: Public + ---C++: return const & + +fields + + myBackSC : SCList from GraphTools; + myVertices : SequenceOfInteger from TColStd; + myFrontSC : SCList from GraphTools; + +end SC; + + diff --git a/src/GraphTools/GraphTools_SC.cxx b/src/GraphTools/GraphTools_SC.cxx new file mode 100644 index 0000000..64e8ea5 --- /dev/null +++ b/src/GraphTools/GraphTools_SC.cxx @@ -0,0 +1,116 @@ +// Created on: 1993-09-30 +// Created by: Denis PASCAL +// Copyright (c) 1993-1999 Matra Datavision +// Copyright (c) 1999-2014 OPEN CASCADE SAS +// +// This file is part of Open CASCADE Technology software library. +// +// This library is free software; you can redistribute it and/or modify it under +// the terms of the GNU Lesser General Public License version 2.1 as published +// by the Free Software Foundation, with special exception defined in the file +// OCCT_LGPL_EXCEPTION.txt. Consult the file LICENSE_LGPL_21.txt included in OCCT +// distribution for complete text of the license and disclaimer of any warranty. +// +// Alternatively, this file may be used under the terms of Open CASCADE +// commercial license or contractual agreement. + +#include + +//======================================================================= +//function : GraphTools_SC +//purpose : +//======================================================================= + +GraphTools_SC::GraphTools_SC () {} + + +//======================================================================= +//function : Reset +//purpose : +//======================================================================= + +void GraphTools_SC::Reset() +{ + myBackSC.Clear(); + myVertices.Clear(); + myFrontSC.Clear(); +} + + +//======================================================================= +//function : AddVertex +//purpose : +//======================================================================= + +void GraphTools_SC::AddVertex(const Standard_Integer V) +{ + myVertices.Append (V); +} + + +//======================================================================= +//function : NbVertices +//purpose : +//======================================================================= + +Standard_Integer GraphTools_SC::NbVertices() const +{ + return myVertices.Length(); +} + + + +//======================================================================= +//function : GetVertex +//purpose : +//======================================================================= + +Standard_Integer GraphTools_SC::GetVertex + (const Standard_Integer index) const +{ + return myVertices(index); +} + +//======================================================================= +//function : AddFrontSC +//purpose : +//======================================================================= + +void GraphTools_SC::AddFrontSC(const Handle(GraphTools_SC)& SC) +{ + myFrontSC.Append(SC); +} + + +//======================================================================= +//function : GetFrontSC +//purpose : +//======================================================================= + +const GraphTools_SCList& GraphTools_SC::GetFrontSC() const +{ + return myFrontSC; +} + + +//======================================================================= +//function : AddBackSC +//purpose : +//======================================================================= + +void GraphTools_SC::AddBackSC(const Handle(GraphTools_SC)& SC) +{ + myBackSC.Append(SC); +} + +//======================================================================= +//function : GetBackSC +//purpose : +//======================================================================= + +const GraphTools_SCList& GraphTools_SC::GetBackSC() const +{ + return myBackSC; +} + + diff --git a/src/GraphTools/GraphTools_SortedSCIterator.gxx b/src/GraphTools/GraphTools_SortedSCIterator.gxx new file mode 100644 index 0000000..bbbde42 --- /dev/null +++ b/src/GraphTools/GraphTools_SortedSCIterator.gxx @@ -0,0 +1,90 @@ +// Created on: 1991-10-23 +// Created by: Denis PASCAL +// Copyright (c) 1991-1999 Matra Datavision +// Copyright (c) 1999-2014 OPEN CASCADE SAS +// +// This file is part of Open CASCADE Technology software library. +// +// This library is free software; you can redistribute it and/or modify it under +// the terms of the GNU Lesser General Public License version 2.1 as published +// by the Free Software Foundation, with special exception defined in the file +// OCCT_LGPL_EXCEPTION.txt. Consult the file LICENSE_LGPL_21.txt included in OCCT +// distribution for complete text of the license and disclaimer of any warranty. +// +// Alternatively, this file may be used under the terms of Open CASCADE +// commercial license or contractual agreement. + +// + +#include +#include + + +//======================================================================= +//function : GraphTools_SortedSCIterator +//purpose : +//======================================================================= + +GraphTools_SortedSCIterator::GraphTools_SortedSCIterator () +{ +} + + +//======================================================================= +//function : GraphTools_SortedSCIterator +//purpose : +//======================================================================= + +GraphTools_SortedSCIterator::GraphTools_SortedSCIterator + (const GraphTools_ReducedGraph& RG) +{ + Initialize (RG); +} + + +//======================================================================= +//function : Initialize +//purpose : +//======================================================================= + +void GraphTools_SortedSCIterator::Initialize + (const GraphTools_ReducedGraph& RG) +{ + myIterator.Initialize(RG.mySort); +} + + + +//======================================================================= +//function : More +//purpose : +//======================================================================= + +Standard_Boolean GraphTools_SortedSCIterator::More() const +{ + return myIterator.More(); +} + + +//======================================================================= +//function : Next +//purpose : +//======================================================================= + +void GraphTools_SortedSCIterator::Next() +{ + myIterator.Next(); +} + +//======================================================================= +//function : Value +//purpose : +//======================================================================= + +Handle(GraphTools_SC) GraphTools_SortedSCIterator::Value () const +{ + return myIterator.Value(); +} + + + diff --git a/src/GraphTools/GraphTools_SortedStrgCmptsFromIterator.cdl b/src/GraphTools/GraphTools_SortedStrgCmptsFromIterator.cdl new file mode 100644 index 0000000..a0c4330 --- /dev/null +++ b/src/GraphTools/GraphTools_SortedStrgCmptsFromIterator.cdl @@ -0,0 +1,129 @@ +-- Created on: 1991-10-23 +-- Created by: Denis PASCAL +-- Copyright (c) 1991-1999 Matra Datavision +-- Copyright (c) 1999-2014 OPEN CASCADE SAS +-- +-- This file is part of Open CASCADE Technology software library. +-- +-- This library is free software; you can redistribute it and/or modify it under +-- the terms of the GNU Lesser General Public License version 2.1 as published +-- by the Free Software Foundation, with special exception defined in the file +-- OCCT_LGPL_EXCEPTION.txt. Consult the file LICENSE_LGPL_21.txt included in OCCT +-- distribution for complete text of the license and disclaimer of any warranty. +-- +-- Alternatively, this file may be used under the terms of Open CASCADE +-- commercial license or contractual agreement. + +generic class SortedStrgCmptsFromIterator from GraphTools + (Graph as any; + Vertex as any; + VHasher as any; + VIterator as any) + + ---Purposes: This generic class implements the Strong Components + -- Research algorithm from a set of vertices. An + -- iterator on adjacent vertices of a given one, are + -- requested. Each Strong Component encapsulates + -- vertices which are part of a cycle, in the underlying + -- graph. The interface of this algorithm is made as an + -- iterator. A each step it is possible to know the + -- number of vertices, which are members of the current + -- Strong Components, and to visit each one. Strong + -- Components are visited in such an order than noone is + -- returned before an other which point to it. + + +uses StackOfInteger from TColStd, + ListOfSequenceOfInteger from GraphTools, + ListIteratorOfListOfSequenceOfInteger from GraphTools + +raises NoMoreObject from Standard, + NoSuchObject from Standard, + DomainError from Standard + + + private class SCMap instantiates IndexedDataMap from TCollection + (Vertex,Integer,VHasher); + +is + + Create + ---Purpose: Create an empty algorithm. + returns SortedStrgCmptsFromIterator from GraphTools; + + FromVertex (me : in out; V : Vertex) + ---Purpose: Add as initial condition. This method is + -- cumulative. Use Perform method before visting the + -- result of the algorithm. + ---Level: Public + raises DomainError from Standard; + + Reset (me : in out); + ---Purpose: Reset the algorithm. It may be reused with new + -- conditions. + ---Level: Public + + Perform (me : in out; G : Graph); + ---Purpose: Peform the algorithm in from initial setted + -- conditions. + ---Level: Public + + More(me) + returns Boolean from Standard; + ---Purpose: returns True if there are others strong + -- components. + ---Level: Public + + Next(me : in out) + ---Purpose: Set the iterator to the next strong component. + ---Level: Public + raises NoMoreObject from Standard; + + NbVertices (me) + returns Integer from Standard + ---Purpose: Returns number of vertices of the current Strong + -- Components. + ---Level: Public + raises NoSuchObject from Standard; + + Value(me; index : Integer from Standard) + returns any Vertex + ---Purpose: returns the vertex of index of the current + -- Strong Component. + ---Level: Public + ---C++: return const & + raises NoSuchObject from Standard; + + Visit (me : in out; k : Integer from Standard; + G : Graph) + ---Level: Internal + returns Integer from Standard; + +fields + +-- conditions + myVertices : SCMap from GraphTools; +-- algorithm + myNowIndex : Integer from Standard; + myStack : StackOfInteger from TColStd; +-- result + mySort : ListOfSequenceOfInteger from GraphTools; + myIterator : ListIteratorOfListOfSequenceOfInteger from GraphTools; + +end SortedStrgCmptsFromIterator; + + + + + + + + + + + + + + + + diff --git a/src/GraphTools/GraphTools_SortedStrgCmptsFromIterator.gxx b/src/GraphTools/GraphTools_SortedStrgCmptsFromIterator.gxx new file mode 100644 index 0000000..ce63ae8 --- /dev/null +++ b/src/GraphTools/GraphTools_SortedStrgCmptsFromIterator.gxx @@ -0,0 +1,200 @@ +// Created on: 1991-10-23 +// Created by: Denis PASCAL +// Copyright (c) 1991-1999 Matra Datavision +// Copyright (c) 1999-2014 OPEN CASCADE SAS +// +// This file is part of Open CASCADE Technology software library. +// +// This library is free software; you can redistribute it and/or modify it under +// the terms of the GNU Lesser General Public License version 2.1 as published +// by the Free Software Foundation, with special exception defined in the file +// OCCT_LGPL_EXCEPTION.txt. Consult the file LICENSE_LGPL_21.txt included in OCCT +// distribution for complete text of the license and disclaimer of any warranty. +// +// Alternatively, this file may be used under the terms of Open CASCADE +// commercial license or contractual agreement. + +// + +#include +#include +#include +#include + + + +//======================================================================= +//function : GraphTools_SortedStrgCmptsFromIterator +//purpose : +//======================================================================= + +GraphTools_SortedStrgCmptsFromIterator:: + GraphTools_SortedStrgCmptsFromIterator () +{ + myNowIndex = 0; +} + + +//======================================================================= +//function : FromVertex +//purpose : +//======================================================================= + +void GraphTools_SortedStrgCmptsFromIterator::FromVertex (const Vertex& V) +{ +#ifdef DEB + Standard_Integer index = +#endif + myVertices.Add (V,0); +} + + + +//======================================================================= +//function : Perform +//purpose : +//======================================================================= + +void GraphTools_SortedStrgCmptsFromIterator::Perform (const Graph& G) +{ + myNowIndex = 0; + mySort.Clear(); + Standard_Integer visited; + Standard_Integer temp; + Standard_Integer index = 1; + while (index <= myVertices.Extent()) { + visited = myVertices.FindFromIndex(index); + if (visited == 0) temp = Visit(index,G); + index ++; + } + myIterator.Initialize(mySort); +} + + +//======================================================================= +//function : Reset +//purpose : +//======================================================================= + +void GraphTools_SortedStrgCmptsFromIterator::Reset () +{ + myVertices.Clear(); + myNowIndex = 0; + myStack.Clear(); + mySort.Clear(); +} + + +//======================================================================= +//function : More +//purpose : declenche l'algorithme de recherche des Strong Components +//======================================================================= + +Standard_Boolean GraphTools_SortedStrgCmptsFromIterator::More() const +{ + return myIterator.More(); +} + + +//======================================================================= +//function : Next +//purpose : +//======================================================================= + +void GraphTools_SortedStrgCmptsFromIterator::Next() +{ + myIterator.Next(); +} + + +//======================================================================= +//function : NbVertices +//purpose : +//======================================================================= + +Standard_Integer GraphTools_SortedStrgCmptsFromIterator::NbVertices() const +{ + return myIterator.Value().Length(); +} + + +//======================================================================= +//function : Value +//purpose : +//======================================================================= + +const Vertex& GraphTools_SortedStrgCmptsFromIterator::Value + (const Standard_Integer I) const +{ + Standard_Integer indexvertex = myIterator.Value().Value(I); + return myVertices.FindKey (indexvertex); +} + +//======================================================================= +//function : Visit +//purpose : private +//======================================================================= + +Standard_Integer GraphTools_SortedStrgCmptsFromIterator::Visit + (const Standard_Integer k, const Graph& G) +{ + Standard_Integer MIN; + Standard_Integer M; + myNowIndex++; + myVertices(k) = myNowIndex; + MIN = myNowIndex; + myStack.Push(k); + Standard_Integer currentVisited; + currentVisited = myVertices.FindFromIndex (k); + Standard_Integer adjacentIndex; + Standard_Integer adjacentVisited; + for (VIterator itV (G,myVertices.FindKey(k)); itV.More(); itV.Next()) { + adjacentIndex = myVertices.FindIndex(itV.Value()); + if (adjacentIndex == 0) { + adjacentIndex = myVertices.Add (itV.Value(),0); + adjacentVisited = 0; + } + else adjacentVisited = myVertices.FindFromIndex (adjacentIndex); + if (adjacentVisited == 0) M = Visit(adjacentIndex,G); + else M = adjacentVisited; + if (M < MIN) MIN = M; + } + if (MIN == currentVisited) { + TColStd_SequenceOfInteger theSequence; + mySort.Prepend(theSequence); + TColStd_SequenceOfInteger& newSC = mySort.First(); + Standard_Boolean more; + do { + newSC.Append(myStack.Top()); + myVertices(myStack.Top()) = IntegerLast(); + more = myStack.Top() != k; + myStack.Pop() ; + } + while (more); + } + return MIN; +} + + + + + + + + + + + + + + + + + + + + + + + + diff --git a/src/GraphTools/GraphTools_SortedStrgCmptsIterator.cdl b/src/GraphTools/GraphTools_SortedStrgCmptsIterator.cdl new file mode 100644 index 0000000..24e14ea --- /dev/null +++ b/src/GraphTools/GraphTools_SortedStrgCmptsIterator.cdl @@ -0,0 +1,117 @@ +-- Created on: 1991-10-23 +-- Created by: Denis PASCAL +-- Copyright (c) 1991-1999 Matra Datavision +-- Copyright (c) 1999-2014 OPEN CASCADE SAS +-- +-- This file is part of Open CASCADE Technology software library. +-- +-- This library is free software; you can redistribute it and/or modify it under +-- the terms of the GNU Lesser General Public License version 2.1 as published +-- by the Free Software Foundation, with special exception defined in the file +-- OCCT_LGPL_EXCEPTION.txt. Consult the file LICENSE_LGPL_21.txt included in OCCT +-- distribution for complete text of the license and disclaimer of any warranty. +-- +-- Alternatively, this file may be used under the terms of Open CASCADE +-- commercial license or contractual agreement. + +generic class SortedStrgCmptsIterator from GraphTools + (Graph as any; + Vertex as any; + GIterator as any; + SSCIterator as any) + +--generic class SortedStrgCmptsIterator from GraphTools +-- (Graph as any; +-- Vertex as any; +-- GIterator as GraphIterator (Graph,Vertex)) +-- SSCIterator as SortedStrgCmptsFromIterator + + ---Purposes: This generic class implements the + -- SortedStrgCptsFromIterator with all vertices of + -- reached by the Tool GIterator. + +raises NoMoreObject from Standard, + NoSuchObject from Standard + +is + + + Create + returns SortedStrgCmptsIterator from GraphTools; + ---Purpose: Create an empty algorithm. + + Create (G : Graph) + ---Purpose: Create the algorithm setting each vertex of + -- reached by GIterator tool, as initial conditions. + -- Use Perform method before visting the result of + -- the algorithm. + returns SortedStrgCmptsIterator from GraphTools; + + FromGraph (me : in out; G : Graph); + ---Purpose: Add each vertex of reached by GIterator tool + -- as initial conditions. Use Perform method + -- before visiting the result of the algorithm. + ---Level: Public + + FromVertex (me : in out; V : Vertex); + ---Purpose: Add as initial condition. This method is + -- cumulative. Use Perform method before visting the + -- result of the algorithm. + ---Level: Public + + Reset (me : in out); + ---Purpose: Reset the algorithm. It may be reused with new + -- initial conditions. + ---Level: Public + + Perform (me : in out; G : Graph); + ---Purpose: Peform the algorithm in from initial setted + -- conditions. + ---Level: Public + + More(me) returns Boolean from Standard; + ---Purpose: returns True if there are others strong + -- components. + ---Level: Public + + Next(me : in out) + ---Purpose: Set the iterator to the next strong component. + ---Level: Public + raises NoMoreObject from Standard; + + NbVertices (me) returns Integer from Standard + ---Purpose: Returns number of vertices of the current Strong + -- Components. + ---Level: Public + raises NoSuchObject from Standard; + + Value(me; I : Integer from Standard) + returns any Vertex + ---Purpose: returns the vertex of index of the current + -- Strong Component. + ---C++: return const & + ---Level: Public + raises NoSuchObject from Standard; + +fields + + myIterator : SSCIterator; + +end SortedStrgCmptsIterator; + + + + + + + + + + + + + + + + + diff --git a/src/GraphTools/GraphTools_SortedStrgCmptsIterator.gxx b/src/GraphTools/GraphTools_SortedStrgCmptsIterator.gxx new file mode 100644 index 0000000..4151cf2 --- /dev/null +++ b/src/GraphTools/GraphTools_SortedStrgCmptsIterator.gxx @@ -0,0 +1,140 @@ +// Created on: 1991-10-23 +// Created by: Denis PASCAL +// Copyright (c) 1991-1999 Matra Datavision +// Copyright (c) 1999-2014 OPEN CASCADE SAS +// +// This file is part of Open CASCADE Technology software library. +// +// This library is free software; you can redistribute it and/or modify it under +// the terms of the GNU Lesser General Public License version 2.1 as published +// by the Free Software Foundation, with special exception defined in the file +// OCCT_LGPL_EXCEPTION.txt. Consult the file LICENSE_LGPL_21.txt included in OCCT +// distribution for complete text of the license and disclaimer of any warranty. +// +// Alternatively, this file may be used under the terms of Open CASCADE +// commercial license or contractual agreement. + +// + +//======================================================================= +//function : GraphTools_SortedStrgCmptsIterator +//purpose : +//======================================================================= + +GraphTools_SortedStrgCmptsIterator::GraphTools_SortedStrgCmptsIterator () +{} + + + +//======================================================================= +//function : GraphTools_SortedStrgCmptsIterator +//purpose : +//======================================================================= + +GraphTools_SortedStrgCmptsIterator::GraphTools_SortedStrgCmptsIterator + (const Graph& G) +{ + FromGraph(G); +} + + +//======================================================================= +//function : FromVertex +//purpose : +//======================================================================= + +void GraphTools_SortedStrgCmptsIterator::FromVertex + (const Vertex& V) +{ + myIterator.FromVertex(V); +} + + +//======================================================================= +//function : FromGraph +//purpose : +//======================================================================= + +void GraphTools_SortedStrgCmptsIterator::FromGraph + (const Graph& G) +{ + for ( GIterator it (G); it.More(); it.Next() ) { + myIterator.FromVertex(it.Value()); + } +} + + +//======================================================================= +//function : Perform +//purpose : +//======================================================================= + +void GraphTools_SortedStrgCmptsIterator::Perform + (const Graph& G) +{ + myIterator.Perform(G); +} + + +//======================================================================= +//function : Reset +//purpose : +//======================================================================= + +void GraphTools_SortedStrgCmptsIterator::Reset () +{ + myIterator.Reset(); +} + + +//======================================================================= +//function : More +//purpose : +//======================================================================= + +Standard_Boolean GraphTools_SortedStrgCmptsIterator::More() const +{ + return myIterator.More(); +} + + +//======================================================================= +//function : Next +//purpose : +//======================================================================= + +void GraphTools_SortedStrgCmptsIterator::Next() +{ + myIterator.Next(); +} + +//======================================================================= +//function : NbVertices +//purpose : +//======================================================================= + +Standard_Integer GraphTools_SortedStrgCmptsIterator::NbVertices() const +{ + return myIterator.NbVertices(); +} + +//======================================================================= +//function : Value +//purpose : +//======================================================================= + +const Vertex& GraphTools_SortedStrgCmptsIterator::Value + (const Standard_Integer I) const +{ + return myIterator.Value(I); +} + + + + + + + + + + diff --git a/src/GraphTools/GraphTools_TSNode.cdl b/src/GraphTools/GraphTools_TSNode.cdl new file mode 100644 index 0000000..cf1d523 --- /dev/null +++ b/src/GraphTools/GraphTools_TSNode.cdl @@ -0,0 +1,49 @@ +-- Created on: 1993-09-28 +-- Created by: Denis PASCAL +-- Copyright (c) 1993-1999 Matra Datavision +-- Copyright (c) 1999-2014 OPEN CASCADE SAS +-- +-- This file is part of Open CASCADE Technology software library. +-- +-- This library is free software; you can redistribute it and/or modify it under +-- the terms of the GNU Lesser General Public License version 2.1 as published +-- by the Free Software Foundation, with special exception defined in the file +-- OCCT_LGPL_EXCEPTION.txt. Consult the file LICENSE_LGPL_21.txt included in OCCT +-- distribution for complete text of the license and disclaimer of any warranty. +-- +-- Alternatively, this file may be used under the terms of Open CASCADE +-- commercial license or contractual agreement. + +class TSNode from GraphTools + +uses SequenceOfInteger from TColStd + +is + + Create returns TSNode from GraphTools; + + Reset (me : in out); + + IncreaseRef (me : in out); + + DecreaseRef (me : in out); + + NbRef (me) returns Integer from Standard; + + AddSuccessor (me : in out; s : Integer from Standard); + + NbSuccessors (me) returns Integer from Standard; + + GetSuccessor (me; index : Integer from Standard) + returns Integer from Standard; + +fields + + referenceCount : Integer from Standard; + mySuccessors : SequenceOfInteger from TColStd; + +end TSNode; + + + + diff --git a/src/GraphTools/GraphTools_TSNode.cxx b/src/GraphTools/GraphTools_TSNode.cxx new file mode 100644 index 0000000..9cda7bb --- /dev/null +++ b/src/GraphTools/GraphTools_TSNode.cxx @@ -0,0 +1,104 @@ +// Created on: 1991-06-20 +// Created by: Denis PASCAL +// Copyright (c) 1991-1999 Matra Datavision +// Copyright (c) 1999-2014 OPEN CASCADE SAS +// +// This file is part of Open CASCADE Technology software library. +// +// This library is free software; you can redistribute it and/or modify it under +// the terms of the GNU Lesser General Public License version 2.1 as published +// by the Free Software Foundation, with special exception defined in the file +// OCCT_LGPL_EXCEPTION.txt. Consult the file LICENSE_LGPL_21.txt included in OCCT +// distribution for complete text of the license and disclaimer of any warranty. +// +// Alternatively, this file may be used under the terms of Open CASCADE +// commercial license or contractual agreement. + +// + +#include + +//======================================================================= +//function : GraphTools_TSNode +//purpose : +//======================================================================= +GraphTools_TSNode::GraphTools_TSNode () +{ + referenceCount = 0; +} + + +//======================================================================= +//function : Reset +//purpose : +//======================================================================= + +void GraphTools_TSNode::Reset () +{ + referenceCount = 0; + mySuccessors.Clear(); +} + + + +//======================================================================= +//function : IncreaseRef +//purpose : +//======================================================================= + +void GraphTools_TSNode::IncreaseRef() { referenceCount++; } + +//======================================================================= +//function : DecreaseRef +//purpose : +//======================================================================= + +void GraphTools_TSNode::DecreaseRef() { referenceCount--; } + + +//======================================================================= +//function : NbRef +//purpose : +//======================================================================= + +Standard_Integer GraphTools_TSNode::NbRef() const +{ + return referenceCount; +} + + +//======================================================================= +//function : AddSuccessor +//purpose : +//======================================================================= + +void GraphTools_TSNode::AddSuccessor(const Standard_Integer s) +{ + mySuccessors.Append(s); +} + + +//======================================================================= +//function : NbSuccessors +//purpose : +//======================================================================= + +Standard_Integer GraphTools_TSNode::NbSuccessors() const +{ + return mySuccessors.Length(); +} + +//======================================================================= +//function : GetSuccessor +//purpose : +//======================================================================= + +Standard_Integer GraphTools_TSNode::GetSuccessor + (const Standard_Integer index) const +{ + return mySuccessors(index); +} + + + + diff --git a/src/GraphTools/GraphTools_TopologicalSortFromIterator.cdl b/src/GraphTools/GraphTools_TopologicalSortFromIterator.cdl new file mode 100644 index 0000000..b61b2a1 --- /dev/null +++ b/src/GraphTools/GraphTools_TopologicalSortFromIterator.cdl @@ -0,0 +1,114 @@ +-- Created on: 1992-12-24 +-- Created by: Denis PASCAL +-- Copyright (c) 1992-1999 Matra Datavision +-- Copyright (c) 1999-2014 OPEN CASCADE SAS +-- +-- This file is part of Open CASCADE Technology software library. +-- +-- This library is free software; you can redistribute it and/or modify it under +-- the terms of the GNU Lesser General Public License version 2.1 as published +-- by the Free Software Foundation, with special exception defined in the file +-- OCCT_LGPL_EXCEPTION.txt. Consult the file LICENSE_LGPL_21.txt included in OCCT +-- distribution for complete text of the license and disclaimer of any warranty. +-- +-- Alternatively, this file may be used under the terms of Open CASCADE +-- commercial license or contractual agreement. + +generic class TopologicalSortFromIterator from GraphTools + (Graph as any; + Vertex as any; + VHasher as any; + VIterator as any) + +--generic class TopologicalSortFromIterator from GraphTools +-- (Graph as any; +-- Vertex as any; +-- VHasher as MapHasher from TCollection (Vertex); +-- VIterator as VertexIterator (Graph,Vertex)) + + ---Purpose: This generic class defines an iterator to visit + -- each vertex of the underlying graph, in such an + -- order that noone vertex is reach before any vertex + -- that point to it. In general the order produced by + -- topological sort is not unique. Usefull for DAG + -- Topological Sort. The option + -- allows the user to ignore (or not) any vertex wich + -- contains a self loop. The option + -- allows the user to visit (or not> vertices which + -- are in a cycle. + + +uses SequenceOfInteger from TColStd + +raises NoSuchObject from Standard, + NoMoreObject from Standard, + DomainError from Standard + + private class TSMap instantiates IndexedDataMap from TCollection + (Vertex,TSNode from GraphTools,VHasher); + +is + + Create + ---Purpose: Create an empty algorithm. + returns TopologicalSortFromIterator from GraphTools; + + FromVertex (me : in out; V : Vertex); + ---Purpose: Add as initial condition. This method is + -- cumulative. Use Perform method before visting the + -- result of the algorithm. + ---Level: Public + + Reset (me : in out); + ---Purpose: Reset the algorithm. It may be reused with new + -- initial conditions. + ---Level: Public + + Perform (me : in out; G : Graph; + ignoreSelfLoop : Boolean from Standard; + processCycle : Boolean from Standard); + ---Purpose: Peform the algorithm in from initial setted + -- conditions according to the two following flags. + -- * allows the user to ignore (or + -- not) any vertex wich contains a self loop. + -- * allows the user to visit (or not> + -- vertex which is in a cycle. + ---Level: Public + + More (me) + returns Boolean from Standard; + ---Level: Public + + Next (me : in out) + raises NoMoreObject from Standard; + ---Level: Public + + Value (me) + returns any Vertex + ---Level: Public + ---C++: return const & + raises NoSuchObject from Standard; + + IsInCycle (me) + returns Boolean from Standard + ---Purpose: Returns TRUE if the current vertex is in a cycle. + ---Level: Public + raises NoSuchObject from Standard; + + +fields + +-- conditions + myVertices : TSMap from GraphTools; + myIgnoreSelfLoop : Boolean from Standard; + myProcessCycle : Boolean from Standard; +-- result + mySort : SequenceOfInteger from TColStd; + myCycles : Integer from Standard; + myCurrent : Integer from Standard; + +end TopologicalSortFromIterator; + + + + diff --git a/src/GraphTools/GraphTools_TopologicalSortFromIterator.gxx b/src/GraphTools/GraphTools_TopologicalSortFromIterator.gxx new file mode 100644 index 0000000..17cbd00 --- /dev/null +++ b/src/GraphTools/GraphTools_TopologicalSortFromIterator.gxx @@ -0,0 +1,225 @@ +// Created on: 1991-05-29 +// Created by: Denis PASCAL +// Copyright (c) 1991-1999 Matra Datavision +// Copyright (c) 1999-2014 OPEN CASCADE SAS +// +// This file is part of Open CASCADE Technology software library. +// +// This library is free software; you can redistribute it and/or modify it under +// the terms of the GNU Lesser General Public License version 2.1 as published +// by the Free Software Foundation, with special exception defined in the file +// OCCT_LGPL_EXCEPTION.txt. Consult the file LICENSE_LGPL_21.txt included in OCCT +// distribution for complete text of the license and disclaimer of any warranty. +// +// Alternatively, this file may be used under the terms of Open CASCADE +// commercial license or contractual agreement. + +// + +#include +#include +#include +#include +#include + +//======================================================================= +//function : GraphTools_TopologicalSortFromIterator +//purpose : +//======================================================================= + +GraphTools_TopologicalSortFromIterator::GraphTools_TopologicalSortFromIterator () {} + + + +//======================================================================= +//function : FromVertex +//purpose : +//======================================================================= + +void GraphTools_TopologicalSortFromIterator::FromVertex (const Vertex& V) +{ + GraphTools_TSNode newnode; + myVertices.Add(V,newnode); +} + + +//======================================================================= +//function : Perform +//purpose : +//======================================================================= + +void GraphTools_TopologicalSortFromIterator::Perform + (const Graph& G, + const Standard_Boolean ignoreSelfLoop, + const Standard_Boolean processCycle) +{ + myIgnoreSelfLoop = ignoreSelfLoop; + myProcessCycle = processCycle; + myCurrent = 1; + mySort.Clear(); + // algorithm DS + Standard_Integer i, indexcurrent, indexadjacent, nbadjacent; + indexcurrent = 1; + while (indexcurrent <= myVertices.Extent()) { + VIterator itV (G,myVertices.FindKey(indexcurrent)); + for ( ; itV.More(); itV.Next()) { + indexadjacent = myVertices.FindIndex(itV.Value()); + if (indexadjacent == 0) { + GraphTools_TSNode newnode; + indexadjacent = myVertices.Add(itV.Value(),newnode); + } + if (! (indexcurrent == indexadjacent && myIgnoreSelfLoop)) { + myVertices(indexcurrent).AddSuccessor(indexadjacent); + myVertices(indexadjacent).IncreaseRef(); + } + } + indexcurrent++; + } + // current root vertices queue + TColStd_QueueOfInteger processQueue; + Standard_Integer nbVertices = myVertices.Extent(); + for (i = 1 ; i <= nbVertices; i++) { + if (myVertices(i).NbRef() == 0) processQueue.Push(i); + } + // acyclic processing + while (!processQueue.IsEmpty()) { + indexcurrent = processQueue.Front(); + mySort.Append(indexcurrent); + nbadjacent = myVertices(indexcurrent).NbSuccessors(); + for (i = 1; i <= nbadjacent; i++) { + indexadjacent = myVertices(indexcurrent).GetSuccessor(i); + myVertices(indexadjacent).DecreaseRef(); + if (myVertices(indexadjacent).NbRef() == 0) { + processQueue.Push (indexadjacent); + } + } + processQueue.Pop(); + } + // cyclic processing + myCycles = mySort.Length() + 1; + if (myProcessCycle) { + for (i = 1 ; i <= nbVertices; i++) { + if (myVertices(i).NbRef() != 0) mySort.Append(i); + } + } +} + + +//======================================================================= +//function : Reset +//purpose : +//======================================================================= + +void GraphTools_TopologicalSortFromIterator::Reset () +{ + myVertices.Clear(); +// myIgnoreSelfLoop : Boolean from Standard; +// myProcessCycle : Boolean from Standard; + mySort.Clear(); +// myCycles : Integer from Standard; + myCurrent = 1; +} + + +//======================================================================= +//function : More +//purpose : +//======================================================================= + +Standard_Boolean GraphTools_TopologicalSortFromIterator::More () const +{ + return myCurrent <= mySort.Length(); +} + + +//======================================================================= +//function : Next +//purpose : +//======================================================================= + +void GraphTools_TopologicalSortFromIterator::Next () +{ + if (!More()) Standard_NoMoreObject::Raise(); + myCurrent ++; +} + + +//======================================================================= +//function : Value +//purpose : +//======================================================================= + +const Vertex& GraphTools_TopologicalSortFromIterator::Value () const { + if (!More()) Standard_NoSuchObject::Raise(); + return myVertices.FindKey (mySort(myCurrent)); +} + + +//======================================================================= +//function : IsInCycle +//purpose : +//======================================================================= + +Standard_Boolean GraphTools_TopologicalSortFromIterator::IsInCycle () const +{ + if (!More()) Standard_NoSuchObject::Raise(); + return myCurrent >= myCycles; +} + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + diff --git a/src/GraphTools/GraphTools_TopologicalSortIterator.cdl b/src/GraphTools/GraphTools_TopologicalSortIterator.cdl new file mode 100644 index 0000000..790f314 --- /dev/null +++ b/src/GraphTools/GraphTools_TopologicalSortIterator.cdl @@ -0,0 +1,107 @@ +-- Created on: 1992-12-24 +-- Created by: Denis PASCAL +-- Copyright (c) 1992-1999 Matra Datavision +-- Copyright (c) 1999-2014 OPEN CASCADE SAS +-- +-- This file is part of Open CASCADE Technology software library. +-- +-- This library is free software; you can redistribute it and/or modify it under +-- the terms of the GNU Lesser General Public License version 2.1 as published +-- by the Free Software Foundation, with special exception defined in the file +-- OCCT_LGPL_EXCEPTION.txt. Consult the file LICENSE_LGPL_21.txt included in OCCT +-- distribution for complete text of the license and disclaimer of any warranty. +-- +-- Alternatively, this file may be used under the terms of Open CASCADE +-- commercial license or contractual agreement. + +generic class TopologicalSortIterator from GraphTools + (Graph as any; + Vertex as any; + GIterator as any; + TSIterator as any) + +--generic class TopologicalSorIterator from GraphTools +-- (Graph as any; +-- Vertex as any; +-- GIterator as GraphIterator (Graph,Vertex)) +-- TSIterator as TopologicalSortFromIterator + + ---Purpose: This generic class defines an iterator to visit + -- each vertex of the underlying graph, in such an + -- order that noone vertex is reach before any vertex + -- that point to it. In general the order produced by + -- topological sort is not unique. Usefull for DAG + -- Topological Sort. + +raises NoSuchObject from Standard, + NoMoreObject from Standard + + +is + + Create + ---Purpose: Create an empty algorithm. + returns TopologicalSortIterator from GraphTools; + + Create (G : Graph) + ---Purpose: Create the algorithm setting each vertex of + -- reached by GIterator tool, as initial conditions. + -- Use Perform method before visting the result of + -- the algorithm. + returns TopologicalSortIterator from GraphTools; + + FromGraph (me : in out; G : Graph); + ---Purpose: Add each vertex of reached by GIterator tool + -- as initial conditions. Use Perform method + -- before visiting the result of the algorithm. + ---Level: Public + + FromVertex (me : in out; V : Vertex); + ---Purpose: Add as initial condition. This method is + -- cumulative. Use Perform method before visting the + -- result of the algorithm. + ---Level: Public + + Reset (me : in out); + ---Purpose: Reset the algorithm. It may be reused with new + -- initial conditions. + ---Level: Public + + Perform (me : in out; G : Graph ; + ignoreSelfLoop : Boolean from Standard; + processCycle : Boolean from Standard); + ---Purpose: Peform the algorithm in from initial setted + -- conditions according to the two following flags. + -- * allows the user to ignore (or + -- not) any vertex wich contains a self loop. + -- * allows the user to visit (or not> + -- vertex which is in a cycle. + ---Level: Public + + More (me) + returns Boolean from Standard; + ---Level: Public + + Next (me : in out) + raises NoMoreObject from Standard; + ---Level: Public + + Value (me) returns any Vertex + ---Level: Public + ---C++: return const & + raises NoSuchObject from Standard; + + IsInCycle (me) returns Boolean from Standard + ---Purpose: Returns TRUE if the current vertex is in a cycle. + ---Level: Public + raises NoSuchObject from Standard; + +fields + + myIterator : TSIterator; + +end TopologicalSortIterator; + + + + diff --git a/src/GraphTools/GraphTools_TopologicalSortIterator.gxx b/src/GraphTools/GraphTools_TopologicalSortIterator.gxx new file mode 100644 index 0000000..a2868eb --- /dev/null +++ b/src/GraphTools/GraphTools_TopologicalSortIterator.gxx @@ -0,0 +1,154 @@ +// Created on: 1991-05-29 +// Created by: Denis PASCAL +// Copyright (c) 1991-1999 Matra Datavision +// Copyright (c) 1999-2014 OPEN CASCADE SAS +// +// This file is part of Open CASCADE Technology software library. +// +// This library is free software; you can redistribute it and/or modify it under +// the terms of the GNU Lesser General Public License version 2.1 as published +// by the Free Software Foundation, with special exception defined in the file +// OCCT_LGPL_EXCEPTION.txt. Consult the file LICENSE_LGPL_21.txt included in OCCT +// distribution for complete text of the license and disclaimer of any warranty. +// +// Alternatively, this file may be used under the terms of Open CASCADE +// commercial license or contractual agreement. + +// + + +//======================================================================= +//function : GraphTools_TopologicalSortIterator +//purpose : +//======================================================================= + +GraphTools_TopologicalSortIterator::GraphTools_TopologicalSortIterator () +{} + + +//======================================================================= +//function : GraphTools_TopologicalSortIterator +//purpose : +//======================================================================= + +GraphTools_TopologicalSortIterator::GraphTools_TopologicalSortIterator + (const Graph& G) +{ + FromGraph (G); +} + + +//======================================================================= +//function : FromVertex +//purpose : +//======================================================================= + +void GraphTools_TopologicalSortIterator::FromVertex + (const Vertex& V) +{ + myIterator.FromVertex(V); +} + + +//======================================================================= +//function : FromGraph +//purpose : +//======================================================================= + +void GraphTools_TopologicalSortIterator::FromGraph + (const Graph& G) +{ + for ( GIterator it (G); it.More(); it.Next() ) { + myIterator.FromVertex(it.Value()); + } +} + + +//======================================================================= +//function : Perform +//purpose : +//======================================================================= + +void GraphTools_TopologicalSortIterator::Perform + (const Graph& G, + const Standard_Boolean ignoreSelfLoops, + const Standard_Boolean processCycle) +{ + myIterator.Perform(G,ignoreSelfLoops,processCycle); +} + + +//======================================================================= +//function : Reset +//purpose : +//======================================================================= + +void GraphTools_TopologicalSortIterator::Reset () +{ + myIterator.Reset(); +} + + +//======================================================================= +//function : More +//purpose : +//======================================================================= + +Standard_Boolean GraphTools_TopologicalSortIterator::More () const +{ + return myIterator.More(); +} + + +//======================================================================= +//function : Next +//purpose : +//======================================================================= + +void GraphTools_TopologicalSortIterator::Next () +{ + myIterator.Next(); +} + + +//======================================================================= +//function : Value +//purpose : +//======================================================================= + +const Vertex& GraphTools_TopologicalSortIterator::Value () const +{ + return myIterator.Value(); +} + + +//======================================================================= +//function : IsInCycle +//purpose : +//======================================================================= + +Standard_Boolean GraphTools_TopologicalSortIterator::IsInCycle () const +{ + return myIterator.IsInCycle(); +} + + + + + + + + + + + + + + + + + + + + + diff --git a/src/GraphTools/GraphTools_VertexIterator.cdl b/src/GraphTools/GraphTools_VertexIterator.cdl new file mode 100644 index 0000000..0b23810 --- /dev/null +++ b/src/GraphTools/GraphTools_VertexIterator.cdl @@ -0,0 +1,69 @@ +-- Created on: 1991-03-06 +-- Created by: Denis Pascal +-- Copyright (c) 1991-1999 Matra Datavision +-- Copyright (c) 1999-2014 OPEN CASCADE SAS +-- +-- This file is part of Open CASCADE Technology software library. +-- +-- This library is free software; you can redistribute it and/or modify it under +-- the terms of the GNU Lesser General Public License version 2.1 as published +-- by the Free Software Foundation, with special exception defined in the file +-- OCCT_LGPL_EXCEPTION.txt. Consult the file LICENSE_LGPL_21.txt included in OCCT +-- distribution for complete text of the license and disclaimer of any warranty. +-- +-- Alternatively, this file may be used under the terms of Open CASCADE +-- commercial license or contractual agreement. + +generic class VertexIterator from GraphTools (Graph as any; + Vertex as any) + +--template class VertexIterator from GraphTools (Graph as any, +-- Vertex as any) + + ---Purpose: Template class which defines Signature of an iterator + -- to visit each adjacent vertex of a given one in the + -- underlying graph. + + +raises NoMoreObject from Standard, + NoSuchObject from Standard + +is + + Create (G : Graph; V : Vertex) returns VertexIterator; + + More (me) returns Boolean; + ---Purpose: Returns TRUE if there are other vertices. + ---Level: Public + + Next(me : in out) + --- Purpose : Set the iterator to the next Vertex. + ---Level: Public + raises NoMoreObject from Standard; + + Value(me) returns Vertex + --- Purpose: Returns the vertex value for the current position + -- of the iterator. + ---Level: Public + raises NoSuchObject from Standard; + +end VertexIterator; + + + + + + + + + + + + + + + + + + + diff --git a/src/GraphTools/GraphTools_VertexIterator.gxx b/src/GraphTools/GraphTools_VertexIterator.gxx new file mode 100644 index 0000000..b628db6 --- /dev/null +++ b/src/GraphTools/GraphTools_VertexIterator.gxx @@ -0,0 +1,15 @@ +// Created on: 1993-09-27 +// Created by: Denis PASCAL +// Copyright (c) 1993-1999 Matra Datavision +// Copyright (c) 1999-2014 OPEN CASCADE SAS +// +// This file is part of Open CASCADE Technology software library. +// +// This library is free software; you can redistribute it and/or modify it under +// the terms of the GNU Lesser General Public License version 2.1 as published +// by the Free Software Foundation, with special exception defined in the file +// OCCT_LGPL_EXCEPTION.txt. Consult the file LICENSE_LGPL_21.txt included in OCCT +// distribution for complete text of the license and disclaimer of any warranty. +// +// Alternatively, this file may be used under the terms of Open CASCADE +// commercial license or contractual agreement. diff --git a/src/TKWOK/EXTERNLIB b/src/TKWOK/EXTERNLIB index 08d6ab9..58c24f0 100755 --- a/src/TKWOK/EXTERNLIB +++ b/src/TKWOK/EXTERNLIB @@ -1,2 +1 @@ -TKAdvTools TKernel diff --git a/src/TKWOK/PACKAGES b/src/TKWOK/PACKAGES index bdd04aa..e302d5e 100755 --- a/src/TKWOK/PACKAGES +++ b/src/TKWOK/PACKAGES @@ -13,3 +13,4 @@ WOKUnix WOKUtils WOKernel WOKNT +GraphTools \ No newline at end of file diff --git a/src/WOKLibs/EXTERNLIB b/src/WOKLibs/EXTERNLIB index 878b0fe..e679489 100755 --- a/src/WOKLibs/EXTERNLIB +++ b/src/WOKLibs/EXTERNLIB @@ -1,4 +1,3 @@ -TKAdvTools TKernel TKWOK TKWOKTcl diff --git a/src/WOKSH/EXTERNLIB b/src/WOKSH/EXTERNLIB index 878b0fe..e679489 100755 --- a/src/WOKSH/EXTERNLIB +++ b/src/WOKSH/EXTERNLIB @@ -1,4 +1,3 @@ -TKAdvTools TKernel TKWOK TKWOKTcl -- 2.39.5