src/GraphTools/GraphTools_TopologicalSortFromIterator.cdl

   1 -- Created on: 1992-12-24
   2 -- Created by: Denis PASCAL
   3 -- Copyright (c) 1992-1999 Matra Datavision
   4 -- Copyright (c) 1999-2014 OPEN CASCADE SAS
   5 --
   6 -- This file is part of Open CASCADE Technology software library.
   7 --
   8 -- This library is free software; you can redistribute it and/or modify it under
   9 -- the terms of the GNU Lesser General Public License version 2.1 as published
  10 -- by the Free Software Foundation, with special exception defined in the file
  11 -- OCCT_LGPL_EXCEPTION.txt. Consult the file LICENSE_LGPL_21.txt included in OCCT
  12 -- distribution for complete text of the license and disclaimer of any warranty.
  13 --
  14 -- Alternatively, this file may be used under the terms of Open CASCADE
  15 -- commercial license or contractual agreement.
  16
  17 generic class TopologicalSortFromIterator from GraphTools
  18     (Graph     as any;
  19      Vertex    as any;
  20      VHasher   as any;
  21      VIterator as any)
  22
  23 --generic class TopologicalSortFromIterator from GraphTools
  24 --               (Graph     as any;
  25 --                Vertex    as any;
  26 --                VHasher   as MapHasher from TCollection (Vertex);
  27 --                VIterator as VertexIterator (Graph,Vertex))
  28
  29         ---Purpose: This generic  class defines  an iterator to  visit
  30         --          each vertex of   the underlying graph,  in such an
  31         --          order that noone vertex is reach before any vertex
  32         --          that point to it. In general the order produced by
  33         --          topological sort  is  not unique. Usefull  for DAG
  34         --          Topological  Sort.  The   option  <ignoreSelfLoop>
  35         --          allows the user to ignore (or not) any vertex wich
  36         --          contains a  self loop.   The option <processCycle>
  37         --          allows the user to  visit (or not> vertices  which
  38         --          are in a cycle.
  39
  40
  41 uses SequenceOfInteger from TColStd
  42
  43 raises NoSuchObject from Standard,
  44        NoMoreObject from Standard,
  45        DomainError  from Standard
  46
  47     private class TSMap instantiates IndexedDataMap from TCollection
  48                 (Vertex,TSNode from GraphTools,VHasher);
  49
  50 is
  51
  52     Create
  53         ---Purpose: Create an empty algorithm.
  54     returns TopologicalSortFromIterator from GraphTools;
  55
  56     FromVertex (me : in out; V : Vertex);
  57         ---Purpose: Add  <V>  as  initial  condition.  This method  is
  58         --          cumulative.  Use Perform method before visting the
  59         --          result of the algorithm.
  60         ---Level: Public
  61
  62     Reset (me : in out);
  63         ---Purpose: Reset the  algorithm.  It  may be reused  with new
  64         --          initial conditions.
  65         ---Level: Public
  66
  67     Perform (me : in out; G              : Graph;
  68                           ignoreSelfLoop : Boolean from Standard;
  69                           processCycle   : Boolean from Standard);
  70         ---Purpose: Peform the  algorithm  in  <G> from initial setted
  71         --          conditions according to  the two following flags.
  72         --          * <ignoreSelfLoop>  allows the  user to ignore (or
  73         --          not) any vertex wich contains a self loop.
  74         --          * <processCycle> allows the user to visit (or not>
  75         --          vertex which is in a cycle.
  76        ---Level: Public
  77
  78     More (me)
  79     returns Boolean from Standard;
  80        ---Level: Public
  81
  82     Next (me : in out)
  83     raises NoMoreObject from Standard;
  84        ---Level: Public
  85
  86     Value (me)
  87     returns any Vertex
  88        ---Level: Public
  89         ---C++: return const &
  90     raises NoSuchObject from Standard;
  91
  92     IsInCycle (me)
  93     returns Boolean from Standard
  94         ---Purpose: Returns TRUE if the current vertex is in a cycle.
  95        ---Level: Public
  96     raises NoSuchObject from Standard;
  97
  98
  99 fields
 100
 101 -- conditions
 102    myVertices       : TSMap   from GraphTools;
 103    myIgnoreSelfLoop : Boolean from Standard;
 104    myProcessCycle   : Boolean from Standard;
 105 -- result
 106    mySort           : SequenceOfInteger from TColStd;
 107    myCycles         : Integer from Standard;
 108    myCurrent        : Integer from Standard;
 109
 110 end TopologicalSortFromIterator;
 111
 112
 113
 114