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:"] println["connected components from 0: " + graph.countConnected[0]] println["connected components from 1: " + graph.countConnected[1]] println["connected components from 2: " + graph.countConnected[2]] println["connected components from 3: " + graph.countConnected[3]] println["connected components from 4: " + graph.countConnected[4]] println["connected components from 5: " + graph.countConnected[5]] // Fake node 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]