%--------------------------------------------------%
% vim: ft=mercury ts=4 sw=4 et
%--------------------------------------------------%
% Copyright (C) 1995-1999,2002-2007,2010-2012 The University of Melbourne.
% Copyright (C) 2014-2018, 2022-2025 The Mercury team.
% This file is distributed under the terms specified in COPYING.LIB.
%--------------------------------------------------%
%
% File: digraph.m
% Original authors: bromage, petdr
% Stability: high.
%
% This module defines a data type representing directed graphs. A directed
% graph of type digraph(T) is logically equivalent to a set of vertices of
% type T, and a set of edges of type pair(T). The endpoints of each edge
% must be included in the set of vertices. Cycles are allowed, including
% cycles consisting of only one edge (with both ends of the edge being
% the same node).
%
%--------------------------------------------------%
%--------------------------------------------------%
:- module digraph.
:- interface.
:- import_module assoc_list.
:- import_module enum.
:- import_module list.
:- import_module map.
:- import_module pair.
:- import_module set.
:- import_module sparse_bitset.
%--------------------------------------------------%
% The type of directed graphs with vertices in T.
%
:- type digraph(T).
% The abstract type that indexes vertices in a digraph.
% Each key is valid only with the digraph it was created from, and
% the predicates and functions in this module may throw an exception
% if their caller passes them an invalid key.
%
:- type digraph_key(T).
:- instance uenum(digraph_key(T)).
:- type digraph_key_set(T) == sparse_bitset(digraph_key(T)).
%--------------------------------------------------%
%
% Constructing digraphs.
%
% init creates an empty digraph.
%
:- func init = digraph(T).
:- pred init(digraph(T)::out) is det.
% add_vertex adds a vertex to the domain of a digraph.
% Returns the old key if one already exists for this vertex,
% otherwise it allocates a new key.
%
:- pred add_vertex(T::in, digraph_key(T)::out,
digraph(T)::in, digraph(T)::out) is det.
% add_edge adds an edge to the digraph if it doesn't already exist,
% and leaves the digraph unchanged otherwise.
%
:- func add_edge(digraph_key(T), digraph_key(T), digraph(T)) = digraph(T).
:- pred add_edge(digraph_key(T)::in, digraph_key(T)::in,
digraph(T)::in, digraph(T)::out) is det.
% add_vertices_and_edge adds a pair of vertices and an edge
% between them to the digraph.
%
% add_vertices_and_edge(X, Y, !G) :-
% add_vertex(X, XKey, !G),
% add_vertex(Y, YKey, !G),
% add_edge(XKey, YKey, !G).
%
:- func add_vertices_and_edge(T, T, digraph(T)) = digraph(T).
:- pred add_vertices_and_edge(T::in, T::in,
digraph(T)::in, digraph(T)::out) is det.
% As above, but takes a pair of vertices in a single argument.
%
:- func add_vertex_pair(pair(T), digraph(T)) = digraph(T).
:- pred add_vertex_pair(pair(T)::in, digraph(T)::in, digraph(T)::out) is det.
% add_assoc_list adds a list of edges to a digraph.
%
:- func add_assoc_list(assoc_list(digraph_key(T), digraph_key(T)),
digraph(T)) = digraph(T).
:- pred add_assoc_list(assoc_list(digraph_key(T), digraph_key(T))::in,
digraph(T)::in, digraph(T)::out) is det.
%--------------------------------------------------%
%
% Deleting from digraphs.
%
% delete_edge deletes an edge from the digraph if it exists,
% and leaves the digraph unchanged otherwise.
%
:- func delete_edge(digraph_key(T), digraph_key(T), digraph(T)) = digraph(T).
:- pred delete_edge(digraph_key(T)::in, digraph_key(T)::in,
digraph(T)::in, digraph(T)::out) is det.
% delete_assoc_list deletes a list of edges from a digraph.
%
:- func delete_assoc_list(assoc_list(digraph_key(T), digraph_key(T)),
digraph(T)) = digraph(T).
:- pred delete_assoc_list(
assoc_list(digraph_key(T), digraph_key(T))::in,
digraph(T)::in, digraph(T)::out) is det.
%--------------------------------------------------%
%
% Searches and lookups.
%
% search_key returns the key associated with a vertex.
% Fails if the vertex is not in the graph.
%
:- pred search_key(digraph(T)::in, T::in, digraph_key(T)::out) is semidet.
% lookup_key returns the key associated with a vertex.
% Throws an exception if the vertex is not in the graph.
%
:- func lookup_key(digraph(T), T) = digraph_key(T).
:- pred lookup_key(digraph(T)::in, T::in, digraph_key(T)::out) is det.
% lookup_vertex returns the vertex associated with a key.
%
:- func lookup_vertex(digraph(T), digraph_key(T)) = T.
:- pred lookup_vertex(digraph(T)::in, digraph_key(T)::in, T::out) is det.
% Given key x, lookup_from returns the set of keys y such that
% there is an edge (x,y) in the digraph.
%
:- func lookup_from(digraph(T), digraph_key(T)) = set(digraph_key(T)).
:- pred lookup_from(digraph(T)::in, digraph_key(T)::in,
set(digraph_key(T))::out) is det.
% As above, but returns a digraph_key_set.
%
:- func lookup_key_set_from(digraph(T), digraph_key(T)) = digraph_key_set(T).
:- pred lookup_key_set_from(digraph(T)::in, digraph_key(T)::in,
digraph_key_set(T)::out) is det.
% Given a key y, lookup_to returns the set of keys x such that
% there is an edge (x,y) in the digraph.
%
:- func lookup_to(digraph(T), digraph_key(T)) = set(digraph_key(T)).
:- pred lookup_to(digraph(T)::in, digraph_key(T)::in,
set(digraph_key(T))::out) is det.
% As above, but returns a digraph_key_set.
%
:- func lookup_key_set_to(digraph(T), digraph_key(T)) = digraph_key_set(T).
:- pred lookup_key_set_to(digraph(T)::in, digraph_key(T)::in,
digraph_key_set(T)::out) is det.
% is_edge checks to see if an edge is in the digraph.
%
:- pred is_edge(digraph(T), digraph_key(T), digraph_key(T)).
:- mode is_edge(in, in, out) is nondet.
:- mode is_edge(in, in, in) is semidet.
% is_edge_rev is equivalent to is_edge, except that
% the nondet mode works in the reverse direction.
%
:- pred is_edge_rev(digraph(T), digraph_key(T), digraph_key(T)).
:- mode is_edge_rev(in, out, in) is nondet.
:- mode is_edge_rev(in, in, in) is semidet.
% vertices returns the set of vertices in a digraph.
%
:- func vertices(digraph(T)) = set(T).
:- pred vertices(digraph(T)::in, set(T)::out) is det.
% is_dag(G) is true if-and-only-if G is a directed acyclic graph.
%
:- pred is_dag(digraph(T)::in) is semidet.
%--------------------------------------------------%
%
% Conversion between digraphs and assoc_lists.
%
% to_assoc_list turns a digraph into a list of pairs of vertices,
% one for each edge.
%
:- func to_assoc_list(digraph(T)) = assoc_list(T, T).
:- pred to_assoc_list(digraph(T)::in, assoc_list(T, T)::out) is det.
% to_key_assoc_list turns a digraph into a list of pairs of keys,
% one for each edge.
%
:- func to_key_assoc_list(digraph(T)) =
assoc_list(digraph_key(T), digraph_key(T)).
:- pred to_key_assoc_list(digraph(T)::in,
assoc_list(digraph_key(T), digraph_key(T))::out) is det.
% from_assoc_list turns a list of pairs of vertices into a digraph.
%
:- func from_assoc_list(assoc_list(T, T)) = digraph(T).
:- pred from_assoc_list(assoc_list(T, T)::in, digraph(T)::out) is det.
%--------------------------------------------------%
%
% Depth-first sorting.
%
% dfs(G, Key, Dfs) is true if Dfs is a depth-first sorting of G
% starting at Key. The set of keys in the list Dfs is equal to the
% set of keys reachable from Key.
%
:- func dfs(digraph(T), digraph_key(T)) = list(digraph_key(T)).
:- pred dfs(digraph(T)::in, digraph_key(T)::in,
list(digraph_key(T))::out) is det.
% dfsrev(G, Key, DfsRev) is true if DfsRev is a reverse
% depth-first sorting of G starting at Key. The set of keys in the
% list DfsRev is equal to the set of keys reachable from Key.
%
:- func dfsrev(digraph(T), digraph_key(T)) = list(digraph_key(T)).
:- pred dfsrev(digraph(T)::in, digraph_key(T)::in,
list(digraph_key(T))::out) is det.
% dfs(G, Dfs) is true if Dfs is a depth-first sorting of G.
% If one considers each edge to point from a parent node to a child node,
% then Dfs will be a list of all the keys in G such that all keys for
% the children of a vertex are placed in the list before the parent key.
%
% If the digraph is cyclic, the position in which cycles are broken
% (that is, in which a child is placed *after* its parent) is undefined.
%
:- func dfs(digraph(T)) = list(digraph_key(T)).
:- pred dfs(digraph(T)::in, list(digraph_key(T))::out) is det.
% dfsrev(G, DfsRev) is true if DfsRev is a reverse depth-first
% sorting of G. That is, DfsRev is the reverse of Dfs from dfs/2.
%
:- func dfsrev(digraph(T)) = list(digraph_key(T)).
:- pred dfsrev(digraph(T)::in, list(digraph_key(T))::out) is det.
% dfs(G, Key, !Visit, Dfs) is true if Dfs is a depth-first
% sorting of G starting at Key, assuming we have already visited !.Visit
% vertices. That is, Dfs is a list of vertices such that all the
% unvisited children of a vertex are placed in the list before the
% parent. !.Visit allows us to initialise a set of previously visited
% vertices. !:Visit is Dfs + !.Visit.
%
:- pred dfs(digraph(T)::in, digraph_key(T)::in, digraph_key_set(T)::in,
digraph_key_set(T)::out, list(digraph_key(T))::out) is det.
% dfsrev(G, Key, !Visit, DfsRev) is true if DfsRev is a
% reverse depth-first sorting of G starting at Key providing we have
% already visited !.Visit nodes, i.e. the reverse of Dfs from dfs/5.
% !:Visit is !.Visit + DfsRev.
%
:- pred dfsrev(digraph(T)::in, digraph_key(T)::in,
digraph_key_set(T)::in, digraph_key_set(T)::out,
list(digraph_key(T))::out) is det.
%--------------------------------------------------%
%
% Reachability.
%
% reachable_vertices_from(G, FromVertex, ReachableVertices):
%
% Return the set of vertices that are reachable from FromVertex in G
% through zero or more edges. This means that the set will always
% include FromVertex.
%
:- pred reachable_vertices_from(digraph(T)::in, T::in, set(T)::out) is det.
%--------------------------------------------------%
%
% Transforming digraphs.
%
% inverse(G, G') is true if-and-only-if the domains of G and G' are equal,
% and for all x, y in this domain, (x,y) is an edge in G if-and-only-if
% (y,x) is an edge in G'.
%
:- func inverse(digraph(T)) = digraph(T).
:- pred inverse(digraph(T)::in, digraph(T)::out) is det.
% compose(G1, G2, G) is true if G is the composition
% of the digraphs G1 and G2. This means that there is an edge (x,y) in G
% if-and-only-if there exists vertex m such that (x,m) is in G1 and
% (m,y) is in G2.
%
:- func compose(digraph(T), digraph(T)) = digraph(T).
:- pred compose(digraph(T)::in, digraph(T)::in, digraph(T)::out)
is det.
%--------------------------------------------------%
%
% Components of digraphs.
%
% components(G, Comp) is true if Comp is the set of the
% connected components of G.
%
:- func components(digraph(T)) = set(set(digraph_key(T))).
:- pred components(digraph(T)::in, set(set(digraph_key(T)))::out)
is det.
% cliques(G, Cliques) is true if Cliques is the set of the
% cliques (strongly connected components) of G.
%
:- func cliques(digraph(T)) = set(set(digraph_key(T))).
:- pred cliques(digraph(T)::in, set(set(digraph_key(T)))::out) is det.
% reduced(G, R) is true if R is the reduced digraph (digraph of cliques)
% obtained from G.
%
:- func reduced(digraph(T)) = digraph(set(T)).
:- pred reduced(digraph(T)::in, digraph(set(T))::out) is det.
% As above, but also return a map from each key in the original digraph
% to the key for its clique in the reduced digraph.
%
:- pred reduced(digraph(T)::in, digraph(set(T))::out,
map(digraph_key(T), digraph_key(set(T)))::out) is det.
%--------------------------------------------------%
%
% Topological sorts.
%
% Both
% return_vertices_in_from_to_order(G, FromToVertices)
% and
% return_vertices_in_to_from_order(G, ToFromVertices)
% do a topological sort of G, the difference being that they return
% the same list of vertices in opposite orders.
%
% If we view each edge in the digraph as representing a <from, to>
% relationship, then FromToVertices will contain a vertex "from"
% *before* all the other vertices "to" for which a <from, to> edge exists
% in the graph. In other words, FromToVertices will be in from-to order.
%
% ToFromVertices will be the reverse of FromToVertices.
%
% Both these predicates will fail if G is cyclic.
%
:- pred return_vertices_in_from_to_order(digraph(T)::in, list(T)::out)
is semidet.
:- pred return_vertices_in_to_from_order(digraph(T)::in, list(T)::out)
is semidet.
% A synonym for return_vertices_in_from_to_order.
%
:- pred tsort(digraph(T)::in, list(T)::out) is semidet.
%--------------------------------------------------%
% Both
% return_sccs_in_from_to_order(G, FromToSccs)
% and
% return_sccs_in_to_from_order(G, ToFromSccs)
% do a topological sort of the strongly connected components (SCCs) of G,
% the difference being that they return the same list of SCCs
% in opposite orders.
%
% If we view each edge in the digraph as representing a <from, to>
% relationship, then FromToSccs will contain SCC A before all SCCs B
% for which there is an edge <from, to> with "from" being in SCC A
% and "to" being in SCC B. In other words, FromToSccs will be in
% from-to order.
%
% ToFromSccs will be the reverse of FromToSccs.
%
:- func return_sccs_in_from_to_order(digraph(T)) = list(set(T)).
:- func return_sccs_in_to_from_order(digraph(T)) = list(set(T)).
% A synonym for return_sccs_in_from_to_order.
%
:- func atsort(digraph(T)) = list(set(T)).
:- pred atsort(digraph(T)::in, list(set(T))::out) is det.
%--------------------------------------------------%
%
% Closures.
%
% symmetric_closure(G) = SC is true if SC is the symmetric closure of G.
% That is, (x,y) is in SC if-and-only-if either (x,y) or (y,x) is in G.
%
:- func symmetric_closure(digraph(T)) = digraph(T).
% Synonyms for symmetric_closure/1.
%
:- func sc(digraph(T)) = digraph(T).
:- pred sc(digraph(T)::in, digraph(T)::out) is det.
% transitive_closure(G) = TC is true if TC is the transitive closure of G.
%
:- func transitive_closure(digraph(T)) = digraph(T).
% Synonyms for transitive_closure/1.
%
:- func tc(digraph(T)) = digraph(T).
:- pred tc(digraph(T)::in, digraph(T)::out) is det.
% reflexive_transitive_closure(G) = RTC is true
% if RTC is the reflexive transitive closure of G.
%
% RTC is the reflexive closure of the transitive closure of G,
% or, equivalently, the transitive closure of the reflexive closure of G.
%
:- func reflexive_transitive_closure(digraph(T)) = digraph(T).
% Synonyms for reflexive_transitive_closure/1.
%
:- func rtc(digraph(T)) = digraph(T).
:- pred rtc(digraph(T)::in, digraph(T)::out) is det.
%--------------------------------------------------%
%
% Traversals.
%
% traverse(G, ProcessVertex, ProcessEdge, !Acc) will traverse the digraph G
% - calling ProcessVertex for each vertex in the digraph, and
% - calling ProcessEdge for each edge in the digraph.
% The processing of each vertex is followed by the processing of
% all the edges originating at that vertex, until all vertices
% have been processed.
%
:- pred traverse(digraph(T), pred(T, A, A), pred(T, T, A, A), A, A).
:- mode traverse(in, in(pred(in, di, uo) is det),
in(pred(in, in, di, uo) is det), di, uo) is det.
:- mode traverse(in, in(pred(in, in, out) is det),
in(pred(in, in, in, out) is det), in, out) is det.
%--------------------------------------------------%
%--------------------------------------------------%