%--------------------------------------------------% % 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-2024 The Mercury team. % This file is distributed under the terms specified in COPYING.LIB. %--------------------------------------------------% % % File: digraph.m % Original authors: bromage, petdr % Stability: medium % % 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)). % 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. % 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. % 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. % 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. % 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. % 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. %--------------------------------------------------% % 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. %--------------------------------------------------% % 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. %--------------------------------------------------% % 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. % inverse(G, G') is true iff the domains of G and G' are equal, % and for all x, y in this domain, (x,y) is an edge in G iff (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 % iff 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. % is_dag(G) is true iff G is a directed acyclic graph. % :- pred is_dag(digraph(T)::in) is semidet. % 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. % tsort(G, TS) is true if TS is a topological sorting of G. % % If we view each edge in the digraph as representing a <from, to> % relationship, then TS will contain a vertex "from" *before* % all the other vertices "to" for which a <from, to> edge exists % in the graph. In other words, TS will be in from-to order. % % tsort fails if G is cyclic. % :- pred tsort(digraph(T)::in, list(T)::out) is semidet. % Both these predicates do a topological sort of G. % % return_vertices_in_from_to_order(G, TS) is a synonym for tsort(G, TS). % return_vertices_in_to_from_order(G, TS) is identical to both % except for the fact that it returns the vertices in the opposite order. % :- 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. % atsort(G, ATS) is true if ATS is a topological sorting % of the strongly connected components (SCCs) in G. % % If we view each edge in the digraph as representing a <from, to> % relationship, then ATS 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, ATS will be in from-to order. % :- func atsort(digraph(T)) = list(set(T)). :- pred atsort(digraph(T)::in, list(set(T))::out) is det. % Both these predicates do a topological sort of the strongly connected % components (SCCs) of G. % % return_sccs_in_from_to_order(G) = ATS is a synonym for atsort(G) = ATS. % return_sccs_in_to_from_order(G) = ATS is identical to both % except for the fact that it returns the SCCs in the opposite order. % :- func return_sccs_in_from_to_order(digraph(T)) = list(set(T)). :- func return_sccs_in_to_from_order(digraph(T)) = list(set(T)). % sc(G, SC) is true if SC is the symmetric closure of G. % That is, (x,y) is in SC iff either (x,y) or (y,x) is in G. % :- func sc(digraph(T)) = digraph(T). :- pred sc(digraph(T)::in, digraph(T)::out) is det. % A synonym for sc/1. % :- func symmetric_closure(digraph(T)) = digraph(T). % tc(G, TC) is true if TC is the transitive closure of G. % :- func tc(digraph(T)) = digraph(T). :- pred tc(digraph(T)::in, digraph(T)::out) is det. % A synonym for tc/1. % :- func transitive_closure(digraph(T)) = digraph(T). % rtc(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 rtc(digraph(T)) = digraph(T). :- pred rtc(digraph(T)::in, digraph(T)::out) is det. % A synonym for rtc/1. % :- func reflexive_transitive_closure(digraph(T)) = digraph(T). % 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. %--------------------------------------------------% %--------------------------------------------------%