func TestDepthFirst(t *testing.T) {
	g := concrete.NewDirectedGraph()

	a := concrete.Node(g.NewNodeID())
	b := concrete.Node(g.NewNodeID())

	g.AddNode(a)
	g.AddNode(b)
	g.SetEdge(concrete.Edge{F: a, T: b}, 1)
	g.SetEdge(concrete.Edge{F: b, T: a}, 1)

	count := 0

	df := &DepthFirst{
		EdgeFilter: func(graph.Edge) bool {
			return true
		},
		Visit: func(u, v graph.Node) {
			count++
			t.Logf("%d -> %d\n", u.ID(), v.ID())
		},
	}

	df.Walk(g, a, func(n graph.Node) bool {
		if count > 100 {
			t.Fatalf("looped")
			return true
		}
		return false
	})
}

// Tests Issue #27
func TestEdgeOvercounting(t *testing.T) {
	g := generateDummyGraph()

	if neigh := g.From(concrete.Node(concrete.Node(2))); len(neigh) != 2 {
		t.Errorf("Node 2 has incorrect number of neighbors got neighbors %v (count %d), expected 2 neighbors {0,1}", neigh, len(neigh))
	}
}

func TestSimpleAStar(t *testing.T) {
	tg, err := concrete.GenerateTileGraph("▀  ▀\n▀▀ ▀\n▀▀ ▀\n▀▀ ▀")
	if err != nil {
		t.Fatal("Couldn't generate tilegraph")
	}

	path, cost, _ := search.AStar(concrete.Node(1), concrete.Node(14), tg, nil, nil)
	if math.Abs(cost-4) > 1e-5 {
		t.Errorf("A* reports incorrect cost for simple tilegraph search")
	}

	if path == nil {
		t.Fatalf("A* fails to find path for for simple tilegraph search")
	} else {
		correctPath := []int{1, 2, 6, 10, 14}
		if len(path) != len(correctPath) {
			t.Fatalf("Astar returns wrong length path for simple tilegraph search")
		}
		for i, node := range path {
			if node.ID() != correctPath[i] {
				t.Errorf("Astar returns wrong path at step", i, "got:", node, "actual:", correctPath[i])
			}
		}
	}
}

func TestTarjan(t *testing.T) {
	for i, test := range tarjanTests {
		g := concrete.NewDirectedGraph()
		for u, e := range test.g {
			g.AddNode(concrete.Node(u))
			for v := range e {
				if !g.NodeExists(concrete.Node(v)) {
					g.AddNode(concrete.Node(v))
				}
				g.AddDirectedEdge(concrete.Edge{H: concrete.Node(u), T: concrete.Node(v)}, 0)
			}
		}
		gotSCCs := search.Tarjan(g)
		// tarjan.strongconnect does range iteration over maps,
		// so sort SCC members to ensure consistent ordering.
		gotIDs := make([][]int, len(gotSCCs))
		for i, scc := range gotSCCs {
			gotIDs[i] = make([]int, len(scc))
			for j, id := range scc {
				gotIDs[i][j] = id.ID()
			}
			sort.Ints(gotIDs[i])
		}
		for _, iv := range test.ambiguousOrder {
			sort.Sort(byComponentLengthOrStart(test.want[iv.start:iv.end]))
			sort.Sort(byComponentLengthOrStart(gotIDs[iv.start:iv.end]))
		}
		if !reflect.DeepEqual(gotIDs, test.want) {
			t.Errorf("unexpected Tarjan scc result for %d:\n\tgot:%v\n\twant:%v", i, gotIDs, 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 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 TestAStar(t *testing.T) {
	for _, test := range aStarTests {
		pt, _ := path.AStar(concrete.Node(test.s), concrete.Node(test.t), test.g, test.heuristic)

		p, cost := pt.To(concrete.Node(test.t))

		if !topo.IsPathIn(test.g, p) {
			t.Error("got path that is not path in input graph for %q", test.name)
		}

		bfp, ok := path.BellmanFordFrom(concrete.Node(test.s), test.g)
		if !ok {
			t.Fatalf("unexpected negative cycle in %q", test.name)
		}
		if want := bfp.WeightTo(concrete.Node(test.t)); cost != want {
			t.Errorf("unexpected cost for %q: got:%v want:%v", test.name, cost, want)
		}

		var got = make([]int, 0, len(p))
		for _, n := range p {
			got = append(got, n.ID())
		}
		if test.wantPath != nil && !reflect.DeepEqual(got, test.wantPath) {
			t.Errorf("unexpected result for %q:\ngot: %v\nwant:%v", test.name, got, test.wantPath)
		}
	}
}

func TestTarjanSCC(t *testing.T) {
	for i, test := range tarjanTests {
		g := concrete.NewDirectedGraph(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)})
			}
		}
		gotSCCs := TarjanSCC(g)
		// tarjan.strongconnect does range iteration over maps,
		// so sort SCC members to ensure consistent ordering.
		gotIDs := make([][]int, len(gotSCCs))
		for i, scc := range gotSCCs {
			gotIDs[i] = make([]int, len(scc))
			for j, id := range scc {
				gotIDs[i][j] = id.ID()
			}
			sort.Ints(gotIDs[i])
		}
		for _, iv := range test.ambiguousOrder {
			sort.Sort(internal.BySliceValues(test.want[iv.start:iv.end]))
			sort.Sort(internal.BySliceValues(gotIDs[iv.start:iv.end]))
		}
		if !reflect.DeepEqual(gotIDs, test.want) {
			t.Errorf("unexpected Tarjan scc result for %d:\n\tgot:%v\n\twant:%v", i, gotIDs, test.want)
		}
	}
}

