Download or view GraphTest.frink in plain text format
use Graph.frink
/** This class tests graph algorithms defined in Graph.frink
*/
/**
Sample 1. From an adjacency matrix.
See the diagrams at
https://www.geeksforgeeks.org/dijkstras-shortest-path-algorithm-greedy-algo-7/
*/
adj = [[0, 4, 0, 0, 0, 0, 0, 8, 0],
[4, 0, 8, 0, 0, 0, 0, 11, 0],
[0, 8, 0, 7, 0, 4, 0, 0, 2],
[0, 0, 7, 0, 9, 14, 0, 0, 0],
[0, 0, 0, 9, 0, 10, 0, 0, 0],
[0, 0, 4, 14, 10, 0, 2, 0, 0],
[0, 0, 0, 0, 0, 2, 0, 1, 6],
[8, 11, 0, 0, 0, 0, 1, 0, 7],
[0, 0, 2, 0, 0, 0, 6, 7, 0]]
//println[formatTable[[["adj = ", formatTableInput[adj]]], "left", "top"]]
println["Sample 1:"]
g = Graph.fromDirectedAdjacencyMatrix[adj, 0]
start = now[]
for n = 0 to 8
{
gp = g.findShortestPath[0, n]
println["Node 0 to node $n: " + gp.getDistance[] + "\t" + gp.getNodes[]]
}
end = now[]
println["Time in Dijkstra: " + (end-start->"ms")]
println[]
//println["Original adjacency:"]
//println[formatTable[adj]]
s = now[]
alldist = g.allShortestDistances[]
for out = 0 to 8
println["Node 0 to node $out: " + alldist.getDistance[0,out]]
e = now[]
println["Time in Floyd: " + (e-s -> "ms")]
println[]
//println[formatTable[alldist.toDict[]]]
/**
Sample 2. From a 4-way grid
Solver for Advent of Code 2021, day 15, part 1
https://adventofcode.com/2021/day/15
This uses Graph.frink to perform the solution and is super-simple!
*/
//lines = readLines["file:input15.txt"]
lines = splitLines["""1163751742
1381373672
2136511328
3694931569
7463417111
1319128137
1359912421
3125421639
1293138521
2311944581"""]
grid = new array
for line = lines
grid.push[eval[toArray[charList[line]]]]
[rows, cols] = grid.dimensions[]
graph = Graph.from4WayGrid[grid, 0]
gp = graph.findShortestPath[ [0,0], [rows-1, cols-1] ]
println["Sample 2:"]
println[" distance is " + gp.getDistance[]]
println[]
// Now graph the path for fun
g = new graphics
g.font["Monospaced", 1]
p = new polyline
for [row,col] = gp.getNodes[]
{
g.text[ grid@row@col, col, row ]
p.addPoint[col,row]
}
g.add[p]
g.show[]
/**
Sample 2.1 From a 4-way grid using A* search
Solver for Advent of Code 2021, day 15, part 1
https://adventofcode.com/2021/day/15
This uses Graph.frink to perform the solution and is super-simple!
*/
//lines = readLines["file:input15.txt"]
lines = splitLines["""1163751742
1381373672
2136511328
3694931569
7463417111
1319128137
1359912421
3125421639
1293138521
2311944581"""]
grid = new array
for line = lines
grid.push[eval[toArray[charList[line]]]]
[rows, cols] = grid.dimensions[]
graph = Graph.from4WayGrid[grid, 0]
f = {|node,data|
[row, col] = node
[trow, tcol] = data
return abs[trow-row] + abs[tcol-col]
}
gpa = graph.findShortestPathAStar[ [0,0], [rows-1, cols-1], f, [rows-1,cols-1] ]
gpd = graph.findShortestPath[ [0,0], [rows-1, cols-1]]
println["Sample 2.1:"]
println[" distance (A*) is " + gpa.getDistance[]]
println[" distance (Dijkstra) is " + gpd.getDistance[]]
println[]
// Now graph the path for fun
g = new graphics
g.font["Monospaced", 1]
p = new polyline
for [row,col] = gp.getNodes[]
{
g.text[ grid@row@col, col, row ]
p.addPoint[col,row]
}
g.add[p]
g.show[]
/**
Sample 3. Solver for Crash and Compile problem.
Find the shortest path between nodes.
*/
line = """(N100,N33),(N44,N27),(N16,N44),(N1,N9),(N16,N22),(N49,N34),(N33,N16),(N22,N0),(N3,N16),(N41,N44),(N3,N35),(N27,N8),(N0,N8),(N9,N0),(N17,N35),(N26,N46)"""
graph = new Graph
for [node1, node2] = line =~ %r/\((.*?),(.*?)\)/g
graph.addBidiEdge[node1, node2]
gp = graph.findShortestPathBreadthFirst["N0", "N100"]
println["Sample 3:"]
println["Node 0 to node $n: " + gp.getDistance[] + "\t" + gp.getNodes[]]
println[]
/**
Sample 4. Maze solver. Crash and Compile DC25 escape easy problem.
https://bitbucket.org/crashandcompile/dc25-problems/src/master/
*/
maze = ["========S=============",
"======== = ========",
"== = = = = = =",
"== = === = = = = =",
"== = ==== = = = ==",
"== = == = = =",
"=== ===== == == =",
"== = = = = == == =",
"E == = == = = =",
"= === = = = = ==",
"= == ==== = ===",
" = = = = == = ===",
"= = = == = == ==",
"== ==== = = = == =",
"== == = == = = = =",
"== = = = = = =",
"==== === = = == =",
"== == = = = = = ==",
"== = = = == = =",
"== ==== = = = === =",
"== = == =",
"======================",
"%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%"]
graph = new Graph
grid = new array
row = 0
start = undef
end = undef
g = new graphics
g.font["Monospaced", 1]
LINES:
for line = maze
{
if line =~ %r/%/
break LINES
gridline = new array
grid.push[gridline]
col = 0
for c = charList[line]
{
g.text[c,col,row]
if c == "S"
start = [row, col]
if c == "E"
end = [row, col]
if c == " " or c == "S" or c == "E"
gridline.push[1]
else
gridline.push[0]
col = col + 1
}
row = row + 1
}
println["Sample 4:"]
graph = Graph.from4WayGrid[grid, 0]
gp = graph.findShortestPathBreadthFirst[ start, end ]
p = new polyline
for [y, x] = gp.getPath[]
{
println["(" + (x+1) + "," + (y+1) + ")"]
p.addPoint[x, y]
}
g.add[p]
g.show[]
/** Test 5. Test for directed graph with negative edge weights which requires
the Bellman-Ford algorithm. See
https://www.geeksforgeeks.org/bellman-ford-algorithm-dp-23/
*/
graph = new Graph
graph.addDirectedEdge[0, 1, -1]
graph.addDirectedEdge[0, 2, 4]
graph.addDirectedEdge[1, 2, 3]
graph.addDirectedEdge[1, 3, 2]
graph.addDirectedEdge[1, 4, 2]
graph.addDirectedEdge[3, 2, 5]
graph.addDirectedEdge[3, 1, 1]
graph.addDirectedEdge[4, 3, -3]
println[]
println["Sample 5:"]
for n = 0 to 4
{
gp = graph.findShortestPathBellmanFord[0, n]
println["Node 0 to node $n: " + gp.getDistance[] + "\t" + gp.getNodes[]]
}
println[]
println["inverted:"]
gi = graph.invert[]
for n = 0 to 4
{
gp = gi.findShortestPathBellmanFord[n, 0]
println["Node $n to node 0: " + gp.getDistance[] + "\t" + gp.getNodes[]]
}
println[]
/** Sample 6. Create a minimum spanning tree.
See:
https://www.geeksforgeeks.org/prims-minimum-spanning-tree-mst-greedy-algo-5/
*/
// This is the graph fron Skiena Figure 6.3
g = new Graph
g.addBidiEdge["A", "B", 5]
g.addBidiEdge["A", "D", 7]
g.addBidiEdge["A", "E", 12]
g.addBidiEdge["B", "C", 7]
g.addBidiEdge["B", "D", 9]
g.addBidiEdge["C", "D", 4]
g.addBidiEdge["C", "F", 2]
g.addBidiEdge["C", "G", 5]
g.addBidiEdge["D", "E", 4]
g.addBidiEdge["D", "F", 3]
g.addBidiEdge["E", "F", 7]
g.addBidiEdge["F", "G", 2]
//println[formatTable[[["adj =", formatTableInput[adj]]], "left", "top"]]
g2 = g.minimumSpanningTree["A", false]
edges = sort[g2.getBidiEdges[], byColumn[0]]
edges.pushFirst[["from", "to", "weight"]]
println["Sample 6:"]
println[formatTable[edges]]
println[]
// Output a graphviz .dot file. This can be rendered with something like:
// dot -Tsvg graph6.dot > graph6.svg
dot = g.toDotFile[false, """node [fontname="sans-serif"]"""]
w = new Writer["graph6.dot"]
w.print[dot]
w.close[]
/** Sample 7. Create a minimal spanning tree using Kruskal's algorithm */
g3 = g.minimumSpanningForest[]
edges = sort[g3.getAllEdgesWithFlags[], byColumn[0]]
edges.pushFirst[["from", "to", "weight"]]
println["Sample 7:"]
println[formatTable[edges]]
println[]
/** Sample 8. Create a minimal spanning forest using Kruskal's algorithm */
// This is the graph fron Skiena Figure 6.3 plus some diconnected edges.
g = new Graph
g.addBidiEdge["A", "B", 5]
g.addBidiEdge["A", "D", 7]
g.addBidiEdge["A", "E", 12]
g.addBidiEdge["B", "C", 7]
g.addBidiEdge["B", "D", 9]
g.addBidiEdge["C", "D", 4]
g.addBidiEdge["C", "F", 2]
g.addBidiEdge["C", "G", 5]
g.addBidiEdge["D", "E", 4]
g.addBidiEdge["D", "F", 3]
g.addBidiEdge["E", "F", 7]
g.addBidiEdge["F", "G", 2]
// The following are disconnected from the main graph
g.addBidiEdge["H", "I", 1]
g.addBidiEdge["J", "K", 10]
g.addBidiEdge["K", "L", 5]
g.addNode["M"]
g4 = g.minimumSpanningForest[]
edges = sort[g4.getAllEdgesWithFlags[], byColumn[0]]
edges.pushFirst[["from", "to", "weight"]]
println["Sample 8:"]
println[formatTable[edges]]
println[]
println["Disconnected nodes: " + g.getDisconnectedNodes[]]
/** Sample 9. Performs a breadth-first search of a graph and prints the nodes
visited. */
g9 = new Graph
// This is the graph in figure 5.9 of Skiena
g9.addBidiEdge[1,6]
g9.addBidiEdge[1,5]
g9.addBidiEdge[1,2]
g9.addBidiEdge[2,3]
g9.addBidiEdge[2,5]
g9.addBidiEdge[3,4]
g9.addBidiEdge[4,5]
println["\nSample 9: Breadth first traversal"]
watcher = new GraphNodeLogger
g9.breadthFirstTraverse[1, watcher]
/** Sample 10. Performs a depth-first search of a graph and prints the nodes
visited. */
println["\nSample 10: depth-first traversal"]
watcher = new GraphNodeLogger
g9.depthFirstTraverse[1, watcher]
/** Sample 11. Topological sort. */
println["\nSample 11: topological sort"]
// Example from https://en.wikipedia.org/wiki/Topological_sorting
g11 = new Graph
g11.addDirectedEdge[5,11]
g11.addDirectedEdge[11,2]
g11.addDirectedEdge[11,9]
g11.addDirectedEdge[11,10]
g11.addDirectedEdge[7,11]
g11.addDirectedEdge[7,8]
g11.addDirectedEdge[8,9]
g11.addDirectedEdge[3,8]
g11.addDirectedEdge[3,10]
println[g11.topologicalSort[]]
// Sample 12: All topological sorts
println["\nSample 12: all topological sorts"]
s12 = g11.allTopologicalSorts[]
while r = s12.nextResult[]
println[r]
// Sample 13: All topological sorts of example page
// From:
// https://www.geeksforgeeks.org/all-topological-sorts-of-a-directed-acyclic-graph/
println["\nSample 13: all topological sorts 2"]
g13 = new Graph
g13.addDirectedEdge[5,0]
g13.addDirectedEdge[5,2]
g13.addDirectedEdge[4,0]
g13.addDirectedEdge[4,1]
g13.addDirectedEdge[2,3]
g13.addDirectedEdge[3,1]
s13 = g13.allTopologicalSorts[]
while r = s13.nextResult[]
println[r]
Download or view GraphTest.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 19966 days, 3 hours, 42 minutes ago.