-- Created on: 1991-04-24 -- Created by: Denis PASCAL -- Copyright (c) 1991-1999 Matra Datavision -- Copyright (c) 1999-2012 OPEN CASCADE SAS -- -- The content of this file is subject to the Open CASCADE Technology Public -- License Version 6.5 (the "License"). You may not use the content of this file -- except in compliance with the License. Please obtain a copy of the License -- at http://www.opencascade.org and read it completely before using this file. -- -- The Initial Developer of the Original Code is Open CASCADE S.A.S., having its -- main offices at: 1, place des Freres Montgolfier, 78280 Guyancourt, France. -- -- The Original Code and all software distributed under the License is -- distributed on an "AS IS" basis, without warranty of any kind, and the -- Initial Developer hereby disclaims all such warranties, including without -- limitation, any warranties of merchantability, fitness for a particular -- purpose or non-infringement. Please see the License for the specific terms -- and conditions governing the rights and limitations under the License. generic class DirectedGraph from GraphDS (GraphDS_Item as any ; GraphDS_Attribute as any) ---Purpose: This class describes a structure which contains a -- list of Vertices and a list of Edges. The vertex -- (also called a Node), is the basic element of the -- graph, it contains an Item. Each edge (also called -- an Arc) defines an oriented link between two -- vertices. it contains an Attribute. In the scheme -- A->B, vertex A is called the SOURCE of the link, B -- its DESTINATION, and B is ADJACENT to A. If there is -- no edge which destinates to a vertex, this vertex is -- a ROOT of the graph. If there is no edge which -- originates from a vertex, this vertex is a LEAF of -- the graph. -- Keywords: SOURCE vertex, DESTINATION Vertex, ROOT vertex, LEAF -- vertex, ADJACENT vertex. Depth-first search, breadth -- first Search. -- References: Software Components with ADA (The Benjamin/Cummings -- Company, Inc. 1986). uses MapOfTransient from TColStd raises NoSuchObject from Standard, DomainError from Standard class Vertex inherits TShared from MMgt ---Purpose: nested public class vertex (composed of an -- associated Item). uses MapOfTransient from TColStd raises NoSuchObject from Standard is Create (value : GraphDS_Item) returns mutable Vertex from GraphDS; --is private; GetItem (me) returns any GraphDS_Item; ---Purpose: returns item associated to . ---C++: return const & ---Level: Internal SetItem (me : mutable; value : GraphDS_Item); ---Purpose: Associates a new item to . ---Level: Internal Contains (me; E : Edge) returns Boolean from Standard; IsFront (me; E : Edge) returns Boolean from Standard; IsBack (me; E : Edge) returns Boolean from Standard; IsRoot (me; ignoreselfloop : Boolean from Standard = Standard_True) ---Purpose: Returns TRUE if NbBackEdges = 0. ---Level: Internal returns Boolean from Standard; IsLeaf (me; ignoreselfloop : Boolean from Standard = Standard_True) ---Purpose: Returns TRUE if NbFrontEdges = 0. ---Level: Internal returns Boolean from Standard; AddEdge (me : mutable; E : Edge) returns Boolean from Standard is private; RemoveEdge (me : mutable; anEdge : Edge) raises NoSuchObject from Standard is private; GetEdges (me) returns MapOfTransient from TColStd ---C++: return const& ---Purpose: Returns field for Iterator; ---Level: Internal is private; fields myItem : GraphDS_Item; myEdges : MapOfTransient from TColStd; friends class DirectedGraph from GraphDS, class Edge from GraphDS, class VerticesIterator from GraphDS, class EdgesIterator from GraphDS end; class Edge inherits TShared from MMgt ---Purpose: Nested public class Edge (composed of an -- associated attribute) An Edge is an oriented link -- between two vertices. raises NoMoreObject from Standard , NoSuchObject from Standard is Create (source,destination : Vertex; value : GraphDS_Attribute) returns mutable Edge; --is private; GetAttribute (me) ---Purpose: returns attribute associated to . ---C++: return const & ---Level: Internal returns any GraphDS_Attribute; SetAttribute (me : mutable; Value : GraphDS_Attribute); ---Purpose: To associate a new attribute to . ---Level: Internal Contains (me; V : Vertex) returns Boolean from Standard; Source (me) ---C++: return const& ---Purpose: Returns the vertex which originates from . ---Level: Internal returns mutable Vertex; Destination (me) ---C++: return const& ---Purpose: Returns the vertex which destinates to . ---Level: Internal returns mutable Vertex; Reverse (me : mutable); ---Purpose: Reverse the orientation of . the source -- vertex becomes the destination vertex. And -- the destination the source. ---Level: Internal IsLoop (me) returns Boolean from Standard; ---Purpose: Returns True if the source and destination vertices -- are equal. ---Level: Internal fields myAttribute : GraphDS_Attribute; mySource : Vertex from GraphDS; myDestination : Vertex from GraphDS; friends class DirectedGraph from GraphDS, class Vertex from GraphDS, class VerticesIterator from GraphDS, class EdgesIterator from GraphDS end; class VerticesIterator ---Purpose: basic tool to iterate on vertices. -- 1 - vertices member of a DirectedGraph. -- 2 - adjacent vertices of a given one. uses MapOfTransient from TColStd, MapIteratorOfMapOfTransient from TColStd raises NoMoreObject from Standard, NoSuchObject from Standard is Create returns VerticesIterator from GraphDS; Create (G : DirectedGraph from GraphDS) returns VerticesIterator from GraphDS; Create (G : DirectedGraph from GraphDS; V : Vertex from GraphDS) returns VerticesIterator from GraphDS; Initialize (me : in out; G : DirectedGraph from GraphDS); ---Level: Public Initialize (me : in out; G : DirectedGraph from GraphDS; V : Vertex from GraphDS); ---Level: Public More (me) returns Boolean from Standard; ---Level: Public Next (me : in out) raises NoMoreObject from Standard; ---Level: Public Value (me) ---C++: return const& ---Level: Public returns Vertex raises NoSuchObject from Standard; fields myMap : MapOfTransient from TColStd; myVertices : MapIteratorOfMapOfTransient from TColStd; end; class EdgesIterator ---Purpose: basic tool to iterate on edges : -- 1 - edges member of a DirectedGraph. -- 2 - edges referenced by a given vertex. uses MapIteratorOfMapOfTransient from TColStd raises NoMoreObject from Standard , NoSuchObject from Standard is Create returns EdgesIterator from GraphDS; Create (G : DirectedGraph from GraphDS) returns EdgesIterator from GraphDS; Create (G : DirectedGraph from GraphDS; V : Vertex from GraphDS) returns EdgesIterator from GraphDS; Initialize (me : in out; G : DirectedGraph from GraphDS); ---Level: Public Initialize (me : in out; G : DirectedGraph from GraphDS; V : Vertex from GraphDS); ---Level: Public More (me) returns Boolean from Standard; ---Level: Public Next (me : in out) raises NoMoreObject from Standard; ---Level: Public Value (me) ---C++: return const& ---Level: Public returns Edge raises NoSuchObject from Standard; fields myEdges : MapIteratorOfMapOfTransient from TColStd; end; is Create returns DirectedGraph from GraphDS; ---Purpose: Create an empty Directed Graph. IsEmpty (me) returns Boolean from Standard; ---Level: Public NbVertices (me) returns Integer from Standard; ---Level: Public NbEdges (me) returns Integer from Standard; ---Level: Public Clear (me : in out); ---Purpose: removes all edges and vertices of . ---Level: Public Contains (me; E : Edge) returns Boolean from Standard; ---Level: Public Contains (me; V : Vertex) returns Boolean from Standard; ---Level: Public IsRoot (me; V : Vertex; ignoreselfloop : Boolean from Standard = Standard_True) returns Boolean from Standard; ---Level: Public IsLeaf (me; V : Vertex; ignoreselfloop : Boolean from Standard = Standard_True) returns Boolean from Standard; ---Level: Public Add (me : in out; value : GraphDS_Item) ---Purpose: Creates a vertex, with a given Item , and -- Adds it to . Of course this new Vertex -- (returned by the method) is a "root" and "leaf" -- vertex of . ---Level: Public returns mutable Vertex; Remove (me : in out; V : Vertex) ---Purpose: Removes from . is raised -- if is not member of . is -- raised if is used by at least one edge of ---Level: Public raises NoSuchObject from Standard, DomainError from Standard; Add (me : in out; source : mutable Vertex; destination : mutable Vertex; value : GraphDS_Attribute) ---Purpose: Creates an Edge, with a given Attribute , -- from to , and Adds it to -- . This new edge is returned by the method. -- is raised if and/or -- are not members of . ---Level: Public returns mutable Edge raises NoSuchObject from Standard; Remove (me : in out; E : Edge) ---Purpose: Removes from . is raised if -- is not member of . ---Level: Public raises NoSuchObject from Standard; fields myVertices : MapOfTransient from TColStd; myEdges : MapOfTransient from TColStd; friends class VerticesIterator from GraphDS, class EdgesIterator from GraphDS end;