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.  
  38. package 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.  
  312. private 
  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); 
  385. end Glib.Graphs;