Directed and undirected graphs are fundamental data structures representing arbitrary relationships between data objects. This package provides a Prolog implementation of directed graphs, undirected graphs being a special case of 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`

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

),
every neighbor appears as a vertex even if it has no neighbors itself,
and no vertex is a neighbor to 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`.
`U` and `V` must be distinct.

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

).

A path from `u` to `v` is represented as a list of vertices,
beginning with `u` and ending with `v`. A vertex cannot appear
twice in a path. A path is maximal in a graph if it cannot be extended.

A tree is a tree-shaped directed graph (all vertices have a single predecessor, except the root node, which has none).

A strongly connected component of a graph is a maximal set of vertices where each vertex has a path in the graph to every other vertex.

Sets are represented as ordered lists (see section Ordered Set Operations).

To load the package, enter the query

| ?- use_module(library(ugraphs)).

The following predicates are defined for directed graphs.

`vertices_edges_to_ugraph(`

`+Vertices`,`+Edges`,`-Graph`)-
Is true if
`Vertices`is a list of vertices,`Edges`is a 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 by any edges. `vertices(`

`+Graph`,`-Vertices`)-
Unifies
`Vertices`with the vertices in`Graph`. `edges(`

`+Graph`,`-Edges`)-
Unifies
`Edges`with the edges in`Graph`. `add_vertices(`

`+Graph1`,`+Vertices`,`-Graph2`)-
`Graph2`is`Graph1`with`Vertices`added to it. `del_vertices(`

`+Graph1`,`+Vertices`,`-Graph2`)-
`Graph2`is`Graph1`with`Vertices`and all edges to and from them removed from it. `add_edges(`

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

`+Graph1`,`+Edges`,`-Graph2`)-
`Graph2`is`Graph1`with`Edges`removed from it. `transpose(`

`+Graph`,`-Transpose`)-
`Transpose`is the graph computed by replacing each edge`(u,v)`in`Graph`by its symmetric edge`(v,u)`. Takes O(N^2) time. `neighbors(`

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

`+Vertex`,`+Graph`,`-Neighbors`)-
`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. `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)`. Takes O(N^2) time. This is useful for making a directed graph undirected. `top_sort(`

`+Graph`,`-Sorted`)-
Finds a topological ordering of a
`Graph`and returns the ordering as a list of`Sorted`vertices. Fails iff no ordering exists, i.e. iff the graph contains cycles. Takes O(N^2) time. `max_path(`

`+V1`,`+V2`,`+Graph`,`-Path`,`-Cost`)-
`Path`is 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`,`-Cost`)-
`Path`is a shortest path of cost`Cost`from`V1`to`V2`in`Graph`. Takes O(N^2) time. `min_paths(`

`+Vertex`,`+Graph`,`-Tree`)-
`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. `path(`

`+Vertex`,`+Graph`,`-Path`)-
Given a
`Graph`and a`Vertex`of`Graph`, returns a maximal`Path`rooted at`Vertex`, enumerating more paths on backtracking. `reduce(`

`+Graph`,`-Reduced`)-
`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`. `reachable(`

`+Vertex`,`+Graph`,`-Reachable`)-
Given a
`Graph`and a`Vertex`of`Graph`, returns the set of vertices that are*reachable*from that`Vertex`, including`Vertex`itself. Takes O(N^2) time. `random_ugraph(`

`+P`,`+N`,`-Graph`)-
Where
`P`is a probability, unifies`Graph`with a random graph of vertices`1..N`where each possible edge is included with probability`P`.

The following predicates are defined for undirected graphs only.

`min_tree(`

`+Graph`,`-Tree`,`-Cost`)-
`Tree`is a spanning tree of`Graph`with cost`Cost`, if it exists. `clique(`

`+Graph`,`+K`,`-Clique`)-
`Clique`is a maximal clique (complete subgraph) of`N`vertices of`Graph`, where`N>=K`.`N`is not necessarily maximal. `independent_set(`

`+Graph`,`+K`,`-Set`)-
`Set`is a maximal independent (unconnected) set of`N`vertices of`Graph`, where`N>=K`.`N`is not necessarily maximal. `coloring(`

`+Graph`,`+K`,`-Coloring`)`colouring(`

`+Graph`,`+K`,`-Coloring`)-
`Coloring`is a mapping from vertices to colors`1..N`of`Graph`such that all edges have distinct end colors, where`N=<K`. The mapping is represented as an ordered list of`Vertex`-`Color`pairs.`N`is not necessarily minimal.

Go to the first, previous, next, last section, table of contents.