func TestBetweenness(t *testing.T) {
	for i, test := range betweennessTests {
		g := concrete.NewGraph()
		for u, e := range test.g {
			// Add nodes that are not defined by an edge.
			if !g.Has(concrete.Node(u)) {
				g.AddNode(concrete.Node(u))
			}
			for v := range e {
				g.SetEdge(concrete.Edge{F: concrete.Node(u), T: concrete.Node(v)}, 0)
			}
		}
		got := Betweenness(g)
		prec := 1 - int(math.Log10(test.wantTol))
		for n := range test.g {
			wantN, gotOK := got[n]
			gotN, wantOK := test.want[n]
			if gotOK != wantOK {
				t.Errorf("unexpected betweenness result for test %d, node %d", i, n)
			}
			if !floats.EqualWithinAbsOrRel(gotN, wantN, test.wantTol, test.wantTol) {
				t.Errorf("unexpected betweenness result for test %d:\ngot: %v\nwant:%v",
					i, orderedFloats(got, prec), orderedFloats(test.want, prec))
				break
			}
		}
	}
}

func TestWalkAll(t *testing.T) {
	for i, test := range walkAllTests {
		g := concrete.NewGraph()

		for u, e := range test.g {
			if !g.Has(concrete.Node(u)) {
				g.AddNode(concrete.Node(u))
			}
			for v := range e {
				if !g.Has(concrete.Node(v)) {
					g.AddNode(concrete.Node(v))
				}
				g.SetEdge(concrete.Edge{F: concrete.Node(u), T: concrete.Node(v)}, 0)
			}
		}
		type walker interface {
			WalkAll(g graph.Undirected, before, after func(), during func(graph.Node))
		}
		for _, w := range []walker{
			&traverse.BreadthFirst{},
			&traverse.DepthFirst{},
		} {
			var (
				c  []graph.Node
				cc [][]graph.Node
			)
			switch w := w.(type) {
			case *traverse.BreadthFirst:
				w.EdgeFilter = test.edge
			case *traverse.DepthFirst:
				w.EdgeFilter = test.edge
			default:
				panic(fmt.Sprintf("bad walker type: %T", w))
			}
			during := func(n graph.Node) {
				c = append(c, n)
			}
			after := func() {
				cc = append(cc, []graph.Node(nil))
				cc[len(cc)-1] = append(cc[len(cc)-1], c...)
				c = c[:0]
			}
			w.WalkAll(g, nil, after, during)

			got := make([][]int, len(cc))
			for j, c := range cc {
				ids := make([]int, len(c))
				for k, n := range c {
					ids[k] = n.ID()
				}
				sort.Ints(ids)
				got[j] = ids
			}
			sort.Sort(internal.BySliceValues(got))
			if !reflect.DeepEqual(got, test.want) {
				t.Errorf("unexpected connected components for test %d using %T:\ngot: %v\nwant:%v", i, w, got, test.want)
			}
		}
	}
}

func TestBronKerbosch(t *testing.T) {
	for i, test := range bronKerboschTests {
		g := concrete.NewGraph()
		for u, e := range test.g {
			// Add nodes that are not defined by an edge.
			if !g.Has(concrete.Node(u)) {
				g.AddNode(concrete.Node(u))
			}
			for v := range e {
				g.SetEdge(concrete.Edge{F: concrete.Node(u), T: concrete.Node(v)}, 0)
			}
		}
		cliques := topo.BronKerbosch(g)
		got := make([][]int, len(cliques))
		for j, c := range cliques {
			ids := make([]int, len(c))
			for k, n := range c {
				ids[k] = n.ID()
			}
			sort.Ints(ids)
			got[j] = ids
		}
		sort.Sort(internal.BySliceValues(got))
		if !reflect.DeepEqual(got, test.want) {
			t.Errorf("unexpected cliques for test %d:\ngot: %v\nwant:%v", i, got, test.want)
		}
	}
}