func TestDenseLists(t *testing.T) {
	dg := concrete.NewDenseGraph(15, true)
	nodes := nodeSorter(dg.NodeList())

	if len(nodes) != 15 {
		t.Fatalf("Wrong number of nodes")
	}

	sort.Sort(nodes)

	for i, node := range dg.NodeList() {
		if i != node.ID() {
			t.Errorf("Node list doesn't return properly id'd nodes")
		}
	}

	edges := dg.DirectedEdgeList()
	if len(edges) != 15*15 {
		t.Errorf("Improper number of edges for passable dense graph")
	}

	dg.RemoveEdge(concrete.Edge{concrete.Node(12), concrete.Node(11)}, true)
	edges = dg.DirectedEdgeList()
	if len(edges) != (15*15)-1 {
		t.Errorf("Removing edge didn't affect edge listing properly")
	}
}

func TestSort(t *testing.T) {
	for i, test := range tarjanTests {
		g := concrete.NewDirectedGraph(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)})
			}
		}
		sorted, err := Sort(g)
		var gotSortedLen int
		for _, n := range sorted {
			if n != nil {
				gotSortedLen++
			}
		}
		if gotSortedLen != test.sortedLength {
			t.Errorf("unexpected number of sortable nodes for test %d: got:%d want:%d", i, gotSortedLen, test.sortedLength)
		}
		if err == nil != test.sortable {
			t.Errorf("unexpected sortability for test %d: got error: %v want: nil-error=%t", i, err, test.sortable)
		}
		if err != nil && len(err.(Unorderable)) != test.unorderableLength {
			t.Errorf("unexpected number of unorderable nodes for test %d: got:%d want:%d", i, len(err.(Unorderable)), test.unorderableLength)
		}
	}
}

func TestHITS(t *testing.T) {
	for i, test := range hitsTests {
		g := concrete.NewDirectedGraph(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)})
			}
		}
		got := HITS(g, test.tol)
		prec := 1 - int(math.Log10(test.wantTol))
		for n := range test.g {
			if !floats.EqualWithinAbsOrRel(got[n].Hub, test.want[n].Hub, test.wantTol, test.wantTol) {
				t.Errorf("unexpected HITS result for test %d:\ngot: %v\nwant:%v",
					i, orderedHubAuth(got, prec), orderedHubAuth(test.want, prec))
				break
			}
			if !floats.EqualWithinAbsOrRel(got[n].Authority, test.want[n].Authority, test.wantTol, test.wantTol) {
				t.Errorf("unexpected HITS result for test %d:\ngot: %v\nwant:%v",
					i, orderedHubAuth(got, prec), orderedHubAuth(test.want, prec))
				break
			}
		}
	}
}

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 TestFWOneEdge(t *testing.T) {
	dg := concrete.NewDenseGraph(2, true)
	aPaths, sPath := search.FloydWarshall(dg, nil)

	path, cost, err := sPath(concrete.Node(0), concrete.Node(1))
	if err != nil {
		t.Fatal(err)
	}

	if math.Abs(cost-1) > 1e-6 {
		t.Errorf("FW got wrong cost %f", cost)
	}

	if len(path) != 2 || path[0].ID() != 0 && path[1].ID() != 1 {
		t.Errorf("Wrong path in FW %v", path)
	}

	paths, cost, err := aPaths(concrete.Node(0), concrete.Node(1))
	if err != nil {
		t.Fatal(err)
	}

	if math.Abs(cost-1) > 1e-6 {
		t.Errorf("FW got wrong cost %f", cost)
	}

	if len(paths) != 1 {
		t.Errorf("Didn't get right paths in FW %v", paths)
	}

	path = paths[0]
	if len(path) != 2 || path[0].ID() != 0 && path[1].ID() != 1 {
		t.Errorf("Wrong path in FW allpaths %v", path)
	}
}

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 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 TestCyclesIn(t *testing.T) {
	for i, test := range cyclesInTests {
		g := concrete.NewDirectedGraph(0, math.Inf(1))
		g.AddNode(concrete.Node(-10)) // Make sure we test graphs with sparse IDs.
		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)})
			}
		}
		cycles := CyclesIn(g)
		var got [][]int
		if cycles != nil {
			got = make([][]int, len(cycles))
		}
		// johnson.circuit does range iteration over maps,
		// so sort to ensure consistent ordering.
		for j, c := range cycles {
			ids := make([]int, len(c))
			for k, n := range c {
				ids[k] = n.ID()
			}
			got[j] = ids
		}
		sort.Sort(internal.BySliceValues(got))
		if !reflect.DeepEqual(got, test.want) {
			t.Errorf("unexpected johnson result for %d:\n\tgot:%#v\n\twant:%#v", i, got, test.want)
		}
	}
}

func directedEdgeAttrGraphFrom(g []set, attr map[edge][]Attribute) graph.Directed {
	dg := concrete.NewDirectedGraph()
	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}]}, 0)
		}
	}
	return dg
}

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 directedGraphFrom(g []set) graph.Directed {
	dg := concrete.NewDirectedGraph()
	for u, e := range g {
		for v := range e {
			dg.SetEdge(concrete.Edge{F: concrete.Node(u), T: concrete.Node(v)}, 0)
		}
	}
	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
}