10.48 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 (vertex-edgelist) pairs, where the pairs are in standard order (as produced by keysort/2 with unique keys), the edgelist is a list of (neighbor-weight) 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 U-V.

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

Re-exported 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(V-WNeibs,WGraph),
	    foreach(V-Neibs,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(V-Neibs,Graph),
	    foreach(V-WNeibs,WGraph)
	do  (   foreach(V1,Neibs),
	        foreach(V1-1,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 proper list of vertices, Edges is a proper 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 single-source 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 minimum-Cost spanning tree of an undirected WeightedGraph with cost Cost, if it exists. Using Kruskal’s algorithm.