graph-bfs-dfs.go

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("⦿")
}