Skip to content

Instantly share code, notes, and snippets.

@danrl
Created April 28, 2019 13:37
Show Gist options
  • Save danrl/cbd4876490e2de71a2ad67226dbc43c3 to your computer and use it in GitHub Desktop.
Save danrl/cbd4876490e2de71a2ad67226dbc43c3 to your computer and use it in GitHub Desktop.
package main
import (
"fmt"
"github.com/danrl/golibby/queue"
"github.com/danrl/golibby/stack"
"github.com/danrl/golibby/graph"
)
func makeGraph() *graph.Graph {
g := graph.New()
for _, s := range []string{
"Flensburg",
"Hamburg",
"Cologne",
"Frankfurt",
"Stuttgart",
"Ulm",
"Munich",
"Nuremberg",
"Erfurt",
"Leipzig",
"Dresden",
"Berlin",
} {
g.NewNode(string(s), nil)
}
g.NewEdge("Flensburg", "Hamburg")
g.NewEdge("Hamburg", "Cologne")
g.NewEdge("Hamburg", "Berlin")
g.NewEdge("Cologne", "Frankfurt")
g.NewEdge("Frankfurt", "Stuttgart")
g.NewEdge("Stuttgart", "Ulm")
g.NewEdge("Ulm", "Munich")
g.NewEdge("Nuremberg", "Frankfurt")
g.NewEdge("Munich", "Nuremberg")
g.NewEdge("Nuremberg", "Leipzig")
g.NewEdge("Leipzig", "Dresden")
g.NewEdge("Leipzig", "Berlin")
g.NewEdge("Dresden", "Berlin")
g.NewEdge("Nuremberg", "Erfurt")
g.NewEdge("Erfurt", "Cologne")
return g
}
func main() {
g := makeGraph()
fmt.Println(g.String())
// finding a path from flensburg to munich
dfs(g, "Flensburg", "Munich")
bfs(g, "Flensburg", "Munich")
doubleBFS(g, "Flensburg", "Munich")
}
func dfs(g *graph.Graph, from, to string) {
// init data structures
next := stack.Stack{}
seen := make(map[string]bool)
// add start node to data structure
next.Push(from)
seen[from] = true
// depth first search
for {
current, err := next.Pop()
if err != nil {
break
}
cur := current.(string)
fmt.Println(cur, "visited")
if cur == to {
fmt.Println("Found it!")
return
}
edges, _ := g.Edges(cur)
for _, e := range edges {
if _, ok := seen[e]; ok {
continue
}
next.Push(e)
seen[e] = true
fmt.Println(e, "added to stack")
}
}
}
func bfs(g *graph.Graph, from, to string) {
// init data structures
q := queue.Queue{}
seen := make(map[string]bool)
prev := make(map[string]string)
// add start node to data structure
q.Add(from)
seen[from] = true
// breadth first search
for {
current, err := q.Remove()
if err != nil {
break
}
cur := current.(string)
fmt.Println(cur, "visited")
if cur == to {
fmt.Println("Found it!")
fmt.Print("Path: ⦿←")
for e, ok := cur, true; ok; e, ok = prev[e] {
fmt.Print(e, "←")
}
fmt.Println("○")
return
}
edges, _ := g.Edges(cur)
for _, e := range edges {
if _, ok := seen[e]; ok {
continue
}
q.Add(e)
seen[e] = true
prev[e] = cur
fmt.Println(e, "added to queue")
}
}
}
func doubleBFS(g *graph.Graph, from, to string) {
// init data structures
qA := queue.Queue{}
seenA := make(map[string]bool)
prevA := make(map[string]string)
qB := queue.Queue{}
seenB := make(map[string]bool)
prevB := make(map[string]string)
// add start and end nodes to data structures
qA.Add(from)
seenA[from] = true
qB.Add(to)
seenB[to] = true
for {
// A
currentA, err := qA.Remove()
if err != nil {
break
}
curA := currentA.(string)
fmt.Println(curA, "visited by A")
if seen, ok := seenB[curA]; curA == to || (ok && seen) {
doubleBFSPrintPath(prevA, prevB, curA)
return
}
edgesA, _ := g.Edges(curA)
for _, e := range edgesA {
if _, ok := seenA[e]; ok {
continue
}
qA.Add(e)
seenA[e] = true
prevA[e] = curA
}
// B
currentB, err := qB.Remove()
if err != nil {
break
}
curB := currentB.(string)
fmt.Println(curB, "visited by B")
if seen, ok := seenA[curB]; curB == from || (ok && seen) {
doubleBFSPrintPath(prevA, prevB, curB)
return
}
edgesB, _ := g.Edges(curB)
for _, e := range edgesB {
if _, ok := seenB[e]; ok {
continue
}
qB.Add(e)
seenB[e] = true
prevB[e] = curB
}
}
}
func doubleBFSPrintPath(a, b map[string]string, meetingPoint string) {
fmt.Println("Meeting point is", meetingPoint)
fmt.Print("A: ")
for e, ok := meetingPoint, true; ok; e, ok = a[e] {
fmt.Print(e, "←")
}
fmt.Print("○\nB: ")
for e, ok := meetingPoint, true; ok; e, ok = b[e] {
fmt.Print(e, "→")
}
fmt.Print("⦿")
}
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment