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)
ugraph_to_wgraph(
+Graph,
-WeightedGraph)
vertices_edges_to_wgraph(
+Vertices,
+Edges,
-WeightedGraph)
vertices(
+WeightedGraph,
-Vertices)
edges(
+WeightedGraph,
-Edges)
add_vertices(
+WeightedGraph1,
+Vertices,
-WeightedGraph2)
del_vertices(
+WeightedGraph1,
+Vertices,
-WeightedGraph2)
add_edges(
+WeightedGraph1,
+Edges,
-WeightedGraph2)
del_edges(
+WeightedGraph1,
+Edges,
-WeightedGraph2)
transpose(
+WeightedGraph,
-Transpose)
neighbors(
+Vertex,
+WeightedGraph,
-Neighbors)
neighbours(
+Vertex,
+WeightedGraph,
-Neighbors)
transitive_closure(
+WeightedGraph,
-Closure)
symmetric_closure(
+WeightedGraph,
-Closure)
top_sort(
+WeightedGraph,
-Sorted)
max_path(
+V1,
+V2,
+WeightedGraph,
-Path,
-Cost)
min_path(
+V1,
+V2,
+WeightedGraph,
-Path,
-Cost)
min_paths(
+Vertex,
+WeightedGraph,
-Tree)
path(
+Vertex,
+WeightedGraph,
-Path)
reduce(
+WeightedGraph,
-Reduced)
reachable(
+Vertex,
+WeightedGraph,
-Reachable)
random_wgraph(
+P,
+N,
+W,
-WeightedGraph)
The following predicate is defined for undirected graphs only.
min_tree(
+WeightedGraph,
-Tree,
-Cost)