Next: lib-varnumbers, Previous: lib-types, Up: The Prolog Library [Contents][Index]

`library(ugraphs)`

This library module provides operations on directed graphs.
An unweighted directed graph (ugraph) is represented as a list of
`(vertex-neighbors)` pairs, where the pairs are in standard order
(as produced by `keysort/2`

with unique keys) and the neighbors of
each vertex are also in standard order (as produced by `sort/2`

), and
every neighbor appears as a vertex even if it has no neighbors
itself.

An undirected graph is represented as a directed graph where for
each edge `(U,V)` there is a symmetric edge `(V,U)`.

An edge `(U,V)` is represented as the term `U-V`.

A vertex can be any term. Two vertices are distinct iff they are
not identical (`==`

).

A path is represented as a list of vertices. No vertex can appear twice in a path.

Exported predicates:

`vertices_edges_to_ugraph(`

`+Vertices`,`+Edges`,`-Graph`)-
is true if

`Vertices`is a proper list of vertices,`Edges`is a proper list of edges, and`Graph`is a graph built from`Vertices`and`Edges`.`Vertices`and`Edges`may be in any order. The vertices mentioned in`Edges`do not have to occur explicitly in`Vertices`.`Vertices`may be used to specify vertices that are not connected to any edges. `vertices(`

`+Graph`,`-Vertices`)-
unifies

`Vertices`with the vertices in`Graph`. Could be defined as:vertices(Graph, Vertices) :- ( foreach(V-_,Graph), foreach(V,Vertices) do true ).

`edges(`

`+Graph`,`-Edges`)-
unifies

`Edges`with the edges in`Graph`. Could be defined as:edges(Graph, Edges) :- ( foreach(V1-Neibs,Graph), fromto(Edges,S0,S,[]) do ( foreach(V2,Neibs), param(V1), fromto(S0,[V1-V2|S1],S1,S) do true ) ).

`add_vertices(`

`+Graph1`,`+Vertices`,`-Graph2`)-
is true if

`Graph2`is`Graph1`with`Vertices`added to it. `del_vertices(`

`+Graph1`,`+Vertices`,`-Graph2`)-
is true if

`Graph2`is`Graph1`with`Vertices`and all edges to and from`Vertices`removed from it. `add_edges(`

`+Graph1`,`+Edges`,`-Graph2`)-
is true if

`Graph2`is`Graph1`with`Edges`and their "to" and "from" vertices added to it. `del_edges(`

`+Graph1`,`+Edges`,`-Graph2`)-
is true if

`Graph2`is`Graph1`with`Edges`removed from it. `transpose_ugraph(`

`+Graph`,`-Transpose`)-
is true if

`Transpose`is the graph computed by replacing each edge`(u,v)`in`Graph`by its symmetric edge`(v,u)`. It can only be used one way around. The cost is`O(N log N)`. `neighbors(`

`+Vertex`,`+Graph`,`-Neighbors`)`neighbours(`

`+Vertex`,`+Graph`,`-Neighbors`)-
is true if

`Vertex`is a vertex in`Graph`and`Neighbors`are its neighbors. `complement(`

`+Graph`,`-Complement`)-
`Complement`is the complement graph of`Graph`, i.e. the graph that has the same vertices as`Graph`but only the edges that are not in`Graph`. `compose(`

`+G1`,`+G2`,`-Composition`)-
computes

`Composition`as the composition of two graphs, which need not have the same set of vertices. `transitive_closure(`

`+Graph`,`-Closure`)-
computes

`Closure`as the transitive closure of`Graph`in`O(N^3)`time. `transitive_reduction(`

`+Graph`,`-Reduction`)*since release 4.3.3*-
computes

`Reduction`as the transitive reduction of`Graph`.Aho et al. let

`GraphT`be the transitive closure of`Graph`. Then an edge`uv`belongs to the transitive reduction iff`uv`belongs to`Graph`but not to the composition of`Graph`and`GraphT`. In this construction, the edges of the composition represent pairs of vertices connected by paths of length two or more. `symmetric_closure(`

`+Graph`,`-Closure`)-
computes

`Closure`as the symmetric closure of`Graph`, i.e. for each edge`(u,v)`in`Graph`, add its symmetric edge`(v,u)`. Approx.`O(N log N)`time. This is useful for making a directed graph undirected. Could be defined as:symmetric_closure(Graph, Closure) :- transpose_ugraph(Graph, Transpose), ( foreach(V-Neibs1,Graph), foreach(V-Neibs2,Transpose), foreach(V-Neibs,Closure) do ord_union(Neibs1, Neibs2, Neibs) ).

`top_sort(`

`+Graph`,`-Sorted`)-
finds a topological ordering of

`Graph`and returns the ordering as a list of`Sorted`vertices. Fails iff no ordering exists, i.e. iff the graph contains cycles. Approx.`O(N log N)`time. `max_path(`

`+V1`,`+V2`,`+Graph`,`-Path`,`-Cost`)-
is true if

`Path`is a list of vertices constituting a longest path of cost`Cost`from`V1`to`V2`in`Graph`, there being no cyclic paths from`V1`to`V2`. Takes`O(N^2)`time. `min_path(`

`+V1`,`+V2`,`+Graph`,`-Path`,`-Length`)-
is true if

`Path`is a list of vertices constituting a shortest path of length`Length`from`V1`to`V2`in`Graph`. Takes`O(N^2)`time. `min_paths(`

`+Vertex`,`+Graph`,`-Tree`)-
is true if

`Tree`is a tree of all the shortest paths from`Vertex`to every other vertex in`Graph`. This is the single-source shortest paths problem. The algorithm is straightforward. `path(`

`+Vertex`,`+Graph`,`-Path`)-
is given a

`Graph`and a`Vertex`of that`Graph`, and returns a maximal`Path`rooted at`Vertex`, enumerating more`Paths`on backtracking. `reduce(`

`+Graph`,`-Reduced`)-
is true if

`Reduced`is the reduced graph for`Graph`. The vertices of the reduced graph are the strongly connected components of`Graph`. There is an edge in`Reduced`from`u`to`v`iff there is an edge in`Graph`from one of the vertices in`u`to one of the vertices in`v`. A strongly connected component is a maximal set of vertices where each vertex has a path to every other vertex. Algorithm from "Algorithms" by Sedgewick, page 482, Tarjan’s algorithm. `reachable(`

`+Vertex`,`+Graph`,`-Reachable`)-
is given a Graph and a

`Vertex`of that`Graph`, and returns the set of vertices that are`Reachable`from that`Vertex`. Takes`O(N^2)`time. `random_ugraph(`

`+P`,`+N`,`-Graph`)-
where

`P`is a probability, unifies`Graph`with a random graph of`N`vertices where each possible edge is included with probability`P`. `min_tree(`

`+Graph`,`-Tree`,`-Cost`)-
is true if

`Tree`is a spanning tree of an*undirected*`Graph`with cost`Cost`, if it exists. Using a version of Prim’s algorithm. `max_cliques(`

`+Graph`,`-Cliques`)*since release 4.3.3*-
is true if

`Cliques`is the set of the maximal cliques of the*undirected*graph`Graph`. That is, all subsets of vertices such that (i) each pair of vertices in any listed subset is connected by an edge, and (ii) no listed subset can have any additional vertex added to it. Using a version of the Bron-Kerbosch algorithm.

Send feedback on this subject.