# GraphTest.frink

``` 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       else          gridline.push       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] 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] 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] 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] ```