src/GraphDS/GraphDS_DirectedGraph.cdl

   1 -- Created on: 1991-04-24
   2 -- Created by: Denis PASCAL
   3 -- Copyright (c) 1991-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 DirectedGraph from GraphDS
  18              (GraphDS_Item      as any ;
  19               GraphDS_Attribute as any)
  20
  21      ---Purpose: This class  describes  a structure  which  contains a
  22      --          list  of Vertices and a  list  of  Edges.  The vertex
  23      --          (also called a  Node), is the  basic element  of  the
  24      --          graph, it contains  an Item.  Each edge (also  called
  25      --          an  Arc)  defines  an   oriented link    between  two
  26      --          vertices.  it  contains an Attribute.   In the scheme
  27      --          A->B,  vertex A is called the   SOURCE of the link, B
  28      --          its DESTINATION, and B is ADJACENT to A.  If there is
  29      --          no edge which destinates  to a vertex, this vertex is
  30      --          a ROOT of  the graph.   If there  is no   edge  which
  31      --          originates from a vertex,  this vertex  is a  LEAF of
  32      --          the graph.
  33     --  Keywords: SOURCE vertex,  DESTINATION Vertex, ROOT vertex, LEAF
  34     --           vertex, ADJACENT vertex. Depth-first search, breadth
  35     --           first Search.
  36     --  References: Software Components with ADA (The Benjamin/Cummings
  37     --             Company, Inc.  1986).
  38
  39 uses MapOfTransient from TColStd
  40
  41 raises NoSuchObject from Standard,
  42        DomainError  from Standard
  43
  44
  45     class Vertex inherits TShared from MMgt
  46
  47         ---Purpose: nested  public class    vertex  (composed  of   an
  48         --          associated Item).
  49
  50     uses   MapOfTransient from TColStd
  51
  52     raises NoSuchObject   from Standard
  53
  54     is
  55
  56         Create (value : GraphDS_Item)
  57         returns mutable Vertex from GraphDS;
  58             --is private;
  59
  60         GetItem (me)
  61         returns any GraphDS_Item;
  62             ---Purpose: returns item associated to <me>.
  63             ---C++: return const &
  64             ---Level: Internal
  65
  66         SetItem (me : mutable; value : GraphDS_Item);
  67             ---Purpose: Associates a new item to <me>.
  68             ---Level: Internal
  69
  70         Contains (me; E : Edge)
  71         returns Boolean from Standard;
  72
  73         IsFront (me; E : Edge)
  74         returns Boolean from Standard;
  75
  76         IsBack (me; E : Edge)
  77         returns Boolean from Standard;
  78
  79         IsRoot (me; ignoreselfloop : Boolean from Standard = Standard_True)
  80         ---Purpose: Returns TRUE if NbBackEdges = 0.
  81         ---Level: Internal
  82         returns Boolean from Standard;
  83
  84         IsLeaf (me; ignoreselfloop : Boolean from Standard = Standard_True)
  85         ---Purpose: Returns TRUE if NbFrontEdges = 0.
  86         ---Level: Internal
  87         returns Boolean from Standard;
  88
  89         AddEdge (me : mutable; E : Edge)
  90         returns Boolean from Standard
  91         is private;
  92
  93         RemoveEdge (me : mutable; anEdge : Edge)
  94         raises NoSuchObject from Standard
  95         is private;
  96
  97         GetEdges (me)
  98         returns MapOfTransient from TColStd
  99         ---C++: return const&
 100         ---Purpose: Returns <myEdges> field for Iterator;
 101         ---Level: Internal
 102         is private;
 103
 104     fields
 105
 106         myItem  : GraphDS_Item;
 107         myEdges : MapOfTransient from TColStd;
 108
 109     friends
 110         class DirectedGraph    from GraphDS,
 111         class Edge             from GraphDS,
 112         class VerticesIterator from GraphDS,
 113         class EdgesIterator    from GraphDS
 114
 115     end;
 116
 117
 118     class Edge inherits TShared from MMgt
 119
 120         ---Purpose: Nested   public   class  Edge   (composed of    an
 121         --          associated attribute) An  Edge is an oriented link
 122         --          between two vertices.
 123
 124     raises NoMoreObject from Standard ,
 125            NoSuchObject from Standard
 126     is
 127
 128         Create (source,destination : Vertex; value : GraphDS_Attribute)
 129         returns mutable Edge;
 130         --is private;
 131
 132         GetAttribute (me)
 133             ---Purpose: returns attribute associated to <me>.
 134             ---C++: return const &
 135             ---Level: Internal
 136         returns any GraphDS_Attribute;
 137
 138         SetAttribute (me : mutable; Value : GraphDS_Attribute);
 139             ---Purpose: To associate a new attribute to <me>.
 140             ---Level: Internal
 141
 142         Contains (me; V : Vertex)
 143         returns Boolean from Standard;
 144
 145         Source (me)
 146             ---C++: return const&
 147             ---Purpose: Returns the vertex which originates from <me>.
 148             ---Level: Internal
 149         returns mutable Vertex;
 150
 151         Destination (me)
 152             ---C++: return const&
 153             ---Purpose: Returns the vertex which destinates to <me>.
 154             ---Level: Internal
 155         returns mutable Vertex;
 156
 157         Reverse (me : mutable);
 158             ---Purpose: Reverse  the orientation of   <me>. the source
 159             --          vertex becomes the  destination  vertex.   And
 160             --          the destination the source.
 161             ---Level: Internal
 162
 163         IsLoop (me)
 164         returns Boolean from Standard;
 165             ---Purpose: Returns True if the source and destination vertices
 166             --          are equal.
 167             ---Level: Internal
 168
 169     fields
 170
 171         myAttribute   : GraphDS_Attribute;
 172         mySource      : Vertex from GraphDS;
 173         myDestination : Vertex from GraphDS;
 174
 175     friends
 176         class DirectedGraph    from GraphDS,
 177         class Vertex           from GraphDS,
 178         class VerticesIterator from GraphDS,
 179         class EdgesIterator    from GraphDS
 180
 181     end;
 182
 183     class VerticesIterator
 184
 185         ---Purpose: basic tool to iterate on vertices.
 186         --          1 - vertices member of a DirectedGraph.
 187         --          2 - adjacent vertices of a given one.
 188
 189     uses MapOfTransient from TColStd,
 190          MapIteratorOfMapOfTransient from TColStd
 191
 192     raises NoMoreObject from Standard,
 193            NoSuchObject from Standard
 194
 195     is
 196
 197         Create
 198         returns VerticesIterator from GraphDS;
 199
 200         Create (G : DirectedGraph from GraphDS)
 201         returns VerticesIterator from GraphDS;
 202
 203         Create (G : DirectedGraph from GraphDS;
 204                 V : Vertex       from GraphDS)
 205         returns VerticesIterator from GraphDS;
 206
 207         Initialize (me : in out; G : DirectedGraph from GraphDS);
 208         ---Level: Public
 209
 210         Initialize (me : in out; G : DirectedGraph from GraphDS;
 211                                  V : Vertex       from GraphDS);
 212         ---Level: Public
 213
 214         More (me)
 215         returns Boolean from Standard;
 216         ---Level: Public
 217
 218         Next (me : in out)
 219         raises NoMoreObject from Standard;
 220         ---Level: Public
 221
 222         Value (me)
 223         ---C++: return const&
 224         ---Level: Public
 225         returns Vertex
 226         raises NoSuchObject from Standard;
 227
 228     fields
 229
 230         myMap      : MapOfTransient from TColStd;
 231         myVertices : MapIteratorOfMapOfTransient from TColStd;
 232
 233     end;
 234
 235
 236     class EdgesIterator
 237
 238         ---Purpose: basic tool to iterate on edges :
 239         --          1 - edges member of a DirectedGraph.
 240         --          2 - edges referenced by a given vertex.
 241
 242     uses MapIteratorOfMapOfTransient from TColStd
 243
 244     raises NoMoreObject from Standard ,
 245            NoSuchObject from Standard
 246
 247     is
 248
 249         Create
 250         returns EdgesIterator from GraphDS;
 251
 252         Create (G : DirectedGraph from GraphDS)
 253         returns EdgesIterator from GraphDS;
 254
 255         Create (G : DirectedGraph from GraphDS;
 256                 V : Vertex from GraphDS)
 257         returns EdgesIterator from GraphDS;
 258
 259         Initialize (me : in out; G : DirectedGraph from GraphDS);
 260         ---Level: Public
 261
 262         Initialize (me : in out; G : DirectedGraph from GraphDS;
 263                                  V : Vertex from GraphDS);
 264         ---Level: Public
 265
 266         More (me)
 267         returns Boolean from Standard;
 268         ---Level: Public
 269
 270         Next (me : in out)
 271         raises NoMoreObject from Standard;
 272         ---Level: Public
 273
 274         Value (me)
 275         ---C++: return const&
 276         ---Level: Public
 277         returns Edge
 278         raises NoSuchObject from Standard;
 279
 280     fields
 281
 282         myEdges : MapIteratorOfMapOfTransient from TColStd;
 283
 284     end;
 285
 286
 287 is
 288
 289     Create
 290     returns DirectedGraph from GraphDS;
 291         ---Purpose: Create an empty Directed Graph.
 292
 293     IsEmpty (me)
 294     returns Boolean from Standard;
 295         ---Level: Public
 296
 297     NbVertices (me)
 298     returns Integer from Standard;
 299         ---Level: Public
 300
 301     NbEdges (me)
 302     returns Integer from Standard;
 303         ---Level: Public
 304
 305     Clear (me : in out);
 306         ---Purpose: removes all edges and vertices of <me>.
 307         ---Level: Public
 308
 309     Contains (me; E : Edge)
 310     returns Boolean from Standard;
 311         ---Level: Public
 312
 313     Contains (me; V : Vertex)
 314     returns Boolean from Standard;
 315         ---Level: Public
 316
 317     IsRoot (me; V : Vertex; ignoreselfloop : Boolean from Standard = Standard_True)
 318     returns Boolean from Standard;
 319         ---Level: Public
 320
 321     IsLeaf (me; V : Vertex; ignoreselfloop : Boolean from Standard = Standard_True)
 322     returns Boolean from Standard;
 323         ---Level: Public
 324
 325     Add (me : in out; value : GraphDS_Item)
 326         ---Purpose: Creates a vertex, with  a given Item  <value>, and
 327         --          Adds it   to <me>.   Of  course  this   new Vertex
 328         --          (returned by the method)  is  a  "root" and "leaf"
 329         --          vertex of <me>.
 330         ---Level: Public
 331     returns mutable Vertex;
 332
 333     Remove (me : in out; V : Vertex)
 334         ---Purpose: Removes <V>  from  <me>.  <NoSuchObject> is raised
 335         --          if   <V> is not  member of  <me>. <DomainError> is
 336         --          raised if <V> is used by at least one edge of <me>
 337         ---Level: Public
 338     raises NoSuchObject from Standard,
 339            DomainError from Standard;
 340
 341     Add (me : in out; source      : mutable Vertex;
 342                       destination : mutable Vertex;
 343                       value       : GraphDS_Attribute)
 344         ---Purpose: Creates  an Edge, with  a given Attribute <value>,
 345         --          from <source>  to  <destination>,  and Adds  it to
 346         --          <me>.  This  new edge is  returned  by the method.
 347         --          <NoSuchObject>     is raised   if  <source> and/or
 348         --          <destination> are not members of <me>.
 349         ---Level: Public
 350     returns mutable Edge
 351     raises NoSuchObject from Standard;
 352
 353     Remove (me : in out; E : Edge)
 354         ---Purpose: Removes  <E>  from <me>. <NoSuchObject> is raised if
 355         --          <E> is not member of <me>.
 356         ---Level: Public
 357     raises NoSuchObject from Standard;
 358
 359 fields
 360
 361     myVertices : MapOfTransient from TColStd;
 362     myEdges    : MapOfTransient from TColStd;
 363
 364 friends
 365     class VerticesIterator from GraphDS,
 366     class EdgesIterator    from GraphDS
 367
 368 end;
 369
 370
 371
 372
 373
 374
 375
 376
 377
 378
 379
 380
 381
 382
 383
 384
 385
 386