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,
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)` 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 section Ordered Set Operations).

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.

Go to the first, previous, next, last section, table of contents.