GraphTest.frink

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 19908 days, 22 hours, 24 minutes ago.