1----------------------------------------------------------------------- 2-- GtkAda - Ada95 binding for Gtk+/Gnome -- 3-- -- 4-- Copyright (C) 2001-2005 AdaCore -- 5-- -- 6-- This library is free software; you can redistribute it and/or -- 7-- modify it under the terms of the GNU General Public -- 8-- License as published by the Free Software Foundation; either -- 9-- version 2 of the License, or (at your option) any later version. -- 10-- -- 11-- This library is distributed in the hope that it will be useful, -- 12-- but WITHOUT ANY WARRANTY; without even the implied warranty of -- 13-- MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU -- 14-- General Public License for more details. -- 15-- -- 16-- You should have received a copy of the GNU General Public -- 17-- License along with this library; if not, write to the -- 18-- Free Software Foundation, Inc., 59 Temple Place - Suite 330, -- 19-- Boston, MA 02111-1307, USA. -- 20-- -- 21-- As a special exception, if other files instantiate generics from -- 22-- this unit, or you link this unit with other files to produce an -- 23-- executable, this unit does not by itself cause the resulting -- 24-- executable to be covered by the GNU General Public License. This -- 25-- exception does not however invalidate any other reasons why the -- 26-- executable file might be covered by the GNU Public License. -- 27----------------------------------------------------------------------- 28 29-- <description> 30-- General implementation for a graph. 31-- This provides a representation for a graph structure, with nodes (vertices) 32-- connected by links (edges). 33-- It is not intended for huges, highly-connected graphs, since there are 34-- several lists provided for efficient access to ancestor and children nodes. 35-- </description> 36-- <group>Glib, the general-purpose library</group> 37 38package Glib.Graphs is 39 40 type Graph is private; 41 type Vertex is abstract tagged private; 42 type Edge is abstract tagged private; 43 44 type Vertex_Access is access all Vertex'Class; 45 type Edge_Access is access all Edge'Class; 46 -- General access types to vertices and edges 47 48 type Vertex_Iterator is private; 49 type Edge_Iterator is private; 50 -- Iterators other the vertices and edges of the graph 51 52 Null_Vertex_Iterator : constant Vertex_Iterator; 53 Null_Edge_Iterator : constant Edge_Iterator; 54 55 type Vertices_Array is array (Natural range <>) of Vertex_Access; 56 type Edges_Array is array (Natural range <>) of Edge_Access; 57 58 ----------------------- 59 -- Modifying a graph -- 60 ----------------------- 61 62 procedure Set_Directed (G : in out Graph; Directed : Boolean); 63 -- Indicate whether the graph is oriented. 64 65 function Is_Directed (G : Graph) return Boolean; 66 -- Return True if the graph is oriented 67 68 procedure Add_Vertex (G : in out Graph; V : access Vertex'Class); 69 -- Add a new vertex to the graph. 70 71 procedure Add_Edge 72 (G : in out Graph; 73 E : access Edge'Class; 74 Source, Dest : access Vertex'Class); 75 -- Add a new edge to the graph. 76 77 procedure Destroy (E : in out Edge) is abstract; 78 -- Destroy the memory occupied by the edge. This doesn't remove the edge 79 -- from the graph. You should override this subprogram for the specific 80 -- edge type you are using. 81 -- This subprogram shouldn't (and in fact can't) free E itself. 82 83 procedure Destroy (V : in out Vertex) is abstract; 84 -- Destroy the memory occupied by the vertex. This doesn't remove the 85 -- vertex from the graph. This subprogram must be overriden. 86 -- This subprogram shouldn't (and in fact can't) free V itself. 87 88 procedure Destroy (G : in out Graph); 89 -- Destroy all the nodes and edges of the graph, and then free the memory 90 -- occupied by the graph itself 91 92 procedure Clear (G : in out Graph); 93 -- Remove all the nodes and edges of the graph. 94 95 procedure Remove (G : in out Graph; E : access Edge'Class); 96 -- Remove the edge from the graph. The primitive 97 -- subprogram Destroy is called for the edge. 98 -- Any iterator currently pointing to E becomes invalid 99 100 procedure Remove (G : in out Graph; V : access Vertex'Class); 101 -- Remove the vertex from the graph. 102 -- Destroy is called for the vertex. 103 -- Note that all the edges to or from the vertex are destroyed (see 104 -- Remove above). 105 -- Any iterator currently pointing to V becomes invalid 106 107 function Is_Acyclic (G : Graph) return Boolean; 108 -- Return True if G contains no cycle. Note that this requires a 109 -- depth-first search, the running time is thus 110 -- O (edges + vertices). 111 -- G must be oriented 112 113 function Get_Src (E : access Edge) return Vertex_Access; 114 function Get_Dest (E : access Edge) return Vertex_Access; 115 -- Return the source and destination for a given edge 116 117 function In_Degree (G : Graph; V : access Vertex'Class) return Natural; 118 function Out_Degree (G : Graph; V : access Vertex'Class) return Natural; 119 -- Return the number of edges ending on V, or starting from V. 120 121 procedure Move_To_Front (G : in out Graph; V : access Vertex'Class); 122 -- Move V to the front of the list of vertices in the graph, so that the 123 -- iterators will return this item first. 124 -- All iterators become obsolete. 125 126 procedure Move_To_Back (G : in out Graph; V : access Vertex'Class); 127 -- Move V to the back of the list of vertices in the graph, so that the 128 -- iterators will return this item last. 129 -- All iterators become obsolete. 130 131 function Get_Index (V : access Vertex) return Natural; 132 -- Return the uniq index associated with the vertex. Each vertex has a 133 -- different index from 0 to Max_Index (Graph) 134 135 function Max_Index (G : Graph) return Natural; 136 -- Return the maximum index used for vertices in the graph. 137 138 -------------------------- 139 -- Breadth First Search -- 140 -------------------------- 141 -- This search algorithm traverse the tree layer after layer (first the 142 -- nodes closer to the specified root, then the grand-children of this 143 -- root, and so on). 144 145 type Breadth_Record is record 146 Vertex : Vertex_Access; 147 Distance : Natural; 148 Predecessor : Vertex_Access; 149 end record; 150 -- Distance is the shortest distance from the root of the breadth-first 151 -- search to Vertex. The graph is considered as unweighted. Thus, Distance 152 -- is 1 for direct children of Root, 2 for grand-children,... 153 -- Predecessor is the parent of Vertex used when computing the distance. 154 155 type Breadth_Vertices_Array is array (Natural range <>) of Breadth_Record; 156 157 function Breadth_First_Search (G : Graph; Root : access Vertex'Class) 158 return Breadth_Vertices_Array; 159 -- Traverse the tree Breadth_First, and sort the nodes accordingly. 160 -- The returned list is sorted so that all nodes at a distance k from Root 161 -- are found before the nodes at a distance (k+1). 162 -- The running time is O(vertices + edges). 163 164 ------------------------ 165 -- Depth First Search -- 166 ------------------------ 167 -- This algorithm traverse the tree in depth, ie all the descendents of the 168 -- first child are found before the second child. 169 -- This algorithm has several properties: it can indicate whether the graph 170 -- is cyclic. Moreover, the subgraph formed by all the nodes and the edges 171 -- between a vertex and its predecessor (see the structure Depth_Record) is 172 -- a tree. 173 -- If the graph is acyclic, then the resulting array is sorted 174 -- topologically: if G contains an edge (u, v), then u appears before v. 175 -- 176 -- The running time for this algorithm is O(vertices + edges) 177 178 type Depth_Record is record 179 Vertex : Vertex_Access; 180 First_Discovered, End_Search : Natural; 181 Predecessor : Vertex_Access; 182 end record; 183 -- First_Discovered and End_Search are the two timestamps computed during 184 -- the search. The former is the time Vertex was first discovered. The 185 -- latter is the time when all the children of vertex were fully 186 -- processed. 187 -- Predecessor is the parent of Vertex. 188 189 type Depth_Vertices_Array is array (Natural range <>) of Depth_Record; 190 191 type Reverse_Edge_Callback is access 192 procedure (G : Graph; Edge : Edge_Access); 193 -- Callback called when the two ends of the edge should be reverted, so as 194 -- to make the graph acyclick 195 196 procedure Revert_Edge (G : Graph; E : Edge_Access); 197 -- Revert the two ends of Edge. This is meant to be used as a callback for 198 -- Depth_First_Search so as to make the graph acyclic. 199 200 function Depth_First_Search (G : Graph) return Depth_Vertices_Array; 201 -- Traverse the tree Depth_First. 202 203 function Depth_First_Search 204 (G : Graph; 205 Acyclic : access Boolean; 206 Reverse_Edge_Cb : Reverse_Edge_Callback := null) 207 return Depth_Vertices_Array; 208 -- Same as above, but Acyclic is also modified to indicate whether G is 209 -- acyclic. 210 -- If Reverse_Edge_Cb is not null, then it is called to reverse the ends of 211 -- selected edges, so that the final graph is acyclic. Note that you *must* 212 -- revert the ends, or there will be an infinite loop. You might also want 213 -- to mark the edge as reverted somehow, so as to draw the arrows on the 214 -- correct side, if your application is graphical. 215 -- 216 -- If Reverse_Edge_Cb is null, no edge is reverted, and the graph is 217 -- unmodified. 218 219 ----------------------------------- 220 -- Strongly connected components -- 221 ----------------------------------- 222 -- Strongly connected components in a directed graph are the maximal set of 223 -- vertices such that for every pair {u, v} of vertices in the set, there 224 -- exist a path from u to v and a path from v to u. 225 -- Two vertices are in different strongly connected components if there 226 -- exist at most one of these paths. 227 228 type Connected_Component; 229 type Connected_Component_List is access Connected_Component; 230 type Connected_Component (Num_Vertices : Natural) is record 231 Vertices : Vertices_Array (1 .. Num_Vertices); 232 Next : Connected_Component_List; 233 end record; 234 235 procedure Free (List : in out Connected_Component_List); 236 -- Free the list of strongly connected components 237 238 function Strongly_Connected_Components (G : Graph) 239 return Connected_Component_List; 240 -- Return the list of strongly connected components. 241 -- This is a linear time algorithm O(vertices + edges). 242 243 function Strongly_Connected_Components 244 (G : Graph; DFS : Depth_Vertices_Array) 245 return Connected_Component_List; 246 -- Same as above, but a depth-first search has already been run on G, and 247 -- we reuse the result. This is of course more efficient than the previous 248 -- function. 249 250 ---------------------------- 251 -- Minimum spanning trees -- 252 ---------------------------- 253 -- A minimum spanning tree is a subset of the edges of G that forms a 254 -- tree (acyclic) and connects all the vertices of G. 255 -- Note that the number of edges in the resulting tree is always 256 -- (number of vertices of G) - 1 257 258 function Kruskal (G : Graph) return Edges_Array; 259 -- Return a minimum spanning tree of G using Kruskal's algorithm. 260 -- This algorithm runs in O(E * log E), with E = number of edges. 261 262 --------------------- 263 -- Vertex iterator -- 264 --------------------- 265 266 function First (G : Graph) return Vertex_Iterator; 267 -- Return a pointer to the first vertex. 268 269 procedure Next (V : in out Vertex_Iterator); 270 -- Moves V to the next vertex in the graph. 271 272 function At_End (V : Vertex_Iterator) return Boolean; 273 -- Return True if V points after the last vertex 274 275 function Get (V : Vertex_Iterator) return Vertex_Access; 276 -- Get the vertex pointed to by V 277 278 ------------------- 279 -- Edge iterator -- 280 ------------------- 281 282 function First 283 (G : Graph; 284 Src, Dest : Vertex_Access := null; 285 Directed : Boolean := True) 286 return Edge_Iterator; 287 -- Return a pointer to the first edge from Src to Dest. 288 -- If either Src or Dest is null, then any vertex matches. Thus, if both 289 -- parameters are nulll, this iterator will traverse the whole graph. 290 -- Note: there might be duplicates returned by this iterator, especially 291 -- when the graph is not oriented. 292 -- Directed can be used to temporarily overrides the setting in the graph: 293 -- If Directed is True, the setting of G is taken into account. 294 -- If Directed is False, the setting of G is ignored, and the graph is 295 -- considered as not directed. 296 297 procedure Next (E : in out Edge_Iterator); 298 -- Moves V to the next edge in the graph. 299 300 function At_End (E : Edge_Iterator) return Boolean; 301 -- Return True if V points after the last edge 302 303 function Get (E : Edge_Iterator) return Edge_Access; 304 -- Get the edge pointed to by E. 305 306 function Repeat_Count (E : Edge_Iterator) return Positive; 307 -- Return the number of similar edges (same ends) that were found before, 308 -- and including this one). 309 -- For instance, if there two edges from A to B, then the first one will 310 -- have a Repeat_Count of 1, and the second 2. 311 312private 313 314 -- Note: we do not use a generic list, since that would require a separate 315 -- package so that we can instanciate it in this package. Doesn't seem 316 -- worth adding this to GtkAda. Nor does it seem interesting to use 317 -- Glib.Glist. 318 319 type Edge_List_Record; 320 type Edge_List is access Edge_List_Record; 321 type Edge_List_Record is record 322 E : Edge_Access; 323 Next : Edge_List; 324 end record; 325 326 procedure Add (List : in out Edge_List; E : access Edge'Class); 327 -- Add a new element to List. 328 -- Edges are inserted in the list so that edges with similar ends are next 329 -- to each other. 330 331 procedure Remove (List : in out Edge_List; E : access Edge'Class); 332 -- Remove an element from List 333 334 function Length (List : Edge_List) return Natural; 335 -- Return the number of elements in the list 336 337 type Vertex_List_Record; 338 type Vertex_List is access Vertex_List_Record; 339 type Vertex_List_Record is record 340 V : Vertex_Access; 341 Next : Vertex_List; 342 end record; 343 344 type Graph is record 345 Vertices : Vertex_List; 346 Num_Vertices : Natural := 0; 347 Directed : Boolean := False; 348 Last_Vertex_Index : Natural := 0; 349 end record; 350 351 procedure Add (List : in out Vertex_List; V : access Vertex'Class); 352 procedure Internal_Remove (G : in out Graph; V : access Vertex'Class); 353 354 type Edge is abstract tagged record 355 Src, Dest : Vertex_Access; 356 end record; 357 358 type Vertex is abstract tagged record 359 Index : Natural; -- Internal unique index for the vertex 360 In_Edges, Out_Edges : Edge_List; 361 end record; 362 363 type Vertex_Iterator is new Vertex_List; 364 type Edge_Iterator is record 365 Directed : Boolean; 366 Src, Dest : Vertex_Access; 367 Current_Edge : Edge_List; 368 Current_Vertex : Vertex_List; 369 First_Pass : Boolean; 370 Repeat_Count : Positive := 1; 371 end record; 372 373 Null_Vertex_Iterator : constant Vertex_Iterator := null; 374 Null_Edge_Iterator : constant Edge_Iterator := 375 (Directed => False, 376 Src => null, 377 Dest => null, 378 Current_Edge => null, 379 Current_Vertex => null, 380 First_Pass => True, 381 Repeat_Count => 1); 382 383 pragma Inline (Get_Index); 384 pragma Inline (Max_Index); 385end Glib.Graphs; 386