1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 100 101 102 103 104 105 106 107 108 109 110 111 112 113 114 115 116 117 118 119 120 121 122 123 124 125 126 127 128 129 130 131 132 133 134 135 136 137 138 139 140 141 142 143 144 145 146 147 148 149 150 151 152 153 154 155 156 157 158 159 160 161 162 163 164 165 166 167 168 169 170 171 172 173 174 175 176 177 178 179 180 181 182 183 184 185 186 187 188 189 190 191 192 193 194 195 196 197 198 199 200 201 202 203 204 205 206 207 208 209 210 211 212 213 214 215 216 217 218 219 220 221 222 223 224 225 226 227 228 229 230 231 232 233 234 235 236 237 238 239 240 241 242 243 244 245 246 247 248 249 250 251 252 253 254 255 256 257 258 259 260 261 262 263 264 265 266 267 268 269 270 271 272 273 274 275 276 277 278 279 280 281 282 283 284 285 286 287 288 289 290 291 292 293 294 295 296 297 298 299 300 301 302 303 304 305 306 307 308 309 310 311 312 313 314 315 316 317 318 319 320 321 322 323 324 325 326 327 328 329 330 331 332 333 334 335 336 337 338 339 340 341 342 343 344 345 346 347 348 349 350 351 352 353 354 355 356 357 358 359 360 361 362 363 364 365 366 367 368 369 370 371 372 373 374 375 376 377 378 379


 GtkAda  Ada95 binding for Gtk+/Gnome 
 
 Copyright (C) 20012005 AdaCore 
 
 This library is free software; you can redistribute it and/or 
 modify it under the terms of the GNU General Public 
 License as published by the Free Software Foundation; either 
 version 2 of the License, or (at your option) any later version. 
 
 This library 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 along with this library; if not, write to the 
 Free Software Foundation, Inc., 59 Temple Place  Suite 330, 
 Boston, MA 021111307, USA. 
 

 <description>
 General implementation for a graph.
 This provides a representation for a graph structure, with nodes (vertices)
 connected by links (edges).
 It is not intended for huges, highlyconnected graphs, since there are
 several lists provided for efficient access to ancestor and children nodes.
 </description>
 <group>Glib, the generalpurpose library</group>
package Glib.Graphs is
type Graph is private;
type Vertex is abstract tagged private;
type Edge is abstract tagged private;
type Vertex_Access is access all Vertex'Class;
type Edge_Access is access all Edge'Class;
 General access types to vertices and edges
type Vertex_Iterator is private;
type Edge_Iterator is private;
 Iterators other the vertices and edges of the graph
Null_Vertex_Iterator : constant Vertex_Iterator;
Null_Edge_Iterator : constant Edge_Iterator;
type Vertices_Array is array (Natural range <>) of Vertex_Access;
type Edges_Array is array (Natural range <>) of Edge_Access;

 Modifying a graph 

procedure Set_Directed (G : in out Graph; Directed : Boolean);
 Indicate whether the graph is oriented.
function Is_Directed (G : Graph) return Boolean;
 Return True if the graph is oriented
procedure Add_Vertex (G : in out Graph; V : access Vertex'Class);
 Add a new vertex to the graph.
procedure Add_Edge
(G : in out Graph;
E : access Edge'Class;
Source, Dest : access Vertex'Class);
 Add a new edge to the graph.
procedure Destroy (E : in out Edge) is abstract;
 Destroy the memory occupied by the edge. This doesn't remove the edge
 from the graph. You should override this subprogram for the specific
 edge type you are using.
 This subprogram shouldn't (and in fact can't) free E itself.
procedure Destroy (V : in out Vertex) is abstract;
 Destroy the memory occupied by the vertex. This doesn't remove the
 vertex from the graph. This subprogram must be overriden.
 This subprogram shouldn't (and in fact can't) free V itself.
procedure Destroy (G : in out Graph);
 Destroy all the nodes and edges of the graph, and then free the memory
 occupied by the graph itself
procedure Clear (G : in out Graph);
 Remove all the nodes and edges of the graph.
