// BronKerbosch returns the set of maximal cliques of the undirected graph g.
func BronKerbosch(g graph.Undirected) [][]graph.Node {
	nodes := g.Nodes()

	// The algorithm used here is essentially BronKerbosch3 as described at
	// http://en.wikipedia.org/w/index.php?title=Bron%E2%80%93Kerbosch_algorithm&oldid=656805858

	p := make(internal.Set, len(nodes))
	for _, n := range nodes {
		p.Add(n)
	}
	x := make(internal.Set)
	var bk bronKerbosch
	order, _ := VertexOrdering(g)
	for _, v := range order {
		neighbours := g.From(v)
		nv := make(internal.Set, len(neighbours))
		for _, n := range neighbours {
			nv.Add(n)
		}
		bk.maximalCliquePivot(g, []graph.Node{v}, make(internal.Set).Intersect(p, nv), make(internal.Set).Intersect(x, nv))
		p.Remove(v)
		x.Add(v)
	}
	return bk
}

// weightFuncFor returns a constructed weight function for g.
func weightFuncFor(g graph.Undirected) func(x, y graph.Node) float64 {
	if wg, ok := g.(graph.Weighter); ok {
		return func(x, y graph.Node) float64 {
			w, ok := wg.Weight(x, y)
			if !ok {
				return 0
			}
			if w < 0 {
				panic(negativeWeight)
			}
			return w
		}
	}
	return func(x, y graph.Node) float64 {
		e := g.Edge(x, y)
		if e == nil {
			return 0
		}
		w := e.Weight()
		if w < 0 {
			panic(negativeWeight)
		}
		return w
	}
}

func benchmarkWalkAllDepthFirst(b *testing.B, g graph.Undirected) {
	n := len(g.Nodes())
	b.ResetTimer()
	var dft DepthFirst
	for i := 0; i < b.N; i++ {
		dft.WalkAll(g, nil, nil, nil)
	}
	if dft.visited.Len() != n {
		b.Fatalf("unexpected number of nodes visited: want: %d got %d", n, dft.visited.Len())
	}
}

// WalkAll calls Walk for each unvisited node of the graph g using edges independent
// of their direction. The functions before and after are called prior to commencing
// and after completing each walk if they are non-nil respectively. The function
// during is called on each node as it is traversed.
func (b *BreadthFirst) WalkAll(g graph.Undirected, before, after func(), during func(graph.Node)) {
	b.Reset()
	for _, from := range g.Nodes() {
		if b.Visited(from) {
			continue
		}
		if before != nil {
			before()
		}
		b.Walk(g, from, func(n graph.Node, _ int) bool {
			if during != nil {
				during(n)
			}
			return false
		})
		if after != nil {
			after()
		}
	}
}

// Q returns the modularity Q score of the graph g subdivided into the
// given communities at the given resolution. If communities is nil, the
// unclustered modularity score is returned. The resolution parameter
// is γ as defined in Reichardt and Bornholdt doi:10.1103/PhysRevE.74.016110.
// Q will panic if g has any edge with negative edge weight.
//
// graph.Undirect may be used as a shim to allow calculation of Q for
// directed graphs.
func Q(g graph.Undirected, communities [][]graph.Node, resolution float64) float64 {
	nodes := g.Nodes()
	weight := weightFuncFor(g)

	// Calculate the total edge weight of the graph
	// and the table of penetrating edge weight sums.
	var m2 float64
	k := make(map[int]float64, len(nodes))
	for _, u := range nodes {
		w := weight(u, u)
		for _, v := range g.From(u) {
			w += weight(u, v)
		}
		m2 += w
		k[u.ID()] = w
	}

	if communities == nil {
		var q float64
		for _, u := range nodes {
			kU := k[u.ID()]
			q += weight(u, u) - resolution*kU*kU/m2
		}
		return q / m2
	}

	// Iterate over the communities, calculating
	// the non-self edge weights for the upper
	// triangle and adjust the diagonal.
	var q float64
	for _, c := range communities {
		for i, u := range c {
			kU := k[u.ID()]
			q += weight(u, u) - resolution*kU*kU/m2
			for _, v := range c[i+1:] {
				q += 2 * (weight(u, v) - resolution*kU*k[v.ID()]/m2)
			}
		}
	}
	return q / m2
}

