28 Weighted Graph Operations
A weighted directed graph (wgraph) is represented as a list of
(vertex-edgelist) pairs, where the pairs are in standard
order (as produced by keysort
with unique keys), the edgelist is
a list of (neighbor-weight) pair also in standard order (as
produced by keysort
with unique keys), every weight is a
nonnegative integer, 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) with weight W is represented as the term
U-(V-W). 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(wgraphs)).
The following predicates are defined for directed graphs.
wgraph_to_ugraph(
+WeightedGraph,
-Graph)
- Graph has the same vertices and edges as WeightedGraph,
except the edges of Graph are unweighted.
ugraph_to_wgraph(
+Graph,
-WeightedGraph)
- WeightedGraph has the same vertices and edges as Graph,
except the edges of WeightedGraph all have weight 1.
vertices_edges_to_wgraph(
+Vertices,
+Edges,
-WeightedGraph)
- Vertices is a list of vertices, Edges is a list
of edges, and WeightedGraph 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(
+WeightedGraph,
-Vertices)
- Unifies Vertices with the vertices in WeightedGraph.
edges(
+WeightedGraph,
-Edges)
- Unifies Edges with the edges in WeightedGraph.
add_vertices(
+WeightedGraph1,
+Vertices,
-WeightedGraph2)
- WeightedGraph2 is WeightedGraph1 with Vertices added
to it.
del_vertices(
+WeightedGraph1,
+Vertices,
-WeightedGraph2)
- WeightedGraph2 is WeightedGraph1 with Vertices and all
edges to and from them removed from it.
add_edges(
+WeightedGraph1,
+Edges,
-WeightedGraph2)
- WeightedGraph2 is WeightedGraph1 with Edges and their
“to” and “from” vertices added to it.
del_edges(
+WeightedGraph1,
+Edges,
-WeightedGraph2)
- WeightedGraph2 is WeightedGraph1 with Edges removed
from it.
transpose(
+WeightedGraph,
-Transpose)
- Transpose is the graph computed by replacing each edge (u,v)
in WeightedGraph by its symmetric edge (v,u). It can only
be used one way around. Takes O(N^2) time.
neighbors(
+Vertex,
+WeightedGraph,
-Neighbors)
neighbours(
+Vertex,
+WeightedGraph,
-Neighbors)
- Vertex is a vertex in WeightedGraph and Neighbors are
its weighted neighbors.
transitive_closure(
+WeightedGraph,
-Closure)
- Computes Closure as the transitive closure of WeightedGraph
in O(N^3) time.
symmetric_closure(
+WeightedGraph,
-Closure)
- Computes Closure as the symmetric closure of WeightedGraph,
i.e. for each edge (u,v) in WeightedGraph, add its symmetric
edge (v,u). Takes O(N^2) time. This is useful for making a
directed graph undirected.
top_sort(
+WeightedGraph,
-Sorted)
- Finds a topological ordering of a WeightedGraph 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,
+WeightedGraph,
-Path,
-Cost)
- Path is a maximum-cost path of cost Cost from V1 to
V2 in WeightedGraph, there being no cyclic paths from
V1 to V2. Takes O(N^2) time.
min_path(
+V1,
+V2,
+WeightedGraph,
-Path,
-Cost)
- Path is a minimum-cost path of cost Cost from V1 to
V2 in WeightedGraph. Takes O(N^2) time.
min_paths(
+Vertex,
+WeightedGraph,
-Tree)
- Tree is a tree of all the minimum-cost paths from Vertex to
every other vertex in WeightedGraph. This is the single-source
minimum-cost paths problem.
path(
+Vertex,
+WeightedGraph,
-Path)
- Given a WeightedGraph and a Vertex of WeightedGraph,
returns a maximal Path rooted at Vertex, enumerating more
paths on backtracking.
reduce(
+WeightedGraph,
-Reduced)
- Reduced is the reduced graph for WeightedGraph. The
vertices of the reduced graph are the strongly connected components of
WeightedGraph. There is an edge in Reduced from u to
v iff there is an edge in WeightedGraph from one of the
vertices in u to one of the vertices in v.
reachable(
+Vertex,
+WeightedGraph,
-Reachable)
- Given a WeightedGraph and a Vertex of WeightedGraph,
returns the set of vertices that are reachable from that
Vertex. Takes O(N^2) time.
random_wgraph(
+P,
+N,
+W,
-WeightedGraph)
- Where P is a probability, unifies WeightedGraph with a
random graph of vertices 1..N where each possible edge is included
with probability P and random weight in 1..W.
The following predicate is defined for undirected graphs only.
min_tree(
+WeightedGraph,
-Tree,
-Cost)
- Tree is a minimum-cost spanning tree of WeightedGraph with
cost Cost, if it exists.