add Go dependencies by godep

see https://github.com/tools/godep

1 files changed, 321 insertions, 0 deletions

diff --git a/vendor/github.com/soniakeys/graph/undir.go b/vendor/github.com/soniakeys/graph/undir.go
new file mode 100644
index 0000000..75a7f24
--- /dev/null
+++ b/vendor/github.com/soniakeys/graph/undir.go
@@ -0,0 +1,321 @@
+// Copyright 2014 Sonia Keys
+// License MIT: http://opensource.org/licenses/MIT
+
+package graph
+
+// undir.go has methods specific to undirected graphs, Undirected and
+// LabeledUndirected.
+
+import "errors"
+
+// AddEdge adds an edge to a graph.
+//
+// It can be useful for constructing undirected graphs.
+//
+// When n1 and n2 are distinct, it adds the arc n1->n2 and the reciprocal
+// n2->n1.  When n1 and n2 are the same, it adds a single arc loop.
+//
+// The pointer receiver allows the method to expand the graph as needed
+// to include the values n1 and n2.  If n1 or n2 happen to be greater than
+// len(*p) the method does not panic, but simply expands the graph.
+func (p *Undirected) AddEdge(n1, n2 NI) {
+	// Similar code in LabeledAdjacencyList.AddEdge.
+
+	// determine max of the two end points
+	max := n1
+	if n2 > max {
+		max = n2
+	}
+	// expand graph if needed, to include both
+	g := p.AdjacencyList
+	if int(max) >= len(g) {
+		p.AdjacencyList = make(AdjacencyList, max+1)
+		copy(p.AdjacencyList, g)
+		g = p.AdjacencyList
+	}
+	// create one half-arc,
+	g[n1] = append(g[n1], n2)
+	// and except for loops, create the reciprocal
+	if n1 != n2 {
+		g[n2] = append(g[n2], n1)
+	}
+}
+
+// EulerianCycleD for undirected graphs is a bit of an experiment.
+//
+// It is about the same as the directed version, but modified for an undirected
+// multigraph.
+//
+// Parameter m in this case must be the size of the undirected graph -- the
+// number of edges.  Use Undirected.Size if the size is unknown.
+//
+// It works, but contains an extra loop that I think spoils the time
+// complexity.  Probably still pretty fast in practice, but a different
+// graph representation might be better.
+func (g Undirected) EulerianCycleD(m int) ([]NI, error) {
+	if len(g.AdjacencyList) == 0 {
+		return nil, nil
+	}
+	e := newEulerian(g.AdjacencyList, m)
+	for e.s >= 0 {
+		v := e.top()
+		e.pushUndir() // call modified method
+		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
+}
+
+// TarjanBiconnectedComponents decomposes a graph into maximal biconnected
+// components, components for which if any node were removed the component
+// would remain connected.
+//
+// The receiver g must be a simple graph.  The method calls the emit argument
+// for each component identified, as long as emit returns true.  If emit
+// returns false, TarjanBiconnectedComponents returns immediately.
+//
+// See also the eqivalent labeled TarjanBiconnectedComponents.
+func (g Undirected) TarjanBiconnectedComponents(emit func([]Edge) bool) {
+	// Implemented closely to pseudocode in "Depth-first search and linear
+	// graph algorithms", Robert Tarjan, SIAM J. Comput. Vol. 1, No. 2,
+	// June 1972.
+	//
+	// Note Tarjan's "adjacency structure" is graph.AdjacencyList,
+	// His "adjacency list" is an element of a graph.AdjacencyList, also
+	// termed a "to-list", "neighbor list", or "child list."
+	number := make([]int, len(g.AdjacencyList))
+	lowpt := make([]int, len(g.AdjacencyList))
+	var stack []Edge
+	var i int
+	var biconnect func(NI, NI) bool
+	biconnect = func(v, u NI) bool {
+		i++
+		number[v] = i
+		lowpt[v] = i
+		for _, w := range g.AdjacencyList[v] {
+			if number[w] == 0 {
+				stack = append(stack, Edge{v, w})
+				if !biconnect(w, v) {
+					return false
+				}
+				if lowpt[w] < lowpt[v] {
+					lowpt[v] = lowpt[w]
+				}
+				if lowpt[w] >= number[v] {
+					var bcc []Edge
+					top := len(stack) - 1
+					for number[stack[top].N1] >= number[w] {
+						bcc = append(bcc, stack[top])
+						stack = stack[:top]
+						top--
+					}
+					bcc = append(bcc, stack[top])
+					stack = stack[:top]
+					top--
+					if !emit(bcc) {
+						return false
+					}
+				}
+			} else if number[w] < number[v] && w != u {
+				stack = append(stack, Edge{v, w})
+				if number[w] < lowpt[v] {
+					lowpt[v] = number[w]
+				}
+			}
+		}
+		return true
+	}
+	for w := range g.AdjacencyList {
+		if number[w] == 0 && !biconnect(NI(w), 0) {
+			return
+		}
+	}
+}
+
+/* half-baked.  Read the 72 paper.  Maybe revisit at some point.
+type BiconnectedComponents struct {
+	Graph  AdjacencyList
+	Start  int
+	Cuts   big.Int // bitmap of node cuts
+	From   []int   // from-tree
+	Leaves []int   // leaves of from-tree
+}
+
+func NewBiconnectedComponents(g Undirected) *BiconnectedComponents {
+	return &BiconnectedComponents{
+		Graph: g,
+		From:  make([]int, len(g)),
+	}
+}
+
+func (b *BiconnectedComponents) Find(start int) {
+	g := b.Graph
+	depth := make([]int, len(g))
+	low := make([]int, len(g))
+	// reset from any previous run
+	b.Cuts.SetInt64(0)
+	bf := b.From
+	for n := range bf {
+		bf[n] = -1
+	}
+	b.Leaves = b.Leaves[:0]
+	d := 1 // depth. d > 0 means visited
+	depth[start] = d
+	low[start] = d
+	d++
+	var df func(int, int)
+	df = func(from, n int) {
+		bf[n] = from
+		depth[n] = d
+		dn := d
+		l := d
+		d++
+		cut := false
+		leaf := true
+		for _, nb := range g[n] {
+			if depth[nb] == 0 {
+				leaf = false
+				df(n, nb)
+				if low[nb] < l {
+					l = low[nb]
+				}
+				if low[nb] >= dn {
+					cut = true
+				}
+			} else if nb != from && depth[nb] < l {
+				l = depth[nb]
+			}
+		}
+		low[n] = l
+		if cut {
+			b.Cuts.SetBit(&b.Cuts, n, 1)
+		}
+		if leaf {
+			b.Leaves = append(b.Leaves, n)
+		}
+		d--
+	}
+	nbs := g[start]
+	if len(nbs) == 0 {
+		return
+	}
+	df(start, nbs[0])
+	var rc uint
+	for _, nb := range nbs[1:] {
+		if depth[nb] == 0 {
+			rc = 1
+			df(start, nb)
+		}
+	}
+	b.Cuts.SetBit(&b.Cuts, start, rc)
+	return
+}
+*/
+
+// AddEdge adds an edge to a labeled graph.
+//
+// It can be useful for constructing undirected graphs.
+//
+// When n1 and n2 are distinct, it adds the arc n1->n2 and the reciprocal
+// n2->n1.  When n1 and n2 are the same, it adds a single arc loop.
+//
+// If the edge already exists in *p, a parallel edge is added.
+//
+// The pointer receiver allows the method to expand the graph as needed
+// to include the values n1 and n2.  If n1 or n2 happen to be greater than
+// len(*p) the method does not panic, but simply expands the graph.
+func (p *LabeledUndirected) AddEdge(e Edge, l LI) {
+	// Similar code in AdjacencyList.AddEdge.
+
+	// determine max of the two end points
+	max := e.N1
+	if e.N2 > max {
+		max = e.N2
+	}
+	// expand graph if needed, to include both
+	g := p.LabeledAdjacencyList
+	if max >= NI(len(g)) {
+		p.LabeledAdjacencyList = make(LabeledAdjacencyList, max+1)
+		copy(p.LabeledAdjacencyList, g)
+		g = p.LabeledAdjacencyList
+	}
+	// create one half-arc,
+	g[e.N1] = append(g[e.N1], Half{To: e.N2, Label: l})
+	// and except for loops, create the reciprocal
+	if e.N1 != e.N2 {
+		g[e.N2] = append(g[e.N2], Half{To: e.N1, Label: l})
+	}
+}
+
+// TarjanBiconnectedComponents decomposes a graph into maximal biconnected
+// components, components for which if any node were removed the component
+// would remain connected.
+//
+// The receiver g must be a simple graph.  The method calls the emit argument
+// for each component identified, as long as emit returns true.  If emit
+// returns false, TarjanBiconnectedComponents returns immediately.
+//
+// See also the eqivalent unlabeled TarjanBiconnectedComponents.
+func (g LabeledUndirected) TarjanBiconnectedComponents(emit func([]LabeledEdge) bool) {
+	// Implemented closely to pseudocode in "Depth-first search and linear
+	// graph algorithms", Robert Tarjan, SIAM J. Comput. Vol. 1, No. 2,
+	// June 1972.
+	//
+	// Note Tarjan's "adjacency structure" is graph.AdjacencyList,
+	// His "adjacency list" is an element of a graph.AdjacencyList, also
+	// termed a "to-list", "neighbor list", or "child list."
+	//
+	// Nearly identical code in undir.go.
+	number := make([]int, len(g.LabeledAdjacencyList))
+	lowpt := make([]int, len(g.LabeledAdjacencyList))
+	var stack []LabeledEdge
+	var i int
+	var biconnect func(NI, NI) bool
+	biconnect = func(v, u NI) bool {
+		i++
+		number[v] = i
+		lowpt[v] = i
+		for _, w := range g.LabeledAdjacencyList[v] {
+			if number[w.To] == 0 {
+				stack = append(stack, LabeledEdge{Edge{v, w.To}, w.Label})
+				if !biconnect(w.To, v) {
+					return false
+				}
+				if lowpt[w.To] < lowpt[v] {
+					lowpt[v] = lowpt[w.To]
+				}
+				if lowpt[w.To] >= number[v] {
+					var bcc []LabeledEdge
+					top := len(stack) - 1
+					for number[stack[top].N1] >= number[w.To] {
+						bcc = append(bcc, stack[top])
+						stack = stack[:top]
+						top--
+					}
+					bcc = append(bcc, stack[top])
+					stack = stack[:top]
+					top--
+					if !emit(bcc) {
+						return false
+					}
+				}
+			} else if number[w.To] < number[v] && w.To != u {
+				stack = append(stack, LabeledEdge{Edge{v, w.To}, w.Label})
+				if number[w.To] < lowpt[v] {
+					lowpt[v] = number[w.To]
+				}
+			}
+		}
+		return true
+	}
+	for w := range g.LabeledAdjacencyList {
+		if number[w] == 0 && !biconnect(NI(w), 0) {
+			return
+		}
+	}
+}