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.