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 19972 days, 19 hours, 10 minutes ago.