func (bk *bronKerbosch) maximalCliquePivot(g graph.Undirected, r []graph.Node, p, x internal.Set) {
	if len(p) == 0 && len(x) == 0 {
		*bk = append(*bk, r)
		return
	}

	neighbours := bk.choosePivotFrom(g, p, x)
	nu := make(internal.Set, len(neighbours))
	for _, n := range neighbours {
		nu.Add(n)
	}
	for _, v := range p {
		if nu.Has(v) {
			continue
		}
		neighbours := g.From(v)
		nv := make(internal.Set, len(neighbours))
		for _, n := range neighbours {
			nv.Add(n)
		}

		var found bool
		for _, n := range r {
			if n.ID() == v.ID() {
				found = true
				break
			}
		}
		var sr []graph.Node
		if !found {
			sr = append(r[:len(r):len(r)], v)
		}

		bk.maximalCliquePivot(g, sr, make(internal.Set).Intersect(p, nv), make(internal.Set).Intersect(x, nv))
		p.Remove(v)
		x.Add(v)
	}
}

func (*bronKerbosch) choosePivotFrom(g graph.Undirected, p, x internal.Set) (neighbors []graph.Node) {
	// TODO(kortschak): Investigate the impact of pivot choice that maximises
	// |p ⋂ neighbours(u)| as a function of input size. Until then, leave as
	// compile time option.
	if !tomitaTanakaTakahashi {
		for _, n := range p {
			return g.From(n)
		}
		for _, n := range x {
			return g.From(n)
		}
		panic("bronKerbosch: empty set")
	}

	var (
		max   = -1
		pivot graph.Node
	)
	maxNeighbors := func(s internal.Set) {
	outer:
		for _, u := range s {
			nb := g.From(u)
			c := len(nb)
			if c <= max {
				continue
			}
			for n := range nb {
				if _, ok := p[n]; ok {
					continue
				}
				c--
				if c <= max {
					continue outer
				}
			}
			max = c
			pivot = u
			neighbors = nb
		}
	}
	maxNeighbors(p)
	maxNeighbors(x)
	if pivot == nil {
		panic("bronKerbosch: empty set")
	}
	return neighbors
}

// VertexOrdering returns the vertex ordering and the k-cores of
// the undirected graph g.
func VertexOrdering(g graph.Undirected) (order []graph.Node, cores [][]graph.Node) {
	nodes := g.Nodes()

	// The algorithm used here is essentially as described at
	// http://en.wikipedia.org/w/index.php?title=Degeneracy_%28graph_theory%29&oldid=640308710

	// Initialize an output list L.
	var l []graph.Node

	// Compute a number d_v for each vertex v in G,
	// the number of neighbors of v that are not already in L.
	// Initially, these numbers are just the degrees of the vertices.
	dv := make(map[int]int, len(nodes))
	var (
		maxDegree  int
		neighbours = make(map[int][]graph.Node)
	)
	for _, n := range nodes {
		adj := g.From(n)
		neighbours[n.ID()] = adj
		dv[n.ID()] = len(adj)
		if len(adj) > maxDegree {
			maxDegree = len(adj)
		}
	}

	// Initialize an array D such that D[i] contains a list of the
	// vertices v that are not already in L for which d_v = i.
	d := make([][]graph.Node, maxDegree+1)
	for _, n := range nodes {
		deg := dv[n.ID()]
		d[deg] = append(d[deg], n)
	}

	// Initialize k to 0.
	k := 0
	// Repeat n times:
	s := []int{0}
	for _ = range nodes { // TODO(kortschak): Remove blank assignment when go1.3.3 is no longer supported.
		// Scan the array cells D[0], D[1], ... until
		// finding an i for which D[i] is nonempty.
		var (
			i  int
			di []graph.Node
		)
		for i, di = range d {
			if len(di) != 0 {
				break
			}
		}

		// Set k to max(k,i).
		if i > k {
			k = i
			s = append(s, make([]int, k-len(s)+1)...)
		}

		// Select a vertex v from D[i]. Add v to the
		// beginning of L and remove it from D[i].
		var v graph.Node
		v, d[i] = di[len(di)-1], di[:len(di)-1]
		l = append(l, v)
		s[k]++
		delete(dv, v.ID())

		// For each neighbor w of v not already in L,
		// subtract one from d_w and move w to the
		// cell of D corresponding to the new value of d_w.
		for _, w := range neighbours[v.ID()] {
			dw, ok := dv[w.ID()]
			if !ok {
				continue
			}
			for i, n := range d[dw] {
				if n.ID() == w.ID() {
					d[dw][i], d[dw] = d[dw][len(d[dw])-1], d[dw][:len(d[dw])-1]
					dw--
					d[dw] = append(d[dw], w)
					break
				}
			}
			dv[w.ID()] = dw
		}
	}

	for i, j := 0, len(l)-1; i < j; i, j = i+1, j-1 {
		l[i], l[j] = l[j], l[i]
	}
	cores = make([][]graph.Node, len(s))
	offset := len(l)
	for i, n := range s {
		cores[i] = l[offset-n : offset]
		offset -= n
	}
	return l, cores
}

