[ The ECLiPSe Libraries | Reference Manual | Alphabetic Index ]

library(graph_algorithms)

Collection of graph algorithms

Predicates

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

Description

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.

Visualization

You can use library(graphviz) or lib(viewable) to draw these graphs.

Overview of Shortest-Path Functionality

This library provides a number of different variants of shortest path algorithms, of which the following table gives an overview:
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

To-do list

The following operations should be added:

About


Generated from graph_algorithms.eci on Mon Mar 31 03:16:27 2008