10.31 Weighted Graph Operations—library(wgraphs)
This library module provides operations on weighted directed graphs.
A weighted directed graph (wgraph) is represented as a list of
(vertexedgelist) pairs, where the pairs are in standard order (as
produced by keysort/2
with unique keys), the edgelist is a list of
(neighborweight) pair also in standard order (as produced by
keysort/2
with unique keys), every weight is a nonnegative integer,
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 UV.
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/2
edges/2
add_vertices/3
neighbors/3
neighbours/3

Reexported from
library(wgraphs)
.
wgraph_to_ugraph(
+WeightedGraph,
Graph)

is true if Graph has the same vertices and edges as WeightedGraph,
except the edges of Graph are unweighted.
Could be defined as:
wgraph_to_ugraph(WGraph, Graph) :
( foreach(VWNeibs,WGraph),
foreach(VNeibs,Graph)
do ( foreach(V1_,WNeibs),
foreach(V1,Neibs)
do true
)
).
ugraph_to_wgraph(
+Graph,
WeightedGraph)

is true if WeightedGraph has the same vertices and edges as Graph,
except the edges of WeightedGraph all have weight 1.
Could be defined as:
ugraph_to_wgraph(Graph, WGraph) :
( foreach(VNeibs,Graph),
foreach(VWNeibs,WGraph)
do ( foreach(V1,Neibs),
foreach(V11,WNeibs)
do true
)
).
ugraph_to_wgraph(+SubGraph, +WeightedGraph, WeightedSubGraph)

is true if WeightedSubGraph has the same vertices and edges as SubGraph
and the same weights as the corresponding edges in WeightedGraph.
vertices_edges_to_wgraph(
+Vertices,
+Edges,
WeightedGraph)

is true if 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 to any edges.
del_vertices(
+WeightedGraph1,
+Vertices,
WeightedGraph2)

is true if WeightedGraph2 is WeightedGraph1 with Vertices and all
edges to and from Vertices removed from it.
add_edges(
+WeightedGraph1,
+Edges,
WeightedGraph2)

is true if WeightedGraph2 is WeightedGraph1 with Edges and their "to"
and "from" vertices added to it.
del_edges(
+WeightedGraph1,
+Edges,
WeightedGraph2)

is true if WeightedGraph2 is WeightedGraph1 with Edges removed from it.
transpose_wgraph(
+WeightedGraph,
Transpose)

is true if 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. The cost is O(N log N).
transitive_closure(
+WeightedGraph,
Closure)

computes Closure as the transitive closure of WeightedGraph in
O(N^3) time. Uses Floyd's algorithm and fragments of Barney
Pell's code.
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). Approx O(N log N) 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 log N) time.
max_path(
+V1,
+V2,
+WeightedGraph,
Path,
Cost)

is true if Path is a list of vertices constituting a longest 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)

is true if Path is a list of vertices constituting a shortest path
with total cost Cost from V1 to V2 in WeightedGraph. Takes O(N^2)
time.
min_paths(
+Vertex,
+WeightedGraph,
Tree)

is true if Tree is a tree of all the shortest paths from Vertex to
every other vertex in WeightedGraph. This is the singlesource
shortest paths problem. Using Dijkstra's algorithm.
path(
+Vertex,
+WeightedGraph,
Path)

is given a WeightedGraph and a Vertex of that WeightedGraph, and
returns a maximal Path rooted at Vertex, enumerating more Paths on
backtracking.
reduce(
+WeightedGraph,
Reduced)

is true if 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. 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,
+WeightedGraph,
Reachable)

is given a WeightedGraph and a Vertex of that WeightedGraph, and
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 with vertices 1..N where each possible edge is included with
probability P and random weight in 1..W.
min_tree(
+WeightedGraph,
Tree,
Cost)

is true if Tree is a minimumCost spanning tree of an undirected
WeightedGraph with cost Cost, if it exists. Using Kruskal's
algorithm.
Send feedback on this subject.