ON THIS PAGE
Unweighted graph-processing utilities
Author(s): Richard A. O'Keefe (original shared code), Mats Carlsson (adapted from original code), Francisco Bueno (modifications), Manuel Carro (modifications).An unweighted directed graph (ugraph) is represented as a list of (vertex-neighbors) pairs, where the pairs are in standard order (as produced by keysort with unique keys) and the neighbors of each vertex are also in standard order (as produced by sort), 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 (==/2).
A path is represented as a list of vertices. No vertex can appear twice in a path.
Usage and interface
- Library usage:
:- use_module(library(graphs/ugraphs)). - Exports:
- Predicates:
vertices_edges_to_ugraph/3, neighbors/3, edges/2, del_edges/3, add_edges/3, vertices/2, del_vertices/3, add_vertices/3, transpose/2, rooted_subgraph/3, point_to/3. - Regular Types:
ugraph/1.
- Predicates:
Documentation on exports
Usage:neighbors(Vertex,Graph,Neighbors)
Is true if Vertex is a vertex in Graph and Neighbors are its neighbors.
- The following properties should hold at call time:
(term_typing:nonvar/1)Vertex is currently a term which is not a free variable.
(term_typing:nonvar/1)Graph is currently a term which is not a free variable.
(term_typing:var/1)Neighbors is a free variable.
Usage:edges(Graph,Edges)
Unifies Edges with the edges in Graph.
- The following properties should hold at call time:
(term_typing:nonvar/1)Graph is currently a term which is not a free variable.
(term_typing:var/1)Edges is a free variable.
Usage:del_edges(Graph1,Edges,Graph2)
Is true if Graph2 is Graph1 with Edges removed from it.
- The following properties should hold at call time:
(term_typing:nonvar/1)Graph1 is currently a term which is not a free variable.
(term_typing:nonvar/1)Edges is currently a term which is not a free variable.
(term_typing:var/1)Graph2 is a free variable.
Usage:add_edges(Graph1,Edges,Graph2)
Is true if Graph2 is Graph1 with Edges and their 'to' and 'from' vertices added to it.
- The following properties should hold at call time:
(term_typing:nonvar/1)Graph1 is currently a term which is not a free variable.
(term_typing:nonvar/1)Edges is currently a term which is not a free variable.
(term_typing:var/1)Graph2 is a free variable.
Usage:vertices(Graph,Vertices)
Unifies Vertices with the vertices in Graph.
- The following properties should hold at call time:
(term_typing:nonvar/1)Graph is currently a term which is not a free variable.
(term_typing:var/1)Vertices is a free variable.
Usage:del_vertices(Graph1,Vertices,Graph2)
Is true if Graph2 is Graph1 with Vertices and all edges to and from Vertices removed from it.
- The following properties should hold at call time:
(term_typing:nonvar/1)Graph1 is currently a term which is not a free variable.
(term_typing:nonvar/1)Vertices is currently a term which is not a free variable.
(term_typing:var/1)Graph2 is a free variable.
Usage:add_vertices(Graph1,Vertices,Graph2)
Is true if Graph2 is Graph1 with Vertices added to it.
- The following properties should hold at call time:
(term_typing:nonvar/1)Graph1 is currently a term which is not a free variable.
(term_typing:nonvar/1)Vertices is currently a term which is not a free variable.
(term_typing:var/1)Graph2 is a free variable.
Usage:transpose(Graph,Transpose)
Is true if Transpose is the graph computed by replacing each edge (u,v) in Graph by its symmetric edge (v,u). It can only be used one way around. The cost is O(N^2).
- The following properties should hold at call time:
(term_typing:nonvar/1)Graph is currently a term which is not a free variable.
(term_typing:var/1)Transpose is a free variable.
Usage:rooted_subgraph(Graph,Sources,SubGraph)
SubGraph is the subgraph of Graph which is reachable from Sources.
- The following properties should hold at call time:
(ugraphs:ugraph/1)Graph is an ugraph.
(basic_props:list/1)Sources is a list.
(term_typing:var/1)SubGraph is a free variable. - The following properties should hold upon exit:
(ugraphs:ugraph/1)SubGraph is an ugraph.
Usage:point_to(Vertex,Graph,Point_to)
Is true if Point_to is the list of nodes which go directly to Vertex in Graph.
- The following properties should hold at call time:
(term_typing:nonvar/1)Vertex is currently a term which is not a free variable.
(term_typing:nonvar/1)Graph is currently a term which is not a free variable.
(term_typing:var/1)Point_to is a free variable.
Usage:ugraph(Graph)
Graph is an ugraph.
Documentation on imports
This module has the following direct dependencies:- System library modules:
sets, sort. - Packages:
prelude, initial, condcomp, assertions, assertions/assertions_basic, isomodes, regtypes.