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 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 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
	})
}

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

// New initializes a graph from input to output.
func New() Graph {
	g := concrete.NewDirectedGraph()
	return Graph{
		Directed:       g,
		GraphDescriber: typedGraph{},

		uniqueNamedGraph: newUniqueNamedGraph(g),

		internal: g,
	}
}

func directedNamedIDGraphFrom(g []set) graph.Directed {
	dg := concrete.NewDirectedGraph(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 ExampleBreadthFirstSearch() {
	g := concrete.NewDirectedGraph()
	var n0, n1, n2, n3 concrete.Node = 0, 1, 2, 3
	g.AddDirectedEdge(concrete.Edge{n0, n1}, 1)
	g.AddDirectedEdge(concrete.Edge{n0, n2}, 1)
	g.AddDirectedEdge(concrete.Edge{n2, n3}, 1)
	path, v := search.BreadthFirstSearch(n0, n3, g)
	fmt.Println("path:", path)
	fmt.Println("nodes visited:", v)
	// Output:
	// path: [0 2 3]
	// nodes visited: 4
}

func generateDummyGraph() *concrete.DirectedGraph {
	nodes := [4]struct{ srcId, targetId int }{
		{2, 1},
		{1, 0},
		{2, 0},
		{0, 2},
	}

	g := concrete.NewDirectedGraph()

	for _, n := range nodes {
		g.SetEdge(concrete.Edge{concrete.Node(n.srcId), concrete.Node(n.targetId)}, 1)
	}

	return g
}

func directedNodeAttrGraphFrom(g []set, attr [][]Attribute) graph.Directed {
	dg := concrete.NewDirectedGraph()
	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 directedNamedIDNodeAttrGraphFrom(g []set, attr [][]Attribute) graph.Directed {
	dg := concrete.NewDirectedGraph(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 directedPortedAttrGraphFrom(g []set, attr [][]Attribute, ports map[edge]portedEdge) graph.Directed {
	dg := concrete.NewDirectedGraph(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 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 TestPageRank(t *testing.T) {
	for i, test := range pageRankTests {
		g := concrete.NewDirectedGraph()
		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 := PageRank(g, test.damp, test.tol)
		prec := 1 - int(math.Log10(test.wantTol))
		for n := range test.g {
			if !floats.EqualWithinAbsOrRel(got[n], test.want[n], test.wantTol, test.wantTol) {
				t.Errorf("unexpected PageRank result for test %d:\ngot: %v\nwant:%v",
					i, orderedFloats(got, prec), orderedFloats(test.want, prec))
				break
			}
		}
	}
}

	Graph             func() graph.Mutable
	Edges             []concrete.Edge
	HasNegativeWeight bool
	HasNegativeCycle  bool

	Query         concrete.Edge
	Weight        float64
	WantPaths     [][]int
	HasUniquePath bool

	NoPathFor concrete.Edge
}{
	// Positive weighted graphs.
	{
		Name:  "empty directed",
		Graph: func() graph.Mutable { return concrete.NewDirectedGraph(0, math.Inf(1)) },

		Query:  concrete.Edge{F: concrete.Node(0), T: concrete.Node(1)},
		Weight: math.Inf(1),

		NoPathFor: concrete.Edge{F: concrete.Node(0), T: concrete.Node(1)},
	},
	{
		Name:  "empty undirected",
		Graph: func() graph.Mutable { return concrete.NewGraph(0, math.Inf(1)) },

		Query:  concrete.Edge{F: concrete.Node(0), T: concrete.Node(1)},
		Weight: math.Inf(1),

		NoPathFor: concrete.Edge{F: concrete.Node(0), T: concrete.Node(1)},
	},

func TestDStarLiteNullHeuristic(t *testing.T) {
	for _, test := range testgraphs.ShortestPathTests {
		// Skip zero-weight cycles.
		if strings.HasPrefix(test.Name, "zero-weight") {
			continue
		}

		g := test.Graph()
		for _, e := range test.Edges {
			g.SetEdge(e)
		}

		var (
			d *DStarLite

			panicked bool
		)
		func() {
			defer func() {
				panicked = recover() != nil
			}()
			d = NewDStarLite(test.Query.From(), test.Query.To(), g.(graph.Graph), path.NullHeuristic, concrete.NewDirectedGraph(0, math.Inf(1)))
		}()
		if panicked || test.HasNegativeWeight {
			if !test.HasNegativeWeight {
				t.Errorf("%q: unexpected panic", test.Name)
			}
			if !panicked {
				t.Errorf("%q: expected panic for negative edge weight", test.Name)
			}
			continue
		}

		p, weight := d.Path()

		if !math.IsInf(weight, 1) && p[0].ID() != test.Query.From().ID() {
			t.Fatalf("%q: unexpected from node ID: got:%d want:%d", p[0].ID(), test.Query.From().ID())
		}
		if weight != test.Weight {
			t.Errorf("%q: unexpected weight from Between: got:%f want:%f",
				test.Name, weight, test.Weight)
		}

		var got []int
		for _, n := range p {
			got = append(got, n.ID())
		}
		ok := len(got) == 0 && len(test.WantPaths) == 0
		for _, sp := range test.WantPaths {
			if reflect.DeepEqual(got, sp) {
				ok = true
				break
			}
		}
		if !ok {
			t.Errorf("%q: unexpected shortest path:\ngot: %v\nwant from:%v",
				test.Name, p, test.WantPaths)
		}
	}
}

func TestDStarLiteDynamic(t *testing.T) {
	for i, test := range dynamicDStarLiteTests {
		for _, remember := range test.remember {
			l := &internal.LimitedVisionGrid{
				Grid:         test.g,
				VisionRadius: test.radius,
				Location:     test.s,
			}
			if remember {
				l.Known = make(map[int]bool)
			}

			l.Grid.AllVisible = test.all

			l.Grid.AllowDiagonal = test.diag
			l.Grid.UnitEdgeWeight = test.unit

			if test.modify != nil {
				test.modify(l)
			}

			got := []graph.Node{test.s}
			l.MoveTo(test.s)

			heuristic := func(a, b graph.Node) float64 {
				ax, ay := l.XY(a)
				bx, by := l.XY(b)
				return test.heuristic(ax-bx, ay-by)
			}

			world := concrete.NewDirectedGraph(0, math.Inf(1))
			d := NewDStarLite(test.s, test.t, l, heuristic, world)
			var (
				dp  *dumper
				buf bytes.Buffer
			)
			_, c := l.Grid.Dims()
			if c <= *maxWide && (*debug || *vdebug) {
				dp = &dumper{
					w: &buf,

					dStarLite: d,
					grid:      l,
				}
			}

			dp.dump(true)
			dp.printEdges("Initial world knowledge: %s\n\n", concreteEdgesOf(l, world.Edges()))
			for d.Step() {
				changes, _ := l.MoveTo(d.Here())
				got = append(got, l.Location)
				d.UpdateWorld(changes)
				dp.dump(true)
				if wantedPath, ok := test.wantedPaths[l.Location.ID()]; ok {
					gotPath, _ := d.Path()
					if !samePath(gotPath, wantedPath) {
						t.Errorf("unexpected intermediate path estimation for test %d %s memory:\ngot: %v\nwant:%v",
							i, memory(remember), gotPath, wantedPath)
					}
				}
				dp.printEdges("Edges changing after last step:\n%s\n\n", concreteEdgesOf(l, changes))
			}

			if weight := weightOf(got, l.Grid); !samePath(got, test.want) || weight != test.weight {
				t.Errorf("unexpected path for test %d %s memory got weight:%v want weight:%v:\ngot: %v\nwant:%v",
					i, memory(remember), weight, test.weight, got, test.want)
				b, err := l.Render(got)
				t.Errorf("path taken (err:%v):\n%s", err, b)
				if c <= *maxWide && (*debug || *vdebug) {
					t.Error(buf.String())
				}
			} else if c <= *maxWide && *vdebug {
				t.Logf("Test %d:\n%s", i, buf.String())
			}
		}
	}
}