func TestConnectedComponents(t *testing.T) {
	for i, test := range connectedComponentTests {
		g := concrete.NewGraph()

		for u, e := range test.g {
			if !g.Has(concrete.Node(u)) {
				g.AddNode(concrete.Node(u))
			}
			for v := range e {
				if !g.Has(concrete.Node(v)) {
					g.AddNode(concrete.Node(v))
				}
				g.SetEdge(concrete.Edge{F: concrete.Node(u), T: concrete.Node(v)}, 0)
			}
		}
		cc := topo.ConnectedComponents(g)
		got := make([][]int, len(cc))
		for j, c := range cc {
			ids := make([]int, len(c))
			for k, n := range c {
				ids[k] = n.ID()
			}
			sort.Ints(ids)
			got[j] = ids
		}
		sort.Sort(internal.BySliceValues(got))
		if !reflect.DeepEqual(got, test.want) {
			t.Errorf("unexpected connected components for test %d %T:\ngot: %v\nwant:%v", i, g, got, test.want)
		}
	}
}

func newSmallGonumGraph() *concrete.Graph {
	eds := []struct{ n1, n2, edgeCost int }{
		{1, 2, 7},
		{1, 3, 9},
		{1, 6, 14},
		{2, 3, 10},
		{2, 4, 15},
		{3, 4, 11},
		{3, 6, 2},
		{4, 5, 7},
		{5, 6, 9},
	}
	g := concrete.NewGraph()
	for n := concrete.Node(1); n <= 6; n++ {
		g.AddNode(n)
	}
	for _, ed := range eds {
		e := concrete.Edge{
			concrete.Node(ed.n1),
			concrete.Node(ed.n2),
		}
		g.AddUndirectedEdge(e, float64(ed.edgeCost))
	}
	return g
}

func TestDepthFirst(t *testing.T) {
	for i, test := range depthFirstTests {
		g := concrete.NewGraph()
		for u, e := range test.g {
			// Add nodes that are not defined by an edge.
			if !g.Has(concrete.Node(u)) {
				g.AddNode(concrete.Node(u))
			}
			for v := range e {
				g.SetEdge(concrete.Edge{F: concrete.Node(u), T: concrete.Node(v)}, 0)
			}
		}
		w := traverse.DepthFirst{
			EdgeFilter: test.edge,
		}
		var got []int
		final := w.Walk(g, test.from, func(n graph.Node) bool {
			if test.until != nil && test.until(n) {
				return true
			}
			got = append(got, n.ID())
			return false
		})
		if !test.final[final] {
			t.Errorf("unexepected final node for test %d:\ngot:  %v\nwant: %v", i, final, test.final)
		}
		sort.Ints(got)
		if test.want != nil && !reflect.DeepEqual(got, test.want) {
			t.Errorf("unexepected DFS traversed nodes for test %d:\ngot:  %v\nwant: %v", i, got, test.want)
		}
	}
}

func TestBetweennessWeighted(t *testing.T) {
	for i, test := range betweennessTests {
		g := concrete.NewGraph(0, math.Inf(1))
		for u, e := range test.g {
			// Add nodes that are not defined by an edge.
			if !g.Has(concrete.Node(u)) {
				g.AddNode(concrete.Node(u))
			}
			for v := range e {
				g.SetEdge(concrete.Edge{F: concrete.Node(u), T: concrete.Node(v), W: 1})
			}
		}

		p, ok := path.FloydWarshall(g)
		if !ok {
			t.Errorf("unexpected negative cycle in test %d", i)
			continue
		}

		got := BetweennessWeighted(g, p)
		prec := 1 - int(math.Log10(test.wantTol))
		for n := range test.g {
			gotN, gotOK := got[n]
			wantN, wantOK := test.want[n]
			if gotOK != wantOK {
				t.Errorf("unexpected betweenness existence for test %d, node %d", i, n)
			}
			if !floats.EqualWithinAbsOrRel(gotN, wantN, test.wantTol, test.wantTol) {
				t.Errorf("unexpected betweenness result for test %d:\ngot: %v\nwant:%v",
					i, orderedFloats(got, prec), orderedFloats(test.want, prec))
				break
			}
		}
	}
}

