 |
YAP 7.1.0
|
|
YAP 7.1.0
|
The following graph manipulation routines are based in code originally written by Richard O'Keefe. More...
The following graph manipulation routines are based in code originally written by Richard O'Keefe.
The code was then extended to be compatible with the SICStus Prolog ugraphs library The routines assume directed graphs, undirected graphs may be implemented by using two edges Graphs are represented in one of two ways:
The S-representation of a graph is a list of (vertex-neighbors) pairs, where the pairs are in standard order (as produced by keysort) and the neighbors of each vertex are also in standard order (as produced by sort) This form is convenient for many calculations
These built-ins are available once included with the use_module(library(ugraphs)) command
| class vertices_edges_to_ugraph/3 |
vertices_edges_to_ugraph(+ Vertices, + Edges, - Graph)
Given a graph with a set of vertices Vertices and a set of edges Edges, Graph must unify with the corresponding s-representation Note that the vertices without edges will appear in Vertices but not in Edges Moreover, it is sufficient for a vertex to appear in Edges
In this case all edges are defined implicitly The next example shows three unconnected edges:
| class add_edges/3 |
add_edges(+ Graph, + Edges, - NewGraph)
Unify NewGraph with a new graph obtained by adding the list of edges Edges to the graph Graph In the next example:
| class add_vertices/3 |
add_vertices(+ Graph, + Vertices, - NewGraph)
Unify NewGraph with a new graph obtained by adding the list of vertices Vertices to the graph Graph In the next example:
| class complement/2 |
complement(+ Graph, - NewGraph)
Unify NewGraph with the graph complementary to Graph In the next example:
| class compose/3 |
| class del_edges/3 |
del_edges(+ Graph, + Edges, - NewGraph)
Unify NewGraph with a new graph obtained by removing the list of edges Edges from the graph Graph Notice that no vertices are deleted In the next example:
| class del_vertices/3 |
del_vertices(+ Graph, + Vertices, - NewGraph)
Unify NewGraph with a new graph obtained by deleting the list of vertices Vertices and all the edges that start from or go to a vertex in Vertices to the graph Graph In the next example:
| class edges/2 |
edges(+ Graph, - Edges)
Unify Edges with all edges appearing in graph Graph In the next example:
| class neighbors/3 |
neighbors(+ Vertex, + Graph, - Vertices)
Unify Vertices with the list of neighbors of vertex Vertex in Graph If the vertice is not in the graph fail In the next example:
| class neighbours/3 |
neighbours(+ Vertex, + Graph, - Vertices)
Unify Vertices with the list of neighbours of vertex Vertex in Graph In the next example:
| class reachable/3 |
reachable(+ Node, + Graph, - Vertices)
Unify Vertices with the set of all vertices in graph Graph that are reachable from Node In the next example:
| class top_sort/3 |
top_sort(+ Graph, - Sort0, - Sort)
Generate the difference list Sort- Sort0 as a topological sorting of graph Graph, if one is possible
| class top_sort/2 |
top_sort(+ Graph, - Sort)
Generate the set of nodes Sort as a topological sorting of graph Graph, if one is possible In the next example we show how topological sorting works for a linear graph:
| class transitive_closure/2 |
transitive_closure(+ Graph, + Closure)
Generate the graph Closure as the transitive closure of graph Graph In the next example:
| class vertices/2 |
vertices(+ Graph, - Vertices)
Unify Vertices with all vertices appearing in graph Graph In the next example:
| class transpose/2 |
transpose(+ Graph, - NewGraph)
Unify NewGraph with a new graph obtained from Graph by replacing all edges of the form V1-V2 by edges of the form V2-V1 The cost is O(|V|^2) In the next example:
Notice that an undirected graph is its own transpose
| class raakau/3 |
raakau(Vertices, InitialValue, Tree)
NOT USED AFTER ALL takes an ordered list of verticies and an initial value, and makes a very special sort of tree out of them, which represents a function sending each vertex to the initial value Note that in the third clause for raakau/6 Z can never be 0, this means that it doesn't matter what "greatest member" is reported for empty trees
1.9.3