// reduce returns a reduced graph constructed from g divided
// into the given communities. The communities value is mutated
// by the call to reduce. If communities is nil and g is a
// ReducedUndirected, it is returned unaltered.
func reduce(g graph.Undirected, communities [][]graph.Node) *ReducedUndirected {
	if communities == nil {
		if r, ok := g.(*ReducedUndirected); ok {
			return r
		}

		nodes := g.Nodes()
		// TODO(kortschak) This sort is necessary really only
		// for testing. In practice we would not be using the
		// community provided by the user for a Q calculation.
		// Probably we should use a function to map the
		// communities in the test sets to the remapped order.
		sort.Sort(ordered.ByID(nodes))
		communities = make([][]graph.Node, len(nodes))
		for i := range nodes {
			communities[i] = []graph.Node{node(i)}
		}

		weight := weightFuncFor(g)
		r := ReducedUndirected{
			nodes:       make([]community, len(nodes)),
			edges:       make([][]int, len(nodes)),
			weights:     make(map[[2]int]float64),
			communities: communities,
		}
		communityOf := make(map[int]int, len(nodes))
		for i, n := range nodes {
			r.nodes[i] = community{id: i, nodes: []graph.Node{n}}
			communityOf[n.ID()] = i
		}
		for _, u := range nodes {
			var out []int
			uid := communityOf[u.ID()]
			for _, v := range g.From(u) {
				vid := communityOf[v.ID()]
				if vid != uid {
					out = append(out, vid)
				}
				if uid < vid {
					// Only store the weight once.
					r.weights[[2]int{uid, vid}] = weight(u, v)
				}
			}
			r.edges[uid] = out
		}
		return &r
	}

	// Remove zero length communities destructively.
	var commNodes int
	for i := 0; i < len(communities); {
		comm := communities[i]
		if len(comm) == 0 {
			communities[i] = communities[len(communities)-1]
			communities[len(communities)-1] = nil
			communities = communities[:len(communities)-1]
		} else {
			commNodes += len(comm)
			i++
		}
	}

	r := ReducedUndirected{
		nodes:   make([]community, len(communities)),
		edges:   make([][]int, len(communities)),
		weights: make(map[[2]int]float64),
	}
	r.communities = make([][]graph.Node, len(communities))
	for i := range r.communities {
		r.communities[i] = []graph.Node{node(i)}
	}
	if g, ok := g.(*ReducedUndirected); ok {
		// Make sure we retain the truncated
		// community structure.
		g.communities = communities
		r.parent = g
	}
	weight := weightFuncFor(g)
	communityOf := make(map[int]int, commNodes)
	for i, comm := range communities {
		r.nodes[i] = community{id: i, nodes: comm}
		for _, n := range comm {
			communityOf[n.ID()] = i
		}
	}
	for uid, comm := range communities {
		var out []int
		for i, u := range comm {
			r.nodes[uid].weight += weight(u, u)
			for _, v := range comm[i+1:] {
				r.nodes[uid].weight += 2 * weight(u, v)
			}
			for _, v := range g.From(u) {
				vid := communityOf[v.ID()]
				found := false
				for _, e := range out {
//.........这里部分代码省略.........