func undirectedEdgeAttrGraphFrom(g []set, attr map[edge][]Attribute) graph.Graph {
	dg := concrete.NewGraph(0, math.Inf(1))
	for u, e := range g {
		for v := range e {
			dg.SetEdge(attrEdge{from: concrete.Node(u), to: concrete.Node(v), attr: attr[edge{from: u, to: v}]})
		}
	}
	return dg
}

func undirectedGraphFrom(g []set) graph.Graph {
	dg := concrete.NewGraph(0, math.Inf(1))
	for u, e := range g {
		for v := range e {
			dg.SetEdge(concrete.Edge{F: concrete.Node(u), T: concrete.Node(v)})
		}
	}
	return dg
}

func TestExhaustiveAStar(t *testing.T) {
	g := concrete.NewGraph()
	nodes := []locatedNode{
		{id: 1, x: 0, y: 6},
		{id: 2, x: 1, y: 0},
		{id: 3, x: 8, y: 7},
		{id: 4, x: 16, y: 0},
		{id: 5, x: 17, y: 6},
		{id: 6, x: 9, y: 8},
	}
	for _, n := range nodes {
		g.AddNode(n)
	}

	edges := []weightedEdge{
		{from: g.Node(1), to: g.Node(2), cost: 7},
		{from: g.Node(1), to: g.Node(3), cost: 9},
		{from: g.Node(1), to: g.Node(6), cost: 14},
		{from: g.Node(2), to: g.Node(3), cost: 10},
		{from: g.Node(2), to: g.Node(4), cost: 15},
		{from: g.Node(3), to: g.Node(4), cost: 11},
		{from: g.Node(3), to: g.Node(6), cost: 2},
		{from: g.Node(4), to: g.Node(5), cost: 7},
		{from: g.Node(5), to: g.Node(6), cost: 9},
	}
	for _, e := range edges {
		g.SetEdge(e, e.cost)
	}

	heuristic := func(u, v graph.Node) float64 {
		lu := u.(locatedNode)
		lv := v.(locatedNode)
		return math.Hypot(lu.x-lv.x, lu.y-lv.y)
	}

	if ok, edge, goal := isMonotonic(g, heuristic); !ok {
		t.Fatalf("non-monotonic heuristic at edge:%v for goal:%v", edge, goal)
	}

	ps := path.DijkstraAllPaths(g)
	for _, start := range g.Nodes() {
		for _, goal := range g.Nodes() {
			pt, _ := path.AStar(start, goal, g, heuristic)
			gotPath, gotWeight := pt.To(goal)
			wantPath, wantWeight, _ := ps.Between(start, goal)
			if gotWeight != wantWeight {
				t.Errorf("unexpected path weight from %v to %v result: got:%s want:%s",
					start, goal, gotWeight, wantWeight)
			}
			if !reflect.DeepEqual(gotPath, wantPath) {
				t.Errorf("unexpected path from %v to %v result:\ngot: %v\nwant:%v",
					start, goal, gotPath, wantPath)
			}
		}
	}
}

func undirectedStructuredGraphFrom(c []edge, g ...[]set) graph.Graph {
	s := &structuredGraph{Graph: concrete.NewGraph(0, math.Inf(1))}
	var base int
	for i, sg := range g {
		sub := concrete.NewGraph(0, math.Inf(1))
		for u, e := range sg {
			for v := range e {
				ce := concrete.Edge{F: concrete.Node(u + base), T: concrete.Node(v + base)}
				sub.SetEdge(ce)
			}
		}
		s.sub = append(s.sub, namedGraph{id: i, Graph: sub})
		base += len(sg)
	}
	for _, e := range c {
		s.SetEdge(concrete.Edge{F: concrete.Node(e.from), T: concrete.Node(e.to)})
	}
	return s
}

func undirectedNamedIDGraphFrom(g []set) graph.Graph {
	dg := concrete.NewGraph(0, math.Inf(1))
	for u, e := range g {
		nu := namedNode{id: u, name: alpha[u : u+1]}
		for v := range e {
			nv := namedNode{id: v, name: alpha[v : v+1]}
			dg.SetEdge(concrete.Edge{F: nu, T: nv})
		}
	}
	return dg
}

