Download or view Graph.frink in plain text format
/** This class contains utilities for representing a graph (in the sense of
a data structure having nodes and edges) and finding shortest paths through
it.
Each node is an arbitrary data structure that is Hashable (that is, can be
put into a set.) Thus, a node can be a string, an integer, an array, or
other data types, whichever is convenient. Each node should be a unique
identifier.
A Graph can be simply constructed by constructing a Graph and adding edges
(bidirectional or directed). The nodes/vertices will be automatically
constructed.
g = new Graph
g.addBidiEdge["A", "B", 5]
g.addBidiEdge["B", "C", 2]
g.addDirectedEdge["A", "D", 2]
THINK ABOUT: Some of these algorithms, like those for finding the shortest
path are dependent on the weights of the edges. For example, Dijkstra's
algorithm cannot be used on a graph with negative edge weights, in which
case you would use Bellman-Ford's algorithm. If the edges all have the
same weight, then a breadth-first search would be faster than Dijkstra's
algorithm. If you want to find all of the shortest distances between all
pairs of points, you might want to use Floyd's algorithm, which can work
for negative-cost edges but not negative-cost cycles. This code could
keep track if the weights meet these criteria and automatically dispatch
to different algorithms for different graphs.
THINK ABOUT: Should the Graph class contain a flag to track if a graph
contains directed and/or bidirectional edges? Querying this rapidly might
useful.
THINK ABOUT: Should the Graph class contain a flag to track if the weights
of edges of a graph are: 1.) all the same 2.) all positive 3.) all
integers 4.) all floats? This would allow, say, the shortestPath
functions to dispatch to the fastest appropriate algorithm or dispatch to
a Java-compiled faster "helper" algorithm (as is done for Floyd's
algorithm if all edge weights are integers.)
See GraphTest.frink for samples of solvers for various problems.
Some of the implementations of these algorithms come from Steven S. Skiena,
_The Algorithm Design Manual_, Second Edition. References to Skiena are to
this book.
*/
class Graph
{
/** A set of nodes defined in the graph. */
var nodes = new set
/** A dict<node, set<GraphEdge>> of out GraphEdges from each node. */
var outEdges = new dict
/** These are constants defining if a node is undiscovered, discovered, or
processed. The numerical constants are defined in the order they should
be processed so you can do greater-than, less-than, less-than-or equals,
etc. */
/** A undiscovered node. */
class var STATE_UNDISCOVERED = 0
/** A discovered node. */
class var STATE_DISCOVERED = 1
/** A processed node. */
class var STATE_PROCESSED = 2
/** Default constructor. This creates an empty graph. */
new[] :=
{
}
/** Copy constructor. */
new[orig is Graph] :=
{
this.nodes = deepCopy[nodes]
this.outEdges = deepCopy[outEdges]
}
/** Construct a new Graph from an adjacency matrix. The adjacency matrix
should be a square matrix of [from, to] indices where the value at each
cell is the weight of going from "from" to "to".
undefValue indicates the value that is in the array if there is no
connection between the nodes. For example, some adjacency matrixes
represent no connection as 0 while others represent it as -1, some
will represent it as undef, etc.
This will identify each node as an integer from 0 to width-1.
See GraphTest.frink for an example of its usage.
*/
class fromDirectedAdjacencyMatrix[matrix, undefValue] :=
{
d = matrix.dimensions[]
dim = d@0
if length[d] != 2 or d@0 != d@1
{
println["Error: Graph.fromAdjacencyMatrix: adjacency matrix is not square."]
}
graph = new Graph
for fromIdx = 0 to dim-1
for toIdx = 0 to dim-1
{
weight = matrix@fromIdx@toIdx
if weight != undefValue
graph.addDirectedEdge[fromIdx, toIdx, weight]
}
return graph
}
/** Construct a new Graph from an adjacency matrix. The adjacency matrix
should be a square matrix of [from, to] indices where the value at each
cell is the weight of going from "from" to "to".
undefValue indicates the value that is in the array if there is no
connection between the nodes. For example, some adjacency matrixes
represent no connection as 0 while others represent it as -1, some
will represent it as undef, etc.
This will identify each node as an integer from 0 to width-1.
See GraphTest.frink for an example of its usage.
*/
class fromBidiAdjacencyMatrix[matrix, undefValue] :=
{
d = matrix.dimensions[]
dim = d@0
if length[d] != 2 or d@0 != d@1
{
println["Error: Graph.fromAdjacencyMatrix: adjacency matrix is not square."]
}
graph = new Graph
for fromIdx = 0 to dim-1
for toIdx = fromIdx+1 to dim-1
{
weight = matrix@fromIdx@toIdx
if weight != undefValue
graph.addBidiEdge[fromIdx, toIdx, weight]
else
{
weight = matrix@toIdx@fromIdx
if weight != undefValue
graph.addBidiEdge[fromIdx, toIdx, weight]
}
}
return graph
}
/** Construct a new graph from a 2-dimensional array of weights where each
node indicates a numeric weight that is incurred when entering the node
in the grid.
For example, this can be used to solve 4-directional mazes.
undefValue indicates the value that is in the array if there is no
connection between the nodes. For example, some adjacency matrixes
represent no connection as 0 while others represent it as -1, etc.
Each node is a [row, col] array where the row and col are zero-based
integers. So, the top-left node is the array [0, 0].
See GraphTest.frink for examples of its usage.
*/
class from4WayGrid[grid, undefValue] :=
{
[rows, cols] = grid.dimensions[]
graph = new Graph
for row = 0 to rows-1
for col = 0 to cols-1
{
weight = grid@row@col
if weight != undefValue
{
if row > 0
graph.addDirectedEdge[[row-1, col], [row, col], weight]
if col > 0
graph.addDirectedEdge[[row, col-1], [row, col], weight]
if row < rows-1
graph.addDirectedEdge[[row+1, col], [row, col], weight]
if col < cols-1
graph.addDirectedEdge[[row, col+1], [row, col], weight]
}
}
return graph
}
/** Returns a set of out GraphEdges for the specified node. */
getOutEdges[node] :=
{
return outEdges@node
}
/** Returns a set of all bidirectional edges in the graph. Each element of
the set is an [node1, node2, weight] array. The nodes are ordered by
the hashcode of the nodes since node identifiers are not required to
be comparable to each other.
*/
getBidiEdges[] :=
{
result = new set
for node1 = nodes
for edge = getOutEdges[node1]
{
if edge.isBidi[]
{
node2 = edge.getOutNode[]
if hashCode[node1] <= hashCode[node2]
result.put[ [node1, node2, edge.getWeight[]] ]
else
result.put[ [node2, node1, edge.getWeight[]] ]
}
}
return result
}
/** Returns a set of the directed-only edges in the graph. This will not
return bidirectional edges. Each element of the set is an
[fromNode, toNode, weight] array.
*/
getDirectedEdges[] :=
{
result = new set
for node1 = nodes
for edge = getOutEdges[node1]
if edge.isDirected[]
result.put[ [node1, edge.getOutNode[], edge.getWeight[]] ]
return result
}
/** Returns an set of all edges in the graph. Each element of
the set is an [inNode, outNode, weight] array. A bidirectional edge is
represented as two edges, one in each direction. If you want to know if
an edge is bidirectional, and only handle it once, see
getAllEdgesWithFlags[] below.
*/
getAllEdges[] :=
{
result = new set
for node1 = nodes
for edge = getOutEdges[node1]
result.put[ [node1, edge.getOutNode[], edge.getWeight[]] ]
return result
}
/** Returns an set of all edges in the graph. Each element of
the set is an [inNode, outNode, weight, bidi] array.
A bidirectional edge is represented as a single edge with the bidi
flag set to true.
A directed edge is represented as a single edge with the bidi flag set
to false.
*/
getAllEdgesWithFlags[] :=
{
result = new set
for [node1, node2, weight] = getBidiEdges[]
result.put[ [node1, node2, weight, true ] ]
for [node1, node2, weight] = getDirectedEdges[]
result.put[ [node1, node2, weight, false ] ]
return result
}
/** Adds a node (possibly without any out edges) to this graph. */
addNode[node] :=
{
nodes.put[node]
}
/** Gets the weight of the edge from fromNode to toNode or undef if it does
not exist. */
getWeight[fromNode, toNode] :=
{
for edge = outEdges@fromNode
if edge.getOutNode[] == toNode
return edge.getWeight[]
return undef
}
/** Adds a bidirectional edge between node1 and node2 to this graph (and
makes sure the nodes are added to the collection of nodes.)
*/
addBidiEdge[node1, node2, weight=1] :=
{
addNode[node1]
addNode[node2]
outEdges.addToSet[node1, new GraphEdge[node2, weight, true]]
outEdges.addToSet[node2, new GraphEdge[node1, weight, true]]
}
/** Add a directional (one-way) edge between node1 and node2 to this graph
(and making sure the nodes are added to the collection of nodes.) */
addDirectedEdge[node1, node2, weight=1] :=
{
addNode[node1]
addNode[node2]
outEdges.addToSet[node1, new GraphEdge[node2, weight, false]]
}
/** Returns a set of all the nodes in this graph. */
getNodes[] :=
{
return nodes
}
/** Returns the number of nodes in the graph. */
getNodeCount[] :=
{
return length[nodes]
}
/** Returns a set of nodes that are not connected to any other nodes in the
graph. */
getDisconnectedNodes[] :=
{
connected = new set
for [node, edges] = outEdges
{
connected.put[node]
for edge = edges
connected.put[edge.getOutNode[]]
}
return setDifference[nodes, connected]
}
/** Invert this graph by creating a duplicate of this graph with directed
edges pointing in the opposite direction. Bidirectional edges are
duplicated and still pointing in both directions. */
invert[] :=
{
g = new Graph
for node = nodes
{
g.addNode[node]
for edge = getOutEdges[node]
{
if edge.isBidi[]
g.addBidiEdge[node, edge.getOutNode[], edge.getWeight[]]
else // Flip edge
g.addDirectedEdge[edge.getOutNode[], node, edge.getWeight[]]
}
}
return g
}
/** This calculates all shortest paths for all pairs of nodes in the graph
using Floyd's algorithm.
This implements a solver for Floyd's algorithm, also called
Floyd-Warshall which finds *all* the shortest distances through a graph
between all pairs of nodes in a graph.
It runs in O(n^3) time which might sound theoretically no better than n
calls to Dijkstra's algorithm (which is O(n^2) and only finds the best
path between two nodes) but these loops are extremely simple and tight,
which makes it efficient. Floyd's algorithm is also much more efficient
than n calls to Dijkstra's algorithm because of the highly-repeated
nature of shortest paths through a graph. However, the algorithm as
written only finds the *lengths* of the paths between nodes and not the
paths themselves, which is sometimes all you need, which also makes it
much faster than an implementation of n calls to Dijkstra's algorithm
that also finds the paths.
See The Algorithm Design Manual, Stephen Skiena, section 6.3.2.
(but don't trust Skiena's implementation or advice on using MAXINT.)
The actual implementation of this delegates to a highly-optimized Java
version that assumes that edges have integer weights:
https://futureboy.us/temp/Floyd.java
The result value is a GraphAllDistances class (see below) which has
accessor methods to find the distances between pairs of values or turn
the results into a dictionary.
If you only need all the distances from *one* node to all other
reachable nodes (and not all pairs of nodes), use the
allShortestDistances[startNode] method which takes a startNode argument
and uses Dijkstra's algorithm.
*/
allShortestDistances[] :=
{
// This calls a highly-optimized version of Floyd's algorithm in Java
// that assumes weights are integers. It modifies the adjOut matrix
// in place.
[indexToNode, nodeToIndex, adjOut] = toIntAdjacencyMatrix[-1]
callJava["frink.function.Floyd", "shortestDistances", [adjOut, -1]]
return new GraphAllDistances[indexToNode, nodeToIndex, adjOut]
}
/** Makes a 2-dimensional Java array of integer weights representing an
adjacency graph of [from][to] weights. */
toIntAdjacencyMatrix[disconnectedValue] :=
{
i = 0
indexToNode = new dict
nodeToIndex = new dict
for n = nodes
{
indexToNode@i = n
nodeToIndex@n = i
i = i + 1
}
adj = newJavaArray["int", [i,i], disconnectedValue]
for [node1, node2, weight] = getBidiEdges[]
{
i1 = nodeToIndex@node1
i2 = nodeToIndex@node2
adj@i1@i2 = weight
adj@i2@i1 = weight
}
for [node1, node2, weight] = getDirectedEdges[]
{
i1 = nodeToIndex@node1
i2 = nodeToIndex@node2
adj@i1@i2 = weight
}
return [indexToNode, nodeToIndex, adj]
}
/** This inverts the toIntAdjacencyMatrix call and returns a dictionary
where the key is an array [node1,node2] and the value is the weight. */
class fromIntAdjacencyMatrix[indexToNode, nodeToIndex, adj, disconnectedValue] :=
{
size = length[adj]
dist = new dict
for row = 0 to size-1
{
rnode = indexToNode@row
for col = 0 to size-1
{
cnode = indexToNode@col
val = adj@row@col
if val != disconnectedValue
dist@([rnode,cnode]) = val
}
}
return dist
}
/** Calculate the shortest path from startNode to endNode using Dijkstra's
algorithm. Weights of edges cannot be negative. If edge weights are
negative, you will need to use findShortestPathBellmanFord.
The result value is a GraphPath (see below) which contains
the shortest path as a list of nodes and a shortest distance. If no
path is found betwen startNode and endNode, this returns undef.
*/
findShortestPath[startNode, endNode] :=
{
// Degenerate case, bail out quickly
if startNode == endNode
return GraphPath.makeDegeneratePath[startNode]
// Sanity check to ensure that the graph actually *contains* the start
// and end node.
if ! nodes.contains[startNode]
{
println["Graph.findShortestPath: Graph does not contain start node " + startNode]
return undef
}
if ! nodes.contains[endNode]
{
println["Graph.findShortestPath: Graph does not contain end node " + endNode]
return undef
}
/** A set of nodes that have been visited. */
visited = new set
/** A dictionary of distances from node1 to the specified node. The key
is the specified node and the value is the distance to that node. */
distance = new dict
/** This is an OrderedList list of the nodes that have already been
processed and their distances from the start node. It is kept in
order with the smallest distances at the end so they will get popped
efficiently. Each element is an array [node, dist] pair.
TODO: Implement a heap (perhaps a Fibonacci heap or binary heap) for
faster insertion? (Update: This was tested and made no appreciable
improvement over OrderedList.)
*/
shortestList = new OrderedList[{|a,b| b@1 <=> a@1}]
/** This is a dictionary of previous nodes for each node. The key is
the node and the value is the previous node that has the shortest
path to this node. This is eventually used to find the shortest path
by enumerating (backwards) from endNode to startNode. */
previousNodes = new dict
// Initialize the distance to the start node to 0.
distance@startNode = 0
// currNode represents the current node we are visiting.
currNode = startNode
VISITED:
while ! visited.contains[currNode] // While current node is not visited
{
visited.put[currNode] // Mark the current node as visited
// Find the shortest already-found distance from startNode to currNode
currDist = distance@currNode
for outEdge = outEdges@currNode
{
// The prospective node we're examining
nextNode = outEdge.getOutNode[]
// The weight from currNode to nextNode
weight = outEdge.getWeight[]
// The total distance from startNode to the next node
potentialDist = currDist + weight
// Look up shortest distance fron start to nextNode, if it exists
nextDist = distance@nextNode
// Is the other node unchecked (which means nextDist should be
// treated as infinite) or this new distance shorter?
if nextDist == undef or potentialDist < nextDist
{
// Update the shortest-possible distance to nextNode
distance@nextNode = potentialDist
previousNodes@nextNode = currNode
shortestList.insert[ [nextNode, potentialDist] ]
}
}
// We have reached the end node. We can bail out early.
// THINK ABOUT: Should we continue calculating and cache all of the
// results which will return all of the shortest distances
// (in the variable distance) to all nodes from startNode?
if currNode == endNode
break VISITED
// Never found and we have no more nodes to evaluate.
if shortestList.isEmpty[]
return undef
// Pop the node with the next shortest distance
currNode = (shortestList.pop[])@0
}
return GraphPath.makeFromPredecessors[previousNodes, startNode, endNode, distance@endNode]
}
/** Calculate all the shortest distances (but not paths) from startNode to
all the reachable nodes in the graph using Dijkstra's algorithm.
Weights of edges cannot be negative.
The algorithm only finds the *lengths* of the paths between nodes and
not the paths themselves, which is sometimes all you need,
The result value is a dict of <node, distance> pairs.
If no path is found betwen startNode and endNode, the dictionary will
not have a mapping and querying the dictionary for that node will return
undef.
If you need all the distances between *all* pairs of nodes, Floyd's
algorithm with no arguments allShortestDistances[] will be faster than
calling this n times.
*/
allShortestDistances[startNode] :=
{
// Sanity check to ensure that the graph actually *contains* the start
// node.
if ! nodes.contains[startNode]
{
println["Graph.allShortestDistances: Graph does not contain start node " + startNode]
return undef
}
/** A set of nodes that have been visited. */
visited = new set
/** A dictionary of distances from node1 to the specified node. The key
is the specified node and the value is the distance to that node. */
distance = new dict
/** This is an OrderedList list of the nodes that have already been
processed and their distances from the start node. It is kept in
order with the smallest distances at the end so they will get popped
efficiently. Each element is an array [node, dist] pair.
TODO: Implement a heap (perhaps a Fibonacci heap or binary heap) for
faster insertion? (Update: This was tested and made no appreciable
improvement over OrderedList.)
*/
shortestList = new OrderedList[{|a,b| b@1 <=> a@1}]
// Initialize the distance to the start node to 0.
distance@startNode = 0
// currNode represents the current node we are visiting.
currNode = startNode
VISITED:
while ! visited.contains[currNode] // While current node is not visited
{
visited.put[currNode] // Mark the current node as visited
// Find the shortest already-found distance from startNode to currNode
currDist = distance@currNode
for outEdge = outEdges@currNode
{
// The prospective node we're examining
nextNode = outEdge.getOutNode[]
// The weight from currNode to nextNode
weight = outEdge.getWeight[]
// The total distance from startNode to the next node
potentialDist = currDist + weight
// Look up shortest distance fron start to nextNode, if it exists
nextDist = distance@nextNode
// Is the other node unchecked (which means nextDist should be
// treated as infinite) or this new distance shorter?
if nextDist == undef or potentialDist < nextDist
{
// Update the shortest-possible distance to nextNode
distance@nextNode = potentialDist
shortestList.insert[ [nextNode, potentialDist] ]
}
}
// Never found and we have no more nodes to evaluate.
if shortestList.isEmpty[]
return distance
// Pop the node with the next shortest distance
currNode = (shortestList.pop[])@0
}
return distance
}
/** This finds the shortest path through a graph using the Bellman-Ford
algorithm. Unlike Dijkstra's algorithm, Bellman-Ford will work on
graphs with negative weights but not negative-weight cycles.
This is probably slower than Dijkstra's algorithm in most cases as it
runs in time O(numVertices * numEdges).
The result value is a GraphPath (see below) which contains
the shortest path as a list of nodes and a shortest distance. If no
path is found betwen startNode and endNode, or if there is a
negative-weight cycle, this returns undef.
*/
findShortestPathBellmanFord[startNode, endNode] :=
{
// Degenerate case, bail out quickly
if startNode == endNode
return GraphPath.makeDegeneratePath[startNode]
// Sanity check to ensure that the graph actually *contains* the start
// and end node.
if ! nodes.contains[startNode]
{
println["Graph.findShortestPathBellmanFord: Graph does not contain start node " + startNode]
return undef
}
if ! nodes.contains[endNode]
{
println["Graph.findShortestPathBellmanFord: Graph does not contain end node " + endNode]
return undef
}
/** A dictionary of distances from node1 to the specified node. The key
is the specified node and the value is the distance to that node. */
distance = new dict
// Initialize the distance to the first node to 0.
distance@startNode = 0
/** This is a dictionary of previous nodes for each node. The key is
the node and the value is the previous node that has the shortest
path to this node. This is eventually used to find the shortest path
by enumerating (backwards) from endNode to startNode. */
previousNodes = new dict
// Step 2: Relax all edges length[vertices] - 1 times. A simple
// shortest path from startNode to any other vertex can
// have at-most length[vertices] - 1 edges
numVertices = length[nodes]
for i = 1 to numVertices-1
{
for currNode = nodes
{
// The distance from startNode to the current node
currDist = distance@currNode
for currEdge = outEdges@currNode
{
nextNode = currEdge.getOutNode[]
weight = currEdge.getWeight[]
if currDist != undef
{
nextDist = distance@nextNode
// The total distance from startNode to the next node
potentialDist = currDist + weight
// Is the other node unchecked or this new distance shorter?
if nextDist == undef or potentialDist < nextDist
{
// Update the shortest-possible distance to nextNode
distance@nextNode = potentialDist
previousNodes@nextNode = currNode
}
}
}
}
}
// Step 3: check for negative-weight cycles. The above
// step guarantees shortest distances if graph doesn't
// contain negative weight cycle. If we get a shorter
// path, then there is a cycle.
for currNode = nodes
{
// The distance from startNode to the current node
currDist = distance@currNode
for currEdge = outEdges@currNode
{
outNode = currEdge.getOutNode[]
weight = currEdge.getWeight[]
// Negative cycle found.
nextDist = distance@outNode
if currDist != undef and nextDist != undef and currDist + weight < nextDist
return undef
}
}
return GraphPath.makeFromPredecessors[previousNodes, startNode, endNode, distance@endNode]
}
/** This finds the shortest path through a graph using a breadth-first
search. This only works on graphs with identical weights. If the edges
do not have identical weights, you must use Dijkstra's algorithm or,
if the graph contains negative weights, you must use Bellman-Ford's
algorithm.
This works in linear time on a graph with identical weights so it is
faster than Dijkstra's algorithm.
The result value is a GraphPath (see below) which contains
the shortest path as a list of nodes and a shortest distance. If no
path is found betwen startNode and endNode, this returns undef.
TODO: Check to see that all edges have weight 1 and don't use this
algorithm if any weights are different?
See Skiena section 5.6
*/
findShortestPathBreadthFirst[startNode, endNode] :=
{
// Degenerate case, bail out quickly
if startNode == endNode
return GraphPath.makeDegeneratePath[startNode]
// Sanity check to ensure that the graph actually *contains* the start
// and end node.
if ! nodes.contains[startNode]
{
println["Graph.findShortestPathBreadthFirst: Graph does not contain start node " + startNode]
return undef
}
if ! nodes.contains[endNode]
{
println["Graph.findShortestPathBreadthFirst: Graph does not contain end node " + endNode]
return undef
}
// A queue of nodes to visit.
queue = new array
// A dictionary containing the states of the nodes. undef should be
// treated as STATE_UNDISCOVERED
states = new dict
queue.push[startNode]
states@startNode = STATE_DISCOVERED
/** This is a dictionary of previous nodes for each node. The key is
the node and the value is the previous node that has the shortest
path to this node. This is eventually used to find the shortest path
by enumerating (backwards) from endNode to startNode. */
previousNodes = new dict
while ! queue.isEmpty[]
{
currNode = queue.popFirst[]
// Bail out early if we've found the end node.
if currNode == endNode
return GraphPath.makeFromPredecessors[previousNodes, startNode, endNode]
states@currNode = STATE_PROCESSED
for outEdge = outEdges@currNode
{
nextNode = outEdge.getOutNode[]
nextState = states.get[nextNode, STATE_UNDISCOVERED]
if nextState < STATE_DISCOVERED
{
queue.push[nextNode]
states@nextNode = STATE_DISCOVERED
previousNodes@nextNode = currNode
}
}
}
// No path found and out of nodes to evaluate.
return undef
}
/** Calculate the shortest path from startNode to endNode using the A*
(pronounced "A-star") algorithm. This is a heuristic search to which you
must provide a heuristic function that estimates the distance to the
goal.
The function heuristicFunction is a function that takes a node and some
optional arbitrary data and returns an estimate of the distance to
endNode.
For example, a heuristic function that finds the Manhattan distance
between a specified node and a target node that is specified as [row,col]
in the data can be called as:
f = {|node,data|
[row, col] = node
[trow, tcol] = data
return abs[trow-row] + abs[tcol-col]
}
gp = graph.findShortestPathAStar[ [0,0], [rows-1, cols-1], f, [rows-1,cols-1] ]
The result value is a GraphPath (see below) which contains
the shortest path as a list of nodes and a shortest distance. If no
path is found betwen startNode and endNode, this returns undef.
See:
https://web.archive.org/web/20171022224528/https://www.policyalmanac.org/games/aStarTutorial.htm
https://theory.stanford.edu/~amitp/GameProgramming/ImplementationNotes.html
https://www.redblobgames.com/pathfinding/a-star/implementation.html
Please note that there is VERY LITTLE SIMILARITY in the implementations
listed in the last two links (which are written by the same guy?!)
*/
findShortestPathAStar[startNode, endNode, heuristicFunction, data=undef] :=
{
// Degenerate case, bail out quickly
if startNode == endNode
return GraphPath.makeDegeneratePath[startNode]
// Sanity check to ensure that the graph actually *contains* the start
// and end node.
if ! nodes.contains[startNode]
{
println["Graph.findShortestPathAStar: Graph does not contain start node " + startNode]
return undef
}
if ! nodes.contains[endNode]
{
println["Graph.findShortestPathAStar: Graph does not contain end node " + endNode]
return undef
}
/** For node n, fScore[n] := distance[n] + h(n). fScore[n] represents our
current best guess as to how cheap a path could be from start to
finish if it goes through n. */
fScore = new dict
/** This is an OrderedList list of the nodes that have already been
processed and their distances from the start node. It is kept in
order with the smallest distances at the end so they will get popped
efficiently. This uses the fScore dictionary to order the items.
TODO: Implement a heap (perhaps a Fibonacci heap or binary heap) for
faster insertion?
*/
shortestList = new OrderedList[{|a,b,fDict| fDict@b <=> fDict@a}, fScore]
/** A dictionary of distances from startNode to the specified node. The
key is the specified node and the value is the distance to that
node. This is called gNode in some literature. */
distance = new dict
/** A set of closed nodes. */
closed = new set
/** This is a dictionary of previous nodes for each node. The key is
the node and the value is the previous node that has the shortest
path to this node. This is eventually used to find the shortest path
by enumerating (backwards) from endNode to startNode. */
previousNodes = new dict
// Initialize the distance to the first node to 0.
distance@startNode = 0
fScore@startNode = heuristicFunction[startNode, data]
shortestList.insert[ startNode ]
while ! shortestList.isEmpty[]
{
currNode = shortestList.pop[]
// Found solution, bail out.
if currNode == endNode
return GraphPath.makeFromPredecessors[previousNodes, startNode, endNode, distance@endNode]
// Find the shortest already-found distance from startNode to currNode
currDist = distance@currNode
for outEdge = outEdges@currNode
{
// The prospective node we're examining
nextNode = outEdge.getOutNode[]
// The weight from currNode to nextNode
weight = outEdge.getWeight[]
// The total distance from startNode to the next node
potentialDist = currDist + weight
// Look up shortest distance fron start to nextNode, if it exists
nextDist = distance@nextNode
// Is the other node unchecked (which means nextDist should be
// treated as infinite) or this new distance shorter?
if nextDist == undef or potentialDist < nextDist
{
// Update the shortest-possible distance to nextNode
distance@nextNode = potentialDist
previousNodes@nextNode = currNode
fScore@nextNode = potentialDist +
heuristicFunction[nextNode, data]
shortestList.insert[ nextNode ]
}
}
}
// If we reached here, destination node was not found
return undef
}
/** Find a minimal spanning tree using Prim's algorithm. This is very
similar to Dijkstra's algorithm. Only a couple of lines are changed.
The result is a new Graph representing the minimum spanning tree.
If the directed flag is true [default is false], only directed edges
will be created, emanating from startNode. Otherwise, all edges will
be bidirectional.
This *will* work to find the maximum spanning tree by negating all of
the weights. Most graph algorithms do not have this property.
This can find the minimum product spanning tree, which is where we find
the tree that represents the minimal *product* of weights. To do this,
take the logarithm of all the weights.
See Skiena section 6.1.1 and 6.3.1
*/
minimumSpanningTree[startNode, directed=false] :=
{
// Sanity check to ensure that the graph actually *contains* the start
// and end node.
if ! nodes.contains[startNode]
{
println["Graph.minimumSpanningTree: Graph does not contain start node " + startNode]
return undef
}
// TODO: Handle degenerate cases with zero one node (copy this graph.)
/** A set of nodes that have been visited. */
visited = new set
/** A dictionary of distances from node1 to the specified node. The key
is the specified node and the value is the distance to that node. */
distance = new dict
/** This is an OrderedList list of the nodes that have already been
processed and their distances from the start node. It is kept in
order with the smallest distances at the end so they will get popped
efficiently. Each element is an array [node, dist] pair.
TODO: Implement a heap (perhaps a Fibonacci heap or binary heap) for
faster insertion?
*/
shortestList = new OrderedList[{|a,b| b@1 <=> a@1}]
/** This is a dictionary of previous nodes for each node. The key is
the node and the value is the previous node that has the shortest
path to this node. This is eventually used to find the shortest path
by enumerating (backwards) from endNode to startNode. */
previousNodes = new dict
// Initialize the distance to the first node to 0.
distance@startNode = 0
// The current node
currNode = startNode
VISITED:
while ! visited.contains[currNode] // While current node is not visited
{
visited.put[currNode] // Mark the current node as visited
// Find the shortest already-found distance from startNode to currNode
currDist = distance@currNode
for outEdge = outEdges@currNode
{
// The prospective node we're examining
nextNode = outEdge.getOutNode[]
// The weight from currNode to nextNode
weight = outEdge.getWeight[]
// Look up shortest distance fron start to nextNode, if it exists
nextDist = distance@nextNode
// Is the other node unchecked (which means nextDist should be
// treated as infinite) or this new distance shorter?
if (nextDist == undef or weight < nextDist) and (! (visited.contains[nextNode]))
{
// Update the shortest-possible distance to nextNode
distance@nextNode = weight
previousNodes@nextNode = currNode
shortestList.insert[ [nextNode, weight] ]
}
}
// Pop the node with the next shortest distance, if there is one.
// If there is not one, the algorithm SHOULD terminate at the top
// while loop.
if ! shortestList.isEmpty[]
currNode = (shortestList.pop[])@0
}
// Make a new Graph based on previousNodes
return makeFromPredecessors[previousNodes, directed]
}
/** Find a minimal spanning forest using Kruskal's algorithm. It assumes
that all edges are bidirectional.
The result is a new Graph representing the minimum spanning forest.
See Skiena section 6.1.2 and 6.1.3
THINK ABOUT: Some of the nodes from the original graph might be
disconnected from this graph (or from each other.) Add them to the
result as disconnected nodes?
*/
minimumSpanningForest[] :=
{
union = new GraphUnionOfSets[this]
edges = sort[getAllEdgesWithFlags[], byColumn[2]] // Sort by weight
edgeCount = length[edges]
result = new Graph
for [n1, n2, weight] = edges
{
g1 = union.get[n1]
g2 = union.get[n2]
if ! union.inSameComponent[g1, g2]
{
// println[g1.node + " and " + g2.node + " in MST"]
result.addBidiEdge[g1.node, g2.node, getWeight[g1.node, g2.node]]
union.unionOfSets[g1, g2]
}
}
// TODO: Look for unconnected nodes and add those to the forest.
return result
}
/** Makes a new Graph from this Graph and a list of predecessors. This is
used to represent the result of spanning-tree algorithms.
The return value is a new Graph.
*/
makeFromPredecessors[previousNodes, directed=false] :=
{
ret = new Graph
for [node, pred] = previousNodes
{
weight = getWeight[pred, node]
if directed
ret.addDirectedEdge[pred, node, weight]
else
ret.addBidiEdge[pred, node, weight]
}
return ret
}
/** Creates a dot file of this graph that can be plotted or manipulated with
the Graphviz set of tools.
See https://www.graphviz.org/doc/info/lang.html
params:
[directed, extraData]
* directed is a boolean flag which controls if edges are rendered as
a directed or undirected (bidirectional.) If directed is true, this
will draw directed edges. If directed is false, this will render
undirected edges.
* extraData is .dot code that will be placed directly into the file.
For example,
"""fontname="Helvetica,Arial,sans-serif"
node [fontname="Helvetica,Arial,sans-serif"]
edge [fontname="Helvetica,Arial,sans-serif"]"""
This can be written to a file with something like:
w = new Writer["graph6.dot"]
w.print[g.toDotFile[false]]
w.close[]
and then rendered to the desired format with a command-line like:
dot -Tsvg graph6.dot > graph6.svg
where "dot" can be another layout program like "neato" or "circo" or
"twopi".
See https://www.graphviz.org/docs/layouts/
*/
toDotFile[directed, extraData=""] :=
{
if directed
res = "digraph"
else
res = "graph"
res = res + "\n{\n"
if extraData != ""
res = res + extraData + "\n"
// Render all edges
for [node1, node2, weight, bidi] = getAllEdgesWithFlags[]
{
res = res + " \"$node1\" " + (directed ? "->" : "--")
res = res + " \"$node2\"\n"
}
res = res + "}"
return res
}
/** This performs a breadth-first traversal of a Graph. It takes a start
node and an object that implements the GraphWatcher interface (defined
below) which is notified when nodes and edges are visited.
See Skiena section 5.6
*/
breadthFirstTraverse[startNode, watcher is GraphWatcher] :=
{
// Sanity check to ensure that the graph actually *contains* the start
// and end node.
if ! nodes.contains[startNode]
{
println["Graph.breadthFirstTraverse: Graph does not contain start node " + startNode]
return undef
}
// A queue of nodes to visit.
queue = new array
// A dictionary containing the states of the nodes. undef should be
// treated as STATE_UNDISCOVERED
states = new dict
queue.push[startNode]
states@startNode = STATE_DISCOVERED
/** This is a dictionary of previous nodes for each node. The key is
the node and the value is the previous node that has the shortest
path to this node. This is eventually used to find the shortest path
by enumerating (backwards) from endNode to startNode. */
previousNodes = new dict
while ! queue.isEmpty[]
{
currNode = queue.popFirst[]
// do process node early behavior here
watcher.nodeVisited[this, currNode]
states@currNode = STATE_PROCESSED
for outEdge = outEdges@currNode
{
nextNode = outEdge.getOutNode[]
nextState = states.get[nextNode, STATE_UNDISCOVERED]
if nextState < STATE_PROCESSED
{
// Do process edge behavior here
watcher.edgeTraversed[this, currNode, nextNode, outEdge]
}
if nextState < STATE_DISCOVERED
{
queue.push[nextNode]
states@nextNode = STATE_DISCOVERED
previousNodes@nextNode = currNode
}
}
// Do process node late behavior here.
watcher.nodeVisitedLate[this, currNode]
}
// TODO: What should this return?
return previousNodes
}
/** This performs a depth-first traversal of a Graph. It takes a start
node and an object that implements the GraphWatcher interface (defined
below) which is notified when nodes and edges are visited.
This is a modification of Skiena section 5.8 to not be recursive and to
fix apparent bugs in Skiena (e.g. nodes visited multiple times.)
*/
depthFirstTraverse[startNode, watcher is GraphWatcher] :=
{
// Sanity check to ensure that the graph actually *contains* the start
// and end node.
if ! nodes.contains[startNode]
{
println["Graph.depthFirstTraverse: Graph does not contain start node " + startNode]
return undef
}
// A stack of nodes to visit.
stack = new array
// A dictionary containing the states of the nodes. undef should be
// treated as STATE_UNDISCOVERED
states = new dict
stack.push[startNode]
/** This is a dictionary of previous nodes for each node. The key is
the node and the value is the previous node that has the shortest
path to this node. This is eventually used to find the shortest path
by enumerating (backwards) from endNode to startNode. */
previousNodes = new dict
while ! stack.isEmpty[]
{
currNode = stack.pop[]
if states.get[currNode, STATE_UNDISCOVERED] < STATE_DISCOVERED
{
states@currNode = STATE_DISCOVERED
// do process node early behavior here
watcher.nodeVisited[this, currNode]
for outEdge = outEdges@currNode
{
nextNode = outEdge.getOutNode[]
nextState = states.get[nextNode, STATE_UNDISCOVERED]
if nextState < STATE_DISCOVERED
{
previousNodes@nextNode = currNode
// Do process edge behavior here
watcher.edgeTraversed[this, currNode, nextNode, outEdge]
stack.push[nextNode]
} else
if nextState < STATE_PROCESSED
watcher.edgeTraversed[this, currNode, nextNode, outEdge]
}
states@currNode = STATE_PROCESSED
// Do process node late behavior here.
watcher.nodeVisitedLate[this, currNode]
}
}
// TODO: What should this return?
return previousNodes
}
/** Performs a topological sort using Kahn's algorithm. A topological sort
returns an array of nodes such that for every directed edge u->v, node
u comes before v in the ordering. This returns only one possible
topological sort (there may be many.) This will return undef if the
graph is not a directed acyclic graph. You can also think of this as a
temporal ordering. If node u must be performed before node v, this makes
sure that u occurs before v in the ordering.
See:
https://www.geeksforgeeks.org/topological-sorting-indegree-based-solution/
https://en.wikipedia.org/wiki/Topological_sorting
*/
topologicalSort[] :=
{
indeg = indegrees[] // Dict of <node, indegrees>
queue = new array // Make a queue and enqueue all nodes with indegree 0
for [node, deg] = indeg
if deg == 0
queue.push[node]
visited = 0
result = new array
while ! queue.isEmpty[]
{
node = queue.pop[]
result.push[node]
// Iterate through all of the node's neighboring nodes and decrease
// their indegree by 1
for outEdge = getOutEdges[node]
{
outnode = outEdge.getOutNode[]
// Decrement the count. If indegree becomes 0, add it to queue
indeg.increment[outnode, -1]
if indeg@outnode == 0
queue.push[outnode]
}
visited = visited + 1
}
if (visited != getNodeCount[])
{
println["Graph.topologicalSort: Cycle detected in graph. visited was $visited, nodeCount was " + getNodeCount[] + " result would be " + result];
return undef;
}
return result
}
/** This returns an object (TopologicalSorter) that can be used to iterate
through all possible topological sorts of this Graph. It can be used
as the following:
results = g.allTopologicalSorts[]
while r = results.nextResult[]
println[r]
where r is an array of nodes in topological sort order.
See:
https://www.geeksforgeeks.org/all-topological-sorts-of-a-directed-acyclic-graph/
*/
allTopologicalSorts[] :=
{
return new TopologicalSorter[this]
}
/** Calculate the indegrees (that is, the number of edges pointing into
each node.) This returns a dictionary of <node, indegrees>. */
indegrees[] :=
{
indeg = new dict
for node = nodes
indeg@node = 0
for [outNode, edges] = outEdges
for edge = edges
indeg.increment[edge.getOutNode[]]
return indeg
}
}
/** This represents a directed edge in a graph and any associated data,
including its weight. More data may eventually be added, such as an edge
identifier, color, or whatever. */
class GraphEdge
{
/** A node that this is connected to. */
var outNode
/** The weight of the node. This should be numeric. */
var weight
/** A boolean flag indicating if this edge is bidirectional. */
var isBidi
/** Create a new GraphEdge to node with the specified weight. */
new[node, weight, isBidirectional] :=
{
outNode = node
this.weight = weight
isBidi = isBidirectional
}
/** Returns the out node of this edge. */
getOutNode[] :=
{
return outNode
}
/** Returns the weight of this edge. */
getWeight[] :=
{
return weight
}
/** Returns true if the edge is bidirectional, false if it is directed. */
isBidi[] :=
{
return isBidi
}
/** Returns true if the edge is directed, false if it is bidirectional. */
isDirected[] :=
{
return ! isBidi
}
}
/** This represents a path through a graph. It contains a list of the nodes
that make up the path and the total cost to follow the path. */
class GraphPath
{
/** An array of nodes between the nodes. */
var path = new array
/** The distance between the start and end node. */
var distance
/** Appends a node to the path. */
appendNode[node] :=
{
path.push[node]
}
/** Prepends a node to the path. */
prependNode[node] :=
{
path.pushFirst[node]
}
/** Gets the path as an array of nodes. */
getNodes[] :=
{
return path
}
/** Gets the path as an array of nodes. */
getPath[] :=
{
return path
}
/** Sets the total distance of the path */
setDistance[dist] :=
{
distance = dist
}
/** Gets the total distance of the path. */
getDistance[] :=
{
return distance
}
/** Makes a dengenerate path where the start and end node are the same and
distance is zero. */
class makeDegeneratePath[node] :=
{
gp = new GraphPath
gp.setDistance[0]
gp.appendNode[node]
return gp
}
/** Makes a GraphPath from a predecessor dictionary going from startNode to
endNode with the specified distance.
*/
class makeFromPredecessors[previousNodes, startNode, endNode, dist] :=
{
gp = new GraphPath
gp.doMakeFromPredecessors[previousNodes, startNode, endNode]
gp.setDistance[dist]
return gp
}
/** Makes a GraphPath from a predecessor dictionary going from startNode to
endNode with no specified total distance. The distance will be created
from the length of the node list.
*/
class makeFromPredecessors[previousNodes, startNode, endNode] :=
{
gp = new GraphPath
gp.doMakeFromPredecessors[previousNodes, startNode, endNode]
gp.setDistance[length[gp.path] - 1]
return gp
}
/** Internal function which performs the creation of the path from a
predecessor list. Does not set the distance.
THINK ABOUT: Instead of prepending nodes to an array, build an array
or a stack and reverse it which will be slightly faster.
*/
doMakeFromPredecessors[previousNodes, startNode, endNode] :=
{
currNode = endNode
do
{
prependNode[currNode]
currNode = previousNodes@currNode
} while currNode != startNode
prependNode[startNode]
}
}
/** This class contains a set of sets of predecessor nodes. This is used in
Kruskal's algorithm. See Skiena 6.1.3.
Also, for other algorithms, see:
https://en.wikipedia.org/wiki/Disjoint-set_data_structure
This is implemented quite differently, though, as a
dict<node, predecessorDict>.
*/
class GraphUnionOfSets
{
/** An dict<node, GraphSingleSet> of GraphSingleSets */
var dictOfSets
/** Construct a union of sets from the specified graph. */
new[g is Graph] :=
{
/** Initialize what is called the "union-set" in a lot of documentation.
this is actually a dictionary of GraphSingleSet objects. */
nodes = g.getNodes[]
dictOfSets = new dict
for node = nodes
dictOfSets@node = new GraphSingleSet[node]
}
/** Returns the GraphSingleSet corresponding to the specified node. */
get[node] :=
{
return dictOfSets@node
}
/** Find the root of a predecessor list. It returns a GraphSingleSet.
This is used in Kruskal's
algorithm. In the typical documentation of Kruskal's algorithm, this
is just called "find". There are other algorithms that modify the
previousNodes list in-place to optimize subsequent lookups but this is
not one of them. For those, see
https://en.wikipedia.org/wiki/Disjoint-set_data_structure
and
Skiena section 6.1.3
*/
findRoot[fromNode is GraphSingleSet] :=
{
// print["Evaluating " + fromNode.node + "..."]
root = fromNode
parent = root.parent
while parent != root
{
root = parent
parent = root.parent
}
// println["root is " + root.node]
return root
}
/** Makes a "union of sets" of two separate trees. This is often called
"union-sets" in the Graph documentation. */
unionOfSets[node1 is GraphSingleSet, node2 is GraphSingleSet] :=
{
r1 = findRoot[node1]
r2 = findRoot[node2]
if r1 == r2 // Already in the same connected graph.
return
/* Now attach the shorter set as a child of the larger set. */
if r1.size >= r2.size
{
r1.size = r1.size + r2.size
r2.parent = r1
} else
{
r2.size = r1.size + r2.size
r1.parent = r2
}
}
/** Returns true if the two nodes are in the same connected graph. This is
often called "same-component" in the literature. */
inSameComponent[node1 is GraphSingleSet, node2 is GraphSingleSet] :=
{
return findRoot[node1] == findRoot[node2]
}
}
/** This is a helper data structure used by GraphUnionOfSets and Kruskal's
algorithm. It represents aspects of a connected Graph that might be
disconnected from other Graphs.
See:
https://en.wikipedia.org/wiki/Disjoint-set_data_structure
*/
class GraphSingleSet
{
/** The node represented by this set. */
var node
/** The parent GraphSingleSet of this node. */
var parent
/** The size of this whole tree. */
var size
/** Construct a new GraphSingleSet for the specified node. */
new[node] :=
{
this.node = node
parent = this
size = 1
}
}
/** This is a public interface for a set of functions that must be implemented
by a class that wants to observe the traversal of a graph (say, breadth-
first, depth-first, or, for a tree, pre-, post-, or in-order search.)
It contains methods that will be called when a node about to be visited,
when a node has just been visited, (you probably don't need to implement
a handler for both of these) and when an edge is traversed. */
interface GraphWatcher
{
/** This method is called during the traverse of a graph as a node is about
to be visited. You probably want to implement this for most graph
traversals. This is called process_vertex_early in Skiena. */
nodeVisited[g is Graph, node]
/** This method is called during the traverse of a graph after a node has
just been visited. The structure of the Graph object may have been
changed as a result. You probably do not need to implement this method
to do anything. This is called process_vertex_late in Skiena.
*/
nodeVisitedLate[g is Graph, node]
/** This method is called as an edge is about to be traversed. You may
not need to implement this to do anything unless the edge has special
properties (e.g. weights that you need to sum.) */
edgeTraversed[g is Graph, fromNode, toNode, edge is GraphEdge]
}
/** This is a sample class that logs the nodes processed by a traversal
algorithm. It implements the GraphWatcher interface. */
class GraphNodeLogger implements GraphWatcher
{
/** This method is called during the traverse of a graph as a node is about
to be visited. You probably want to implement this for most graph
traversals. This is called process_vertex_early in Skiena. */
nodeVisited[g is Graph, node] :=
{
println["Visited $node"]
}
/** This method is called during the traverse of a graph after a node has
just been visited. The structure of the Graph object may have been
changed as a result. You probably do not need to implement this method
to do anything. This is called process_vertex_late in Skiena.
*/
nodeVisitedLate[g is Graph, node] :=
{
}
/** This method is called as an edge is about to be traversed. You may
not need to implement this to do anything unless the edge has special
properties (e.g. weights that you need to sum.) */
edgeTraversed[g is Graph, fromNode, toNode, edge is GraphEdge] :=
{
}
}
/** This is a sample class that logs the edges traversed by a traversal
algorithm. It implements the GraphWatcher interface. */
class GraphEdgeLogger implements GraphWatcher
{
/** This method is called during the traverse of a graph as a node is about
to be visited. You probably want to implement this for most graph
traversals. This is called process_vertex_early in Skiena. */
nodeVisited[g is Graph, node] :=
{
}
/** This method is called during the traverse of a graph after a node has
just been visited. The structure of the Graph object may have been
changed as a result. You probably do not need to implement this method
to do anything. This is called process_vertex_late in Skiena.
*/
nodeVisitedLate[g is Graph, node] :=
{
}
/** This method is called as an edge is about to be traversed. You may
not need to implement this to do anything unless the edge has special
properties (e.g. weights that you need to sum.) */
edgeTraversed[g is Graph, fromNode, toNode, edge is GraphEdge] :=
{
println["$fromNode -> $toNode"]
}
}
/** This class keeps track of all distances between every pair of nodes in a
graph and has accessor methods. It is generated by Floyd's algorithm in
Graph.allShortestDistances[].
*/
class GraphAllDistances
{
/** A dict from index number to node. */
var indexToNode
/** A dict from node to index number. */
var nodeToIndex
/** A adjacency matrix as a Java int[][]. */
var adj
/** The int value that indicates that nodes are not connected. */
var disconnectedValue = -1
/** A 2-d int adjacency matrix. */
new[indexToNode, nodeToIndex, adj] :=
{
this.indexToNode = indexToNode
this.nodeToIndex = nodeToIndex
this.adj = adj
}
/** Get the distance between node1 and node2. Returns undef if they are
not connected. */
getDistance[node1, node2] :=
{
if node1 == node2
return 0
i1 = nodeToIndex@node1
i2 = nodeToIndex@node2
if i1 != undef and i2 != undef
return adj@i1@i2
else
{
println["GraphAllDistances.getDistance: Nodes not in graph! [$node1, $node2]"]
return undef
}
}
/** This returns a dictionary
where the key is an array [node1,node2] and the value is the weight. */
toDict[] :=
{
size = length[adj]
dist = new dict
for row = 0 to size-1
{
rnode = indexToNode@row
dist@([rnode,rnode]) = 0 // Add trivial 0 distance to self.
COL:
for col = 0 to size-1
{
if col == row
next COL;
cnode = indexToNode@col
val = adj@row@col
if val != disconnectedValue
dist@([rnode,cnode]) = val
}
}
return dist
}
}
/** This class is used to produce all topological sorts of a given graph.
You can use it by calling the following methods on a Graph g.
results = g.allTopologicalSorts[]
while r = results.nextResult[]
println[r]
*/
class TopologicalSorter
{
/** A set of results that have been solved. This is an array of nodes. */
var results = new array
/** Remaining states as a stack of TopologicalSortState. */
var states = new array
/** The graph. */
var graph
/** Construct a new TopologicalSorter that wraps the specified Graph. */
new[g is Graph] :=
{
graph = g
indegrees = graph.indegrees[]
addState[new TopologicalSortState[new set, new array, indegrees, this]]
}
/** Returns the next result, or undef if no more exist. */
nextResult[] :=
{
if ! results.isEmpty[]
return results.pop[]
while ! states.isEmpty[]
{
doSort[states.pop[]]
if ! results.isEmpty[]
return results.pop[]
}
return undef
}
/** Internal function to do one iteration of topological sort. */
doSort[state is TopologicalSortState] :=
{
done = false
for node = graph.getNodes[]
{
if ((! (state.visited.contains[node])) and (state.indeg)@node == 0)
{
i1 = deepCopy[state.indeg]
for outEdge = graph.getOutEdges[node]
i1.increment[outEdge.getOutNode[], -1]
newVis = state.visited.shallowCopy[]
newVis.put[node]
newRes = state.result.shallowCopy[]
newRes.push[node]
// println["state is " + state]
addState[new TopologicalSortState[newVis,
newRes,
i1,
this]]
done = true
}
}
if !done
addResult[state.result]
}
/** Adds a new result, which is an array of nodes. */
addResult[result] :=
{
results.push[result]
}
/** Adds a new state. */
addState[state is TopologicalSortState] :=
{
states.push[state]
}
}
/** This class encapsulates the state of a TopologicalSorter. */
class TopologicalSortState
{
var visited
var result
var indeg
var sorter
new[v, r, i, s is TopologicalSorter] :=
{
visited = v
result = r
indeg = i
sorter = s
}
}
Download or view Graph.frink in plain text format
This is a program written in the programming language Frink.
For more information, view the Frink
Documentation or see More Sample Frink Programs.
Alan Eliasen was born 19965 days, 0 hours, 18 minutes ago.