// Uninformed bidirectional search to discover all shortest paths
// between two nodes in an undirected, unweighted graph.
//
// Dan Cross <net!gajendra!cross>

package main

import (
	"fmt"
	"sort"
)

type Vertex int
type VertexSet map[Vertex]bool
type VertexSlice []Vertex

func (vs VertexSlice) Len() int           { return len(vs) }
func (vs VertexSlice) Less(i, j int) bool { return vs[i] < vs[j] }
func (vs VertexSlice) Swap(i, j int)      { vs[i], vs[j] = vs[j], vs[i] }

func MakeVertexSet(vs ...Vertex) VertexSet {
	return VertexSet{}.Insert(vs...)
}

func (s VertexSet) AsSortedSlice() VertexSlice {
	var vs VertexSlice
	for v := range s {
		vs = append(vs, v)
	}
	sort.Sort(vs)
	return vs
}

func (s VertexSet) String() string {
	r := "["
	for n, v := range s.AsSortedSlice() {
		if n > 0 {
			r += ","
		}
		r += fmt.Sprintf(" %d", v)
	}
	r += " ]"
	return r
}

func (s VertexSet) Insert(vs ...Vertex) VertexSet {
	for _, v := range vs {
		s[v] = true
	}
	return s
}

func (s VertexSet) Append(vs VertexSet) VertexSet {
	for v := range vs {
		s.Insert(v)
	}
	return s
}

func (s VertexSet) Intersection(t VertexSet) VertexSet {
	r := MakeVertexSet()
	for v := range s {
		if t[v] {
			r.Insert(v)
		}
	}
	return r
}

type Graph map[Vertex]VertexSet

func MakeGraph(nodes map[Vertex]VertexSlice) Graph {
	g := Graph{}
	for v, adj := range nodes {
		g[v] = MakeVertexSet(adj...)
	}
	return g
}

func (g Graph) String() string {
	r := "{"
	for n, v := range g.NodesAsSortedSlice() {
		if n > 0 {
			r += ","
		}
		r += fmt.Sprintf(" %d:%s", v, g[Vertex(v)])
	}
	r += " }"
	return r
}

func (g Graph) NodesAsVertexSet() VertexSet {
	vs := MakeVertexSet()
	for v := range g {
		vs.Insert(v)
	}
	return vs
}

func (g Graph) NodesAsSortedSlice() VertexSlice {
	return g.NodesAsVertexSet().AsSortedSlice()
}

func (g Graph) AddEdge(a, b Vertex) {
	if g[a] == nil {
		g[a] = MakeVertexSet()
	}
	g[a].Insert(b)
}

func (g Graph) Advance(f VertexSet, visited VertexSet, thunk func(Vertex, Vertex)) VertexSet {
	next := MakeVertexSet()
	for v := range f {
		for v1 := range g[v] {
			if !visited[v1] {
				next.Insert(v1)
				thunk(v1, v)
			}
		}
	}
	visited.Append(next)
	return next
}

func (g Graph) Traverse(I VertexSet, thunk func(Vertex, Vertex)) {
	visited := I
	for Q := I; len(Q) > 0; {
		Q = g.Advance(Q, visited, thunk)
	}
}

func Paths(G Graph, a, b Vertex) Graph {
	if a == b {
		return Graph{}
	}
	f1 := MakeVertexSet(a)
	v1 := MakeVertexSet(a)
	p1 := Graph{}
	f2 := MakeVertexSet(b)
	v2 := MakeVertexSet(b)
	p2 := Graph{}
	I := f1.Intersection(f2)
	for len(I) == 0 && len(f1) > 0 && len(f2) > 0 {
		if len(f1) <= len(f2) {
			f1 = G.Advance(f1, v1, func(a, b Vertex) { p1.AddEdge(a, b) })
		} else {
			f2 = G.Advance(f2, v2, func(a, b Vertex) { p2.AddEdge(a, b) })
		}
		I = f1.Intersection(f2)
	}
	R := Graph{}
	p1.Traverse(I, func(a, b Vertex) { R.AddEdge(a, b) })
	p2.Traverse(I, func(a, b Vertex) { R.AddEdge(b, a) })
	return R
}

func (g Graph) PrintPaths(start Vertex, path []Vertex) {
	if g[start] == nil {
		fmt.Println(path)
		return
	}
	for _, v := range g[start].AsSortedSlice() {
		g.PrintPaths(v, append(path, v))
	}
}

func main() {
	G := MakeGraph(map[Vertex]VertexSlice{
		1:  {2, 3, 7},
		2:  {1, 4, 5},
		3:  {1, 5},
		4:  {2, 6},
		5:  {2, 3, 6, 9},
		6:  {4, 5, 9, 13},
		7:  {1, 8},
		8:  {7, 9},
		9:  {5, 6, 8},
		10: {11, 12, 14},
		11: {10, 13, 14},
		12: {10, 13, 14},
		13: {6, 11, 12},
		14: {10, 11, 12},
	})
	fmt.Println(G)
	P := Paths(G, 1, 14)
	fmt.Println(P)
	P.PrintPaths(1, []Vertex{1})
	P = Paths(G, 1, 1)
	fmt.Println(P)
	P.PrintPaths(1, []Vertex{1})
	P = Paths(G, 1, 2)
	fmt.Println(P)
	P.PrintPaths(1, []Vertex{1})
}