-- Copyright 1994 Grady Booch
-- Copyright 1998-2002 Simon Wright <simon@pushface.org>
-- This package is free software; you can redistribute it and/or
-- modify it under terms of the GNU General Public License as
-- published by the Free Software Foundation; either version 2, or
-- (at your option) any later version. This package is distributed in
-- the hope that it will be useful, but WITHOUT ANY WARRANTY; without
-- even the implied warranty of MERCHANTABILITY or FITNESS FOR A
-- PARTICULAR PURPOSE. See the GNU General Public License for more
-- details. You should have received a copy of the GNU General Public
-- License distributed with this package; see file COPYING. If not,
-- write to the Free Software Foundation, 59 Temple Place - Suite
-- 330, Boston, MA 02111-1307, USA.
-- As a special exception, if other files instantiate generics from
-- this unit, or you link this unit with other files to produce an
-- executable, this unit does not by itself cause the resulting
-- executable to be covered by the GNU General Public License. This
-- exception does not however invalidate any other reasons why the
-- executable file might be covered by the GNU Public License.
-- $RCSfile: bc-graphs.ads,v $
-- $Revision: 1.16.2.1 $
-- $Date: 2002/12/29 16:42:23 $
-- $Author: simon $
with Ada.Finalization;
with System.Storage_Pools;
generic
type Vertex_Item is private;
with function "=" (L, R : Vertex_Item) return Boolean is <>;
type Arc_Item is private;
with function "=" (L, R : Arc_Item) return Boolean is <>;
Storage : in out System.Storage_Pools.Root_Storage_Pool'Class;
package BC.Graphs is
pragma Elaborate_Body;
-- A directed graph is an unrooted collection of vertices and
-- directed arcs where cycles and cross-references are not
-- permitted. An undirected graph is an unrooted collection of
-- vertices and undirected arcs where cycles and cross-references
-- are permitted. Three types collaborate to form the abstraction
-- of a directed and undirected graph: a graph type, a vertex
-- type, and an arc type.
-- Directed and undirected graphs are monolithic structures
-- although copying, assignment, and equality are
-- prohibited. Their vertices and arcs are polylithic structures,
-- and hence the semantics of copying, assignment, and equality
-- involve structural sharing. Care must be taken in manipulating
-- the same vertex or arc named by more than one alias.
-- These classes are not intended to be subclassed.
-- These abstractions have been carefully constructed to eliminate
-- all storage leaks, except in the case of intentional
-- abuses. When a graph is manipulated, all items that become
-- unreachable are automatically reclaimed. Furthermore, this
-- design protects against dangling references: an item is never
-- reclaimed if there exists a reference to it.
-- Each vertex and arc is a member of exactly one graph;
-- furthermore, the vertices at both ends of an arc are guaranteed
-- to be members of the same graph as the arc. This guarantee is
-- provided by an implementation strategy whereby every graph is
-- given a unique identity, and each vertex and arc is created
-- only in the context of a particular graph.
-- Note that objects of type Vertex, Arc are handles or references
-- to the actual Graph components.
-- Note that Containers contain just one sort of Item; Graphs
-- aren't therefore Containers.
type Abstract_Graph
is abstract new Ada.Finalization.Limited_Controlled with private;
type Graph_Ptr is access all Abstract_Graph'Class;
type Abstract_Vertex
is abstract new Ada.Finalization.Controlled with private;
type Abstract_Arc is abstract new Ada.Finalization.Controlled with private;
----------------------
-- Graph operations --
----------------------
procedure Clear (G : in out Abstract_Graph);
-- Destroy all the vertices in the graph, and by implication, all
-- the arcs in the graph. The semantics of destroy are such that
-- any aliased vertices and arcs are not eliminated from the
-- graph, because to do so would introduce dangling references.
procedure Create_Vertex (G : in out Abstract_Graph;
V : in out Abstract_Vertex'Class;
I : Vertex_Item);
-- Create a new vertex and add it to the graph, setting the second
-- argument of this function as an alias to this new vertex.
-- Arc creation is provided in concrete derivations.
procedure Destroy_Vertex (G : in out Abstract_Graph;
V : in out Abstract_Vertex'Class);
-- Destroy the given vertex and any associated arcs. If the vertex
-- has no other aliases, eliminate it from the graph.
procedure Destroy_Arc (G : in out Abstract_Graph;
A : in out Abstract_Arc'Class);
-- Destroy the given arc. If the arc has no other aliases,
-- eliminate it from the graph.
function Number_Of_Vertices (G : Abstract_Graph) return Natural;
-- Return the number of vertices in the graph.
function Is_Empty (G : Abstract_Graph) return Boolean;
-- Return True if and only if the graph does not contain any
-- vertices or arcs.
function Is_Member (G : Abstract_Graph;
V : Abstract_Vertex'Class) return Boolean;
-- Return True if and only if the given vertex is not null and
-- denotes a vertex in the graph.
function Is_Member (G : Abstract_Graph;
A : Abstract_Arc'Class) return Boolean;
-- Return True if and only if the given arc is not null and
-- denotes an arc in the graph.
-----------------------
-- Vertex operations --
-----------------------
function "=" (L, R : Abstract_Vertex) return Boolean;
-- Return True if and only if both vertices are null or are an
-- alias to the same vertex.
procedure Clear (V : in out Abstract_Vertex);
-- If the vertex is not null, remove this alias.
procedure Set_Item (V : in out Abstract_Vertex; I : Vertex_Item);
-- Set the item of the given vertex.
function Is_Null (V : Abstract_Vertex) return Boolean;
-- Return True if and only if the vertex is null.
function Is_Shared (V : Abstract_Vertex) return Boolean;
-- Return True if and only if the vertex has other aliases.
function Item (V : Abstract_Vertex) return Vertex_Item;
-- Return the item associated with the vertex.
generic
with procedure Process (I : in out Vertex_Item);
procedure Access_Vertex_Item (V : Abstract_Vertex'Class);
-- Process has read-write access to the item associated with the
-- vertex.
function Enclosing_Graph (V : Abstract_Vertex) return Graph_Ptr;
-- Return the graph enclosing the vertex.
--------------------
-- Arc operations --
--------------------
function "=" (L, R : Abstract_Arc) return Boolean;
-- Return True if and only if both arcs are null or are an alias
-- to the same arc.
procedure Clear (A : in out Abstract_Arc);
-- If the arc is not null, remove this alias.
procedure Set_Item (A : in out Abstract_Arc; I : Arc_Item);
-- Set the item of the given arc.
function Is_Null (A : Abstract_Arc) return Boolean;
-- Return 1 if and only if the arc is null.
function Is_Shared (A : Abstract_Arc) return Boolean;
-- Return True if and only if the arc has other aliases.
function Item (A : Abstract_Arc) return Arc_Item;
-- Return the item associated with the arc.
generic
with procedure Process (I : in out Arc_Item);
procedure Access_Arc_Item (A : Abstract_Arc'Class);
-- Process has read-write access to the item associated with the arc.
function Enclosing_Graph (A : Abstract_Arc) return Graph_Ptr;
-- Return the graph enclosing the arc.
--------------------------------------------
-- Iteration over the Vertices in a Graph --
--------------------------------------------
-- Active iteration
type Graph_Iterator (<>) is abstract tagged private;
function New_Graph_Iterator (For_The_Graph : Abstract_Graph)
return Graph_Iterator'Class is abstract;
-- Return a reset Graph_Iterator bound to the specific Graph.
procedure Reset (Obj : in out Graph_Iterator) is abstract;
-- Reset the Graph_Iterator to the beginning.
procedure Next (Obj : in out Graph_Iterator) is abstract;
-- Advance the Graph_Iterator to the next Vertex in the Graph.
function Is_Done (Obj : Graph_Iterator) return Boolean is abstract;
-- Return True if there are no more Vertices in the Graph.
function Current_Vertex (Obj : Graph_Iterator) return Abstract_Vertex'Class
is abstract;
-- Return the current Vertex.
-- Passive iteration
generic
with procedure Apply (Elem : in Abstract_Vertex'Class; OK : out Boolean);
procedure Visit_Vertices (Using : in out Graph_Iterator'Class);
-- Call Apply with a handle on each Vertex in the Graph to which
-- the iterator Using is bound. The iteration will terminate early
-- if Apply sets OK to False.
---------------------------------------------------
-- Iteration over the Arcs connected to a Vertex --
---------------------------------------------------
-- Note, in the case of a Directed Graph, this iterator covers
-- both outgoing and incoming arcs. See BC.Graphs.Directed_Graphs
-- for separate iteration over either type of arc.
-- Active iteration
type Vertex_Iterator (<>) is abstract tagged private;
function New_Vertex_Iterator (For_The_Vertex : Abstract_Vertex)
return Vertex_Iterator'Class is abstract;
-- Return a reset Vertex_Iterator bound to the specific Vertex.
procedure Reset (Obj : in out Vertex_Iterator) is abstract;
-- Reset the Vertex_Iterator to the beginning.
procedure Next (Obj : in out Vertex_Iterator) is abstract;
-- Advance the Vertex_Iterator to the next Arc in the Vertex.
function Is_Done (Obj : Vertex_Iterator) return Boolean is abstract;
-- Return True if there are no more Arcs in the Vertex.
function Current_Arc
(Obj : Vertex_Iterator) return Abstract_Arc'Class is abstract;
-- Return the current Arc.
-- Passive iteration
generic
with procedure Apply (Elem : in Abstract_Arc'Class; OK : out Boolean);
procedure Visit_Arcs (Using : in out Vertex_Iterator'Class);
-- Call Apply with a handle on each Arc in the Vertex to which the
-- iterator Using is bound. The iteration will terminate early if
-- Apply sets OK to False.
private
type Vertex_Node;
type Vertex_Node_Ptr is access Vertex_Node;
for Vertex_Node_Ptr'Storage_Pool use Storage;
type Arc_Node;
type Arc_Node_Ptr is access Arc_Node;
for Arc_Node_Ptr'Storage_Pool use Storage;
-- A Vertex Node is a simple node consisting of an item, a pointer
-- to the enclosing graph, a pointer to the next vertex, pointers
-- to the outgoing and incoming arcs, and a reference count
-- XXX controlled only for check at finalization
type Vertex_Node is new Ada.Finalization.Controlled with record
Item : Vertex_Item;
Enclosing : Graph_Ptr;
Incoming : Arc_Node_Ptr;
Outgoing : Arc_Node_Ptr;
Next : Vertex_Node_Ptr;
Count : Natural;
end record;
procedure Clear_Vertex_Node (G : in out Abstract_Graph'Class;
N : in out Vertex_Node_Ptr);
procedure Finalize (V : in out Vertex_Node);
-- An Arc Node is a simple node consisting of an item, a pointer
-- to the enclosing graph, a pointer to the next arc, pointers to
-- the vertices to and from the arc, and a reference count
-- XXX controlled only for check at finalization
type Arc_Node is new Ada.Finalization.Controlled with record
Item : Arc_Item;
Enclosing : Graph_Ptr;
From : Vertex_Node_Ptr;
To : Vertex_Node_Ptr;
Next_Incoming : Arc_Node_Ptr;
Next_Outgoing : Arc_Node_Ptr;
Count : Natural;
end record;
procedure Finalize (A : in out Arc_Node);
type Abstract_Graph
is abstract new Ada.Finalization.Limited_Controlled with record
Rep : Vertex_Node_Ptr;
end record;
procedure Finalize (G : in out Abstract_Graph);
type Abstract_Vertex is abstract new Ada.Finalization.Controlled with record
Rep : Vertex_Node_Ptr;
end record;
procedure Adjust (V : in out Abstract_Vertex);
procedure Finalize (V : in out Abstract_Vertex);
type Abstract_Arc is abstract new Ada.Finalization.Controlled with record
Rep : Arc_Node_Ptr;
end record;
procedure Adjust (A : in out Abstract_Arc);
procedure Finalize (A : in out Abstract_Arc);
-- Iteration
type Graph_Iterator is abstract tagged record
For_The_Graph : Graph_Ptr;
end record;
type Vertex_Ptr is access all Abstract_Vertex'Class;
type Vertex_Iterator is abstract tagged record
For_The_Vertex : Vertex_Ptr;
end record;
end BC.Graphs;
syntax highlighted by Code2HTML, v. 0.9.1