procedure Remove (G : in out Graph; E : access Edge'Class);
 Remove the edge from the graph. The primitive
 subprogram Destroy is called for the edge.
 Any iterator currently pointing to E becomes invalid
procedure Remove (G : in out Graph; V : access Vertex'Class);
 Remove the vertex from the graph.
 Destroy is called for the vertex.
 Note that all the edges to or from the vertex are destroyed (see
 Remove above).
 Any iterator currently pointing to V becomes invalid
function Is_Acyclic (G : Graph) return Boolean;
 Return True if G contains no cycle. Note that this requires a
 depthfirst search, the running time is thus
 O (edges + vertices).
 G must be oriented
function Get_Src (E : access Edge) return Vertex_Access;
function Get_Dest (E : access Edge) return Vertex_Access;
 Return the source and destination for a given edge
function In_Degree (G : Graph; V : access Vertex'Class) return Natural;
function Out_Degree (G : Graph; V : access Vertex'Class) return Natural;
 Return the number of edges ending on V, or starting from V.
procedure Move_To_Front (G : in out Graph; V : access Vertex'Class);
 Move V to the front of the list of vertices in the graph, so that the
 iterators will return this item first.
 All iterators become obsolete.
procedure Move_To_Back (G : in out Graph; V : access Vertex'Class);
 Move V to the back of the list of vertices in the graph, so that the
 iterators will return this item last.
 All iterators become obsolete.
function Get_Index (V : access Vertex) return Natural;
 Return the uniq index associated with the vertex. Each vertex has a
 different index from 0 to Max_Index (Graph)
function Max_Index (G : Graph) return Natural;
 Return the maximum index used for vertices in the graph.

 Breadth First Search 

 This search algorithm traverse the tree layer after layer (first the
 nodes closer to the specified root, then the grandchildren of this
 root, and so on).
type Breadth_Record is record
Vertex : Vertex_Access;
Distance : Natural;
Predecessor : Vertex_Access;
end record;
 Distance is the shortest distance from the root of the breadthfirst
 search to Vertex. The graph is considered as unweighted. Thus, Distance
 is 1 for direct children of Root, 2 for grandchildren,...
 Predecessor is the parent of Vertex used when computing the distance.
type Breadth_Vertices_Array is array (Natural range <>) of Breadth_Record;
function Breadth_First_Search (G : Graph; Root : access Vertex'Class)
return Breadth_Vertices_Array;
 Traverse the tree Breadth_First, and sort the nodes accordingly.
 The returned list is sorted so that all nodes at a distance k from Root
 are found before the nodes at a distance (k+1).
 The running time is O(vertices + edges).

 Depth First Search 

 This algorithm traverse the tree in depth, ie all the descendents of the
 first child are found before the second child.
 This algorithm has several properties: it can indicate whether the graph
 is cyclic. Moreover, the subgraph formed by all the nodes and the edges
 between a vertex and its predecessor (see the structure Depth_Record) is
 a tree.
 If the graph is acyclic, then the resulting array is sorted
 topologically: if G contains an edge (u, v), then u appears before v.

 The running time for this algorithm is O(vertices + edges)
type Depth_Record is record
Vertex : Vertex_Access;
First_Discovered, End_Search : Natural;
Predecessor : Vertex_Access;
end record;
 First_Discovered and End_Search are the two timestamps computed during
 the search. The former is the time Vertex was first discovered. The
 latter is the time when all the children of vertex were fully
 processed.
 Predecessor is the parent of Vertex.
type Depth_Vertices_Array is array (Natural range <>) of Depth_Record;
type Reverse_Edge_Callback is access
procedure (G : Graph; Edge : Edge_Access);
 Callback called when the two ends of the edge should be reverted, so as
 to make the graph acyclick
procedure Revert_Edge (G : Graph; E : Edge_Access);
 Revert the two ends of Edge. This is meant to be used as a callback for
 Depth_First_Search so as to make the graph acyclic.
function Depth_First_Search (G : Graph) return Depth_Vertices_Array;
 Traverse the tree Depth_First.
function Depth_First_Search
(G : Graph;
Acyclic : access Boolean;
Reverse_Edge_Cb : Reverse_Edge_Callback := null)
return Depth_Vertices_Array;
 Same as above, but Acyclic is also modified to indicate whether G is
 acyclic.
 If Reverse_Edge_Cb is not null, then it is called to reverse the ends of
 selected edges, so that the final graph is acyclic. Note that you *must*
 revert the ends, or there will be an infinite loop. You might also want
 to mark the edge as reverted somehow, so as to draw the arrows on the
 correct side, if your application is graphical.

 If Reverse_Edge_Cb is null, no edge is reverted, and the graph is
 unmodified.

 Strongly connected components 

 Strongly connected components in a directed graph are the maximal set of
 vertices such that for every pair {u, v} of vertices in the set, there
 exist a path from u to v and a path from v to u.
 Two vertices are in different strongly connected components if there
 exist at most one of these paths.
type Connected_Component;
type Connected_Component_List is access Connected_Component;
type Connected_Component (Num_Vertices : Natural) is record
Vertices : Vertices_Array (1 .. Num_Vertices);
Next : Connected_Component_List;
end record;
procedure Free (List : in out Connected_Component_List);
 Free the list of strongly connected components
function Strongly_Connected_Components (G : Graph)
return Connected_Component_List;
 Return the list of strongly connected components.
 This is a linear time algorithm O(vertices + edges).
function Strongly_Connected_Components
(G : Graph; DFS : Depth_Vertices_Array)
return Connected_Component_List;
 Same as above, but a depthfirst search has already been run on G, and
 we reuse the result. This is of course more efficient than the previous
 function.

 Minimum spanning trees 

 A minimum spanning tree is a subset of the edges of G that forms a
 tree (acyclic) and connects all the vertices of G.
 Note that the number of edges in the resulting tree is always
 (number of vertices of G)  1
function Kruskal (G : Graph) return Edges_Array;
 Return a minimum spanning tree of G using Kruskal's algorithm.
 This algorithm runs in O(E * log E), with E = number of edges.

 Vertex iterator 

function First (G : Graph) return Vertex_Iterator;
 Return a pointer to the first vertex.
procedure Next (V : in out Vertex_Iterator);
 Moves V to the next vertex in the graph.
function At_End (V : Vertex_Iterator) return Boolean;
 Return True if V points after the last vertex
function Get (V : Vertex_Iterator) return Vertex_Access;
 Get the vertex pointed to by V

 Edge iterator 

function First
(G : Graph;
Src, Dest : Vertex_Access := null;
Directed : Boolean := True)
return Edge_Iterator;
 Return a pointer to the first edge from Src to Dest.
 If either Src or Dest is null, then any vertex matches. Thus, if both
 parameters are nulll, this iterator will traverse the whole graph.
 Note: there might be duplicates returned by this iterator, especially
 when the graph is not oriented.
 Directed can be used to temporarily overrides the setting in the graph:
 If Directed is True, the setting of G is taken into account.
 If Directed is False, the setting of G is ignored, and the graph is
 considered as not directed.
procedure Next (E : in out Edge_Iterator);
 Moves V to the next edge in the graph.
function At_End (E : Edge_Iterator) return Boolean;
 Return True if V points after the last edge
function Get (E : Edge_Iterator) return Edge_Access;
 Get the edge pointed to by E.
function Repeat_Count (E : Edge_Iterator) return Positive;
 Return the number of similar edges (same ends) that were found before,
 and including this one).
 For instance, if there two edges from A to B, then the first one will
 have a Repeat_Count of 1, and the second 2.
private
 Note: we do not use a generic list, since that would require a separate
 package so that we can instanciate it in this package. Doesn't seem
 worth adding this to GtkAda. Nor does it seem interesting to use
 Glib.Glist.
type Edge_List_Record;
type Edge_List is access Edge_List_Record;
type Edge_List_Record is record
E : Edge_Access;
Next : Edge_List;
end record;
procedure Add (List : in out Edge_List; E : access Edge'Class);
 Add a new element to List.
 Edges are inserted in the list so that edges with similar ends are next
 to each other.
procedure Remove (List : in out Edge_List; E : access Edge'Class);
 Remove an element from List
function Length (List : Edge_List) return Natural;
 Return the number of elements in the list
type Vertex_List_Record;
type Vertex_List is access Vertex_List_Record;
type Vertex_List_Record is record
V : Vertex_Access;
Next : Vertex_List;
end record;
type Graph is record
Vertices : Vertex_List;
Num_Vertices : Natural := 0;
Directed : Boolean := False;
Last_Vertex_Index : Natural := 0;
end record;
procedure Add (List : in out Vertex_List; V : access Vertex'Class);
procedure Internal_Remove (G : in out Graph; V : access Vertex'Class);
type Edge is abstract tagged record
Src, Dest : Vertex_Access;
end record;
type Vertex is abstract tagged record
Index : Natural;  Internal unique index for the vertex
In_Edges, Out_Edges : Edge_List;
end record;
type Vertex_Iterator is new Vertex_List;
type Edge_Iterator is record
Directed : Boolean;
Src, Dest : Vertex_Access;
Current_Edge : Edge_List;
Current_Vertex : Vertex_List;
First_Pass : Boolean;
Repeat_Count : Positive := 1;
end record;
Null_Vertex_Iterator : constant Vertex_Iterator := null;
Null_Edge_Iterator : constant Edge_Iterator :=
(Directed => False,
Src => null,
Dest => null,
Current_Edge => null,
Current_Vertex => null,
First_Pass => True,
Repeat_Count => 1);
pragma Inline (Get_Index);
pragma Inline (Max_Index);
end Glib.Graphs;