func undirectedSubGraphFrom(g []set, s map[int][]set) graph.Graph {
	var base int
	subs := make(map[int]subGraph)
	for i, sg := range s {
		sub := concrete.NewGraph(0, math.Inf(1))
		for u, e := range sg {
			for v := range e {
				ce := concrete.Edge{F: concrete.Node(u + base), T: concrete.Node(v + base)}
				sub.SetEdge(ce)
			}
		}
		subs[i] = subGraph{id: i, Graph: sub}
		base += len(sg)
	}

	dg := concrete.NewGraph(0, math.Inf(1))
	for u, e := range g {
		var nu graph.Node
		if sg, ok := subs[u]; ok {
			sg.id += base
			nu = sg
		} else {
			nu = concrete.Node(u + base)
		}
		for v := range e {
			var nv graph.Node
			if sg, ok := subs[v]; ok {
				sg.id += base
				nv = sg
			} else {
				nv = concrete.Node(v + base)
			}
			dg.SetEdge(concrete.Edge{F: nu, T: nv})
		}
	}
	return dg
}

func undirectedNamedIDNodeAttrGraphFrom(g []set, attr [][]Attribute) graph.Graph {
	dg := concrete.NewGraph(0, math.Inf(1))
	for u, e := range g {
		var at []Attribute
		if u < len(attr) {
			at = attr[u]
		}
		nu := namedAttrNode{id: u, name: alpha[u : u+1], attr: at}
		for v := range e {
			if v < len(attr) {
				at = attr[v]
			}
			nv := namedAttrNode{id: v, name: alpha[v : v+1], attr: at}
			dg.SetEdge(concrete.Edge{F: nu, T: nv})
		}
	}
	return dg
}

func undirectedNodeAttrGraphFrom(g []set, attr [][]Attribute) graph.Graph {
	dg := concrete.NewGraph()
	for u, e := range g {
		var at []Attribute
		if u < len(attr) {
			at = attr[u]
		}
		nu := attrNode{id: u, attr: at}
		for v := range e {
			if v < len(attr) {
				at = attr[v]
			}
			nv := attrNode{id: v, attr: at}
			dg.SetEdge(concrete.Edge{F: nu, T: nv}, 0)
		}
	}
	return dg
}

func TestMaxID(t *testing.T) {
	g := concrete.NewGraph()
	nodes := make(map[graph.Node]struct{})
	for i := concrete.Node(0); i < 3; i++ {
		g.AddNode(i)
		nodes[i] = struct{}{}
	}
	g.RemoveNode(concrete.Node(0))
	delete(nodes, concrete.Node(0))
	g.RemoveNode(concrete.Node(2))
	delete(nodes, concrete.Node(2))
	n := concrete.Node(g.NewNodeID())
	g.AddNode(n)
	if !g.Has(n) {
		t.Error("added node does not exist in graph")
	}
	if _, exists := nodes[n]; exists {
		t.Errorf("Created already existing node id: %v", n.ID())
	}
}

func undirectedPortedAttrGraphFrom(g []set, attr [][]Attribute, ports map[edge]portedEdge) graph.Graph {
	dg := concrete.NewGraph(0, math.Inf(1))
	for u, e := range g {
		var at []Attribute
		if u < len(attr) {
			at = attr[u]
		}
		nu := attrNode{id: u, attr: at}
		for v := range e {
			if v < len(attr) {
				at = attr[v]
			}
			pe := ports[edge{from: u, to: v}]
			pe.from = nu
			pe.to = attrNode{id: v, attr: at}
			dg.SetEdge(pe)
		}
	}
	return dg
}

