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