func (g *UndirectedGraph) Degree(n graph.Node) int {
	if _, ok := g.nodeMap[n.ID()]; !ok {
		return 0
	}

	return len(g.neighbors[n.ID()])
}

// Builds a BFS tree (as a directed graph) from the given graph and start node.
func BFSTree(g graph.Graph, start graph.Node) *simple.DirectedGraph {
	if !g.Has(start) {
		panic(fmt.Sprintf("BFSTree: Start node %r not in graph %r", start, g))
	}

	ret := simple.NewDirectedGraph(0.0, math.Inf(1))
	seen := make(map[int]bool)
	q := queue.New()
	q.Add(start)
	ret.AddNode(simple.Node(start.ID()))

	for q.Length() > 0 {
		node := q.Peek().(graph.Node)
		q.Remove()
		for _, neighbor := range g.From(node) {
			if !seen[neighbor.ID()] {
				seen[neighbor.ID()] = true
				ret.AddNode(simple.Node(neighbor.ID()))
				ret.SetEdge(simple.Edge{F: simple.Node(node.ID()), T: simple.Node(neighbor.ID()), W: g.Edge(node, neighbor).Weight()})
				q.Add(neighbor)
			}
		}
	}

	return ret
}

// NewImagePipelineFromImageTagLocation returns the ImagePipeline and all the nodes contributing to it
func NewImagePipelineFromImageTagLocation(g osgraph.Graph, node graph.Node, imageTagLocation ImageTagLocation) (ImagePipeline, IntSet) {
	covered := IntSet{}
	covered.Insert(node.ID())

	flow := ImagePipeline{}
	flow.Image = imageTagLocation

	for _, input := range g.PredecessorNodesByEdgeKind(node, buildedges.BuildOutputEdgeKind) {
		covered.Insert(input.ID())
		build := input.(*buildgraph.BuildConfigNode)
		if flow.Build != nil {
			// report this as an error (unexpected duplicate input build)
		}
		if build.BuildConfig == nil {
			// report this as as a missing build / broken link
			break
		}

		base, src, coveredInputs, _ := findBuildInputs(g, build)
		covered.Insert(coveredInputs.List()...)
		flow.Build = build
		flow.BaseImage = base
		flow.Source = src
	}

	return flow, covered
}

// XY returns the cartesian coordinates of n. If n is not a node
// in the grid, (NaN, NaN) is returned.
func (l *LimitedVisionGrid) XY(n graph.Node) (x, y float64) {
	if !l.Has(n) {
		return math.NaN(), math.NaN()
	}
	r, c := l.RowCol(n.ID())
	return float64(c), float64(r)
}

func (g *GraphNode) From(n graph.Node) []graph.Node {
	if n.ID() == g.ID() {
		return g.neighbors
	}

	visited := map[int]struct{}{g.id: struct{}{}}
	for _, root := range g.roots {
		visited[root.ID()] = struct{}{}

		if result := root.findNeighbors(n, visited); result != nil {
			return result
		}
	}

	for _, neigh := range g.neighbors {
		visited[neigh.ID()] = struct{}{}

		if gn, ok := neigh.(*GraphNode); ok {
			if result := gn.findNeighbors(n, visited); result != nil {
				return result
			}
		}
	}

	return nil
}

func (g *GraphNode) findNeighbors(n graph.Node, visited map[int]struct{}) []graph.Node {
	if n.ID() == g.ID() {
		return g.neighbors
	}

	for _, root := range g.roots {
		if _, ok := visited[root.ID()]; ok {
			continue
		}
		visited[root.ID()] = struct{}{}

		if result := root.findNeighbors(n, visited); result != nil {
			return result
		}
	}

	for _, neigh := range g.neighbors {
		if _, ok := visited[neigh.ID()]; ok {
			continue
		}
		visited[neigh.ID()] = struct{}{}

		if gn, ok := neigh.(*GraphNode); ok {
			if result := gn.findNeighbors(n, visited); result != nil {
				return result
			}
		}
	}

	return nil
}

// Walk performs a depth-first traversal of the graph g starting from the given node,
// depending on the the EdgeFilter field and the until parameter if they are non-nil. The
// traversal follows edges for which EdgeFilter(edge) is true and returns the first node
// for which until(node) is true. During the traversal, if the Visit field is non-nil, it
// is called with the nodes joined by each followed edge.
func (d *DepthFirst) Walk(g graph.Graph, from graph.Node, until func(graph.Node) bool) graph.Node {
	if d.visited == nil {
		d.visited = &intsets.Sparse{}
	}
	d.stack.Push(from)
	d.visited.Insert(from.ID())

	for d.stack.Len() > 0 {
		t := d.stack.Pop()
		if until != nil && until(t) {
			return t
		}
		for _, n := range g.From(t) {
			if d.EdgeFilter != nil && !d.EdgeFilter(g.Edge(t, n)) {
				continue
			}
			if d.visited.Has(n.ID()) {
				continue
			}
			if d.Visit != nil {
				d.Visit(t, n)
			}
			d.visited.Insert(n.ID())
			d.stack.Push(n)
		}
	}

	return nil
}

