- all_short_paths_as_edges(+Graph, +DistanceArg, +SourceNode, +Tolerance, -Lengths, -Predecessors)
- Computes all shortest paths from a single source to every reachable node
- all_short_paths_as_graph(+Graph, +DistanceArg, +SourceNode, +Tolerance, -Lengths, -SubGraph)
- Computes all shortest paths from a single source in form of a subgraph
- articulation_points(+Graph, -Articulations)
- Finds the articulation points of the graph
- biconnected_components(+Graph, -Articulations, -BCC)
- Finds the biconnected components of the graph
- connected_components(+Graph, -ConnectedComponents)
- Computes the connected components of graph
- critical_links(+Graph, -Links)
- Finds critical links in a bidirected graph
- graph_adjacent_edge(+Graph, +Node, ?Edge)
- Succeeds if Edge is an edge adjacent to Node in Graph
- graph_cycles(+Graph, -BreakingEdges)
- Computes a list of edges whose removal would make the graph acyclic
- graph_edge(+Graph, ?Edge)
- Succeeds if Edge is an edge in graph
- graph_get_adjacent_edges(+Graph, +SourceNode, -EdgeList)
- Returns a sorted list of all edges starting from SourceNode
- graph_get_all_edges(+Graph, -EdgeList)
- Returns a sorted list of all edges in the graph
- graph_get_edge(+Graph, +Source, +Target, -Edge)
- Finds a graph edge given source and target node
- graph_get_edges(+Graph, +Source, +Target, -Edges)
- Finds all edges between source node and target node
- graph_get_incoming_edges(+Graph, +TargetNode, -EdgeList)
- Returns a sorted list of all edges ending in TargetNode
- graph_get_maxnode(+Graph, -MaxNode)
- Returns the highest node number in Graph
- graph_get_nodenames(+Graph, -NodeNameArray)
- Returns the array of node names
- graph_is_acyclic(+Graph)
- Succeeds iff the given graph has no cycles
- graph_is_bidirected(+Graph)
- Tests whether a graph is bidirected
- graph_node(+Graph, ?Node)
- Succeeds if Node is a node of the graph
- graph_reverse_edges(+Graph, -RevGraph)
- Makes a graph with reversed edges
- graph_set_nodenames(+Graph, ++NodeNameArray)
- Add node names to an existing graph
- graph_set_random_weights(+Graph, +Min, +Max)
- Unifies all the graph's edge data fields with random numbers
- incremental_all_shortest_paths_as_edges(+Graph, +DistanceArg, +SourceNode, +Modified, -Lengths, -Predecessors)
- Incrementally computes all shortest paths from a single source to every reachable node given a list of modified edges
- incremental_all_shortest_paths_as_graph(+Graph, +DistanceArg, +SourceNode, +Modified, -Lengths, -SubGraph)
- Incrementally computes all shortest paths from a single source to every reachable node given a list of modified edges
- incremental_single_pair_all_shortest_paths_as_graph(+Graph, +DistanceArg, +SourceNode, +SinkNode, +Modified, -Length, -SubGraph)
- Computes all shortest paths from source to sink in form of a subgraph
- incremental_single_pair_shortest_path(+Graph, +DistanceArg, +SourceNode, +SinkNode, +Modified, -Path)
- Computes short paths from a source to a sink node
- is_sub_graph(+SubGraph, +SuperGraph)
- Succeeds iff SubGraph is a subgraph of SuperGraph
- make_graph(+NNodes, ++EdgeList, -Graph)
- Creates a graph with minimal overhead
- make_graph_symbolic(+NodeNameArray, ++SymbolicEdgeList, -Graph)
- Creates a graph using node names
- make_random_graph(+NNodes, +NEdges, +AntiParallelFree, +LoopFree, +ParallelFree, -Graph)
- Creates a random graph with the given properties
- make_sub_graph(+Graph, ++Nodes, -SubGraph)
- Creates a subgraph (projection on nodes) of a given graph
- make_undirected_graph(+DirectedGraph, -UndirectedGraph)
- Creates an undirected from a directed graph
- maximum_matching_hopcroft_karp(+G, ++A, ++B, -MaximalM)
- Compute the maximum matching in a bipartite graph using Hopcroft and Karp's algorithm
- minimum_spanning_forest(+Graph, +DistanceArg, -Forest, -ForestSize, -ForestWeight)
- Computes a minimum spanning forest, its size and weight
- minimum_spanning_tree(+Graph, +DistanceArg, -Tree, -TreeWeight)
- Computes a minimum spanning tree and its weight
- node_to_nodename(+Graph, +Node, -NodeName)
- Retrieves the name of a node
- nodename_to_node(+Graph, +NodeName, -Node)
- Retrieves the node number given a node name
- nodenames_to_nodes(+Graph, +NodeNames, -Nodes)
- Returns the names corresponding to a list of nodes
- nodes_to_nodenames(+Graph, +Nodes, -NodeNames)
- Returns the names corresponding to a list of nodes
- possible_path(+SourceNode, +SinkNode, +Tolerance, +Lengths, +Predecessors, -Path)
- Computes an actual path from a predecessors array
- possible_path(+DistanceArg, +SourceNode, +SinkNode, +Tolerance, +Lengths, +Predecessors, -Path)
- Computes an actual path from a predecessors array
- proper_graph(+Graph)
- Tests the integrity of the given graph data structure
- shortest_paths(+Graph, +DistanceArg, +SourceNode, -Paths)
- Computes one shortest path from a single source to every reachable node
- shortest_paths_bellman_ford(+Graph, +DistanceArg, +SourceNode, -Paths)
- Computes one shortest path from a single source to every reachable node (allowing negative distances)
- single_pair_all_short_paths_as_graph(+Graph, +DistanceArg, +SourceNode, +SinkNode, +Tolerance, -Length, -SubGraph)
- Computes all shortest paths from source to sink in form of a subgraph
- single_pair_short_path(+Graph, +DistanceArg, +SourceNode, +SinkNode, +Tolerance, -Path)
- Computes short paths from a source to a sink node
- single_pair_shortest_path(+Graph, +DistanceArg, +SourceNode, +SinkNode, -Path)
- Computes one shortest path from a source to a sink node
- single_pair_shortest_path_bellman_ford(+Graph, +DistanceArg, +SourceNode, +SinkNode, -Path)
- Computes one shortest path from a source to a sink node (allowing negative distances)
- strong_components(+Graph, -StrongComponents)
- Computes the strongly connected components of a graph
- top_sort(+Graph, -Sorted)
- Finds a topological ordering of the graph if one exists
This library is a collection of graph algorithms.
In its simplest form, a graph consists of a (possibly empty) set of nodes (numbered from 1 to NNodes), and zero or more directed edges between these nodes. An edge is represented by the data structure
e(Source, Target, EdgeData)where Source and Target are integers indicating the start and end point of the edge, and EdgeData is an arbitrary data structure holding additional information about the edge, e.g. capacity, distance, weight, name etc. The EdgeData field should have the same structure for all edges in a graph. If there is no information attached to edges, the field should be set to 1 for edges between different nodes and to 0 otherwise. Several library predicates inspect the EdgeData field or an argument of the EdgeData field, e.g. the shortest path predicate can use any numeric component of EdgeData as the distance criterion.
The most efficient way to create a graph is to use make_graph/3 which takes the number of nodes and a list of edges and constructs the graph data structure. For example, the 13-node graph from Sedgewick, figure 32.1 can be created as follows:
make_graph( 13,
[ e(1,6,1),e(1,2,1),e(1,7,1),e(3,1,1),e(4,6,1),e(5,4,1),
e(6,5,1),e(7,5,1),e(7,10,1),e(7,3,1),e(8,7,1),e(8,9,1),e(9,8,1),
e(10,11,1),e(10,12,1),e(10,13,1),e(12,7,1),e(12,13,1),e(13,12,1) ],
Graph).
Often, the nodes have names or other information attached.
This can be added to the Graph using graph_set_nodenames/2 which
takes an existing graph and adds an array of node information
(usually the node names, but any ground term can be used).
For the Sedgewick-graph above, we could invoke
graph_set_nodenames(Graph, [](a,b,c,d,e,f,g,h,i,j,k,l,m))
If nodes have names anyway, it can be more convenient to specify
the edges in terms of these node names rather than node numbers.
Such symbolic edges are written in the form
edge(SourceName, TargetName, EdgeData)where SourceName and TargetName should match an entry (usually the node name) in the graph's nodename-array. A graph can now be constructed by giving a nodename-array and a list of symbolic edges to make_graph_symbolic/3, e.g. to build the same graph as above, use
make_graph_symbolic(
[](a,b,c,d,e,f,g,h,i,j,k,l,m),
[ edge(a,f,1),edge(a,b,1),edge(a,g,1),edge(c,a,1),edge(d,f,1),edge(e,d,1),
edge(f,e,1),edge(g,e,1),edge(g,j,1),edge(g,c,1),edge(h,g,1),edge(h,i,1),edge(i,h,1),
edge(j,k,1),edge(j,l,1),edge(j,m,1),edge(l,g,1),edge(l,m,1),edge(m,l,1) ],
Graph).
Note the use of the functor e/3 for the internal edge representation
and edge/3 for the symbolic edge representation.
There is no special data structure for undirected graphs - they can be represented by having reverse edges corresponding to every edge. It is allowed to have parallel edges (more than one edge from S to T) as long as their EdgeData fields differ.
| Predicate | Sinks | Paths | Determinism | Edge Weights | Tolerance |
|---|---|---|---|---|---|
| shortest_paths/4 | all | one | det | non-negative | no |
| shortest_paths_bellman_ford/4 | all | one | det | arbitrary | no |
| all_short_paths_as_graph/6 | all | all | det | non-negative | yes |
| all_short_paths_as_edges/6 + possible_path/7 | all | all | nondet | non-negative | yes |
| incremental_all_shortest_paths_as_graph/6 | all | all | det | positive | no |
| incremental_all_shortest_paths_as_edges/6 + possible_path/7 | all | all | nondet | positive | no |
| single_pair_shortest_path/5 | single | one | semidet | non-negative | no |
| single_pair_shortest_path_bellman_ford/5 | single | one | semidet | arbitrary | no |
| single_pair_all_short_paths_as_graph/7 | single | all | det | non-negative | yes |
| single_pair_short_path/6 | single | all | nondet | non-negative | yes |
| incremental_single_pair_all_shortest_paths_as_graph/7 | single | all | det | positive | no |
| incremental_single_pair_shortest_path/6 | single | all | nondet | positive | no |