func TestVertexOrdering(t *testing.T) {
	for i, test := range vOrderTests {
		g := concrete.NewGraph()
		for u, e := range test.g {
			// Add nodes that are not defined by an edge.
			if !g.Has(concrete.Node(u)) {
				g.AddNode(concrete.Node(u))
			}
			for v := range e {
				g.SetEdge(concrete.Edge{F: concrete.Node(u), T: concrete.Node(v)}, 0)
			}
		}
		order, core := topo.VertexOrdering(g)
		if len(core)-1 != test.wantK {
			t.Errorf("unexpected value of k for test %d: got: %d want: %d", i, len(core)-1, test.wantK)
		}
		var offset int
		for k, want := range test.wantCore {
			sort.Ints(want)
			got := make([]int, len(want))
			for j, n := range order[len(order)-len(want)-offset : len(order)-offset] {
				got[j] = n.ID()
			}
			sort.Ints(got)
			if !reflect.DeepEqual(got, want) {
				t.Errorf("unexpected %d-core for test %d:\ngot: %v\nwant:%v", got, test.wantCore)
			}

			for j, n := range core[k] {
				got[j] = n.ID()
			}
			sort.Ints(got)
			if !reflect.DeepEqual(got, want) {
				t.Errorf("unexpected %d-core for test %d:\ngot: %v\nwant:%v", got, test.wantCore)
			}
			offset += len(want)
		}
	}
}

func TestIsPath(t *testing.T) {
	dg := concrete.NewDirectedGraph()
	if !topo.IsPathIn(dg, nil) {
		t.Error("IsPath returns false on nil path")
	}
	p := []graph.Node{concrete.Node(0)}
	if topo.IsPathIn(dg, p) {
		t.Error("IsPath returns true on nonexistant node")
	}
	dg.AddNode(p[0])
	if !topo.IsPathIn(dg, p) {
		t.Error("IsPath returns false on single-length path with existing node")
	}
	p = append(p, concrete.Node(1))
	dg.AddNode(p[1])
	if topo.IsPathIn(dg, p) {
		t.Error("IsPath returns true on bad path of length 2")
	}
	dg.SetEdge(concrete.Edge{p[0], p[1]}, 1)
	if !topo.IsPathIn(dg, p) {
		t.Error("IsPath returns false on correct path of length 2")
	}
	p[0], p[1] = p[1], p[0]
	if topo.IsPathIn(dg, p) {
		t.Error("IsPath erroneously returns true for a reverse path")
	}
	p = []graph.Node{p[1], p[0], concrete.Node(2)}
	dg.SetEdge(concrete.Edge{p[1], p[2]}, 1)
	if !topo.IsPathIn(dg, p) {
		t.Error("IsPath does not find a correct path for path > 2 nodes")
	}
	ug := concrete.NewGraph()
	ug.SetEdge(concrete.Edge{p[1], p[0]}, 1)
	ug.SetEdge(concrete.Edge{p[1], p[2]}, 1)
	if !topo.IsPathIn(dg, p) {
		t.Error("IsPath does not correctly account for undirected behavior")
	}
}

func TestBreadthFirst(t *testing.T) {
	for i, test := range breadthFirstTests {
		g := concrete.NewGraph()
		for u, e := range test.g {
			// Add nodes that are not defined by an edge.
			if !g.Has(concrete.Node(u)) {
				g.AddNode(concrete.Node(u))
			}
			for v := range e {
				g.SetEdge(concrete.Edge{F: concrete.Node(u), T: concrete.Node(v)}, 0)
			}
		}
		w := traverse.BreadthFirst{
			EdgeFilter: test.edge,
		}
		var got [][]int
		final := w.Walk(g, test.from, func(n graph.Node, d int) bool {
			if test.until != nil && test.until(n, d) {
				return true
			}
			if d >= len(got) {
				got = append(got, []int(nil))
			}
			got[d] = append(got[d], n.ID())
			return false
		})
		if !test.final[final] {
			t.Errorf("unexepected final node for test %d:\ngot:  %v\nwant: %v", i, final, test.final)
		}
		for _, l := range got {
			sort.Ints(l)
		}
		if !reflect.DeepEqual(got, test.want) {
			t.Errorf("unexepected BFS level structure for test %d:\ngot:  %v\nwant: %v", i, got, test.want)
		}
	}
}