// NewImagePipelineFromImageTagLocation returns the ImagePipeline and all the nodes contributing to it
func NewImagePipelineFromImageTagLocation(g osgraph.Graph, node graph.Node, imageTagLocation ImageTagLocation) (ImagePipeline, IntSet) {
	covered := IntSet{}
	covered.Insert(node.ID())

	flow := ImagePipeline{}
	flow.Image = imageTagLocation

	for _, input := range g.PredecessorNodesByEdgeKind(node, buildedges.BuildOutputEdgeKind) {
		covered.Insert(input.ID())
		build := input.(*buildgraph.BuildConfigNode)
		if flow.Build != nil {
			// report this as an error (unexpected duplicate input build)
		}
		if build.BuildConfig == nil {
			// report this as as a missing build / broken link
			break
		}

		base, src, coveredInputs, _ := findBuildInputs(g, build)
		covered.Insert(coveredInputs.List()...)
		flow.BaseImage = base
		flow.Source = src
		flow.Build = build
		flow.LastSuccessfulBuild, flow.LastUnsuccessfulBuild, flow.ActiveBuilds = buildedges.RelevantBuilds(g, flow.Build)
	}

	for _, input := range g.SuccessorNodesByEdgeKind(node, imageedges.ReferencedImageStreamGraphEdgeKind) {
		covered.Insert(input.ID())
		imageStreamNode := input.(*imagegraph.ImageStreamNode)

		flow.DestinationResolved = (len(imageStreamNode.Status.DockerImageRepository) != 0)
	}

	return flow, covered
}

func (g *DenseGraph) EdgeTo(n, succ graph.Node) graph.Edge {
	if g.adjacencyMatrix[n.ID()*g.numNodes+succ.ID()] != inf {
		return Edge{n, succ}
	}

	return nil
}

func coordinatesForID(n graph.Node, c, r int) [2]int {
	id := n.ID()
	if id >= c*r {
		panic("out of range")
	}
	return [2]int{id / r, id % r}
}

// XY returns the cartesian coordinates of n. If n is not a node
// in the grid, (NaN, NaN) is returned.
func (g *Grid) XY(n graph.Node) (x, y float64) {
	if !g.Has(n) {
		return math.NaN(), math.NaN()
	}
	r, c := g.RowCol(n.ID())
	return float64(c), float64(r)
}

// key returns the key for the node u and whether the node is
// in the queue. If the node is not in the queue, key is returned
// as +Inf.
func (q *primQueue) key(u graph.Node) (key float64, ok bool) {
	i, ok := q.indexOf[u.ID()]
	if !ok {
		return math.Inf(1), false
	}
	return q.nodes[i].Weight(), ok
}

// WeightTo returns the weight of the minimum path to v.
func (p Shortest) WeightTo(v graph.Node) float64 {
	to, toOK := p.indexOf[v.ID()]
	if !toOK {
		return math.Inf(1)
	}
	return p.dist[to]
}

func newShortestFrom(u graph.Node, nodes []graph.Node) Shortest {
	indexOf := make(map[int]int, len(nodes))
	uid := u.ID()
	for i, n := range nodes {
		indexOf[n.ID()] = i
		if n.ID() == uid {
			u = n
		}
	}

	p := Shortest{
		from: u,

		nodes:   nodes,
		indexOf: indexOf,

		dist: make([]float64, len(nodes)),
		next: make([]int, len(nodes)),
	}
	for i := range nodes {
		p.dist[i] = math.Inf(1)
		p.next[i] = -1
	}
	p.dist[indexOf[uid]] = 0

	return p
}

// From returns all nodes in g that can be reached directly from u.
func (g *ReducedUndirected) From(u graph.Node) []graph.Node {
	out := g.edges[u.ID()]
	nodes := make([]graph.Node, len(out))
	for i, vid := range out {
		nodes[i] = g.nodes[vid]
	}
	return nodes
}

func (g *TileGraph) HasEdge(u, v graph.Node) bool {
	if !g.Has(u) || !g.Has(v) {
		return false
	}
	r1, c1 := g.IDToCoords(u.ID())
	r2, c2 := g.IDToCoords(v.ID())
	return (c1 == c2 && (r2 == r1+1 || r2 == r1-1)) || (r1 == r2 && (c2 == c1+1 || c2 == c1-1))
}

// Weight returns the weight of the minimum path between u and v.
func (p AllShortest) Weight(u, v graph.Node) float64 {
	from, fromOK := p.indexOf[u.ID()]
	to, toOK := p.indexOf[v.ID()]
	if !fromOK || !toOK {
		return math.Inf(1)
	}
	return p.dist.At(from, to)
}

func nodeID(n graph.Node) string {
	switch n := n.(type) {
	case Node:
		return n.DOTID()
	default:
		return fmt.Sprint(n.ID())
	}
}

// Adds a node to the graph. Implementation note: if you add a node close to or at
// the max int on your machine NewNode will become slower.
func (g *DirectedGraph) AddNode(n graph.Node) {
	g.nodeMap[n.ID()] = n
	g.successors[n.ID()] = make(map[int]WeightedEdge)
	g.predecessors[n.ID()] = make(map[int]WeightedEdge)

	delete(g.freeMap, n.ID())
	g.maxID = max(g.maxID, n.ID())
}

func (g *UndirectedGraph) EdgeBetween(u, v graph.Node) graph.Edge {
	// We don't need to check if neigh exists because
	// it's implicit in the neighbors access.
	if !g.Has(u) {
		return nil
	}

	return g.neighbors[u.ID()][v.ID()]
}