27 Unweighted Graph Operations
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.