func (g LabeledDirected) Transpose() (t LabeledDirected, ma int) {
	ta := make(LabeledAdjacencyList, len(g.LabeledAdjacencyList))
	for n, nbs := range g.LabeledAdjacencyList {
		for _, nb := range nbs {
			ta[nb.To] = append(ta[nb.To], Half{To: NI(n), Label: nb.Label})
			ma++
		}
	}
	return LabeledDirected{ta}, ma
}
Transpose constructs a new adjacency list that is the transpose of g.

For every arc from->to of g, the result will have an arc to->from.
Transpose also counts arcs as it traverses and returns ma the number of
arcs in g (equal to the number of arcs in the result.)
package graph
import "errors"
func (g Directed) DAGMaxLenPath(ordering []NI) (path []NI) {
	var n NI
	mlp := make([][]NI, len(g.AdjacencyList))  
	for i := len(ordering) - 1; i >= 0; i-- {
		fr := ordering[i]  
		to := g.AdjacencyList[fr]
		if len(to) == 0 {
			continue
		}
		mt := to[0]
		for _, to := range to[1:] {
			if len(mlp[to]) > len(mlp[mt]) {
				mt = to
			}
		}
		p := append([]NI{mt}, mlp[mt]...)
		mlp[fr] = p
		if len(p) > len(path) {
			n = fr
			path = p
		}
	}
	return append([]NI{n}, path...)
}
func (g Directed) EulerianCycle() ([]NI, error) {
	c, m := g.Copy()
	return c.EulerianCycleD(m)
}
func (g Directed) EulerianCycleD(ma int) ([]NI, error) {
	if len(g.AdjacencyList) == 0 {
		return nil, nil
	}
	e := newEulerian(g.AdjacencyList, ma)
	for e.s >= 0 {
		v := e.top()  
		e.push()
		if e.top() != v {
			return nil, errors.New("not balanced")
		}
		e.keep()
	}
	if !e.uv.Zero() {
		return nil, errors.New("not strongly connected")
	}
	return e.p, nil
}
func (g Directed) EulerianPath() ([]NI, error) {
	ind := g.InDegree()
	var start NI
	for n, to := range g.AdjacencyList {
		if len(to) > ind[n] {
			start = NI(n)
			break
		}
	}
	c, m := g.Copy()
	return c.EulerianPathD(m, start)
}
func (g Directed) EulerianPathD(ma int, start NI) ([]NI, error) {
	if len(g.AdjacencyList) == 0 {
		return nil, nil
	}
	e := newEulerian(g.AdjacencyList, ma)
	e.p[0] = start
	e.push()
	e.keep()
	for e.s >= 0 {
		start = e.top()
		e.push()
		if e.top() != start {
			return nil, errors.New("no Eulerian path")
		}
		e.keep()
	}
	if !e.uv.Zero() {
		return nil, errors.New("no Eulerian path")
	}
	return e.p, nil
}
func (e *eulerian) push() {
	for u := e.top(); ; {
		e.uv.SetBit(u, 0)  
		arcs := e.g[u]
		if len(arcs) == 0 {
			return  
		}
		w := arcs[0]  
		e.s++         
		e.p[e.s] = w
		e.g[u] = arcs[1:]  
		u = w
	}
}
func (e *eulerian) pushUndir() {
	for u := e.top(); ; {
		e.uv.SetBit(u, 0)
		arcs := e.g[u]
		if len(arcs) == 0 {
			return
		}
		w := arcs[0]
		e.s++
		e.p[e.s] = w
		e.g[u] = arcs[1:]  
		a2 := e.g[w]
		for x, rx := range a2 {
			if rx == u {  
				last := len(a2) - 1
				a2[x] = a2[last]    
				e.g[w] = a2[:last]  
				break
			}
		}
		u = w
	}
}
func (e *eulerian) keep() {
	for e.s >= 0 {
		n := e.top()
		if len(e.g[n]) > 0 {
			break
		}
		e.p[e.m] = n
		e.s--
		e.m--
	}
}
type eulerian struct {
	g  AdjacencyList  
	m  int            
	uv Bits           
	p []NI  
	s int   
}
func (e *eulerian) top() NI {
	return e.p[e.s]
}
func newEulerian(g AdjacencyList, m int) *eulerian {
	e := &eulerian{
		g: g,
		m: m,
		p: make([]NI, m+1),
	}
	e.uv.SetAll(len(g))
	return e
}
func (g Directed) MaximalNonBranchingPaths(emit func([]NI) bool) {
	ind := g.InDegree()
	var uv Bits
	uv.SetAll(len(g.AdjacencyList))
	for v, vTo := range g.AdjacencyList {
		if !(ind[v] == 1 && len(vTo) == 1) {
			for _, w := range vTo {
				n := []NI{NI(v), w}
				uv.SetBit(NI(v), 0)
				uv.SetBit(w, 0)
				wTo := g.AdjacencyList[w]
				for ind[w] == 1 && len(wTo) == 1 {
					u := wTo[0]
					n = append(n, u)
					uv.SetBit(u, 0)
					w = u
					wTo = g.AdjacencyList[w]
				}
				if !emit(n) {  
					return
				}
			}
		}
	}
	for b := uv.From(0); b >= 0; b = uv.From(b + 1) {
		v := NI(b)
		n := []NI{v}
		for w := v; ; {
			w = g.AdjacencyList[w][0]
			uv.SetBit(w, 0)
			n = append(n, w)
			if w == v {
				break
			}
		}
		if !emit(n) {  
			return
		}
	}
}
func (g Directed) Undirected() Undirected {
	c, _ := g.AdjacencyList.Copy()                   
	rw := make(AdjacencyList, len(g.AdjacencyList))  
	for fr, to := range g.AdjacencyList {
	arc:  
		for _, to := range to {
			if to == NI(fr) {
				continue  
			}
			wf := rw[fr]
			for i, w := range wf {
				if w == to {  
					last := len(wf) - 1
					wf[i] = wf[last]
					rw[fr] = wf[:last]
					continue arc
				}
			}
			rw[to] = append(rw[to], NI(fr))
		}
	}
	for fr, to := range rw {
		c[fr] = append(c[fr], to...)
	}
	return Undirected{c}
}
func (g Directed) Transpose() (t Directed, ma int) {
	ta := make(AdjacencyList, len(g.AdjacencyList))
	for n, nbs := range g.AdjacencyList {
		for _, nb := range nbs {
			ta[nb] = append(ta[nb], NI(n))
			ma++
		}
	}
	return Directed{ta}, ma
}
func (g LabeledDirected) DAGMaxLenPath(ordering []NI) (n NI, path []Half) {
	mlp := make([][]Half, len(g.LabeledAdjacencyList))  
	for i := len(ordering) - 1; i >= 0; i-- {
		fr := ordering[i]  
		to := g.LabeledAdjacencyList[fr]
		if len(to) == 0 {
			continue
		}
		mt := to[0]
		for _, to := range to[1:] {
			if len(mlp[to.To]) > len(mlp[mt.To]) {
				mt = to
			}
		}
		p := append([]Half{mt}, mlp[mt.To]...)
		mlp[fr] = p
		if len(p) > len(path) {
			n = fr
			path = p
		}
	}
	return
}
func (g LabeledDirected) FromListLabels() (*FromList, []LI, NI) {
	labels := make([]LI, len(g.LabeledAdjacencyList))
	paths := make([]PathEnd, len(g.LabeledAdjacencyList))
	for i := range paths {
		paths[i].From = -1
	}
	for fr, to := range g.LabeledAdjacencyList {
		for _, to := range to {
			if paths[to.To].From >= 0 {
				return nil, nil, to.To
			}
			paths[to.To].From = NI(fr)
			labels[to.To] = to.Label
		}
	}
	return &FromList{Paths: paths}, labels, -1
}