Node:UGraphs, Next:WGraphs, Previous:Trees, Up:Top

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 Ordsets).

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 \geq 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 \geq 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 \leq K. The mapping is represented as an ordered list of`Vertex`-`Color`pairs.`n`is not necessarily minimal.