diff options
Diffstat (limited to 'vendor/github.com/soniakeys')
23 files changed, 0 insertions, 6591 deletions
diff --git a/vendor/github.com/soniakeys/graph/.gitignore b/vendor/github.com/soniakeys/graph/.gitignore deleted file mode 100644 index 3be6158..0000000 --- a/vendor/github.com/soniakeys/graph/.gitignore +++ /dev/null @@ -1,2 +0,0 @@ -*.dot - diff --git a/vendor/github.com/soniakeys/graph/.travis.yml b/vendor/github.com/soniakeys/graph/.travis.yml deleted file mode 100644 index bcc4f9f..0000000 --- a/vendor/github.com/soniakeys/graph/.travis.yml +++ /dev/null @@ -1,8 +0,0 @@ -sudo: false -language: go -# update travis.sh when changing version number here -go: - - 1.2.1 - - 1.6 -install: go get -t ./... -script: ./travis.sh diff --git a/vendor/github.com/soniakeys/graph/adj.go b/vendor/github.com/soniakeys/graph/adj.go deleted file mode 100644 index 165f365..0000000 --- a/vendor/github.com/soniakeys/graph/adj.go +++ /dev/null @@ -1,325 +0,0 @@ -// Copyright 2014 Sonia Keys -// License MIT: https://opensource.org/licenses/MIT - -package graph - -// adj.go contains methods on AdjacencyList and LabeledAdjacencyList. -// -// AdjacencyList methods are placed first and are alphabetized. -// LabeledAdjacencyList methods follow, also alphabetized. -// Only exported methods need be alphabetized; non-exported methods can -// be left near their use. - -import ( - "math" - "sort" -) - -// HasParallelSort identifies if a graph contains parallel arcs, multiple arcs -// that lead from a node to the same node. -// -// If the graph has parallel arcs, the results fr and to represent an example -// where there are parallel arcs from node fr to node to. -// -// If there are no parallel arcs, the method returns false -1 -1. -// -// Multiple loops on a node count as parallel arcs. -// -// "Sort" in the method name indicates that sorting is used to detect parallel -// arcs. Compared to method HasParallelMap, this may give better performance -// for small or sparse graphs but will have asymtotically worse performance for -// large dense graphs. -func (g AdjacencyList) HasParallelSort() (has bool, fr, to NI) { - var t NodeList - for n, to := range g { - if len(to) == 0 { - continue - } - // different code in the labeled version, so no code gen. - t = append(t[:0], to...) - sort.Sort(t) - t0 := t[0] - for _, to := range t[1:] { - if to == t0 { - return true, NI(n), t0 - } - t0 = to - } - } - return false, -1, -1 -} - -// IsUndirected returns true if g represents an undirected graph. -// -// Returns true when all non-loop arcs are paired in reciprocal pairs. -// Otherwise returns false and an example unpaired arc. -func (g AdjacencyList) IsUndirected() (u bool, from, to NI) { - // similar code in dot/writeUndirected - unpaired := make(AdjacencyList, len(g)) - for fr, to := range g { - arc: // for each arc in g - for _, to := range to { - if to == NI(fr) { - continue // loop - } - // search unpaired arcs - ut := unpaired[to] - for i, u := range ut { - if u == NI(fr) { // found reciprocal - last := len(ut) - 1 - ut[i] = ut[last] - unpaired[to] = ut[:last] - continue arc - } - } - // reciprocal not found - unpaired[fr] = append(unpaired[fr], to) - } - } - for fr, to := range unpaired { - if len(to) > 0 { - return false, NI(fr), to[0] - } - } - return true, -1, -1 -} - -// Edgelist constructs the edge list rerpresentation of a graph. -// -// An edge is returned for each arc of the graph. For undirected graphs -// this includes reciprocal edges. -// -// See also WeightedEdgeList method. -func (g LabeledAdjacencyList) EdgeList() (el []LabeledEdge) { - for fr, to := range g { - for _, to := range to { - el = append(el, LabeledEdge{Edge{NI(fr), to.To}, to.Label}) - } - } - return -} - -// FloydWarshall finds all pairs shortest distances for a simple weighted -// graph without negative cycles. -// -// In result array d, d[i][j] will be the shortest distance from node i -// to node j. Any diagonal element < 0 indicates a negative cycle exists. -// -// If g is an undirected graph with no negative edge weights, the result -// array will be a distance matrix, for example as used by package -// github.com/soniakeys/cluster. -func (g LabeledAdjacencyList) FloydWarshall(w WeightFunc) (d [][]float64) { - d = newFWd(len(g)) - for fr, to := range g { - for _, to := range to { - d[fr][to.To] = w(to.Label) - } - } - solveFW(d) - return -} - -// little helper function, makes a blank matrix for FloydWarshall. -func newFWd(n int) [][]float64 { - d := make([][]float64, n) - for i := range d { - di := make([]float64, n) - for j := range di { - if j != i { - di[j] = math.Inf(1) - } - } - d[i] = di - } - return d -} - -// Floyd Warshall solver, once the matrix d is initialized by arc weights. -func solveFW(d [][]float64) { - for k, dk := range d { - for _, di := range d { - dik := di[k] - for j := range d { - if d2 := dik + dk[j]; d2 < di[j] { - di[j] = d2 - } - } - } - } -} - -// HasArcLabel returns true if g has any arc from node fr to node to -// with label l. -// -// Also returned is the index within the slice of arcs from node fr. -// If no arc from fr to to is present, HasArcLabel returns false, -1. -func (g LabeledAdjacencyList) HasArcLabel(fr, to NI, l LI) (bool, int) { - t := Half{to, l} - for x, h := range g[fr] { - if h == t { - return true, x - } - } - return false, -1 -} - -// HasParallelSort identifies if a graph contains parallel arcs, multiple arcs -// that lead from a node to the same node. -// -// If the graph has parallel arcs, the results fr and to represent an example -// where there are parallel arcs from node fr to node to. -// -// If there are no parallel arcs, the method returns -1 -1. -// -// Multiple loops on a node count as parallel arcs. -// -// "Sort" in the method name indicates that sorting is used to detect parallel -// arcs. Compared to method HasParallelMap, this may give better performance -// for small or sparse graphs but will have asymtotically worse performance for -// large dense graphs. -func (g LabeledAdjacencyList) HasParallelSort() (has bool, fr, to NI) { - var t NodeList - for n, to := range g { - if len(to) == 0 { - continue - } - // slightly different code needed here compared to AdjacencyList - t = t[:0] - for _, to := range to { - t = append(t, to.To) - } - sort.Sort(t) - t0 := t[0] - for _, to := range t[1:] { - if to == t0 { - return true, NI(n), t0 - } - t0 = to - } - } - return false, -1, -1 -} - -// IsUndirected returns true if g represents an undirected graph. -// -// Returns true when all non-loop arcs are paired in reciprocal pairs with -// matching labels. Otherwise returns false and an example unpaired arc. -// -// Note the requirement that reciprocal pairs have matching labels is -// an additional test not present in the otherwise equivalent unlabeled version -// of IsUndirected. -func (g LabeledAdjacencyList) IsUndirected() (u bool, from NI, to Half) { - unpaired := make(LabeledAdjacencyList, len(g)) - for fr, to := range g { - arc: // for each arc in g - for _, to := range to { - if to.To == NI(fr) { - continue // loop - } - // search unpaired arcs - ut := unpaired[to.To] - for i, u := range ut { - if u.To == NI(fr) && u.Label == to.Label { // found reciprocal - last := len(ut) - 1 - ut[i] = ut[last] - unpaired[to.To] = ut[:last] - continue arc - } - } - // reciprocal not found - unpaired[fr] = append(unpaired[fr], to) - } - } - for fr, to := range unpaired { - if len(to) > 0 { - return false, NI(fr), to[0] - } - } - return true, -1, to -} - -// NegativeArc returns true if the receiver graph contains a negative arc. -func (g LabeledAdjacencyList) NegativeArc(w WeightFunc) bool { - for _, nbs := range g { - for _, nb := range nbs { - if w(nb.Label) < 0 { - return true - } - } - } - return false -} - -// Unlabeled constructs the unlabeled graph corresponding to g. -func (g LabeledAdjacencyList) Unlabeled() AdjacencyList { - a := make(AdjacencyList, len(g)) - for n, nbs := range g { - to := make([]NI, len(nbs)) - for i, nb := range nbs { - to[i] = nb.To - } - a[n] = to - } - return a -} - -// WeightedEdgeList constructs a WeightedEdgeList object from a -// LabeledAdjacencyList. -// -// Internally it calls g.EdgeList() to obtain the Edges member. -// See LabeledAdjacencyList.EdgeList(). -func (g LabeledAdjacencyList) WeightedEdgeList(w WeightFunc) *WeightedEdgeList { - return &WeightedEdgeList{ - Order: len(g), - WeightFunc: w, - Edges: g.EdgeList(), - } -} - -// WeightedInDegree computes the weighted in-degree of each node in g -// for a given weight function w. -// -// The weighted in-degree of a node is the sum of weights of arcs going to -// the node. -// -// A weighted degree of a node is often termed the "strength" of a node. -// -// See note for undirected graphs at LabeledAdjacencyList.WeightedOutDegree. -func (g LabeledAdjacencyList) WeightedInDegree(w WeightFunc) []float64 { - ind := make([]float64, len(g)) - for _, to := range g { - for _, to := range to { - ind[to.To] += w(to.Label) - } - } - return ind -} - -// WeightedOutDegree computes the weighted out-degree of the specified node -// for a given weight function w. -// -// The weighted out-degree of a node is the sum of weights of arcs going from -// the node. -// -// A weighted degree of a node is often termed the "strength" of a node. -// -// Note for undirected graphs, the WeightedOutDegree result for a node will -// equal the WeightedInDegree for the node. You can use WeightedInDegree if -// you have need for the weighted degrees of all nodes or use WeightedOutDegree -// to compute the weighted degrees of individual nodes. In either case loops -// are counted just once, unlike the (unweighted) UndirectedDegree methods. -func (g LabeledAdjacencyList) WeightedOutDegree(n NI, w WeightFunc) (d float64) { - for _, to := range g[n] { - d += w(to.Label) - } - return -} - -// More about loops and strength: I didn't see consensus on this especially -// in the case of undirected graphs. Some sources said to add in-degree and -// out-degree, which would seemingly double both loops and non-loops. -// Some said to double loops. Some said sum the edge weights and had no -// comment on loops. R of course makes everything an option. The meaning -// of "strength" where loops exist is unclear. So while I could write an -// UndirectedWeighted degree function that doubles loops but not edges, -// I'm going to just leave this for now. diff --git a/vendor/github.com/soniakeys/graph/adj_RO.go b/vendor/github.com/soniakeys/graph/adj_RO.go deleted file mode 100644 index 1d37d14..0000000 --- a/vendor/github.com/soniakeys/graph/adj_RO.go +++ /dev/null @@ -1,387 +0,0 @@ -// Copyright 2014 Sonia Keys -// License MIT: http://opensource.org/licenses/MIT - -package graph - -// adj_RO.go is code generated from adj_cg.go by directives in graph.go. -// Editing adj_cg.go is okay. -// DO NOT EDIT adj_RO.go. The RO is for Read Only. - -import ( - "math/rand" - "time" -) - -// ArcSize returns the number of arcs in g. -// -// Note that for an undirected graph without loops, the number of undirected -// edges -- the traditional meaning of graph size -- will be ArcSize()/2. -// On the other hand, if g is an undirected graph that has or may have loops, -// g.ArcSize()/2 is not a meaningful quantity. -// -// There are equivalent labeled and unlabeled versions of this method. -func (g AdjacencyList) ArcSize() int { - m := 0 - for _, to := range g { - m += len(to) - } - return m -} - -// BoundsOk validates that all arcs in g stay within the slice bounds of g. -// -// BoundsOk returns true when no arcs point outside the bounds of g. -// Otherwise it returns false and an example arc that points outside of g. -// -// Most methods of this package assume the BoundsOk condition and may -// panic when they encounter an arc pointing outside of the graph. This -// function can be used to validate a graph when the BoundsOk condition -// is unknown. -// -// There are equivalent labeled and unlabeled versions of this method. -func (g AdjacencyList) BoundsOk() (ok bool, fr NI, to NI) { - for fr, to := range g { - for _, to := range to { - if to < 0 || to >= NI(len(g)) { - return false, NI(fr), to - } - } - } - return true, -1, to -} - -// BreadthFirst traverses a directed or undirected graph in breadth first order. -// -// Argument start is the start node for the traversal. If r is nil, nodes are -// visited in deterministic order. If a random number generator is supplied, -// nodes at each level are visited in random order. -// -// Argument f can be nil if you have no interest in the FromList path result. -// If FromList f is non-nil, the method populates f.Paths and sets f.MaxLen. -// It does not set f.Leaves. For convenience argument f can be a zero value -// FromList. If f.Paths is nil, the FromList is initialized first. If f.Paths -// is non-nil however, the FromList is used as is. The method uses a value of -// PathEnd.Len == 0 to indentify unvisited nodes. Existing non-zero values -// will limit the traversal. -// -// Traversal calls the visitor function v for each node starting with node -// start. If v returns true, traversal continues. If v returns false, the -// traversal terminates immediately. PathEnd Len and From values are updated -// before calling the visitor function. -// -// On return f.Paths and f.MaxLen are set but not f.Leaves. -// -// Returned is the number of nodes visited and ok = true if the traversal -// ran to completion or ok = false if it was terminated by the visitor -// function returning false. -// -// There are equivalent labeled and unlabeled versions of this method. -func (g AdjacencyList) BreadthFirst(start NI, r *rand.Rand, f *FromList, v OkNodeVisitor) (visited int, ok bool) { - switch { - case f == nil: - e := NewFromList(len(g)) - f = &e - case f.Paths == nil: - *f = NewFromList(len(g)) - } - rp := f.Paths - // the frontier consists of nodes all at the same level - frontier := []NI{start} - level := 1 - // assign path when node is put on frontier, - rp[start] = PathEnd{Len: level, From: -1} - for { - f.MaxLen = level - level++ - var next []NI - if r == nil { - for _, n := range frontier { - visited++ - if !v(n) { // visit nodes as they come off frontier - return - } - for _, nb := range g[n] { - if rp[nb].Len == 0 { - next = append(next, nb) - rp[nb] = PathEnd{From: n, Len: level} - } - } - } - } else { // take nodes off frontier at random - for _, i := range r.Perm(len(frontier)) { - n := frontier[i] - // remainder of block same as above - visited++ - if !v(n) { - return - } - for _, nb := range g[n] { - if rp[nb].Len == 0 { - next = append(next, nb) - rp[nb] = PathEnd{From: n, Len: level} - } - } - } - } - if len(next) == 0 { - break - } - frontier = next - } - return visited, true -} - -// BreadthFirstPath finds a single path from start to end with a minimum -// number of nodes. -// -// Returned is the path as list of nodes. -// The result is nil if no path was found. -// -// There are equivalent labeled and unlabeled versions of this method. -func (g AdjacencyList) BreadthFirstPath(start, end NI) []NI { - var f FromList - g.BreadthFirst(start, nil, &f, func(n NI) bool { return n != end }) - return f.PathTo(end, nil) -} - -// Copy makes a deep copy of g. -// Copy also computes the arc size ma, the number of arcs. -// -// There are equivalent labeled and unlabeled versions of this method. -func (g AdjacencyList) Copy() (c AdjacencyList, ma int) { - c = make(AdjacencyList, len(g)) - for n, to := range g { - c[n] = append([]NI{}, to...) - ma += len(to) - } - return -} - -// DepthFirst traverses a graph depth first. -// -// As it traverses it calls visitor function v for each node. If v returns -// false at any point, the traversal is terminated immediately and DepthFirst -// returns false. Otherwise DepthFirst returns true. -// -// DepthFirst uses argument bm is used as a bitmap to guide the traversal. -// For a complete traversal, bm should be 0 initially. During the -// traversal, bits are set corresponding to each node visited. -// The bit is set before calling the visitor function. -// -// Argument bm can be nil if you have no need for it. -// In this case a bitmap is created internally for one-time use. -// -// Alternatively v can be nil. In this case traversal still proceeds and -// updates the bitmap, which can be a useful result. -// DepthFirst always returns true in this case. -// -// It makes no sense for both bm and v to be nil. In this case DepthFirst -// returns false immediately. -// -// There are equivalent labeled and unlabeled versions of this method. -func (g AdjacencyList) DepthFirst(start NI, bm *Bits, v OkNodeVisitor) (ok bool) { - if bm == nil { - if v == nil { - return false - } - bm = &Bits{} - } - var df func(n NI) bool - df = func(n NI) bool { - if bm.Bit(n) == 1 { - return true - } - bm.SetBit(n, 1) - if v != nil && !v(n) { - return false - } - for _, nb := range g[n] { - if !df(nb) { - return false - } - } - return true - } - return df(start) -} - -// DepthFirstRandom traverses a graph depth first, but following arcs in -// random order among arcs from a single node. -// -// If Rand r is nil, the method creates a new source and generator for -// one-time use. -// -// Usage is otherwise like the DepthFirst method. See DepthFirst. -// -// There are equivalent labeled and unlabeled versions of this method. -func (g AdjacencyList) DepthFirstRandom(start NI, bm *Bits, v OkNodeVisitor, r *rand.Rand) (ok bool) { - if bm == nil { - if v == nil { - return false - } - bm = &Bits{} - } - if r == nil { - r = rand.New(rand.NewSource(time.Now().UnixNano())) - } - var df func(n NI) bool - df = func(n NI) bool { - if bm.Bit(n) == 1 { - return true - } - bm.SetBit(n, 1) - if v != nil && !v(n) { - return false - } - to := g[n] - for _, i := range r.Perm(len(to)) { - if !df(to[i]) { - return false - } - } - return true - } - return df(start) -} - -// HasArc returns true if g has any arc from node fr to node to. -// -// Also returned is the index within the slice of arcs from node fr. -// If no arc from fr to to is present, HasArc returns false, -1. -// -// There are equivalent labeled and unlabeled versions of this method. -func (g AdjacencyList) HasArc(fr, to NI) (bool, int) { - for x, h := range g[fr] { - if h == to { - return true, x - } - } - return false, -1 -} - -// HasLoop identifies if a graph contains a loop, an arc that leads from a -// a node back to the same node. -// -// If the graph has a loop, the result is an example node that has a loop. -// -// If g contains a loop, the method returns true and an example of a node -// with a loop. If there are no loops in g, the method returns false, -1. -// -// There are equivalent labeled and unlabeled versions of this method. -func (g AdjacencyList) HasLoop() (bool, NI) { - for fr, to := range g { - for _, to := range to { - if NI(fr) == to { - return true, to - } - } - } - return false, -1 -} - -// HasParallelMap identifies if a graph contains parallel arcs, multiple arcs -// that lead from a node to the same node. -// -// If the graph has parallel arcs, the method returns true and -// results fr and to represent an example where there are parallel arcs -// from node fr to node to. -// -// If there are no parallel arcs, the method returns false, -1 -1. -// -// Multiple loops on a node count as parallel arcs. -// -// "Map" in the method name indicates that a Go map is used to detect parallel -// arcs. Compared to method HasParallelSort, this gives better asymtotic -// performance for large dense graphs but may have increased overhead for -// small or sparse graphs. -// -// There are equivalent labeled and unlabeled versions of this method. -func (g AdjacencyList) HasParallelMap() (has bool, fr, to NI) { - for n, to := range g { - if len(to) == 0 { - continue - } - m := map[NI]struct{}{} - for _, to := range to { - if _, ok := m[to]; ok { - return true, NI(n), to - } - m[to] = struct{}{} - } - } - return false, -1, -1 -} - -// IsSimple checks for loops and parallel arcs. -// -// A graph is "simple" if it has no loops or parallel arcs. -// -// IsSimple returns true, -1 for simple graphs. If a loop or parallel arc is -// found, simple returns false and a node that represents a counterexample -// to the graph being simple. -// -// See also separate methods HasLoop and HasParallel. -// -// There are equivalent labeled and unlabeled versions of this method. -func (g AdjacencyList) IsSimple() (ok bool, n NI) { - if lp, n := g.HasLoop(); lp { - return false, n - } - if pa, n, _ := g.HasParallelSort(); pa { - return false, n - } - return true, -1 -} - -// IsolatedNodes returns a bitmap of isolated nodes in receiver graph g. -// -// An isolated node is one with no arcs going to or from it. -// -// There are equivalent labeled and unlabeled versions of this method. -func (g AdjacencyList) IsolatedNodes() (i Bits) { - i.SetAll(len(g)) - for fr, to := range g { - if len(to) > 0 { - i.SetBit(NI(fr), 0) - for _, to := range to { - i.SetBit(to, 0) - } - } - } - return -} - -/* -MaxmimalClique finds a maximal clique containing the node n. - -Not sure this is good for anything. It produces a single maximal clique -but there can be multiple maximal cliques containing a given node. -This algorithm just returns one of them, not even necessarily the -largest one. - -func (g LabeledAdjacencyList) MaximalClique(n int) []int { - c := []int{n} - var m bitset.BitSet - m.Set(uint(n)) - for fr, to := range g { - if fr == n { - continue - } - if len(to) < len(c) { - continue - } - f := 0 - for _, to := range to { - if m.Test(uint(to.To)) { - f++ - if f == len(c) { - c = append(c, to.To) - m.Set(uint(to.To)) - break - } - } - } - } - return c -} -*/ diff --git a/vendor/github.com/soniakeys/graph/adj_cg.go b/vendor/github.com/soniakeys/graph/adj_cg.go deleted file mode 100644 index a484ee0..0000000 --- a/vendor/github.com/soniakeys/graph/adj_cg.go +++ /dev/null @@ -1,387 +0,0 @@ -// Copyright 2014 Sonia Keys -// License MIT: http://opensource.org/licenses/MIT - -package graph - -// adj_RO.go is code generated from adj_cg.go by directives in graph.go. -// Editing adj_cg.go is okay. -// DO NOT EDIT adj_RO.go. The RO is for Read Only. - -import ( - "math/rand" - "time" -) - -// ArcSize returns the number of arcs in g. -// -// Note that for an undirected graph without loops, the number of undirected -// edges -- the traditional meaning of graph size -- will be ArcSize()/2. -// On the other hand, if g is an undirected graph that has or may have loops, -// g.ArcSize()/2 is not a meaningful quantity. -// -// There are equivalent labeled and unlabeled versions of this method. -func (g LabeledAdjacencyList) ArcSize() int { - m := 0 - for _, to := range g { - m += len(to) - } - return m -} - -// BoundsOk validates that all arcs in g stay within the slice bounds of g. -// -// BoundsOk returns true when no arcs point outside the bounds of g. -// Otherwise it returns false and an example arc that points outside of g. -// -// Most methods of this package assume the BoundsOk condition and may -// panic when they encounter an arc pointing outside of the graph. This -// function can be used to validate a graph when the BoundsOk condition -// is unknown. -// -// There are equivalent labeled and unlabeled versions of this method. -func (g LabeledAdjacencyList) BoundsOk() (ok bool, fr NI, to Half) { - for fr, to := range g { - for _, to := range to { - if to.To < 0 || to.To >= NI(len(g)) { - return false, NI(fr), to - } - } - } - return true, -1, to -} - -// BreadthFirst traverses a directed or undirected graph in breadth first order. -// -// Argument start is the start node for the traversal. If r is nil, nodes are -// visited in deterministic order. If a random number generator is supplied, -// nodes at each level are visited in random order. -// -// Argument f can be nil if you have no interest in the FromList path result. -// If FromList f is non-nil, the method populates f.Paths and sets f.MaxLen. -// It does not set f.Leaves. For convenience argument f can be a zero value -// FromList. If f.Paths is nil, the FromList is initialized first. If f.Paths -// is non-nil however, the FromList is used as is. The method uses a value of -// PathEnd.Len == 0 to indentify unvisited nodes. Existing non-zero values -// will limit the traversal. -// -// Traversal calls the visitor function v for each node starting with node -// start. If v returns true, traversal continues. If v returns false, the -// traversal terminates immediately. PathEnd Len and From values are updated -// before calling the visitor function. -// -// On return f.Paths and f.MaxLen are set but not f.Leaves. -// -// Returned is the number of nodes visited and ok = true if the traversal -// ran to completion or ok = false if it was terminated by the visitor -// function returning false. -// -// There are equivalent labeled and unlabeled versions of this method. -func (g LabeledAdjacencyList) BreadthFirst(start NI, r *rand.Rand, f *FromList, v OkNodeVisitor) (visited int, ok bool) { - switch { - case f == nil: - e := NewFromList(len(g)) - f = &e - case f.Paths == nil: - *f = NewFromList(len(g)) - } - rp := f.Paths - // the frontier consists of nodes all at the same level - frontier := []NI{start} - level := 1 - // assign path when node is put on frontier, - rp[start] = PathEnd{Len: level, From: -1} - for { - f.MaxLen = level - level++ - var next []NI - if r == nil { - for _, n := range frontier { - visited++ - if !v(n) { // visit nodes as they come off frontier - return - } - for _, nb := range g[n] { - if rp[nb.To].Len == 0 { - next = append(next, nb.To) - rp[nb.To] = PathEnd{From: n, Len: level} - } - } - } - } else { // take nodes off frontier at random - for _, i := range r.Perm(len(frontier)) { - n := frontier[i] - // remainder of block same as above - visited++ - if !v(n) { - return - } - for _, nb := range g[n] { - if rp[nb.To].Len == 0 { - next = append(next, nb.To) - rp[nb.To] = PathEnd{From: n, Len: level} - } - } - } - } - if len(next) == 0 { - break - } - frontier = next - } - return visited, true -} - -// BreadthFirstPath finds a single path from start to end with a minimum -// number of nodes. -// -// Returned is the path as list of nodes. -// The result is nil if no path was found. -// -// There are equivalent labeled and unlabeled versions of this method. -func (g LabeledAdjacencyList) BreadthFirstPath(start, end NI) []NI { - var f FromList - g.BreadthFirst(start, nil, &f, func(n NI) bool { return n != end }) - return f.PathTo(end, nil) -} - -// Copy makes a deep copy of g. -// Copy also computes the arc size ma, the number of arcs. -// -// There are equivalent labeled and unlabeled versions of this method. -func (g LabeledAdjacencyList) Copy() (c LabeledAdjacencyList, ma int) { - c = make(LabeledAdjacencyList, len(g)) - for n, to := range g { - c[n] = append([]Half{}, to...) - ma += len(to) - } - return -} - -// DepthFirst traverses a graph depth first. -// -// As it traverses it calls visitor function v for each node. If v returns -// false at any point, the traversal is terminated immediately and DepthFirst -// returns false. Otherwise DepthFirst returns true. -// -// DepthFirst uses argument bm is used as a bitmap to guide the traversal. -// For a complete traversal, bm should be 0 initially. During the -// traversal, bits are set corresponding to each node visited. -// The bit is set before calling the visitor function. -// -// Argument bm can be nil if you have no need for it. -// In this case a bitmap is created internally for one-time use. -// -// Alternatively v can be nil. In this case traversal still proceeds and -// updates the bitmap, which can be a useful result. -// DepthFirst always returns true in this case. -// -// It makes no sense for both bm and v to be nil. In this case DepthFirst -// returns false immediately. -// -// There are equivalent labeled and unlabeled versions of this method. -func (g LabeledAdjacencyList) DepthFirst(start NI, bm *Bits, v OkNodeVisitor) (ok bool) { - if bm == nil { - if v == nil { - return false - } - bm = &Bits{} - } - var df func(n NI) bool - df = func(n NI) bool { - if bm.Bit(n) == 1 { - return true - } - bm.SetBit(n, 1) - if v != nil && !v(n) { - return false - } - for _, nb := range g[n] { - if !df(nb.To) { - return false - } - } - return true - } - return df(start) -} - -// DepthFirstRandom traverses a graph depth first, but following arcs in -// random order among arcs from a single node. -// -// If Rand r is nil, the method creates a new source and generator for -// one-time use. -// -// Usage is otherwise like the DepthFirst method. See DepthFirst. -// -// There are equivalent labeled and unlabeled versions of this method. -func (g LabeledAdjacencyList) DepthFirstRandom(start NI, bm *Bits, v OkNodeVisitor, r *rand.Rand) (ok bool) { - if bm == nil { - if v == nil { - return false - } - bm = &Bits{} - } - if r == nil { - r = rand.New(rand.NewSource(time.Now().UnixNano())) - } - var df func(n NI) bool - df = func(n NI) bool { - if bm.Bit(n) == 1 { - return true - } - bm.SetBit(n, 1) - if v != nil && !v(n) { - return false - } - to := g[n] - for _, i := range r.Perm(len(to)) { - if !df(to[i].To) { - return false - } - } - return true - } - return df(start) -} - -// HasArc returns true if g has any arc from node fr to node to. -// -// Also returned is the index within the slice of arcs from node fr. -// If no arc from fr to to is present, HasArc returns false, -1. -// -// There are equivalent labeled and unlabeled versions of this method. -func (g LabeledAdjacencyList) HasArc(fr, to NI) (bool, int) { - for x, h := range g[fr] { - if h.To == to { - return true, x - } - } - return false, -1 -} - -// HasLoop identifies if a graph contains a loop, an arc that leads from a -// a node back to the same node. -// -// If the graph has a loop, the result is an example node that has a loop. -// -// If g contains a loop, the method returns true and an example of a node -// with a loop. If there are no loops in g, the method returns false, -1. -// -// There are equivalent labeled and unlabeled versions of this method. -func (g LabeledAdjacencyList) HasLoop() (bool, NI) { - for fr, to := range g { - for _, to := range to { - if NI(fr) == to.To { - return true, to.To - } - } - } - return false, -1 -} - -// HasParallelMap identifies if a graph contains parallel arcs, multiple arcs -// that lead from a node to the same node. -// -// If the graph has parallel arcs, the method returns true and -// results fr and to represent an example where there are parallel arcs -// from node fr to node to. -// -// If there are no parallel arcs, the method returns false, -1 -1. -// -// Multiple loops on a node count as parallel arcs. -// -// "Map" in the method name indicates that a Go map is used to detect parallel -// arcs. Compared to method HasParallelSort, this gives better asymtotic -// performance for large dense graphs but may have increased overhead for -// small or sparse graphs. -// -// There are equivalent labeled and unlabeled versions of this method. -func (g LabeledAdjacencyList) HasParallelMap() (has bool, fr, to NI) { - for n, to := range g { - if len(to) == 0 { - continue - } - m := map[NI]struct{}{} - for _, to := range to { - if _, ok := m[to.To]; ok { - return true, NI(n), to.To - } - m[to.To] = struct{}{} - } - } - return false, -1, -1 -} - -// IsSimple checks for loops and parallel arcs. -// -// A graph is "simple" if it has no loops or parallel arcs. -// -// IsSimple returns true, -1 for simple graphs. If a loop or parallel arc is -// found, simple returns false and a node that represents a counterexample -// to the graph being simple. -// -// See also separate methods HasLoop and HasParallel. -// -// There are equivalent labeled and unlabeled versions of this method. -func (g LabeledAdjacencyList) IsSimple() (ok bool, n NI) { - if lp, n := g.HasLoop(); lp { - return false, n - } - if pa, n, _ := g.HasParallelSort(); pa { - return false, n - } - return true, -1 -} - -// IsolatedNodes returns a bitmap of isolated nodes in receiver graph g. -// -// An isolated node is one with no arcs going to or from it. -// -// There are equivalent labeled and unlabeled versions of this method. -func (g LabeledAdjacencyList) IsolatedNodes() (i Bits) { - i.SetAll(len(g)) - for fr, to := range g { - if len(to) > 0 { - i.SetBit(NI(fr), 0) - for _, to := range to { - i.SetBit(to.To, 0) - } - } - } - return -} - -/* -MaxmimalClique finds a maximal clique containing the node n. - -Not sure this is good for anything. It produces a single maximal clique -but there can be multiple maximal cliques containing a given node. -This algorithm just returns one of them, not even necessarily the -largest one. - -func (g LabeledAdjacencyList) MaximalClique(n int) []int { - c := []int{n} - var m bitset.BitSet - m.Set(uint(n)) - for fr, to := range g { - if fr == n { - continue - } - if len(to) < len(c) { - continue - } - f := 0 - for _, to := range to { - if m.Test(uint(to.To)) { - f++ - if f == len(c) { - c = append(c, to.To) - m.Set(uint(to.To)) - break - } - } - } - } - return c -} -*/ diff --git a/vendor/github.com/soniakeys/graph/bits.go b/vendor/github.com/soniakeys/graph/bits.go deleted file mode 100644 index b86703c..0000000 --- a/vendor/github.com/soniakeys/graph/bits.go +++ /dev/null @@ -1,207 +0,0 @@ -// Copyright 2014 Sonia Keys -// License MIT: http://opensource.org/licenses/MIT - -package graph - -import ( - "fmt" - "math/big" -) - -// Bits is bitmap, or bitset, intended to store a single bit of information -// per node of a graph. -// -// The current implementation is backed by a big.Int and so is a reference -// type in the same way a big.Int is. -type Bits struct { - i big.Int -} - -// NewBits constructs a Bits value with the bits ns set to 1. -func NewBits(ns ...NI) (b Bits) { - for _, n := range ns { - b.SetBit(n, 1) - } - return -} - -// AllNot sets n bits of z to the complement of x. -// -// It is a convenience method for SetAll followed by AndNot. -func (z *Bits) AllNot(n int, x Bits) { - var y Bits - y.SetAll(n) - z.AndNot(y, x) -} - -// And sets z = x & y. -func (z *Bits) And(x, y Bits) { - z.i.And(&x.i, &y.i) -} - -// AndNot sets z = x &^ y. -func (z *Bits) AndNot(x, y Bits) { - z.i.AndNot(&x.i, &y.i) -} - -// Bit returns the value of the n'th bit of x. -func (b Bits) Bit(n NI) uint { - return b.i.Bit(int(n)) -} - -// Clear sets all bits to 0. -func (z *Bits) Clear() { - *z = Bits{} -} - -// Format satisfies fmt.Formatter for fmt.Printf and related methods. -// -// graph.Bits format exactly like big.Ints. -func (b Bits) Format(s fmt.State, ch rune) { - b.i.Format(s, ch) -} - -// From returns the position of the first 1 bit at or after (from) position n. -// -// It returns -1 if there is no one bit at or after position n. -// -// This provides one way to iterate over one bits. -// To iterate over the one bits, call with n = 0 to get the the first -// one bit, then call with the result + 1 to get successive one bits. -// Unlike the Iterate method, this technique is stateless and so allows -// bits to be changed between successive calls. -// -// See also Iterate. -// -// (From is just a short word that means "at or after" here; -// it has nothing to do with arc direction.) -func (b Bits) From(n NI) NI { - words := b.i.Bits() - i := int(n) - x := i >> wordExp // x now index of word containing bit i. - if x >= len(words) { - return -1 - } - // test for 1 in this word at or after n - if wx := words[x] >> (uint(i) & (wordSize - 1)); wx != 0 { - return n + NI(trailingZeros(wx)) - } - x++ - for y, wy := range words[x:] { - if wy != 0 { - return NI((x+y)<<wordExp | trailingZeros(wy)) - } - } - return -1 -} - -// Iterate calls Visitor v for each bit with a value of 1, in order -// from lowest bit to highest bit. -// -// Iteration continues to the highest bit as long as v returns true. -// It stops if v returns false. -// -// Iterate returns true normally. It returns false if v returns false. -// -// Bit values should not be modified during iteration, by the visitor function -// for example. See From for an iteration method that allows modification. -func (b Bits) Iterate(v OkNodeVisitor) bool { - for x, w := range b.i.Bits() { - if w != 0 { - t := trailingZeros(w) - i := t // index in w of next 1 bit - for { - if !v(NI(x<<wordExp | i)) { - return false - } - w >>= uint(t + 1) - if w == 0 { - break - } - t = trailingZeros(w) - i += 1 + t - } - } - } - return true -} - -// Or sets z = x | y. -func (z *Bits) Or(x, y Bits) { - z.i.Or(&x.i, &y.i) -} - -// PopCount returns the number of 1 bits. -func (b Bits) PopCount() (c int) { - // algorithm selected to be efficient for sparse bit sets. - for _, w := range b.i.Bits() { - for w != 0 { - w &= w - 1 - c++ - } - } - return -} - -// Set sets the bits of z to the bits of x. -func (z *Bits) Set(x Bits) { - z.i.Set(&x.i) -} - -var one = big.NewInt(1) - -// SetAll sets z to have n 1 bits. -// -// It's useful for initializing z to have a 1 for each node of a graph. -func (z *Bits) SetAll(n int) { - z.i.Sub(z.i.Lsh(one, uint(n)), one) -} - -// SetBit sets the n'th bit to b, where be is a 0 or 1. -func (z *Bits) SetBit(n NI, b uint) { - z.i.SetBit(&z.i, int(n), b) -} - -// Single returns true if b has exactly one 1 bit. -func (b Bits) Single() bool { - // like PopCount, but stop as soon as two are found - c := 0 - for _, w := range b.i.Bits() { - for w != 0 { - w &= w - 1 - c++ - if c == 2 { - return false - } - } - } - return c == 1 -} - -// Slice returns a slice with the positions of each 1 bit. -func (b Bits) Slice() (s []NI) { - // (alternative implementation might use Popcount and make to get the - // exact cap slice up front. unclear if that would be better.) - b.Iterate(func(n NI) bool { - s = append(s, n) - return true - }) - return -} - -// Xor sets z = x ^ y. -func (z *Bits) Xor(x, y Bits) { - z.i.Xor(&x.i, &y.i) -} - -// Zero returns true if there are no 1 bits. -func (b Bits) Zero() bool { - return len(b.i.Bits()) == 0 -} - -// trailingZeros returns the number of trailing 0 bits in v. -// -// If v is 0, it returns 0. -func trailingZeros(v big.Word) int { - return deBruijnBits[v&-v*deBruijnMultiple>>deBruijnShift] -} diff --git a/vendor/github.com/soniakeys/graph/bits32.go b/vendor/github.com/soniakeys/graph/bits32.go deleted file mode 100644 index 18e07f9..0000000 --- a/vendor/github.com/soniakeys/graph/bits32.go +++ /dev/null @@ -1,23 +0,0 @@ -// Copyright 2014 Sonia Keys -// License MIT: http://opensource.org/licenses/MIT - -// +build 386 arm - -package graph - -// "word" here is math/big.Word -const ( - wordSize = 32 - wordExp = 5 // 2^5 = 32 -) - -// deBruijn magic numbers used in trailingZeros() -// -// reference: http://graphics.stanford.edu/~seander/bithacks.html -const deBruijnMultiple = 0x077CB531 -const deBruijnShift = 27 - -var deBruijnBits = []int{ - 0, 1, 28, 2, 29, 14, 24, 3, 30, 22, 20, 15, 25, 17, 4, 8, - 31, 27, 13, 23, 21, 19, 16, 7, 26, 12, 18, 6, 11, 5, 10, 9, -} diff --git a/vendor/github.com/soniakeys/graph/bits64.go b/vendor/github.com/soniakeys/graph/bits64.go deleted file mode 100644 index ab601dd..0000000 --- a/vendor/github.com/soniakeys/graph/bits64.go +++ /dev/null @@ -1,22 +0,0 @@ -// Copyright 2014 Sonia Keys -// License MIT: http://opensource.org/licenses/MIT - -// +build !386,!arm - -package graph - -const ( - wordSize = 64 - wordExp = 6 // 2^6 = 64 -) - -// reference: http://graphics.stanford.edu/~seander/bithacks.html -const deBruijnMultiple = 0x03f79d71b4ca8b09 -const deBruijnShift = 58 - -var deBruijnBits = []int{ - 0, 1, 56, 2, 57, 49, 28, 3, 61, 58, 42, 50, 38, 29, 17, 4, - 62, 47, 59, 36, 45, 43, 51, 22, 53, 39, 33, 30, 24, 18, 12, 5, - 63, 55, 48, 27, 60, 41, 37, 16, 46, 35, 44, 21, 52, 32, 23, 11, - 54, 26, 40, 15, 34, 20, 31, 10, 25, 14, 19, 9, 13, 8, 7, 6, -} diff --git a/vendor/github.com/soniakeys/graph/dir.go b/vendor/github.com/soniakeys/graph/dir.go deleted file mode 100644 index 508306d..0000000 --- a/vendor/github.com/soniakeys/graph/dir.go +++ /dev/null @@ -1,538 +0,0 @@ -// Copyright 2014 Sonia Keys -// License MIT: http://opensource.org/licenses/MIT - -package graph - -// dir.go has methods specific to directed graphs, types Directed and -// LabeledDirected. -// -// Methods on Directed are first, with exported methods alphabetized. - -import "errors" - -// DAGMaxLenPath finds a maximum length path in a directed acyclic graph. -// -// Argument ordering must be a topological ordering of g. -func (g Directed) DAGMaxLenPath(ordering []NI) (path []NI) { - // dynamic programming. visit nodes in reverse order. for each, compute - // longest path as one plus longest of 'to' nodes. - // Visits each arc once. O(m). - // - // Similar code in label.go - var n NI - mlp := make([][]NI, len(g.AdjacencyList)) // index by node number - for i := len(ordering) - 1; i >= 0; i-- { - fr := ordering[i] // node number - 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...) -} - -// EulerianCycle finds an Eulerian cycle in a directed multigraph. -// -// * If g has no nodes, result is nil, nil. -// -// * If g is Eulerian, result is an Eulerian cycle with err = nil. -// The cycle result is a list of nodes, where the first and last -// nodes are the same. -// -// * Otherwise, result is nil, error -// -// Internally, EulerianCycle copies the entire graph g. -// See EulerianCycleD for a more space efficient version. -func (g Directed) EulerianCycle() ([]NI, error) { - c, m := g.Copy() - return c.EulerianCycleD(m) -} - -// EulerianCycleD finds an Eulerian cycle in a directed multigraph. -// -// EulerianCycleD is destructive on its receiver g. See EulerianCycle for -// a non-destructive version. -// -// Argument ma must be the correct arc size, or number of arcs in g. -// -// * If g has no nodes, result is nil, nil. -// -// * If g is Eulerian, result is an Eulerian cycle with err = nil. -// The cycle result is a list of nodes, where the first and last -// nodes are the same. -// -// * Otherwise, result is nil, error -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() // v is node that starts cycle - e.push() - // if Eulerian, we'll always come back to starting node - 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 -} - -// EulerianPath finds an Eulerian path in a directed multigraph. -// -// * If g has no nodes, result is nil, nil. -// -// * If g has an Eulerian path, result is an Eulerian path with err = nil. -// The path result is a list of nodes, where the first node is start. -// -// * Otherwise, result is nil, error -// -// Internally, EulerianPath copies the entire graph g. -// See EulerianPathD for a more space efficient version. -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) -} - -// EulerianPathD finds an Eulerian path in a directed multigraph. -// -// EulerianPathD is destructive on its receiver g. See EulerianPath for -// a non-destructive version. -// -// Argument ma must be the correct arc size, or number of arcs in g. -// Argument start must be a valid start node for the path. -// -// * If g has no nodes, result is nil, nil. -// -// * If g has an Eulerian path, result is an Eulerian path with err = nil. -// The path result is a list of nodes, where the first node is start. -// -// * Otherwise, result is nil, error -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 - // unlike EulerianCycle, the first path doesn't have be a cycle. - e.push() - e.keep() - for e.s >= 0 { - start = e.top() - e.push() - // paths after the first must be cycles though - // (as long as there are nodes on the stack) - 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 -} - -// starting at the node on the top of the stack, follow arcs until stuck. -// mark nodes visited, push nodes on stack, remove arcs from g. -func (e *eulerian) push() { - for u := e.top(); ; { - e.uv.SetBit(u, 0) // reset unvisited bit - arcs := e.g[u] - if len(arcs) == 0 { - return // stuck - } - w := arcs[0] // follow first arc - e.s++ // push followed node on stack - e.p[e.s] = w - e.g[u] = arcs[1:] // consume arc - u = w - } -} - -// like push, but for for undirected graphs. -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:] // consume arc - // here is the only difference, consume reciprocal arc as well: - a2 := e.g[w] - for x, rx := range a2 { - if rx == u { // here it is - last := len(a2) - 1 - a2[x] = a2[last] // someone else gets the seat - e.g[w] = a2[:last] // and it's gone. - break - } - } - u = w - } -} - -// starting with the node on top of the stack, move nodes with no arcs. -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 // working copy of graph, it gets consumed - m int // number of arcs in g, updated as g is consumed - uv Bits // unvisited - // low end of p is stack of unfinished nodes - // high end is finished path - p []NI // stack + path - s int // stack pointer -} - -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 -} - -// MaximalNonBranchingPaths finds all paths in a directed graph that are -// "maximal" and "non-branching". -// -// A non-branching path is one where path nodes other than the first and last -// have exactly one arc leading to the node and one arc leading from the node, -// thus there is no possibility to branch away to a different path. -// -// A maximal non-branching path cannot be extended to a longer non-branching -// path by including another node at either end. -// -// In the case of a cyclic non-branching path, the first and last elements -// of the path will be the same node, indicating an isolated cycle. -// -// The method calls the emit argument for each path or isolated cycle in g, -// as long as emit returns true. If emit returns false, -// MaximalNonBranchingPaths returns immediately. -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) { // n is a path - return - } - } - } - } - // use uv.From rather than uv.Iterate. - // Iterate doesn't work here because we're modifying uv - 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) { // n is an isolated cycle - return - } - } -} - -// Undirected returns copy of g augmented as needed to make it undirected. -func (g Directed) Undirected() Undirected { - c, _ := g.AdjacencyList.Copy() // start with a copy - rw := make(AdjacencyList, len(g.AdjacencyList)) // "reciprocals wanted" - for fr, to := range g.AdjacencyList { - arc: // for each arc in g - for _, to := range to { - if to == NI(fr) { - continue // loop - } - // search wanted arcs - wf := rw[fr] - for i, w := range wf { - if w == to { // found, remove - last := len(wf) - 1 - wf[i] = wf[last] - rw[fr] = wf[:last] - continue arc - } - } - // arc not found, add to reciprocal to wanted list - rw[to] = append(rw[to], NI(fr)) - } - } - // add missing reciprocals - for fr, to := range rw { - c[fr] = append(c[fr], to...) - } - return Undirected{c} -} - -// StronglyConnectedComponents identifies strongly connected components -// in a directed graph. -// -// Algorithm by David J. Pearce, from "An Improved Algorithm for Finding the -// Strongly Connected Components of a Directed Graph". It is algorithm 3, -// PEA_FIND_SCC2 in -// http://homepages.mcs.vuw.ac.nz/~djp/files/P05.pdf, accessed 22 Feb 2015. -// -// Returned is a list of components, each component is a list of nodes. -/* -func (g Directed) StronglyConnectedComponents() []int { - rindex := make([]int, len(g)) - S := []int{} - index := 1 - c := len(g) - 1 - visit := func(v int) { - root := true - rindex[v] = index - index++ - for _, w := range g[v] { - if rindex[w] == 0 { - visit(w) - } - if rindex[w] < rindex[v] { - rindex[v] = rindex[w] - root = false - } - } - if root { - index-- - for top := len(S) - 1; top >= 0 && rindex[v] <= rindex[top]; top-- { - w = rindex[top] - S = S[:top] - rindex[w] = c - index-- - } - rindex[v] = c - c-- - } else { - S = append(S, v) - } - } - for v := range g { - if rindex[v] == 0 { - visit(v) - } - } - return rindex -} -*/ - -// Transpose constructs a new adjacency list with all arcs reversed. -// -// 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.) -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 -} - -// DAGMaxLenPath finds a maximum length path in a directed acyclic graph. -// -// Length here means number of nodes or arcs, not a sum of arc weights. -// -// Argument ordering must be a topological ordering of g. -// -// Returned is a node beginning a maximum length path, and a path of arcs -// starting from that node. -func (g LabeledDirected) DAGMaxLenPath(ordering []NI) (n NI, path []Half) { - // dynamic programming. visit nodes in reverse order. for each, compute - // longest path as one plus longest of 'to' nodes. - // Visits each arc once. Time complexity O(m). - // - // Similar code in dir.go. - mlp := make([][]Half, len(g.LabeledAdjacencyList)) // index by node number - for i := len(ordering) - 1; i >= 0; i-- { - fr := ordering[i] // node number - 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 -} - -// FromListLabels transposes a labeled graph into a FromList and associated -// list of labels. -// -// Receiver g should be connected as a tree or forest. Specifically no node -// can have multiple incoming arcs. If any node n in g has multiple incoming -// arcs, the method returns (nil, nil, n) where n is a node with multiple -// incoming arcs. -// -// Otherwise (normally) the method populates the From members in a -// FromList.Path, populates a slice of labels, and returns the FromList, -// labels, and -1. -// -// Other members of the FromList are left as zero values. -// Use FromList.RecalcLen and FromList.RecalcLeaves as needed. -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 -} - -// 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.) -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 -} - -// Undirected returns a new undirected graph derived from g, augmented as -// needed to make it undirected, with reciprocal arcs having matching labels. -func (g LabeledDirected) Undirected() LabeledUndirected { - c, _ := g.LabeledAdjacencyList.Copy() // start with a copy - // "reciprocals wanted" - rw := make(LabeledAdjacencyList, len(g.LabeledAdjacencyList)) - for fr, to := range g.LabeledAdjacencyList { - arc: // for each arc in g - for _, to := range to { - if to.To == NI(fr) { - continue // arc is a loop - } - // search wanted arcs - wf := rw[fr] - for i, w := range wf { - if w == to { // found, remove - last := len(wf) - 1 - wf[i] = wf[last] - rw[fr] = wf[:last] - continue arc - } - } - // arc not found, add to reciprocal to wanted list - rw[to.To] = append(rw[to.To], Half{To: NI(fr), Label: to.Label}) - } - } - // add missing reciprocals - for fr, to := range rw { - c[fr] = append(c[fr], to...) - } - return LabeledUndirected{c} -} - -// Unlabeled constructs the unlabeled directed graph corresponding to g. -func (g LabeledDirected) Unlabeled() Directed { - return Directed{g.LabeledAdjacencyList.Unlabeled()} -} - -// UnlabeledTranspose constructs a new adjacency list that is the unlabeled -// 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.) -// -// It is equivalent to g.Unlabeled().Transpose() but constructs the result -// directly. -func (g LabeledDirected) UnlabeledTranspose() (t Directed, ma int) { - ta := make(AdjacencyList, len(g.LabeledAdjacencyList)) - for n, nbs := range g.LabeledAdjacencyList { - for _, nb := range nbs { - ta[nb.To] = append(ta[nb.To], NI(n)) - ma++ - } - } - return Directed{ta}, ma -} diff --git a/vendor/github.com/soniakeys/graph/dir_RO.go b/vendor/github.com/soniakeys/graph/dir_RO.go deleted file mode 100644 index 77558a9..0000000 --- a/vendor/github.com/soniakeys/graph/dir_RO.go +++ /dev/null @@ -1,395 +0,0 @@ -// Copyright 2014 Sonia Keys -// License MIT: http://opensource.org/licenses/MIT - -package graph - -// dir_RO.go is code generated from dir_cg.go by directives in graph.go. -// Editing dir_cg.go is okay. It is the code generation source. -// DO NOT EDIT dir_RO.go. -// The RO means read only and it is upper case RO to slow you down a bit -// in case you start to edit the file. - -// Balanced returns true if for every node in g, in-degree equals out-degree. -// -// There are equivalent labeled and unlabeled versions of this method. -func (g Directed) Balanced() bool { - for n, in := range g.InDegree() { - if in != len(g.AdjacencyList[n]) { - return false - } - } - return true -} - -// Copy makes a deep copy of g. -// Copy also computes the arc size ma, the number of arcs. -// -// There are equivalent labeled and unlabeled versions of this method. -func (g Directed) Copy() (c Directed, ma int) { - l, s := g.AdjacencyList.Copy() - return Directed{l}, s -} - -// Cyclic determines if g contains a cycle, a non-empty path from a node -// back to itself. -// -// Cyclic returns true if g contains at least one cycle. It also returns -// an example of an arc involved in a cycle. -// Cyclic returns false if g is acyclic. -// -// Also see Topological, which detects cycles. -// -// There are equivalent labeled and unlabeled versions of this method. -func (g Directed) Cyclic() (cyclic bool, fr NI, to NI) { - a := g.AdjacencyList - fr, to = -1, -1 - var temp, perm Bits - var df func(NI) - df = func(n NI) { - switch { - case temp.Bit(n) == 1: - cyclic = true - return - case perm.Bit(n) == 1: - return - } - temp.SetBit(n, 1) - for _, nb := range a[n] { - df(nb) - if cyclic { - if fr < 0 { - fr, to = n, nb - } - return - } - } - temp.SetBit(n, 0) - perm.SetBit(n, 1) - } - for n := range a { - if perm.Bit(NI(n)) == 1 { - continue - } - if df(NI(n)); cyclic { // short circuit as soon as a cycle is found - break - } - } - return -} - -// FromList transposes a labeled graph into a FromList. -// -// Receiver g should be connected as a tree or forest. Specifically no node -// can have multiple incoming arcs. If any node n in g has multiple incoming -// arcs, the method returns (nil, n) where n is a node with multiple -// incoming arcs. -// -// Otherwise (normally) the method populates the From members in a -// FromList.Path and returns the FromList and -1. -// -// Other members of the FromList are left as zero values. -// Use FromList.RecalcLen and FromList.RecalcLeaves as needed. -// -// Unusual cases are parallel arcs and loops. A parallel arc represents -// a case of multiple arcs going to some node and so will lead to a (nil, n) -// return, even though a graph might be considered a multigraph tree. -// A single loop on a node that would otherwise be a root node, though, -// is not a case of multiple incoming arcs and so does not force a (nil, n) -// result. -// -// There are equivalent labeled and unlabeled versions of this method. -func (g Directed) FromList() (*FromList, NI) { - paths := make([]PathEnd, len(g.AdjacencyList)) - for i := range paths { - paths[i].From = -1 - } - for fr, to := range g.AdjacencyList { - for _, to := range to { - if paths[to].From >= 0 { - return nil, to - } - paths[to].From = NI(fr) - } - } - return &FromList{Paths: paths}, -1 -} - -// InDegree computes the in-degree of each node in g -// -// There are equivalent labeled and unlabeled versions of this method. -func (g Directed) InDegree() []int { - ind := make([]int, len(g.AdjacencyList)) - for _, nbs := range g.AdjacencyList { - for _, nb := range nbs { - ind[nb]++ - } - } - return ind -} - -// IsTree identifies trees in directed graphs. -// -// Return value isTree is true if the subgraph reachable from root is a tree. -// Further, return value allTree is true if the entire graph g is reachable -// from root. -// -// There are equivalent labeled and unlabeled versions of this method. -func (g Directed) IsTree(root NI) (isTree, allTree bool) { - a := g.AdjacencyList - var v Bits - v.SetAll(len(a)) - var df func(NI) bool - df = func(n NI) bool { - if v.Bit(n) == 0 { - return false - } - v.SetBit(n, 0) - for _, to := range a[n] { - if !df(to) { - return false - } - } - return true - } - isTree = df(root) - return isTree, isTree && v.Zero() -} - -// Tarjan identifies strongly connected components in a directed graph using -// Tarjan's algorithm. -// -// The method calls the emit argument for each component identified. Each -// component is a list of nodes. A property of the algorithm is that -// components are emitted in reverse topological order of the condensation. -// (See https://en.wikipedia.org/wiki/Strongly_connected_component#Definitions -// for description of condensation.) -// -// There are equivalent labeled and unlabeled versions of this method. -// -// See also TarjanForward and TarjanCondensation. -func (g Directed) Tarjan(emit func([]NI) bool) { - // See "Depth-first search and linear graph algorithms", Robert Tarjan, - // SIAM J. Comput. Vol. 1, No. 2, June 1972. - // - // Implementation here from Wikipedia pseudocode, - // http://en.wikipedia.org/w/index.php?title=Tarjan%27s_strongly_connected_components_algorithm&direction=prev&oldid=647184742 - var indexed, stacked Bits - a := g.AdjacencyList - index := make([]int, len(a)) - lowlink := make([]int, len(a)) - x := 0 - var S []NI - var sc func(NI) bool - sc = func(n NI) bool { - index[n] = x - indexed.SetBit(n, 1) - lowlink[n] = x - x++ - S = append(S, n) - stacked.SetBit(n, 1) - for _, nb := range a[n] { - if indexed.Bit(nb) == 0 { - if !sc(nb) { - return false - } - if lowlink[nb] < lowlink[n] { - lowlink[n] = lowlink[nb] - } - } else if stacked.Bit(nb) == 1 { - if index[nb] < lowlink[n] { - lowlink[n] = index[nb] - } - } - } - if lowlink[n] == index[n] { - var c []NI - for { - last := len(S) - 1 - w := S[last] - S = S[:last] - stacked.SetBit(w, 0) - c = append(c, w) - if w == n { - if !emit(c) { - return false - } - break - } - } - } - return true - } - for n := range a { - if indexed.Bit(NI(n)) == 0 && !sc(NI(n)) { - return - } - } -} - -// TarjanForward returns strongly connected components. -// -// It returns components in the reverse order of Tarjan, for situations -// where a forward topological ordering is easier. -func (g Directed) TarjanForward() [][]NI { - var r [][]NI - g.Tarjan(func(c []NI) bool { - r = append(r, c) - return true - }) - scc := make([][]NI, len(r)) - last := len(r) - 1 - for i, ci := range r { - scc[last-i] = ci - } - return scc -} - -// TarjanCondensation returns strongly connected components and their -// condensation graph. -// -// Components are ordered in a forward topological ordering. -func (g Directed) TarjanCondensation() (scc [][]NI, cd AdjacencyList) { - scc = g.TarjanForward() - cd = make(AdjacencyList, len(scc)) // return value - cond := make([]NI, len(g.AdjacencyList)) // mapping from g node to cd node - for cn := NI(len(scc) - 1); cn >= 0; cn-- { - c := scc[cn] - for _, n := range c { - cond[n] = NI(cn) // map g node to cd node - } - var tos []NI // list of 'to' nodes - var m Bits // tos map - m.SetBit(cn, 1) - for _, n := range c { - for _, to := range g.AdjacencyList[n] { - if ct := cond[to]; m.Bit(ct) == 0 { - m.SetBit(ct, 1) - tos = append(tos, ct) - } - } - } - cd[cn] = tos - } - return -} - -// Topological computes a topological ordering of a directed acyclic graph. -// -// For an acyclic graph, return value ordering is a permutation of node numbers -// in topologically sorted order and cycle will be nil. If the graph is found -// to be cyclic, ordering will be nil and cycle will be the path of a found -// cycle. -// -// There are equivalent labeled and unlabeled versions of this method. -func (g Directed) Topological() (ordering, cycle []NI) { - a := g.AdjacencyList - ordering = make([]NI, len(a)) - i := len(ordering) - var temp, perm Bits - var cycleFound bool - var cycleStart NI - var df func(NI) - df = func(n NI) { - switch { - case temp.Bit(n) == 1: - cycleFound = true - cycleStart = n - return - case perm.Bit(n) == 1: - return - } - temp.SetBit(n, 1) - for _, nb := range a[n] { - df(nb) - if cycleFound { - if cycleStart >= 0 { - // a little hack: orderng won't be needed so repurpose the - // slice as cycle. this is read out in reverse order - // as the recursion unwinds. - x := len(ordering) - 1 - len(cycle) - ordering[x] = n - cycle = ordering[x:] - if n == cycleStart { - cycleStart = -1 - } - } - return - } - } - temp.SetBit(n, 0) - perm.SetBit(n, 1) - i-- - ordering[i] = n - } - for n := range a { - if perm.Bit(NI(n)) == 1 { - continue - } - df(NI(n)) - if cycleFound { - return nil, cycle - } - } - return ordering, nil -} - -// TopologicalKahn computes a topological ordering of a directed acyclic graph. -// -// For an acyclic graph, return value ordering is a permutation of node numbers -// in topologically sorted order and cycle will be nil. If the graph is found -// to be cyclic, ordering will be nil and cycle will be the path of a found -// cycle. -// -// This function is based on the algorithm by Arthur Kahn and requires the -// transpose of g be passed as the argument. -// -// There are equivalent labeled and unlabeled versions of this method. -func (g Directed) TopologicalKahn(tr Directed) (ordering, cycle []NI) { - // code follows Wikipedia pseudocode. - var L, S []NI - // rem for "remaining edges," this function makes a local copy of the - // in-degrees and consumes that instead of consuming an input. - rem := make([]int, len(g.AdjacencyList)) - for n, fr := range tr.AdjacencyList { - if len(fr) == 0 { - // accumulate "set of all nodes with no incoming edges" - S = append(S, NI(n)) - } else { - // initialize rem from in-degree - rem[n] = len(fr) - } - } - for len(S) > 0 { - last := len(S) - 1 // "remove a node n from S" - n := S[last] - S = S[:last] - L = append(L, n) // "add n to tail of L" - for _, m := range g.AdjacencyList[n] { - // WP pseudo code reads "for each node m..." but it means for each - // node m *remaining in the graph.* We consume rem rather than - // the graph, so "remaining in the graph" for us means rem[m] > 0. - if rem[m] > 0 { - rem[m]-- // "remove edge from the graph" - if rem[m] == 0 { // if "m has no other incoming edges" - S = append(S, m) // "insert m into S" - } - } - } - } - // "If graph has edges," for us means a value in rem is > 0. - for c, in := range rem { - if in > 0 { - // recover cyclic nodes - for _, nb := range g.AdjacencyList[c] { - if rem[nb] > 0 { - cycle = append(cycle, NI(c)) - break - } - } - } - } - if len(cycle) > 0 { - return nil, cycle - } - return L, nil -} diff --git a/vendor/github.com/soniakeys/graph/dir_cg.go b/vendor/github.com/soniakeys/graph/dir_cg.go deleted file mode 100644 index 2b82f4f..0000000 --- a/vendor/github.com/soniakeys/graph/dir_cg.go +++ /dev/null @@ -1,395 +0,0 @@ -// Copyright 2014 Sonia Keys -// License MIT: http://opensource.org/licenses/MIT - -package graph - -// dir_RO.go is code generated from dir_cg.go by directives in graph.go. -// Editing dir_cg.go is okay. It is the code generation source. -// DO NOT EDIT dir_RO.go. -// The RO means read only and it is upper case RO to slow you down a bit -// in case you start to edit the file. - -// Balanced returns true if for every node in g, in-degree equals out-degree. -// -// There are equivalent labeled and unlabeled versions of this method. -func (g LabeledDirected) Balanced() bool { - for n, in := range g.InDegree() { - if in != len(g.LabeledAdjacencyList[n]) { - return false - } - } - return true -} - -// Copy makes a deep copy of g. -// Copy also computes the arc size ma, the number of arcs. -// -// There are equivalent labeled and unlabeled versions of this method. -func (g LabeledDirected) Copy() (c LabeledDirected, ma int) { - l, s := g.LabeledAdjacencyList.Copy() - return LabeledDirected{l}, s -} - -// Cyclic determines if g contains a cycle, a non-empty path from a node -// back to itself. -// -// Cyclic returns true if g contains at least one cycle. It also returns -// an example of an arc involved in a cycle. -// Cyclic returns false if g is acyclic. -// -// Also see Topological, which detects cycles. -// -// There are equivalent labeled and unlabeled versions of this method. -func (g LabeledDirected) Cyclic() (cyclic bool, fr NI, to Half) { - a := g.LabeledAdjacencyList - fr, to.To = -1, -1 - var temp, perm Bits - var df func(NI) - df = func(n NI) { - switch { - case temp.Bit(n) == 1: - cyclic = true - return - case perm.Bit(n) == 1: - return - } - temp.SetBit(n, 1) - for _, nb := range a[n] { - df(nb.To) - if cyclic { - if fr < 0 { - fr, to = n, nb - } - return - } - } - temp.SetBit(n, 0) - perm.SetBit(n, 1) - } - for n := range a { - if perm.Bit(NI(n)) == 1 { - continue - } - if df(NI(n)); cyclic { // short circuit as soon as a cycle is found - break - } - } - return -} - -// FromList transposes a labeled graph into a FromList. -// -// Receiver g should be connected as a tree or forest. Specifically no node -// can have multiple incoming arcs. If any node n in g has multiple incoming -// arcs, the method returns (nil, n) where n is a node with multiple -// incoming arcs. -// -// Otherwise (normally) the method populates the From members in a -// FromList.Path and returns the FromList and -1. -// -// Other members of the FromList are left as zero values. -// Use FromList.RecalcLen and FromList.RecalcLeaves as needed. -// -// Unusual cases are parallel arcs and loops. A parallel arc represents -// a case of multiple arcs going to some node and so will lead to a (nil, n) -// return, even though a graph might be considered a multigraph tree. -// A single loop on a node that would otherwise be a root node, though, -// is not a case of multiple incoming arcs and so does not force a (nil, n) -// result. -// -// There are equivalent labeled and unlabeled versions of this method. -func (g LabeledDirected) FromList() (*FromList, NI) { - 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, to.To - } - paths[to.To].From = NI(fr) - } - } - return &FromList{Paths: paths}, -1 -} - -// InDegree computes the in-degree of each node in g -// -// There are equivalent labeled and unlabeled versions of this method. -func (g LabeledDirected) InDegree() []int { - ind := make([]int, len(g.LabeledAdjacencyList)) - for _, nbs := range g.LabeledAdjacencyList { - for _, nb := range nbs { - ind[nb.To]++ - } - } - return ind -} - -// IsTree identifies trees in directed graphs. -// -// Return value isTree is true if the subgraph reachable from root is a tree. -// Further, return value allTree is true if the entire graph g is reachable -// from root. -// -// There are equivalent labeled and unlabeled versions of this method. -func (g LabeledDirected) IsTree(root NI) (isTree, allTree bool) { - a := g.LabeledAdjacencyList - var v Bits - v.SetAll(len(a)) - var df func(NI) bool - df = func(n NI) bool { - if v.Bit(n) == 0 { - return false - } - v.SetBit(n, 0) - for _, to := range a[n] { - if !df(to.To) { - return false - } - } - return true - } - isTree = df(root) - return isTree, isTree && v.Zero() -} - -// Tarjan identifies strongly connected components in a directed graph using -// Tarjan's algorithm. -// -// The method calls the emit argument for each component identified. Each -// component is a list of nodes. A property of the algorithm is that -// components are emitted in reverse topological order of the condensation. -// (See https://en.wikipedia.org/wiki/Strongly_connected_component#Definitions -// for description of condensation.) -// -// There are equivalent labeled and unlabeled versions of this method. -// -// See also TarjanForward and TarjanCondensation. -func (g LabeledDirected) Tarjan(emit func([]NI) bool) { - // See "Depth-first search and linear graph algorithms", Robert Tarjan, - // SIAM J. Comput. Vol. 1, No. 2, June 1972. - // - // Implementation here from Wikipedia pseudocode, - // http://en.wikipedia.org/w/index.php?title=Tarjan%27s_strongly_connected_components_algorithm&direction=prev&oldid=647184742 - var indexed, stacked Bits - a := g.LabeledAdjacencyList - index := make([]int, len(a)) - lowlink := make([]int, len(a)) - x := 0 - var S []NI - var sc func(NI) bool - sc = func(n NI) bool { - index[n] = x - indexed.SetBit(n, 1) - lowlink[n] = x - x++ - S = append(S, n) - stacked.SetBit(n, 1) - for _, nb := range a[n] { - if indexed.Bit(nb.To) == 0 { - if !sc(nb.To) { - return false - } - if lowlink[nb.To] < lowlink[n] { - lowlink[n] = lowlink[nb.To] - } - } else if stacked.Bit(nb.To) == 1 { - if index[nb.To] < lowlink[n] { - lowlink[n] = index[nb.To] - } - } - } - if lowlink[n] == index[n] { - var c []NI - for { - last := len(S) - 1 - w := S[last] - S = S[:last] - stacked.SetBit(w, 0) - c = append(c, w) - if w == n { - if !emit(c) { - return false - } - break - } - } - } - return true - } - for n := range a { - if indexed.Bit(NI(n)) == 0 && !sc(NI(n)) { - return - } - } -} - -// TarjanForward returns strongly connected components. -// -// It returns components in the reverse order of Tarjan, for situations -// where a forward topological ordering is easier. -func (g LabeledDirected) TarjanForward() [][]NI { - var r [][]NI - g.Tarjan(func(c []NI) bool { - r = append(r, c) - return true - }) - scc := make([][]NI, len(r)) - last := len(r) - 1 - for i, ci := range r { - scc[last-i] = ci - } - return scc -} - -// TarjanCondensation returns strongly connected components and their -// condensation graph. -// -// Components are ordered in a forward topological ordering. -func (g LabeledDirected) TarjanCondensation() (scc [][]NI, cd AdjacencyList) { - scc = g.TarjanForward() - cd = make(AdjacencyList, len(scc)) // return value - cond := make([]NI, len(g.LabeledAdjacencyList)) // mapping from g node to cd node - for cn := NI(len(scc) - 1); cn >= 0; cn-- { - c := scc[cn] - for _, n := range c { - cond[n] = NI(cn) // map g node to cd node - } - var tos []NI // list of 'to' nodes - var m Bits // tos map - m.SetBit(cn, 1) - for _, n := range c { - for _, to := range g.LabeledAdjacencyList[n] { - if ct := cond[to.To]; m.Bit(ct) == 0 { - m.SetBit(ct, 1) - tos = append(tos, ct) - } - } - } - cd[cn] = tos - } - return -} - -// Topological computes a topological ordering of a directed acyclic graph. -// -// For an acyclic graph, return value ordering is a permutation of node numbers -// in topologically sorted order and cycle will be nil. If the graph is found -// to be cyclic, ordering will be nil and cycle will be the path of a found -// cycle. -// -// There are equivalent labeled and unlabeled versions of this method. -func (g LabeledDirected) Topological() (ordering, cycle []NI) { - a := g.LabeledAdjacencyList - ordering = make([]NI, len(a)) - i := len(ordering) - var temp, perm Bits - var cycleFound bool - var cycleStart NI - var df func(NI) - df = func(n NI) { - switch { - case temp.Bit(n) == 1: - cycleFound = true - cycleStart = n - return - case perm.Bit(n) == 1: - return - } - temp.SetBit(n, 1) - for _, nb := range a[n] { - df(nb.To) - if cycleFound { - if cycleStart >= 0 { - // a little hack: orderng won't be needed so repurpose the - // slice as cycle. this is read out in reverse order - // as the recursion unwinds. - x := len(ordering) - 1 - len(cycle) - ordering[x] = n - cycle = ordering[x:] - if n == cycleStart { - cycleStart = -1 - } - } - return - } - } - temp.SetBit(n, 0) - perm.SetBit(n, 1) - i-- - ordering[i] = n - } - for n := range a { - if perm.Bit(NI(n)) == 1 { - continue - } - df(NI(n)) - if cycleFound { - return nil, cycle - } - } - return ordering, nil -} - -// TopologicalKahn computes a topological ordering of a directed acyclic graph. -// -// For an acyclic graph, return value ordering is a permutation of node numbers -// in topologically sorted order and cycle will be nil. If the graph is found -// to be cyclic, ordering will be nil and cycle will be the path of a found -// cycle. -// -// This function is based on the algorithm by Arthur Kahn and requires the -// transpose of g be passed as the argument. -// -// There are equivalent labeled and unlabeled versions of this method. -func (g LabeledDirected) TopologicalKahn(tr Directed) (ordering, cycle []NI) { - // code follows Wikipedia pseudocode. - var L, S []NI - // rem for "remaining edges," this function makes a local copy of the - // in-degrees and consumes that instead of consuming an input. - rem := make([]int, len(g.LabeledAdjacencyList)) - for n, fr := range tr.AdjacencyList { - if len(fr) == 0 { - // accumulate "set of all nodes with no incoming edges" - S = append(S, NI(n)) - } else { - // initialize rem from in-degree - rem[n] = len(fr) - } - } - for len(S) > 0 { - last := len(S) - 1 // "remove a node n from S" - n := S[last] - S = S[:last] - L = append(L, n) // "add n to tail of L" - for _, m := range g.LabeledAdjacencyList[n] { - // WP pseudo code reads "for each node m..." but it means for each - // node m *remaining in the graph.* We consume rem rather than - // the graph, so "remaining in the graph" for us means rem[m] > 0. - if rem[m.To] > 0 { - rem[m.To]-- // "remove edge from the graph" - if rem[m.To] == 0 { // if "m has no other incoming edges" - S = append(S, m.To) // "insert m into S" - } - } - } - } - // "If graph has edges," for us means a value in rem is > 0. - for c, in := range rem { - if in > 0 { - // recover cyclic nodes - for _, nb := range g.LabeledAdjacencyList[c] { - if rem[nb.To] > 0 { - cycle = append(cycle, NI(c)) - break - } - } - } - } - if len(cycle) > 0 { - return nil, cycle - } - return L, nil -} diff --git a/vendor/github.com/soniakeys/graph/doc.go b/vendor/github.com/soniakeys/graph/doc.go deleted file mode 100644 index 6d07278..0000000 --- a/vendor/github.com/soniakeys/graph/doc.go +++ /dev/null @@ -1,128 +0,0 @@ -// Copyright 2014 Sonia Keys -// License MIT: http://opensource.org/licenses/MIT - -// Graph algorithms: Dijkstra, A*, Bellman Ford, Floyd Warshall; -// Kruskal and Prim minimal spanning tree; topological sort and DAG longest -// and shortest paths; Eulerian cycle and path; degeneracy and k-cores; -// Bron Kerbosch clique finding; connected components; and others. -// -// This is a graph library of integer indexes. To use it with application -// data, you associate data with integer indexes, perform searches or other -// operations with the library, and then use the integer index results to refer -// back to your application data. -// -// Thus it does not store application data, pointers to application data, -// or require you to implement an interface on your application data. -// The idea is to keep the library methods fast and lean. -// -// Representation overview -// -// The package defines a type for a node index (NI) which is just an integer -// type. It defines types for a number of number graph representations using -// NI. The fundamental graph type is AdjacencyList, which is the -// common "list of lists" graph representation. It is a list as a slice -// with one element for each node of the graph. Each element is a list -// itself, a list of neighbor nodes, implemented as an NI slice. Methods -// on an AdjacencyList generally work on any representable graph, including -// directed or undirected graphs, simple graphs or multigraphs. -// -// The type Undirected embeds an AdjacencyList adding methods specific to -// undirected graphs. Similarly the type Directed adds methods meaningful -// for directed graphs. -// -// Similar to NI, the type LI is a "label index" which labels a -// node-to-neighbor "arc" or edge. Just as an NI can index arbitrary node -// data, an LI can index arbitrary arc or edge data. A number of algorithms -// use a "weight" associated with an arc. This package does not represent -// weighted arcs explicitly, but instead uses the LI as a more general -// mechanism allowing not only weights but arbitrary data to be associated -// with arcs. While AdjacencyList represents an arc with simply an NI, -// the type LabeledAdjacencyList uses a type that pairs an NI with an LI. -// This type is named Half, for half-arc. (A full arc would represent -// both ends.) Types LabeledDirected and LabeledUndirected embed a -// LabeledAdjacencyList. -// -// In contrast to Half, the type Edge represents both ends of an edge (but -// no label.) The type LabeledEdge adds the label. The type WeightedEdgeList -// bundles a list of LabeledEdges with a WeightFunc. WeightedEdgeList is -// currently only used by Kruskal methods. -// -// FromList is a compact rooted tree (or forest) respresentation. Like -// AdjacencyList and LabeledAdjacencyList, it is a list with one element for -// each node of the graph. Each element contains only a single neighbor -// however, its parent in the tree, the "from" node. -// -// Code generation -// -// A number of methods on AdjacencyList, Directed, and Undirected are -// applicable to LabeledAdjacencyList, LabeledDirected, and LabeledUndirected -// simply by ignoring the label. In these cases code generation provides -// methods on both types from a single source implementation. These methods -// are documented with the sentence "There are equivalent labeled and unlabeled -// versions of this method" and examples are provided only for the unlabeled -// version. -// -// Terminology -// -// This package uses the term "node" rather than "vertex." It uses "arc" -// to mean a directed edge, and uses "from" and "to" to refer to the ends -// of an arc. It uses "start" and "end" to refer to endpoints of a search -// or traversal. -// -// The usage of "to" and "from" is perhaps most strange. In common speech -// they are prepositions, but throughout this package they are used as -// adjectives, for example to refer to the "from node" of an arc or the -// "to node". The type "FromList" is named to indicate it stores a list of -// "from" values. -// -// A "half arc" refers to just one end of an arc, either the to or from end. -// -// Two arcs are "reciprocal" if they connect two distinct nodes n1 and n2, -// one arc leading from n1 to n2 and the other arc leading from n2 to n1. -// Undirected graphs are represented with reciprocal arcs. -// -// A node with an arc to itself represents a "loop." Duplicate arcs, where -// a node has multiple arcs to another node, are termed "parallel arcs." -// A graph with no loops or parallel arcs is "simple." A graph that allows -// parallel arcs is a "multigraph" -// -// The "size" of a graph traditionally means the number of undirected edges. -// This package uses "arc size" to mean the number of arcs in a graph. For an -// undirected graph without loops, arc size is 2 * size. -// -// The "order" of a graph is the number of nodes. An "ordering" though means -// an ordered list of nodes. -// -// A number of graph search algorithms use a concept of arc "weights." -// The sum of arc weights along a path is a "distance." In contrast, the -// number of nodes in a path, including start and end nodes, is the path's -// "length." (Yes, mixing weights and lengths would be nonsense physically, -// but the terms used here are just distinct terms for abstract values. -// The actual meaning to an application is likely to be something else -// entirely and is not relevant within this package.) -// -// Finally, this package documentation takes back the word "object" in some -// places to refer to a Go value, especially a value of a type with methods. -// -// Shortest path searches -// -// This package implements a number of shortest path searches. Most work -// with weighted graphs that are directed or undirected, and with graphs -// that may have loops or parallel arcs. For weighted graphs, "shortest" -// is defined as the path distance (sum of arc weights) with path length -// (number of nodes) breaking ties. If multiple paths have the same minimum -// distance with the same minimum length, search methods are free to return -// any of them. -// -// Type name Description, methods -// BreadthFirst Unweigted arcs, traversal, single path search or all paths. -// BreadthFirst2 Direction-optimizing variant of BreadthFirst. -// Dijkstra Non-negative arc weights, single or all paths. -// AStar Non-negative arc weights, heuristic guided, single path. -// BellmanFord Negative arc weights allowed, no negative cycles, all paths. -// DAGPath O(n) algorithm for DAGs, arc weights of any sign. -// FloydWarshall all pairs distances, no negative cycles. -// -// These searches typically have one method that is full-featured and -// then a convenience method with a simpler API targeting a simpler use case. -package graph diff --git a/vendor/github.com/soniakeys/graph/fromlist.go b/vendor/github.com/soniakeys/graph/fromlist.go deleted file mode 100644 index 31d41fa..0000000 --- a/vendor/github.com/soniakeys/graph/fromlist.go +++ /dev/null @@ -1,418 +0,0 @@ -// Copyright 2014 Sonia Keys -// License MIT: http://opensource.org/licenses/MIT - -package graph - -// FromList represents a rooted tree (or forest) where each node is associated -// with a half arc identifying an arc "from" another node. -// -// Other terms for this data structure include "parent list", -// "predecessor list", "in-tree", "inverse arborescence", and -// "spaghetti stack." -// -// The Paths member represents the tree structure. Leaves and MaxLen are -// not always needed. Where Leaves is used it serves as a bitmap where -// Leaves.Bit(n) == 1 for each leaf n of the tree. Where MaxLen is used it is -// provided primarily as a convenience for functions that might want to -// anticipate the maximum path length that would be encountered traversing -// the tree. -// -// Various graph search methods use a FromList to returns search results. -// For a start node of a search, From will be -1 and Len will be 1. For other -// nodes reached by the search, From represents a half arc in a path back to -// start and Len represents the number of nodes in the path. For nodes not -// reached by the search, From will be -1 and Len will be 0. -// -// A single FromList can also represent a forest. In this case paths from -// all leaves do not return to a single root node, but multiple root nodes. -// -// While a FromList generally encodes a tree or forest, it is technically -// possible to encode a cyclic graph. A number of FromList methods require -// the receiver to be acyclic. Graph methods documented to return a tree or -// forest will never return a cyclic FromList. In other cases however, -// where a FromList is not known to by cyclic, the Cyclic method can be -// useful to validate the acyclic property. -type FromList struct { - Paths []PathEnd // tree representation - Leaves Bits // leaves of tree - MaxLen int // length of longest path, max of all PathEnd.Len values -} - -// PathEnd associates a half arc and a path length. -// -// A PathEnd list is an element type of FromList. -type PathEnd struct { - From NI // a "from" half arc, the node the arc comes from - Len int // number of nodes in path from start -} - -// NewFromList creates a FromList object of given order. -// -// The Paths member is allocated to length n but there is no other -// initialization. -func NewFromList(n int) FromList { - return FromList{Paths: make([]PathEnd, n)} -} - -// BoundsOk validates the "from" values in the list. -// -// Negative values are allowed as they indicate root nodes. -// -// BoundsOk returns true when all from values are less than len(t). -// Otherwise it returns false and a node with a from value >= len(t). -func (f FromList) BoundsOk() (ok bool, n NI) { - for n, e := range f.Paths { - if int(e.From) >= len(f.Paths) { - return false, NI(n) - } - } - return true, -1 -} - -// CommonStart returns the common start node of minimal paths to a and b. -// -// It returns -1 if a and b cannot be traced back to a common node. -// -// The method relies on populated PathEnd.Len members. Use RecalcLen if -// the Len members are not known to be present and correct. -func (f FromList) CommonStart(a, b NI) NI { - p := f.Paths - if p[a].Len < p[b].Len { - a, b = b, a - } - for bl := p[b].Len; p[a].Len > bl; { - a = p[a].From - if a < 0 { - return -1 - } - } - for a != b { - a = p[a].From - if a < 0 { - return -1 - } - b = p[b].From - } - return a -} - -// Cyclic determines if f contains a cycle, a non-empty path from a node -// back to itself. -// -// Cyclic returns true if g contains at least one cycle. It also returns -// an example of a node involved in a cycle. -// -// Cyclic returns (false, -1) in the normal case where f is acyclic. -// Note that the bool is not an "ok" return. A cyclic FromList is usually -// not okay. -func (f FromList) Cyclic() (cyclic bool, n NI) { - var vis Bits - p := f.Paths - for i := range p { - var path Bits - for n := NI(i); vis.Bit(n) == 0; { - vis.SetBit(n, 1) - path.SetBit(n, 1) - if n = p[n].From; n < 0 { - break - } - if path.Bit(n) == 1 { - return true, n - } - } - } - return false, -1 -} - -// IsolatedNodeBits returns a bitmap of isolated nodes in receiver graph f. -// -// An isolated node is one with no arcs going to or from it. -func (f FromList) IsolatedNodes() (iso Bits) { - p := f.Paths - iso.SetAll(len(p)) - for n, e := range p { - if e.From >= 0 { - iso.SetBit(NI(n), 0) - iso.SetBit(e.From, 0) - } - } - return -} - -// PathTo decodes a FromList, recovering a single path. -// -// The path is returned as a list of nodes where the first element will be -// a root node and the last element will be the specified end node. -// -// Only the Paths member of the receiver is used. Other members of the -// FromList do not need to be valid, however the MaxLen member can be useful -// for allocating argument p. -// -// Argument p can provide the result slice. If p has capacity for the result -// it will be used, otherwise a new slice is created for the result. -// -// See also function PathTo. -func (f FromList) PathTo(end NI, p []NI) []NI { - return PathTo(f.Paths, end, p) -} - -// PathTo decodes a single path from a PathEnd list. -// -// A PathEnd list is the main data representation in a FromList. See FromList. -// -// PathTo returns a list of nodes where the first element will be -// a root node and the last element will be the specified end node. -// -// Argument p can provide the result slice. If p has capacity for the result -// it will be used, otherwise a new slice is created for the result. -// -// See also method FromList.PathTo. -func PathTo(paths []PathEnd, end NI, p []NI) []NI { - n := paths[end].Len - if n == 0 { - return nil - } - if cap(p) >= n { - p = p[:n] - } else { - p = make([]NI, n) - } - for { - n-- - p[n] = end - if n == 0 { - return p - } - end = paths[end].From - } -} - -// Preorder traverses f calling Visitor v in preorder. -// -// Nodes are visited in order such that for any node n with from node fr, -// fr is visited before n. Where f represents a tree, the visit ordering -// corresponds to a preordering, or depth first traversal of the tree. -// Where f represents a forest, the preorderings of the trees can be -// intermingled. -// -// Leaves must be set correctly first. Use RecalcLeaves if leaves are not -// known to be set correctly. FromList f cannot be cyclic. -// -// Traversal continues while v returns true. It terminates if v returns false. -// Preorder returns true if it completes without v returning false. Preorder -// returns false if traversal is terminated by v returning false. -func (f FromList) Preorder(v OkNodeVisitor) bool { - p := f.Paths - var done Bits - var df func(NI) bool - df = func(n NI) bool { - done.SetBit(n, 1) - if fr := p[n].From; fr >= 0 && done.Bit(fr) == 0 { - df(fr) - } - return v(n) - } - for n := range f.Paths { - p[n].Len = 0 - } - return f.Leaves.Iterate(func(n NI) bool { - return df(n) - }) -} - -// RecalcLeaves recomputes the Leaves member of f. -func (f *FromList) RecalcLeaves() { - p := f.Paths - lv := &f.Leaves - lv.SetAll(len(p)) - for n := range f.Paths { - if fr := p[n].From; fr >= 0 { - lv.SetBit(fr, 0) - } - } -} - -// RecalcLen recomputes Len for each path end, and recomputes MaxLen. -// -// RecalcLen relies on the Leaves member being valid. If it is not known -// to be valid, call RecalcLeaves before calling RecalcLen. -func (f *FromList) RecalcLen() { - p := f.Paths - var setLen func(NI) int - setLen = func(n NI) int { - switch { - case p[n].Len > 0: - return p[n].Len - case p[n].From < 0: - p[n].Len = 1 - return 1 - } - l := 1 + setLen(p[n].From) - p[n].Len = l - return l - } - for n := range f.Paths { - p[n].Len = 0 - } - f.MaxLen = 0 - f.Leaves.Iterate(func(n NI) bool { - if l := setLen(NI(n)); l > f.MaxLen { - f.MaxLen = l - } - return true - }) -} - -// ReRoot reorients the tree containing n to make n the root node. -// -// It keeps the tree connected by "reversing" the path from n to the old root. -// -// After ReRoot, the Leaves and Len members are invalid. -// Call RecalcLeaves or RecalcLen as needed. -func (f *FromList) ReRoot(n NI) { - p := f.Paths - fr := p[n].From - if fr < 0 { - return - } - p[n].From = -1 - for { - ff := p[fr].From - p[fr].From = n - if ff < 0 { - return - } - n = fr - fr = ff - } -} - -// Root finds the root of a node in a FromList. -func (f FromList) Root(n NI) NI { - for p := f.Paths; ; { - fr := p[n].From - if fr < 0 { - return n - } - n = fr - } -} - -// Transpose constructs the directed graph corresponding to FromList f -// but with arcs in the opposite direction. That is, from roots toward leaves. -// -// The method relies only on the From member of f.Paths. Other members of -// the FromList are not used. -// -// See FromList.TransposeRoots for a version that also accumulates and returns -// information about the roots. -func (f FromList) Transpose() Directed { - g := make(AdjacencyList, len(f.Paths)) - for n, p := range f.Paths { - if p.From == -1 { - continue - } - g[p.From] = append(g[p.From], NI(n)) - } - return Directed{g} -} - -// TransposeLabeled constructs the directed labeled graph corresponding -// to FromList f but with arcs in the opposite direction. That is, from -// roots toward leaves. -// -// The argument labels can be nil. In this case labels are generated matching -// the path indexes. This corresponds to the "to", or child node. -// -// If labels is non-nil, it must be the same length as f.Paths and is used -// to look up label numbers by the path index. -// -// The method relies only on the From member of f.Paths. Other members of -// the FromList are not used. -// -// See FromList.TransposeLabeledRoots for a version that also accumulates -// and returns information about the roots. -func (f FromList) TransposeLabeled(labels []LI) LabeledDirected { - g := make(LabeledAdjacencyList, len(f.Paths)) - for n, p := range f.Paths { - if p.From == -1 { - continue - } - l := LI(n) - if labels != nil { - l = labels[n] - } - g[p.From] = append(g[p.From], Half{NI(n), l}) - } - return LabeledDirected{g} -} - -// TransposeLabeledRoots constructs the labeled directed graph corresponding -// to FromList f but with arcs in the opposite direction. That is, from -// roots toward leaves. -// -// TransposeLabeledRoots also returns a count of roots of the resulting forest -// and a bitmap of the roots. -// -// The argument labels can be nil. In this case labels are generated matching -// the path indexes. This corresponds to the "to", or child node. -// -// If labels is non-nil, it must be the same length as t.Paths and is used -// to look up label numbers by the path index. -// -// The method relies only on the From member of f.Paths. Other members of -// the FromList are not used. -// -// See FromList.TransposeLabeled for a simpler verstion that returns the -// forest only. -func (f FromList) TransposeLabeledRoots(labels []LI) (forest LabeledDirected, nRoots int, roots Bits) { - p := f.Paths - nRoots = len(p) - roots.SetAll(len(p)) - g := make(LabeledAdjacencyList, len(p)) - for i, p := range f.Paths { - if p.From == -1 { - continue - } - l := LI(i) - if labels != nil { - l = labels[i] - } - n := NI(i) - g[p.From] = append(g[p.From], Half{n, l}) - if roots.Bit(n) == 1 { - roots.SetBit(n, 0) - nRoots-- - } - } - return LabeledDirected{g}, nRoots, roots -} - -// TransposeRoots constructs the directed graph corresponding to FromList f -// but with arcs in the opposite direction. That is, from roots toward leaves. -// -// TransposeRoots also returns a count of roots of the resulting forest and -// a bitmap of the roots. -// -// The method relies only on the From member of f.Paths. Other members of -// the FromList are not used. -// -// See FromList.Transpose for a simpler verstion that returns the forest only. -func (f FromList) TransposeRoots() (forest Directed, nRoots int, roots Bits) { - p := f.Paths - nRoots = len(p) - roots.SetAll(len(p)) - g := make(AdjacencyList, len(p)) - for i, e := range p { - if e.From == -1 { - continue - } - n := NI(i) - g[e.From] = append(g[e.From], n) - if roots.Bit(n) == 1 { - roots.SetBit(n, 0) - nRoots-- - } - } - return Directed{g}, nRoots, roots -} diff --git a/vendor/github.com/soniakeys/graph/graph.go b/vendor/github.com/soniakeys/graph/graph.go deleted file mode 100644 index a2044e9..0000000 --- a/vendor/github.com/soniakeys/graph/graph.go +++ /dev/null @@ -1,181 +0,0 @@ -// Copyright 2014 Sonia Keys -// License MIT: http://opensource.org/licenses/MIT - -package graph - -// graph.go contains type definitions for all graph types and components. -// Also, go generate directives for source transformations. -// -// For readability, the types are defined in a dependency order: -// -// NI -// NodeList -// AdjacencyList -// Directed -// Undirected -// LI -// Half -// LabeledAdjacencyList -// LabeledDirected -// LabeledUndirected -// Edge -// LabeledEdge -// WeightFunc -// WeightedEdgeList - -//go:generate cp adj_cg.go adj_RO.go -//go:generate gofmt -r "LabeledAdjacencyList -> AdjacencyList" -w adj_RO.go -//go:generate gofmt -r "n.To -> n" -w adj_RO.go -//go:generate gofmt -r "Half -> NI" -w adj_RO.go - -//go:generate cp dir_cg.go dir_RO.go -//go:generate gofmt -r "LabeledDirected -> Directed" -w dir_RO.go -//go:generate gofmt -r "LabeledAdjacencyList -> AdjacencyList" -w dir_RO.go -//go:generate gofmt -r "n.To -> n" -w dir_RO.go -//go:generate gofmt -r "Half -> NI" -w dir_RO.go - -//go:generate cp undir_cg.go undir_RO.go -//go:generate gofmt -r "LabeledUndirected -> Undirected" -w undir_RO.go -//go:generate gofmt -r "LabeledAdjacencyList -> AdjacencyList" -w undir_RO.go -//go:generate gofmt -r "n.To -> n" -w undir_RO.go -//go:generate gofmt -r "Half -> NI" -w undir_RO.go - -// NI is a "node int" -// -// It is a node number or node ID. NIs are used extensively as slice indexes. -// NIs typically account for a significant fraction of the memory footprint of -// a graph. -type NI int32 - -// NodeList satisfies sort.Interface. -type NodeList []NI - -func (l NodeList) Len() int { return len(l) } -func (l NodeList) Less(i, j int) bool { return l[i] < l[j] } -func (l NodeList) Swap(i, j int) { l[i], l[j] = l[j], l[i] } - -// An AdjacencyList represents a graph as a list of neighbors for each node. -// The "node ID" of a node is simply it's slice index in the AdjacencyList. -// For an AdjacencyList g, g[n] represents arcs going from node n to nodes -// g[n]. -// -// Adjacency lists are inherently directed but can be used to represent -// directed or undirected graphs. See types Directed and Undirected. -type AdjacencyList [][]NI - -// Directed represents a directed graph. -// -// Directed methods generally rely on the graph being directed, specifically -// that arcs do not have reciprocals. -type Directed struct { - AdjacencyList // embedded to include AdjacencyList methods -} - -// Undirected represents an undirected graph. -// -// In an undirected graph, for each arc between distinct nodes there is also -// a reciprocal arc, an arc in the opposite direction. Loops do not have -// reciprocals. -// -// Undirected methods generally rely on the graph being undirected, -// specifically that every arc between distinct nodes has a reciprocal. -type Undirected struct { - AdjacencyList // embedded to include AdjacencyList methods -} - -// LI is a label integer, used for associating labels with arcs. -type LI int32 - -// Half is a half arc, representing a labeled arc and the "neighbor" node -// that the arc leads to. -// -// Halfs can be composed to form a labeled adjacency list. -type Half struct { - To NI // node ID, usable as a slice index - Label LI // half-arc ID for application data, often a weight -} - -// A LabeledAdjacencyList represents a graph as a list of neighbors for each -// node, connected by labeled arcs. -// -// Arc labels are not necessarily unique arc IDs. Different arcs can have -// the same label. -// -// Arc labels are commonly used to assocate a weight with an arc. Arc labels -// are general purpose however and can be used to associate arbitrary -// information with an arc. -// -// Methods implementing weighted graph algorithms will commonly take a -// weight function that turns a label int into a float64 weight. -// -// If only a small amount of information -- such as an integer weight or -// a single printable character -- needs to be associated, it can sometimes -// be possible to encode the information directly into the label int. For -// more generality, some lookup scheme will be needed. -// -// In an undirected labeled graph, reciprocal arcs must have identical labels. -// Note this does not preclude parallel arcs with different labels. -type LabeledAdjacencyList [][]Half - -// LabeledDirected represents a directed labeled graph. -// -// This is the labeled version of Directed. See types LabeledAdjacencyList -// and Directed. -type LabeledDirected struct { - LabeledAdjacencyList // embedded to include LabeledAdjacencyList methods -} - -// LabeledUndirected represents an undirected labeled graph. -// -// This is the labeled version of Undirected. See types LabeledAdjacencyList -// and Undirected. -type LabeledUndirected struct { - LabeledAdjacencyList // embedded to include LabeledAdjacencyList methods -} - -// Edge is an undirected edge between nodes N1 and N2. -type Edge struct{ N1, N2 NI } - -// LabeledEdge is an undirected edge with an associated label. -type LabeledEdge struct { - Edge - LI -} - -// WeightFunc returns a weight for a given label. -// -// WeightFunc is a parameter type for various search functions. The intent -// is to return a weight corresponding to an arc label. The name "weight" -// is an abstract term. An arc "weight" will typically have some application -// specific meaning other than physical weight. -type WeightFunc func(label LI) (weight float64) - -// WeightedEdgeList is a graph representation. -// -// It is a labeled edge list, with an associated weight function to return -// a weight given an edge label. -// -// Also associated is the order, or number of nodes of the graph. -// All nodes occurring in the edge list must be strictly less than Order. -// -// WeigtedEdgeList sorts by weight, obtained by calling the weight function. -// If weight computation is expensive, consider supplying a cached or -// memoized version. -type WeightedEdgeList struct { - Order int - WeightFunc - Edges []LabeledEdge -} - -// Len implements sort.Interface. -func (l WeightedEdgeList) Len() int { return len(l.Edges) } - -// Less implements sort.Interface. -func (l WeightedEdgeList) Less(i, j int) bool { - return l.WeightFunc(l.Edges[i].LI) < l.WeightFunc(l.Edges[j].LI) -} - -// Swap implements sort.Interface. -func (l WeightedEdgeList) Swap(i, j int) { - l.Edges[i], l.Edges[j] = l.Edges[j], l.Edges[i] -} diff --git a/vendor/github.com/soniakeys/graph/hacking.md b/vendor/github.com/soniakeys/graph/hacking.md deleted file mode 100644 index 30d2d7c..0000000 --- a/vendor/github.com/soniakeys/graph/hacking.md +++ /dev/null @@ -1,37 +0,0 @@ -#Hacking - -Basic use of the package is just go get, or git clone; go install. There are -no dependencies outside the standard library. - -The primary to-do list is the issue tracker on Github. I maintained a -journal on google drive for a while but at some point filed issues for all -remaining ideas in that document that still seemed relevant. So currently -there is no other roadmap or planning document. - -CI is currently on travis-ci.org. The .travis.yml builds for go 1.2.1 -following https://github.com/soniakeys/graph/issues/49, and it currently builds -for go 1.6 as well. The travis script calls a shell script right away because -I didn’t see a way to get it to do different steps for the different go -versions. For 1.2.1, I just wanted the basic tests. For a current go version -such as 1.6, there’s a growing list of checks. - -The GOARCH=386 test is for https://github.com/soniakeys/graph/issues/41. -The problem is the architecture specific code in bits32.go and bits64.go. -Yes, there are architecture independent algorithms. There is also assembly -to access machine instructions. Anyway, it’s the way it is for now. - -Im not big on making go vet happy just for a badge but I really like the -example check that I believe appeared with go 1.6. (I think it will be a -standard check with 1.7, so the test script will have to change then.) - -https://github.com/client9/misspell has been valuable. - -Also I wrote https://github.com/soniakeys/vetc to validate that each source -file has copyright/license statement. - -Then, it’s not in the ci script, but I wrote https://github.com/soniakeys/rcv -to put coverage stats in the readme. Maybe it could be commit hook or -something but for now I’ll try just running it manually now and then. - -Go fmt is not in the ci script, but I have at least one editor set up to run -it on save, so code should stay formatted pretty well. diff --git a/vendor/github.com/soniakeys/graph/mst.go b/vendor/github.com/soniakeys/graph/mst.go deleted file mode 100644 index 028e680..0000000 --- a/vendor/github.com/soniakeys/graph/mst.go +++ /dev/null @@ -1,244 +0,0 @@ -// Copyright 2014 Sonia Keys -// License MIT: http://opensource.org/licenses/MIT - -package graph - -import ( - "container/heap" - "sort" -) - -type dsElement struct { - from NI - rank int -} - -type disjointSet struct { - set []dsElement -} - -func newDisjointSet(n int) disjointSet { - set := make([]dsElement, n) - for i := range set { - set[i].from = -1 - } - return disjointSet{set} -} - -// return true if disjoint trees were combined. -// false if x and y were already in the same tree. -func (ds disjointSet) union(x, y NI) bool { - xr := ds.find(x) - yr := ds.find(y) - if xr == yr { - return false - } - switch xe, ye := &ds.set[xr], &ds.set[yr]; { - case xe.rank < ye.rank: - xe.from = yr - case xe.rank == ye.rank: - xe.rank++ - fallthrough - default: - ye.from = xr - } - return true -} - -func (ds disjointSet) find(n NI) NI { - // fast paths for n == root or from root. - // no updates need in these cases. - s := ds.set - fr := s[n].from - if fr < 0 { // n is root - return n - } - n, fr = fr, s[fr].from - if fr < 0 { // n is from root - return n - } - // otherwise updates needed. - // two iterative passes (rather than recursion or stack) - // pass 1: find root - r := fr - for { - f := s[r].from - if f < 0 { - break - } - r = f - } - // pass 2: update froms - for { - s[n].from = r - if fr == r { - return r - } - n = fr - fr = s[n].from - } -} - -// Kruskal implements Kruskal's algorithm for constructing a minimum spanning -// forest on an undirected graph. -// -// While the input graph is interpreted as undirected, the receiver edge list -// does not actually need to contain reciprocal arcs. A property of the -// algorithm is that arc direction is ignored. Thus only a single arc out of -// a reciprocal pair must be present in the edge list. Reciprocal arcs (and -// parallel arcs) are allowed though, and do not affect the result. -// -// The forest is returned as an undirected graph. -// -// Also returned is a total distance for the returned forest. -// -// The edge list of the receiver is sorted as a side effect of this method. -// See KruskalSorted for a version that relies on the edge list being already -// sorted. -func (l WeightedEdgeList) Kruskal() (g LabeledUndirected, dist float64) { - sort.Sort(l) - return l.KruskalSorted() -} - -// KruskalSorted implements Kruskal's algorithm for constructing a minimum -// spanning tree on an undirected graph. -// -// While the input graph is interpreted as undirected, the receiver edge list -// does not actually need to contain reciprocal arcs. A property of the -// algorithm is that arc direction is ignored. Thus only a single arc out of -// a reciprocal pair must be present in the edge list. Reciprocal arcs (and -// parallel arcs) are allowed though, and do not affect the result. -// -// When called, the edge list of the receiver must be already sorted by weight. -// See Kruskal for a version that accepts an unsorted edge list. -// -// The forest is returned as an undirected graph. -// -// Also returned is a total distance for the returned forest. -func (l WeightedEdgeList) KruskalSorted() (g LabeledUndirected, dist float64) { - ds := newDisjointSet(l.Order) - g.LabeledAdjacencyList = make(LabeledAdjacencyList, l.Order) - for _, e := range l.Edges { - if ds.union(e.N1, e.N2) { - g.AddEdge(Edge{e.N1, e.N2}, e.LI) - dist += l.WeightFunc(e.LI) - } - } - return -} - -// Prim implements the JarnÃk-Prim-Dijkstra algorithm for constructing -// a minimum spanning tree on an undirected graph. -// -// Prim computes a minimal spanning tree on the connected component containing -// the given start node. The tree is returned in FromList f. Argument f -// cannot be a nil pointer although it can point to a zero value FromList. -// -// If the passed FromList.Paths has the len of g though, it will be reused. -// In the case of a graph with multiple connected components, this allows a -// spanning forest to be accumulated by calling Prim successively on -// representative nodes of the components. In this case if leaves for -// individual trees are of interest, pass a non-nil zero-value for the argument -// componentLeaves and it will be populated with leaves for the single tree -// spanned by the call. -// -// If argument labels is non-nil, it must have the same length as g and will -// be populated with labels corresponding to the edges of the tree. -// -// Returned are the number of nodes spanned for the single tree (which will be -// the order of the connected component) and the total spanned distance for the -// single tree. -func (g LabeledUndirected) Prim(start NI, w WeightFunc, f *FromList, labels []LI, componentLeaves *Bits) (numSpanned int, dist float64) { - al := g.LabeledAdjacencyList - if len(f.Paths) != len(al) { - *f = NewFromList(len(al)) - } - b := make([]prNode, len(al)) // "best" - for n := range b { - b[n].nx = NI(n) - b[n].fx = -1 - } - rp := f.Paths - var frontier prHeap - rp[start] = PathEnd{From: -1, Len: 1} - numSpanned = 1 - fLeaves := &f.Leaves - fLeaves.SetBit(start, 1) - if componentLeaves != nil { - componentLeaves.SetBit(start, 1) - } - for a := start; ; { - for _, nb := range al[a] { - if rp[nb.To].Len > 0 { - continue // already in MST, no action - } - switch bp := &b[nb.To]; { - case bp.fx == -1: // new node for frontier - bp.from = fromHalf{From: a, Label: nb.Label} - bp.wt = w(nb.Label) - heap.Push(&frontier, bp) - case w(nb.Label) < bp.wt: // better arc - bp.from = fromHalf{From: a, Label: nb.Label} - bp.wt = w(nb.Label) - heap.Fix(&frontier, bp.fx) - } - } - if len(frontier) == 0 { - break // done - } - bp := heap.Pop(&frontier).(*prNode) - a = bp.nx - rp[a].Len = rp[bp.from.From].Len + 1 - rp[a].From = bp.from.From - if len(labels) != 0 { - labels[a] = bp.from.Label - } - dist += bp.wt - fLeaves.SetBit(bp.from.From, 0) - fLeaves.SetBit(a, 1) - if componentLeaves != nil { - componentLeaves.SetBit(bp.from.From, 0) - componentLeaves.SetBit(a, 1) - } - numSpanned++ - } - return -} - -// fromHalf is a half arc, representing a labeled arc and the "neighbor" node -// that the arc originates from. -// -// (This used to be exported when there was a LabeledFromList. Currently -// unexported now that it seems to have much more limited use.) -type fromHalf struct { - From NI - Label LI -} - -type prNode struct { - nx NI - from fromHalf - wt float64 // p.Weight(from.Label) - fx int -} - -type prHeap []*prNode - -func (h prHeap) Len() int { return len(h) } -func (h prHeap) Less(i, j int) bool { return h[i].wt < h[j].wt } -func (h prHeap) Swap(i, j int) { - h[i], h[j] = h[j], h[i] - h[i].fx = i - h[j].fx = j -} -func (p *prHeap) Push(x interface{}) { - nd := x.(*prNode) - nd.fx = len(*p) - *p = append(*p, nd) -} -func (p *prHeap) Pop() interface{} { - r := *p - last := len(r) - 1 - *p = r[:last] - return r[last] -} diff --git a/vendor/github.com/soniakeys/graph/random.go b/vendor/github.com/soniakeys/graph/random.go deleted file mode 100644 index 99f0445..0000000 --- a/vendor/github.com/soniakeys/graph/random.go +++ /dev/null @@ -1,325 +0,0 @@ -// Copyright 2016 Sonia Keys -// License MIT: https://opensource.org/licenses/MIT - -package graph - -import ( - "errors" - "math" - "math/rand" - "time" -) - -// Euclidean generates a random simple graph on the Euclidean plane. -// -// Nodes are associated with coordinates uniformly distributed on a unit -// square. Arcs are added between random nodes with a bias toward connecting -// nearer nodes. -// -// Unfortunately the function has a few "knobs". -// The returned graph will have order nNodes and arc size nArcs. The affinity -// argument controls the bias toward connecting nearer nodes. The function -// selects random pairs of nodes as a candidate arc then rejects the candidate -// if the nodes fail an affinity test. Also parallel arcs are rejected. -// As more affine or denser graphs are requested, rejections increase, -// increasing run time. The patience argument controls the number of arc -// rejections allowed before the function gives up and returns an error. -// Note that higher affinity will require more patience and that some -// combinations of nNodes and nArcs cannot be achieved with any amount of -// patience given that the returned graph must be simple. -// -// If Rand r is nil, the method creates a new source and generator for -// one-time use. -// -// Returned is a directed simple graph and associated positions indexed by -// node number. -// -// See also LabeledEuclidean. -func Euclidean(nNodes, nArcs int, affinity float64, patience int, r *rand.Rand) (g Directed, pos []struct{ X, Y float64 }, err error) { - a := make(AdjacencyList, nNodes) // graph - // generate random positions - if r == nil { - r = rand.New(rand.NewSource(time.Now().UnixNano())) - } - pos = make([]struct{ X, Y float64 }, nNodes) - for i := range pos { - pos[i].X = r.Float64() - pos[i].Y = r.Float64() - } - // arcs - var tooFar, dup int -arc: - for i := 0; i < nArcs; { - if tooFar == nArcs*patience { - err = errors.New("affinity not found") - return - } - if dup == nArcs*patience { - err = errors.New("overcrowding") - return - } - n1 := NI(r.Intn(nNodes)) - var n2 NI - for { - n2 = NI(r.Intn(nNodes)) - if n2 != n1 { // no graph loops - break - } - } - c1 := &pos[n1] - c2 := &pos[n2] - dist := math.Hypot(c2.X-c1.X, c2.Y-c1.Y) - if dist*affinity > r.ExpFloat64() { // favor near nodes - tooFar++ - continue - } - for _, nb := range a[n1] { - if nb == n2 { // no parallel arcs - dup++ - continue arc - } - } - a[n1] = append(a[n1], n2) - i++ - } - g = Directed{a} - return -} - -// LabeledEuclidean generates a random simple graph on the Euclidean plane. -// -// Arc label values in the returned graph g are indexes into the return value -// wt. Wt is the Euclidean distance between the from and to nodes of the arc. -// -// Otherwise the function arguments and return values are the same as for -// function Euclidean. See Euclidean. -func LabeledEuclidean(nNodes, nArcs int, affinity float64, patience int, r *rand.Rand) (g LabeledDirected, pos []struct{ X, Y float64 }, wt []float64, err error) { - a := make(LabeledAdjacencyList, nNodes) // graph - wt = make([]float64, nArcs) // arc weights - // generate random positions - if r == nil { - r = rand.New(rand.NewSource(time.Now().UnixNano())) - } - pos = make([]struct{ X, Y float64 }, nNodes) - for i := range pos { - pos[i].X = r.Float64() - pos[i].Y = r.Float64() - } - // arcs - var tooFar, dup int -arc: - for i := 0; i < nArcs; { - if tooFar == nArcs*patience { - err = errors.New("affinity not found") - return - } - if dup == nArcs*patience { - err = errors.New("overcrowding") - return - } - n1 := NI(r.Intn(nNodes)) - var n2 NI - for { - n2 = NI(r.Intn(nNodes)) - if n2 != n1 { // no graph loops - break - } - } - c1 := &pos[n1] - c2 := &pos[n2] - dist := math.Hypot(c2.X-c1.X, c2.Y-c1.Y) - if dist*affinity > r.ExpFloat64() { // favor near nodes - tooFar++ - continue - } - for _, nb := range a[n1] { - if nb.To == n2 { // no parallel arcs - dup++ - continue arc - } - } - wt[i] = dist - a[n1] = append(a[n1], Half{n2, LI(i)}) - i++ - } - g = LabeledDirected{a} - return -} - -// Geometric generates a random geometric graph (RGG) on the Euclidean plane. -// -// An RGG is an undirected simple graph. Nodes are associated with coordinates -// uniformly distributed on a unit square. Edges are added between all nodes -// falling within a specified distance or radius of each other. -// -// The resulting number of edges is somewhat random but asymptotically -// approaches m = Ï€r²n²/2. The method accumulates and returns the actual -// number of edges constructed. -// -// If Rand r is nil, the method creates a new source and generator for -// one-time use. -// -// See also LabeledGeometric. -func Geometric(nNodes int, radius float64, r *rand.Rand) (g Undirected, pos []struct{ X, Y float64 }, m int) { - // Expected degree is approximately nÏ€r². - a := make(AdjacencyList, nNodes) - if r == nil { - r = rand.New(rand.NewSource(time.Now().UnixNano())) - } - pos = make([]struct{ X, Y float64 }, nNodes) - for i := range pos { - pos[i].X = r.Float64() - pos[i].Y = r.Float64() - } - for u, up := range pos { - for v := u + 1; v < len(pos); v++ { - vp := pos[v] - if math.Hypot(up.X-vp.X, up.Y-vp.Y) < radius { - a[u] = append(a[u], NI(v)) - a[v] = append(a[v], NI(u)) - m++ - } - } - } - g = Undirected{a} - return -} - -// LabeledGeometric generates a random geometric graph (RGG) on the Euclidean -// plane. -// -// Edge label values in the returned graph g are indexes into the return value -// wt. Wt is the Euclidean distance between nodes of the edge. The graph -// size m is len(wt). -// -// See Geometric for additional description. -func LabeledGeometric(nNodes int, radius float64, r *rand.Rand) (g LabeledUndirected, pos []struct{ X, Y float64 }, wt []float64) { - a := make(LabeledAdjacencyList, nNodes) - if r == nil { - r = rand.New(rand.NewSource(time.Now().UnixNano())) - } - pos = make([]struct{ X, Y float64 }, nNodes) - for i := range pos { - pos[i].X = r.Float64() - pos[i].Y = r.Float64() - } - for u, up := range pos { - for v := u + 1; v < len(pos); v++ { - vp := pos[v] - if w := math.Hypot(up.X-vp.X, up.Y-vp.Y); w < radius { - a[u] = append(a[u], Half{NI(v), LI(len(wt))}) - a[v] = append(a[v], Half{NI(u), LI(len(wt))}) - wt = append(wt, w) - } - } - } - g = LabeledUndirected{a} - return -} - -// KroneckerDirected generates a Kronecker-like random directed graph. -// -// The returned graph g is simple and has no isolated nodes but is not -// necessarily fully connected. The number of of nodes will be <= 2^scale, -// and will be near 2^scale for typical values of arcFactor, >= 2. -// ArcFactor * 2^scale arcs are generated, although loops and duplicate arcs -// are rejected. -// -// If Rand r is nil, the method creates a new source and generator for -// one-time use. -// -// Return value ma is the number of arcs retained in the result graph. -func KroneckerDirected(scale uint, arcFactor float64, r *rand.Rand) (g Directed, ma int) { - a, m := kronecker(scale, arcFactor, true, r) - return Directed{a}, m -} - -// KroneckerUndirected generates a Kronecker-like random undirected graph. -// -// The returned graph g is simple and has no isolated nodes but is not -// necessarily fully connected. The number of of nodes will be <= 2^scale, -// and will be near 2^scale for typical values of edgeFactor, >= 2. -// EdgeFactor * 2^scale edges are generated, although loops and duplicate edges -// are rejected. -// -// If Rand r is nil, the method creates a new source and generator for -// one-time use. -// -// Return value m is the true number of edges--not arcs--retained in the result -// graph. -func KroneckerUndirected(scale uint, edgeFactor float64, r *rand.Rand) (g Undirected, m int) { - al, s := kronecker(scale, edgeFactor, false, r) - return Undirected{al}, s -} - -// Styled after the Graph500 example code. Not well tested currently. -// Graph500 example generates undirected only. No idea if the directed variant -// here is meaningful or not. -// -// note mma returns arc size ma for dir=true, but returns size m for dir=false -func kronecker(scale uint, edgeFactor float64, dir bool, r *rand.Rand) (g AdjacencyList, mma int) { - if r == nil { - r = rand.New(rand.NewSource(time.Now().UnixNano())) - } - N := NI(1 << scale) // node extent - M := int(edgeFactor*float64(N) + .5) // number of arcs/edges to generate - a, b, c := 0.57, 0.19, 0.19 // initiator probabilities - ab := a + b - cNorm := c / (1 - ab) - aNorm := a / ab - ij := make([][2]NI, M) - var bm Bits - var nNodes int - for k := range ij { - var i, j NI - for b := NI(1); b < N; b <<= 1 { - if r.Float64() > ab { - i |= b - if r.Float64() > cNorm { - j |= b - } - } else if r.Float64() > aNorm { - j |= b - } - } - if bm.Bit(i) == 0 { - bm.SetBit(i, 1) - nNodes++ - } - if bm.Bit(j) == 0 { - bm.SetBit(j, 1) - nNodes++ - } - r := r.Intn(k + 1) // shuffle edges as they are generated - ij[k] = ij[r] - ij[r] = [2]NI{i, j} - } - p := r.Perm(nNodes) // mapping to shuffle IDs of non-isolated nodes - px := 0 - rn := make([]NI, N) - for i := range rn { - if bm.Bit(NI(i)) == 1 { - rn[i] = NI(p[px]) // fill lookup table - px++ - } - } - g = make(AdjacencyList, nNodes) -ij: - for _, e := range ij { - if e[0] == e[1] { - continue // skip loops - } - ri, rj := rn[e[0]], rn[e[1]] - for _, nb := range g[ri] { - if nb == rj { - continue ij // skip parallel edges - } - } - g[ri] = append(g[ri], rj) - mma++ - if !dir { - g[rj] = append(g[rj], ri) - } - } - return -} diff --git a/vendor/github.com/soniakeys/graph/readme.md b/vendor/github.com/soniakeys/graph/readme.md deleted file mode 100644 index 539670f..0000000 --- a/vendor/github.com/soniakeys/graph/readme.md +++ /dev/null @@ -1,38 +0,0 @@ -#Graph - -A graph library with goals of speed and simplicity, Graph implements -graph algorithms on graphs of zero-based integer node IDs. - -[](https://godoc.org/github.com/soniakeys/graph) [](https://gowalker.org/github.com/soniakeys/graph) [](http://go-search.org/view?id=github.com%2Fsoniakeys%2Fgraph)[](https://travis-ci.org/soniakeys/graph) - -Status, 4 Apr 2016: The repo has benefitted recently from being included -in another package. In response to users of that package, this repo now -builds for 32 bit Windows and ARM, and for Go versions back to 1.2.1. -Thank you all who have filed issues. - -###Non-source files of interest - -The directory [tutorials](tutorials) is a work in progress - there are only -a couple of tutorials there yet - but the concept is to provide some topical -walk-throughs to supplement godoc. The source-based godoc documentation -remains the primary documentation. - -* [Dijkstra's algorithm](tutorials/dijkstra.md) -* [AdjacencyList types](tutorials/adjacencylist.md) - -The directory [bench](bench) is another work in progress. The concept is -to present some plots showing benchmark performance approaching some -theoretical asymptote. - -[hacking.md](hacking.md) has some information about how the library is -developed, built, and tested. It might be of interest if for example you -plan to fork or contribute to the the repository. - -###Test coverage -8 Apr 2016 -``` -graph 95.3% -graph/df 20.7% -graph/dot 77.5% -graph/treevis 79.4% -``` diff --git a/vendor/github.com/soniakeys/graph/sssp.go b/vendor/github.com/soniakeys/graph/sssp.go deleted file mode 100644 index 32cc192..0000000 --- a/vendor/github.com/soniakeys/graph/sssp.go +++ /dev/null @@ -1,881 +0,0 @@ -// Copyright 2013 Sonia Keys -// License MIT: http://opensource.org/licenses/MIT - -package graph - -import ( - "container/heap" - "fmt" - "math" -) - -// rNode holds data for a "reached" node -type rNode struct { - nx NI - state int8 // state constants defined below - f float64 // "g+h", path dist + heuristic estimate - fx int // heap.Fix index -} - -// for rNode.state -const ( - unreached = 0 - reached = 1 - open = 1 - closed = 2 -) - -type openHeap []*rNode - -// A Heuristic is defined on a specific end node. The function -// returns an estimate of the path distance from node argument -// "from" to the end node. Two subclasses of heuristics are "admissible" -// and "monotonic." -// -// Admissible means the value returned is guaranteed to be less than or -// equal to the actual shortest path distance from the node to end. -// -// An admissible estimate may further be monotonic. -// Monotonic means that for any neighboring nodes A and B with half arc aB -// leading from A to B, and for heuristic h defined on some end node, then -// h(A) <= aB.ArcWeight + h(B). -// -// See AStarA for additional notes on implementing heuristic functions for -// AStar search methods. -type Heuristic func(from NI) float64 - -// Admissible returns true if heuristic h is admissible on graph g relative to -// the given end node. -// -// If h is inadmissible, the string result describes a counter example. -func (h Heuristic) Admissible(g LabeledAdjacencyList, w WeightFunc, end NI) (bool, string) { - // invert graph - inv := make(LabeledAdjacencyList, len(g)) - for from, nbs := range g { - for _, nb := range nbs { - inv[nb.To] = append(inv[nb.To], - Half{To: NI(from), Label: nb.Label}) - } - } - // run dijkstra - // Dijkstra.AllPaths takes a start node but after inverting the graph - // argument end now represents the start node of the inverted graph. - f, dist, _ := inv.Dijkstra(end, -1, w) - // compare h to found shortest paths - for n := range inv { - if f.Paths[n].Len == 0 { - continue // no path, any heuristic estimate is fine. - } - if !(h(NI(n)) <= dist[n]) { - return false, fmt.Sprintf("h(%d) = %g, "+ - "required to be <= found shortest path (%g)", - n, h(NI(n)), dist[n]) - } - } - return true, "" -} - -// Monotonic returns true if heuristic h is monotonic on weighted graph g. -// -// If h is non-monotonic, the string result describes a counter example. -func (h Heuristic) Monotonic(g LabeledAdjacencyList, w WeightFunc) (bool, string) { - // precompute - hv := make([]float64, len(g)) - for n := range g { - hv[n] = h(NI(n)) - } - // iterate over all edges - for from, nbs := range g { - for _, nb := range nbs { - arcWeight := w(nb.Label) - if !(hv[from] <= arcWeight+hv[nb.To]) { - return false, fmt.Sprintf("h(%d) = %g, "+ - "required to be <= arc weight + h(%d) (= %g + %g = %g)", - from, hv[from], - nb.To, arcWeight, hv[nb.To], arcWeight+hv[nb.To]) - } - } - } - return true, "" -} - -// AStarA finds a path between two nodes. -// -// AStarA implements both algorithm A and algorithm A*. The difference in the -// two algorithms is strictly in the heuristic estimate returned by argument h. -// If h is an "admissible" heuristic estimate, then the algorithm is termed A*, -// otherwise it is algorithm A. -// -// Like Dijkstra's algorithm, AStarA with an admissible heuristic finds the -// shortest path between start and end. AStarA generally runs faster than -// Dijkstra though, by using the heuristic distance estimate. -// -// AStarA with an inadmissible heuristic becomes algorithm A. Algorithm A -// will find a path, but it is not guaranteed to be the shortest path. -// The heuristic still guides the search however, so a nearly admissible -// heuristic is likely to find a very good path, if not the best. Quality -// of the path returned degrades gracefully with the quality of the heuristic. -// -// The heuristic function h should ideally be fairly inexpensive. AStarA -// may call it more than once for the same node, especially as graph density -// increases. In some cases it may be worth the effort to memoize or -// precompute values. -// -// Argument g is the graph to be searched, with arc weights returned by w. -// As usual for AStar, arc weights must be non-negative. -// Graphs may be directed or undirected. -// -// If AStarA finds a path it returns a FromList encoding the path, the arc -// labels for path nodes, the total path distance, and ok = true. -// Otherwise it returns ok = false. -func (g LabeledAdjacencyList) AStarA(w WeightFunc, start, end NI, h Heuristic) (f FromList, labels []LI, dist float64, ok bool) { - // NOTE: AStarM is largely duplicate code. - - f = NewFromList(len(g)) - labels = make([]LI, len(g)) - d := make([]float64, len(g)) - r := make([]rNode, len(g)) - for i := range r { - r[i].nx = NI(i) - } - // start node is reached initially - cr := &r[start] - cr.state = reached - cr.f = h(start) // total path estimate is estimate from start - rp := f.Paths - rp[start] = PathEnd{Len: 1, From: -1} // path length at start is 1 node - // oh is a heap of nodes "open" for exploration. nodes go on the heap - // when they get an initial or new "g" path distance, and therefore a - // new "f" which serves as priority for exploration. - oh := openHeap{cr} - for len(oh) > 0 { - bestPath := heap.Pop(&oh).(*rNode) - bestNode := bestPath.nx - if bestNode == end { - return f, labels, d[end], true - } - bp := &rp[bestNode] - nextLen := bp.Len + 1 - for _, nb := range g[bestNode] { - alt := &r[nb.To] - ap := &rp[alt.nx] - // "g" path distance from start - g := d[bestNode] + w(nb.Label) - if alt.state == reached { - if g > d[nb.To] { - // candidate path to nb is longer than some alternate path - continue - } - if g == d[nb.To] && nextLen >= ap.Len { - // candidate path has identical length of some alternate - // path but it takes no fewer hops. - continue - } - // cool, we found a better way to get to this node. - // record new path data for this node and - // update alt with new data and make sure it's on the heap. - *ap = PathEnd{From: bestNode, Len: nextLen} - labels[nb.To] = nb.Label - d[nb.To] = g - alt.f = g + h(nb.To) - if alt.fx < 0 { - heap.Push(&oh, alt) - } else { - heap.Fix(&oh, alt.fx) - } - } else { - // bestNode being reached for the first time. - *ap = PathEnd{From: bestNode, Len: nextLen} - labels[nb.To] = nb.Label - d[nb.To] = g - alt.f = g + h(nb.To) - alt.state = reached - heap.Push(&oh, alt) // and it's now open for exploration - } - } - } - return // no path -} - -// AStarAPath finds a shortest path using the AStarA algorithm. -// -// This is a convenience method with a simpler result than the AStarA method. -// See documentation on the AStarA method. -// -// If a path is found, the non-nil node path is returned with the total path -// distance. Otherwise the returned path will be nil. -func (g LabeledAdjacencyList) AStarAPath(start, end NI, h Heuristic, w WeightFunc) ([]NI, float64) { - f, _, d, _ := g.AStarA(w, start, end, h) - return f.PathTo(end, nil), d -} - -// AStarM is AStarA optimized for monotonic heuristic estimates. -// -// Note that this function requires a monotonic heuristic. Results will -// not be meaningful if argument h is non-monotonic. -// -// See AStarA for general usage. See Heuristic for notes on monotonicity. -func (g LabeledAdjacencyList) AStarM(w WeightFunc, start, end NI, h Heuristic) (f FromList, labels []LI, dist float64, ok bool) { - // NOTE: AStarM is largely code duplicated from AStarA. - // Differences are noted in comments in this method. - - f = NewFromList(len(g)) - labels = make([]LI, len(g)) - d := make([]float64, len(g)) - r := make([]rNode, len(g)) - for i := range r { - r[i].nx = NI(i) - } - cr := &r[start] - - // difference from AStarA: - // instead of a bit to mark a reached node, there are two states, - // open and closed. open marks nodes "open" for exploration. - // nodes are marked open as they are reached, then marked - // closed as they are found to be on the best path. - cr.state = open - - cr.f = h(start) - rp := f.Paths - rp[start] = PathEnd{Len: 1, From: -1} - oh := openHeap{cr} - for len(oh) > 0 { - bestPath := heap.Pop(&oh).(*rNode) - bestNode := bestPath.nx - if bestNode == end { - return f, labels, d[end], true - } - - // difference from AStarA: - // move nodes to closed list as they are found to be best so far. - bestPath.state = closed - - bp := &rp[bestNode] - nextLen := bp.Len + 1 - for _, nb := range g[bestNode] { - alt := &r[nb.To] - - // difference from AStarA: - // Monotonicity means that f cannot be improved. - if alt.state == closed { - continue - } - - ap := &rp[alt.nx] - g := d[bestNode] + w(nb.Label) - - // difference from AStarA: - // test for open state, not just reached - if alt.state == open { - - if g > d[nb.To] { - continue - } - if g == d[nb.To] && nextLen >= ap.Len { - continue - } - *ap = PathEnd{From: bestNode, Len: nextLen} - labels[nb.To] = nb.Label - d[nb.To] = g - alt.f = g + h(nb.To) - - // difference from AStarA: - // we know alt was on the heap because we found it marked open - heap.Fix(&oh, alt.fx) - } else { - *ap = PathEnd{From: bestNode, Len: nextLen} - labels[nb.To] = nb.Label - d[nb.To] = g - alt.f = g + h(nb.To) - - // difference from AStarA: - // nodes are opened when first reached - alt.state = open - heap.Push(&oh, alt) - } - } - } - return -} - -// AStarMPath finds a shortest path using the AStarM algorithm. -// -// This is a convenience method with a simpler result than the AStarM method. -// See documentation on the AStarM and AStarA methods. -// -// If a path is found, the non-nil node path is returned with the total path -// distance. Otherwise the returned path will be nil. -func (g LabeledAdjacencyList) AStarMPath(start, end NI, h Heuristic, w WeightFunc) ([]NI, float64) { - f, _, d, _ := g.AStarM(w, start, end, h) - return f.PathTo(end, nil), d -} - -// implement container/heap -func (h openHeap) Len() int { return len(h) } -func (h openHeap) Less(i, j int) bool { return h[i].f < h[j].f } -func (h openHeap) Swap(i, j int) { - h[i], h[j] = h[j], h[i] - h[i].fx = i - h[j].fx = j -} -func (p *openHeap) Push(x interface{}) { - h := *p - fx := len(h) - h = append(h, x.(*rNode)) - h[fx].fx = fx - *p = h -} - -func (p *openHeap) Pop() interface{} { - h := *p - last := len(h) - 1 - *p = h[:last] - h[last].fx = -1 - return h[last] -} - -// BellmanFord finds shortest paths from a start node in a weighted directed -// graph using the Bellman-Ford-Moore algorithm. -// -// WeightFunc w must translate arc labels to arc weights. -// Negative arc weights are allowed but not negative cycles. -// Loops and parallel arcs are allowed. -// -// If the algorithm completes without encountering a negative cycle the method -// returns shortest paths encoded in a FromList, path distances indexed by -// node, and return value end = -1. -// -// If it encounters a negative cycle reachable from start it returns end >= 0. -// In this case the cycle can be obtained by calling f.BellmanFordCycle(end). -// -// Negative cycles are only detected when reachable from start. A negative -// cycle not reachable from start will not prevent the algorithm from finding -// shortest paths from start. -// -// See also NegativeCycle to find a cycle anywhere in the graph, and see -// HasNegativeCycle for lighter-weight negative cycle detection, -func (g LabeledDirected) BellmanFord(w WeightFunc, start NI) (f FromList, dist []float64, end NI) { - a := g.LabeledAdjacencyList - f = NewFromList(len(a)) - dist = make([]float64, len(a)) - inf := math.Inf(1) - for i := range dist { - dist[i] = inf - } - rp := f.Paths - rp[start] = PathEnd{Len: 1, From: -1} - dist[start] = 0 - for _ = range a[1:] { - imp := false - for from, nbs := range a { - fp := &rp[from] - d1 := dist[from] - for _, nb := range nbs { - d2 := d1 + w(nb.Label) - to := &rp[nb.To] - // TODO improve to break ties - if fp.Len > 0 && d2 < dist[nb.To] { - *to = PathEnd{From: NI(from), Len: fp.Len + 1} - dist[nb.To] = d2 - imp = true - } - } - } - if !imp { - break - } - } - for from, nbs := range a { - d1 := dist[from] - for _, nb := range nbs { - if d1+w(nb.Label) < dist[nb.To] { - // return nb as end of a path with negative cycle at root - return f, dist, NI(from) - } - } - } - return f, dist, -1 -} - -// BellmanFordCycle decodes a negative cycle detected by BellmanFord. -// -// Receiver f and argument end must be results returned from BellmanFord. -func (f FromList) BellmanFordCycle(end NI) (c []NI) { - p := f.Paths - var b Bits - for b.Bit(end) == 0 { - b.SetBit(end, 1) - end = p[end].From - } - for b.Bit(end) == 1 { - c = append(c, end) - b.SetBit(end, 0) - end = p[end].From - } - for i, j := 0, len(c)-1; i < j; i, j = i+1, j-1 { - c[i], c[j] = c[j], c[i] - } - return -} - -// HasNegativeCycle returns true if the graph contains any negative cycle. -// -// HasNegativeCycle uses a Bellman-Ford-like algorithm, but finds negative -// cycles anywhere in the graph. Also path information is not computed, -// reducing memory use somewhat compared to BellmanFord. -// -// See also NegativeCycle to obtain the cycle, and see BellmanFord for -// single source shortest path searches. -func (g LabeledDirected) HasNegativeCycle(w WeightFunc) bool { - a := g.LabeledAdjacencyList - dist := make([]float64, len(a)) - for _ = range a[1:] { - imp := false - for from, nbs := range a { - d1 := dist[from] - for _, nb := range nbs { - d2 := d1 + w(nb.Label) - if d2 < dist[nb.To] { - dist[nb.To] = d2 - imp = true - } - } - } - if !imp { - break - } - } - for from, nbs := range a { - d1 := dist[from] - for _, nb := range nbs { - if d1+w(nb.Label) < dist[nb.To] { - return true // negative cycle - } - } - } - return false -} - -// NegativeCycle finds a negative cycle if one exists. -// -// NegativeCycle uses a Bellman-Ford-like algorithm, but finds negative -// cycles anywhere in the graph. If a negative cycle exists, one will be -// returned. The result is nil if no negative cycle exists. -// -// See also HasNegativeCycle for lighter-weight cycle detection, and see -// BellmanFord for single source shortest paths. -func (g LabeledDirected) NegativeCycle(w WeightFunc) (c []NI) { - a := g.LabeledAdjacencyList - f := NewFromList(len(a)) - p := f.Paths - for n := range p { - p[n] = PathEnd{From: -1, Len: 1} - } - dist := make([]float64, len(a)) - for _ = range a { - imp := false - for from, nbs := range a { - fp := &p[from] - d1 := dist[from] - for _, nb := range nbs { - d2 := d1 + w(nb.Label) - to := &p[nb.To] - if fp.Len > 0 && d2 < dist[nb.To] { - *to = PathEnd{From: NI(from), Len: fp.Len + 1} - dist[nb.To] = d2 - imp = true - } - } - } - if !imp { - return nil - } - } - var vis Bits -a: - for n := range a { - end := NI(n) - var b Bits - for b.Bit(end) == 0 { - if vis.Bit(end) == 1 { - continue a - } - vis.SetBit(end, 1) - b.SetBit(end, 1) - end = p[end].From - if end < 0 { - continue a - } - } - for b.Bit(end) == 1 { - c = append(c, end) - b.SetBit(end, 0) - end = p[end].From - } - for i, j := 0, len(c)-1; i < j; i, j = i+1, j-1 { - c[i], c[j] = c[j], c[i] - } - return c - } - return nil // no negative cycle -} - -// A NodeVisitor is an argument to some graph traversal methods. -// -// Graph traversal methods call the visitor function for each node visited. -// Argument n is the node being visited. -type NodeVisitor func(n NI) - -// An OkNodeVisitor function is an argument to some graph traversal methods. -// -// Graph traversal methods call the visitor function for each node visited. -// The argument n is the node being visited. If the visitor function -// returns true, the traversal will continue. If the visitor function -// returns false, the traversal will terminate immediately. -type OkNodeVisitor func(n NI) (ok bool) - -// BreadthFirst2 traverses a graph breadth first using a direction -// optimizing algorithm. -// -// The code is experimental and currently seems no faster than the -// conventional breadth first code. -// -// Use AdjacencyList.BreadthFirst instead. -func BreadthFirst2(g, tr AdjacencyList, ma int, start NI, f *FromList, v OkNodeVisitor) int { - if tr == nil { - var d Directed - d, ma = Directed{g}.Transpose() - tr = d.AdjacencyList - } - switch { - case f == nil: - e := NewFromList(len(g)) - f = &e - case f.Paths == nil: - *f = NewFromList(len(g)) - } - if ma <= 0 { - ma = g.ArcSize() - } - rp := f.Paths - level := 1 - rp[start] = PathEnd{Len: level, From: -1} - if !v(start) { - f.MaxLen = level - return -1 - } - nReached := 1 // accumulated for a return value - // the frontier consists of nodes all at the same level - frontier := []NI{start} - mf := len(g[start]) // number of arcs leading out from frontier - ctb := ma / 10 // threshold change from top-down to bottom-up - k14 := 14 * ma / len(g) // 14 * mean degree - cbt := len(g) / k14 // threshold change from bottom-up to top-down - // var fBits, nextb big.Int - fBits := make([]bool, len(g)) - nextb := make([]bool, len(g)) - zBits := make([]bool, len(g)) - for { - // top down step - level++ - var next []NI - for _, n := range frontier { - for _, nb := range g[n] { - if rp[nb].Len == 0 { - rp[nb] = PathEnd{From: n, Len: level} - if !v(nb) { - f.MaxLen = level - return -1 - } - next = append(next, nb) - nReached++ - } - } - } - if len(next) == 0 { - break - } - frontier = next - if mf > ctb { - // switch to bottom up! - } else { - // stick with top down - continue - } - // convert frontier representation - nf := 0 // number of vertices on the frontier - for _, n := range frontier { - // fBits.SetBit(&fBits, n, 1) - fBits[n] = true - nf++ - } - bottomUpLoop: - level++ - nNext := 0 - for n := range tr { - if rp[n].Len == 0 { - for _, nb := range tr[n] { - // if fBits.Bit(nb) == 1 { - if fBits[nb] { - rp[n] = PathEnd{From: nb, Len: level} - if !v(nb) { - f.MaxLen = level - return -1 - } - // nextb.SetBit(&nextb, n, 1) - nextb[n] = true - nReached++ - nNext++ - break - } - } - } - } - if nNext == 0 { - break - } - fBits, nextb = nextb, fBits - // nextb.SetInt64(0) - copy(nextb, zBits) - nf = nNext - if nf < cbt { - // switch back to top down! - } else { - // stick with bottom up - goto bottomUpLoop - } - // convert frontier representation - mf = 0 - frontier = frontier[:0] - for n := range g { - // if fBits.Bit(n) == 1 { - if fBits[n] { - frontier = append(frontier, NI(n)) - mf += len(g[n]) - fBits[n] = false - } - } - // fBits.SetInt64(0) - } - f.MaxLen = level - 1 - return nReached -} - -// DAGMinDistPath finds a single shortest path. -// -// Shortest means minimum sum of arc weights. -// -// Returned is the path and distance as returned by FromList.PathTo. -// -// This is a convenience method. See DAGOptimalPaths for more options. -func (g LabeledDirected) DAGMinDistPath(start, end NI, w WeightFunc) ([]NI, float64, error) { - return g.dagPath(start, end, w, false) -} - -// DAGMaxDistPath finds a single longest path. -// -// Longest means maximum sum of arc weights. -// -// Returned is the path and distance as returned by FromList.PathTo. -// -// This is a convenience method. See DAGOptimalPaths for more options. -func (g LabeledDirected) DAGMaxDistPath(start, end NI, w WeightFunc) ([]NI, float64, error) { - return g.dagPath(start, end, w, true) -} - -func (g LabeledDirected) dagPath(start, end NI, w WeightFunc, longest bool) ([]NI, float64, error) { - o, _ := g.Topological() - if o == nil { - return nil, 0, fmt.Errorf("not a DAG") - } - f, dist, _ := g.DAGOptimalPaths(start, end, o, w, longest) - if f.Paths[end].Len == 0 { - return nil, 0, fmt.Errorf("no path from %d to %d", start, end) - } - return f.PathTo(end, nil), dist[end], nil -} - -// DAGOptimalPaths finds either longest or shortest distance paths in a -// directed acyclic graph. -// -// Path distance is the sum of arc weights on the path. -// Negative arc weights are allowed. -// Where multiple paths exist with the same distance, the path length -// (number of nodes) is used as a tie breaker. -// -// Receiver g must be a directed acyclic graph. Argument o must be either nil -// or a topological ordering of g. If nil, a topologcal ordering is -// computed internally. If longest is true, an optimal path is a longest -// distance path. Otherwise it is a shortest distance path. -// -// Argument start is the start node for paths, end is the end node. If end -// is a valid node number, the method returns as soon as the optimal path -// to end is found. If end is -1, all optimal paths from start are found. -// -// Paths and path distances are encoded in the returned FromList and dist -// slice. The number of nodes reached is returned as nReached. -func (g LabeledDirected) DAGOptimalPaths(start, end NI, ordering []NI, w WeightFunc, longest bool) (f FromList, dist []float64, nReached int) { - a := g.LabeledAdjacencyList - f = NewFromList(len(a)) - dist = make([]float64, len(a)) - if ordering == nil { - ordering, _ = g.Topological() - } - // search ordering for start - o := 0 - for ordering[o] != start { - o++ - } - var fBetter func(cand, ext float64) bool - var iBetter func(cand, ext int) bool - if longest { - fBetter = func(cand, ext float64) bool { return cand > ext } - iBetter = func(cand, ext int) bool { return cand > ext } - } else { - fBetter = func(cand, ext float64) bool { return cand < ext } - iBetter = func(cand, ext int) bool { return cand < ext } - } - p := f.Paths - p[start] = PathEnd{From: -1, Len: 1} - f.MaxLen = 1 - leaves := &f.Leaves - leaves.SetBit(start, 1) - nReached = 1 - for n := start; n != end; n = ordering[o] { - if p[n].Len > 0 && len(a[n]) > 0 { - nDist := dist[n] - candLen := p[n].Len + 1 // len for any candidate arc followed from n - for _, to := range a[n] { - leaves.SetBit(to.To, 1) - candDist := nDist + w(to.Label) - switch { - case p[to.To].Len == 0: // first path to node to.To - nReached++ - case fBetter(candDist, dist[to.To]): // better distance - case candDist == dist[to.To] && iBetter(candLen, p[to.To].Len): // same distance but better path length - default: - continue - } - dist[to.To] = candDist - p[to.To] = PathEnd{From: n, Len: candLen} - if candLen > f.MaxLen { - f.MaxLen = candLen - } - } - leaves.SetBit(n, 0) - } - o++ - if o == len(ordering) { - break - } - } - return -} - -// Dijkstra finds shortest paths by Dijkstra's algorithm. -// -// Shortest means shortest distance where distance is the -// sum of arc weights. Where multiple paths exist with the same distance, -// a path with the minimum number of nodes is returned. -// -// As usual for Dijkstra's algorithm, arc weights must be non-negative. -// Graphs may be directed or undirected. Loops and parallel arcs are -// allowed. -func (g LabeledAdjacencyList) Dijkstra(start, end NI, w WeightFunc) (f FromList, dist []float64, reached int) { - r := make([]tentResult, len(g)) - for i := range r { - r[i].nx = NI(i) - } - f = NewFromList(len(g)) - dist = make([]float64, len(g)) - current := start - rp := f.Paths - rp[current] = PathEnd{Len: 1, From: -1} // path length at start is 1 node - cr := &r[current] - cr.dist = 0 // distance at start is 0. - cr.done = true // mark start done. it skips the heap. - nDone := 1 // accumulated for a return value - var t tent - for current != end { - nextLen := rp[current].Len + 1 - for _, nb := range g[current] { - // d.arcVis++ - hr := &r[nb.To] - if hr.done { - continue // skip nodes already done - } - dist := cr.dist + w(nb.Label) - vl := rp[nb.To].Len - visited := vl > 0 - if visited { - if dist > hr.dist { - continue // distance is worse - } - // tie breaker is a nice touch and doesn't seem to - // impact performance much. - if dist == hr.dist && nextLen >= vl { - continue // distance same, but number of nodes is no better - } - } - // the path through current to this node is shortest so far. - // record new path data for this node and update tentative set. - hr.dist = dist - rp[nb.To].Len = nextLen - rp[nb.To].From = current - if visited { - heap.Fix(&t, hr.fx) - } else { - heap.Push(&t, hr) - } - } - //d.ndVis++ - if len(t) == 0 { - return f, dist, nDone // no more reachable nodes. AllPaths normal return - } - // new current is node with smallest tentative distance - cr = heap.Pop(&t).(*tentResult) - cr.done = true - nDone++ - current = cr.nx - dist[current] = cr.dist // store final distance - } - // normal return for single shortest path search - return f, dist, -1 -} - -// DijkstraPath finds a single shortest path. -// -// Returned is the path and distance as returned by FromList.PathTo. -func (g LabeledAdjacencyList) DijkstraPath(start, end NI, w WeightFunc) ([]NI, float64) { - f, dist, _ := g.Dijkstra(start, end, w) - return f.PathTo(end, nil), dist[end] -} - -// tent implements container/heap -func (t tent) Len() int { return len(t) } -func (t tent) Less(i, j int) bool { return t[i].dist < t[j].dist } -func (t tent) Swap(i, j int) { - t[i], t[j] = t[j], t[i] - t[i].fx = i - t[j].fx = j -} -func (s *tent) Push(x interface{}) { - nd := x.(*tentResult) - nd.fx = len(*s) - *s = append(*s, nd) -} -func (s *tent) Pop() interface{} { - t := *s - last := len(t) - 1 - *s = t[:last] - return t[last] -} - -type tentResult struct { - dist float64 // tentative distance, sum of arc weights - nx NI // slice index, "node id" - fx int // heap.Fix index - done bool -} - -type tent []*tentResult diff --git a/vendor/github.com/soniakeys/graph/travis.sh b/vendor/github.com/soniakeys/graph/travis.sh deleted file mode 100644 index 5a8030a..0000000 --- a/vendor/github.com/soniakeys/graph/travis.sh +++ /dev/null @@ -1,11 +0,0 @@ -#!/bin/bash -set -ex -go test ./... -if [ "$TRAVIS_GO_VERSION" = "1.6" ]; then - GOARCH=386 go test ./... - go tool vet -example . - go get github.com/client9/misspell/cmd/misspell - go get github.com/soniakeys/vetc - misspell -error * */* */*/* - vetc -fi diff --git a/vendor/github.com/soniakeys/graph/undir.go b/vendor/github.com/soniakeys/graph/undir.go deleted file mode 100644 index 75a7f24..0000000 --- a/vendor/github.com/soniakeys/graph/undir.go +++ /dev/null @@ -1,321 +0,0 @@ -// 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 - } - } -} diff --git a/vendor/github.com/soniakeys/graph/undir_RO.go b/vendor/github.com/soniakeys/graph/undir_RO.go deleted file mode 100644 index fd8e377..0000000 --- a/vendor/github.com/soniakeys/graph/undir_RO.go +++ /dev/null @@ -1,659 +0,0 @@ -// Copyright 2014 Sonia Keys -// License MIT: http://opensource.org/licenses/MIT - -package graph - -// undir_RO.go is code generated from undir_cg.go by directives in graph.go. -// Editing undir_cg.go is okay. It is the code generation source. -// DO NOT EDIT undir_RO.go. -// The RO means read only and it is upper case RO to slow you down a bit -// in case you start to edit the file. - -// Bipartite determines if a connected component of an undirected graph -// is bipartite, a component where nodes can be partitioned into two sets -// such that every edge in the component goes from one set to the other. -// -// Argument n can be any representative node of the component. -// -// If the component is bipartite, Bipartite returns true and a two-coloring -// of the component. Each color set is returned as a bitmap. If the component -// is not bipartite, Bipartite returns false and a representative odd cycle. -// -// There are equivalent labeled and unlabeled versions of this method. -func (g Undirected) Bipartite(n NI) (b bool, c1, c2 Bits, oc []NI) { - b = true - var open bool - var df func(n NI, c1, c2 *Bits) - df = func(n NI, c1, c2 *Bits) { - c1.SetBit(n, 1) - for _, nb := range g.AdjacencyList[n] { - if c1.Bit(nb) == 1 { - b = false - oc = []NI{nb, n} - open = true - return - } - if c2.Bit(nb) == 1 { - continue - } - df(nb, c2, c1) - if b { - continue - } - switch { - case !open: - case n == oc[0]: - open = false - default: - oc = append(oc, n) - } - return - } - } - df(n, &c1, &c2) - if b { - return b, c1, c2, nil - } - return b, Bits{}, Bits{}, oc -} - -// BronKerbosch1 finds maximal cliques in an undirected graph. -// -// The graph must not contain parallel edges or loops. -// -// See https://en.wikipedia.org/wiki/Clique_(graph_theory) and -// https://en.wikipedia.org/wiki/Bron%E2%80%93Kerbosch_algorithm for background. -// -// This method implements the BronKerbosch1 algorithm of WP; that is, -// the original algorithm without improvements. -// -// The method calls the emit argument for each maximal clique in g, as long -// as emit returns true. If emit returns false, BronKerbosch1 returns -// immediately. -// -// There are equivalent labeled and unlabeled versions of this method. -// -// See also more sophisticated variants BronKerbosch2 and BronKerbosch3. -func (g Undirected) BronKerbosch1(emit func([]NI) bool) { - a := g.AdjacencyList - var f func(R, P, X *Bits) bool - f = func(R, P, X *Bits) bool { - switch { - case !P.Zero(): - var r2, p2, x2 Bits - pf := func(n NI) bool { - r2.Set(*R) - r2.SetBit(n, 1) - p2.Clear() - x2.Clear() - for _, to := range a[n] { - if P.Bit(to) == 1 { - p2.SetBit(to, 1) - } - if X.Bit(to) == 1 { - x2.SetBit(to, 1) - } - } - if !f(&r2, &p2, &x2) { - return false - } - P.SetBit(n, 0) - X.SetBit(n, 1) - return true - } - if !P.Iterate(pf) { - return false - } - case X.Zero(): - return emit(R.Slice()) - } - return true - } - var R, P, X Bits - P.SetAll(len(a)) - f(&R, &P, &X) -} - -// BKPivotMaxDegree is a strategy for BronKerbosch methods. -// -// To use it, take the method value (see golang.org/ref/spec#Method_values) -// and pass it as the argument to BronKerbosch2 or 3. -// -// The strategy is to pick the node from P or X with the maximum degree -// (number of edges) in g. Note this is a shortcut from evaluating degrees -// in P. -// -// There are equivalent labeled and unlabeled versions of this method. -func (g Undirected) BKPivotMaxDegree(P, X *Bits) (p NI) { - // choose pivot u as highest degree node from P or X - a := g.AdjacencyList - maxDeg := -1 - P.Iterate(func(n NI) bool { // scan P - if d := len(a[n]); d > maxDeg { - p = n - maxDeg = d - } - return true - }) - X.Iterate(func(n NI) bool { // scan X - if d := len(a[n]); d > maxDeg { - p = n - maxDeg = d - } - return true - }) - return -} - -// BKPivotMinP is a strategy for BronKerbosch methods. -// -// To use it, take the method value (see golang.org/ref/spec#Method_values) -// and pass it as the argument to BronKerbosch2 or 3. -// -// The strategy is to simply pick the first node in P. -// -// There are equivalent labeled and unlabeled versions of this method. -func (g Undirected) BKPivotMinP(P, X *Bits) NI { - return P.From(0) -} - -// BronKerbosch2 finds maximal cliques in an undirected graph. -// -// The graph must not contain parallel edges or loops. -// -// See https://en.wikipedia.org/wiki/Clique_(graph_theory) and -// https://en.wikipedia.org/wiki/Bron%E2%80%93Kerbosch_algorithm for background. -// -// This method implements the BronKerbosch2 algorithm of WP; that is, -// the original algorithm plus pivoting. -// -// The argument is a pivot function that must return a node of P or X. -// P is guaranteed to contain at least one node. X is not. -// For example see BKPivotMaxDegree. -// -// The method calls the emit argument for each maximal clique in g, as long -// as emit returns true. If emit returns false, BronKerbosch1 returns -// immediately. -// -// There are equivalent labeled and unlabeled versions of this method. -// -// See also simpler variant BronKerbosch1 and more sophisticated variant -// BronKerbosch3. -func (g Undirected) BronKerbosch2(pivot func(P, X *Bits) NI, emit func([]NI) bool) { - a := g.AdjacencyList - var f func(R, P, X *Bits) bool - f = func(R, P, X *Bits) bool { - switch { - case !P.Zero(): - var r2, p2, x2, pnu Bits - // compute P \ N(u). next 5 lines are only difference from BK1 - pnu.Set(*P) - for _, to := range a[pivot(P, X)] { - pnu.SetBit(to, 0) - } - // remaining code like BK1 - pf := func(n NI) bool { - r2.Set(*R) - r2.SetBit(n, 1) - p2.Clear() - x2.Clear() - for _, to := range a[n] { - if P.Bit(to) == 1 { - p2.SetBit(to, 1) - } - if X.Bit(to) == 1 { - x2.SetBit(to, 1) - } - } - if !f(&r2, &p2, &x2) { - return false - } - P.SetBit(n, 0) - X.SetBit(n, 1) - return true - } - if !pnu.Iterate(pf) { - return false - } - case X.Zero(): - return emit(R.Slice()) - } - return true - } - var R, P, X Bits - P.SetAll(len(a)) - f(&R, &P, &X) -} - -// BronKerbosch3 finds maximal cliques in an undirected graph. -// -// The graph must not contain parallel edges or loops. -// -// See https://en.wikipedia.org/wiki/Clique_(graph_theory) and -// https://en.wikipedia.org/wiki/Bron%E2%80%93Kerbosch_algorithm for background. -// -// This method implements the BronKerbosch3 algorithm of WP; that is, -// the original algorithm with pivoting and degeneracy ordering. -// -// The argument is a pivot function that must return a node of P or X. -// P is guaranteed to contain at least one node. X is not. -// For example see BKPivotMaxDegree. -// -// The method calls the emit argument for each maximal clique in g, as long -// as emit returns true. If emit returns false, BronKerbosch1 returns -// immediately. -// -// There are equivalent labeled and unlabeled versions of this method. -// -// See also simpler variants BronKerbosch1 and BronKerbosch2. -func (g Undirected) BronKerbosch3(pivot func(P, X *Bits) NI, emit func([]NI) bool) { - a := g.AdjacencyList - var f func(R, P, X *Bits) bool - f = func(R, P, X *Bits) bool { - switch { - case !P.Zero(): - var r2, p2, x2, pnu Bits - // compute P \ N(u). next lines are only difference from BK1 - pnu.Set(*P) - for _, to := range a[pivot(P, X)] { - pnu.SetBit(to, 0) - } - // remaining code like BK2 - pf := func(n NI) bool { - r2.Set(*R) - r2.SetBit(n, 1) - p2.Clear() - x2.Clear() - for _, to := range a[n] { - if P.Bit(to) == 1 { - p2.SetBit(to, 1) - } - if X.Bit(to) == 1 { - x2.SetBit(to, 1) - } - } - if !f(&r2, &p2, &x2) { - return false - } - P.SetBit(n, 0) - X.SetBit(n, 1) - return true - } - if !pnu.Iterate(pf) { - return false - } - case X.Zero(): - return emit(R.Slice()) - } - return true - } - var R, P, X Bits - P.SetAll(len(a)) - // code above same as BK2 - // code below new to BK3 - _, ord, _ := g.Degeneracy() - var p2, x2 Bits - for _, n := range ord { - R.SetBit(n, 1) - p2.Clear() - x2.Clear() - for _, to := range a[n] { - if P.Bit(to) == 1 { - p2.SetBit(to, 1) - } - if X.Bit(to) == 1 { - x2.SetBit(to, 1) - } - } - if !f(&R, &p2, &x2) { - return - } - R.SetBit(n, 0) - P.SetBit(n, 0) - X.SetBit(n, 1) - } -} - -// ConnectedComponentBits returns a function that iterates over connected -// components of g, returning a member bitmap for each. -// -// Each call of the returned function returns the order (number of nodes) -// and bits of a connected component. The returned function returns zeros -// after returning all connected components. -// -// There are equivalent labeled and unlabeled versions of this method. -// -// See also ConnectedComponentReps, which has lighter weight return values. -func (g Undirected) ConnectedComponentBits() func() (order int, bits Bits) { - a := g.AdjacencyList - var vg Bits // nodes visited in graph - var vc *Bits // nodes visited in current component - var nc int - var df func(NI) - df = func(n NI) { - vg.SetBit(n, 1) - vc.SetBit(n, 1) - nc++ - for _, nb := range a[n] { - if vg.Bit(nb) == 0 { - df(nb) - } - } - return - } - var n NI - return func() (o int, bits Bits) { - for ; n < NI(len(a)); n++ { - if vg.Bit(n) == 0 { - vc = &bits - nc = 0 - df(n) - return nc, bits - } - } - return - } -} - -// ConnectedComponentLists returns a function that iterates over connected -// components of g, returning the member list of each. -// -// Each call of the returned function returns a node list of a connected -// component. The returned function returns nil after returning all connected -// components. -// -// There are equivalent labeled and unlabeled versions of this method. -// -// See also ConnectedComponentReps, which has lighter weight return values. -func (g Undirected) ConnectedComponentLists() func() []NI { - a := g.AdjacencyList - var vg Bits // nodes visited in graph - var m []NI // members of current component - var df func(NI) - df = func(n NI) { - vg.SetBit(n, 1) - m = append(m, n) - for _, nb := range a[n] { - if vg.Bit(nb) == 0 { - df(nb) - } - } - return - } - var n NI - return func() []NI { - for ; n < NI(len(a)); n++ { - if vg.Bit(n) == 0 { - m = nil - df(n) - return m - } - } - return nil - } -} - -// ConnectedComponentReps returns a representative node from each connected -// component of g. -// -// Returned is a slice with a single representative node from each connected -// component and also a parallel slice with the order, or number of nodes, -// in the corresponding component. -// -// This is fairly minimal information describing connected components. -// From a representative node, other nodes in the component can be reached -// by depth first traversal for example. -// -// There are equivalent labeled and unlabeled versions of this method. -// -// See also ConnectedComponentBits and ConnectedComponentLists which can -// collect component members in a single traversal, and IsConnected which -// is an even simpler boolean test. -func (g Undirected) ConnectedComponentReps() (reps []NI, orders []int) { - a := g.AdjacencyList - var c Bits - var o int - var df func(NI) - df = func(n NI) { - c.SetBit(n, 1) - o++ - for _, nb := range a[n] { - if c.Bit(nb) == 0 { - df(nb) - } - } - return - } - for n := range a { - if c.Bit(NI(n)) == 0 { - reps = append(reps, NI(n)) - o = 0 - df(NI(n)) - orders = append(orders, o) - } - } - return -} - -// Copy makes a deep copy of g. -// Copy also computes the arc size ma, the number of arcs. -// -// There are equivalent labeled and unlabeled versions of this method. -func (g Undirected) Copy() (c Undirected, ma int) { - l, s := g.AdjacencyList.Copy() - return Undirected{l}, s -} - -// Degeneracy computes k-degeneracy, vertex ordering and k-cores. -// -// See Wikipedia https://en.wikipedia.org/wiki/Degeneracy_(graph_theory) -// -// There are equivalent labeled and unlabeled versions of this method. -func (g Undirected) Degeneracy() (k int, ordering []NI, cores []int) { - a := g.AdjacencyList - // WP algorithm - ordering = make([]NI, len(a)) - var L Bits - d := make([]int, len(a)) - var D [][]NI - for v, nb := range a { - dv := len(nb) - d[v] = dv - for len(D) <= dv { - D = append(D, nil) - } - D[dv] = append(D[dv], NI(v)) - } - for ox := range a { - // find a non-empty D - i := 0 - for len(D[i]) == 0 { - i++ - } - // k is max(i, k) - if i > k { - for len(cores) <= i { - cores = append(cores, 0) - } - cores[k] = ox - k = i - } - // select from D[i] - Di := D[i] - last := len(Di) - 1 - v := Di[last] - // Add v to ordering, remove from Di - ordering[ox] = v - L.SetBit(v, 1) - D[i] = Di[:last] - // move neighbors - for _, nb := range a[v] { - if L.Bit(nb) == 1 { - continue - } - dn := d[nb] // old number of neighbors of nb - Ddn := D[dn] // nb is in this list - // remove it from the list - for wx, w := range Ddn { - if w == nb { - last := len(Ddn) - 1 - Ddn[wx], Ddn[last] = Ddn[last], Ddn[wx] - D[dn] = Ddn[:last] - } - } - dn-- // new number of neighbors - d[nb] = dn - // re--add it to it's new list - D[dn] = append(D[dn], nb) - } - } - cores[k] = len(ordering) - return -} - -// Degree for undirected graphs, returns the degree of a node. -// -// The degree of a node in an undirected graph is the number of incident -// edges, where loops count twice. -// -// If g is known to be loop-free, the result is simply equivalent to len(g[n]). -// See handshaking lemma example at AdjacencyList.ArcSize. -// -// There are equivalent labeled and unlabeled versions of this method. -func (g Undirected) Degree(n NI) int { - to := g.AdjacencyList[n] - d := len(to) // just "out" degree, - for _, to := range to { - if to == n { - d++ // except loops count twice - } - } - return d -} - -// FromList constructs a FromList representing the tree reachable from -// the given root. -// -// The connected component containing root should represent a simple graph, -// connected as a tree. -// -// For nodes connected as a tree, the Path member of the returned FromList -// will be populated with both From and Len values. The MaxLen member will be -// set but Leaves will be left a zero value. Return value cycle will be -1. -// -// If the connected component containing root is not connected as a tree, -// a cycle will be detected. The returned FromList will be a zero value and -// return value cycle will be a node involved in the cycle. -// -// Loops and parallel edges will be detected as cycles, however only in the -// connected component containing root. If g is not fully connected, nodes -// not reachable from root will have PathEnd values of {From: -1, Len: 0}. -// -// There are equivalent labeled and unlabeled versions of this method. -func (g Undirected) FromList(root NI) (f FromList, cycle NI) { - p := make([]PathEnd, len(g.AdjacencyList)) - for i := range p { - p[i].From = -1 - } - ml := 0 - var df func(NI, NI) bool - df = func(fr, n NI) bool { - l := p[n].Len + 1 - for _, to := range g.AdjacencyList[n] { - if to == fr { - continue - } - if p[to].Len > 0 { - cycle = to - return false - } - p[to] = PathEnd{From: n, Len: l} - if l > ml { - ml = l - } - if !df(n, to) { - return false - } - } - return true - } - p[root].Len = 1 - if !df(-1, root) { - return - } - return FromList{Paths: p, MaxLen: ml}, -1 -} - -// IsConnected tests if an undirected graph is a single connected component. -// -// There are equivalent labeled and unlabeled versions of this method. -// -// See also ConnectedComponentReps for a method returning more information. -func (g Undirected) IsConnected() bool { - a := g.AdjacencyList - if len(a) == 0 { - return true - } - var b Bits - b.SetAll(len(a)) - var df func(NI) - df = func(n NI) { - b.SetBit(n, 0) - for _, to := range a[n] { - if b.Bit(to) == 1 { - df(to) - } - } - } - df(0) - return b.Zero() -} - -// IsTree identifies trees in undirected graphs. -// -// Return value isTree is true if the connected component reachable from root -// is a tree. Further, return value allTree is true if the entire graph g is -// connected. -// -// There are equivalent labeled and unlabeled versions of this method. -func (g Undirected) IsTree(root NI) (isTree, allTree bool) { - a := g.AdjacencyList - var v Bits - v.SetAll(len(a)) - var df func(NI, NI) bool - df = func(fr, n NI) bool { - if v.Bit(n) == 0 { - return false - } - v.SetBit(n, 0) - for _, to := range a[n] { - if to != fr && !df(n, to) { - return false - } - } - return true - } - v.SetBit(root, 0) - for _, to := range a[root] { - if !df(root, to) { - return false, false - } - } - return true, v.Zero() -} - -// Size returns the number of edges in g. -// -// See also ArcSize and HasLoop. -func (g Undirected) Size() int { - m2 := 0 - for fr, to := range g.AdjacencyList { - m2 += len(to) - for _, to := range to { - if to == NI(fr) { - m2++ - } - } - } - return m2 / 2 -} diff --git a/vendor/github.com/soniakeys/graph/undir_cg.go b/vendor/github.com/soniakeys/graph/undir_cg.go deleted file mode 100644 index 35b5b97..0000000 --- a/vendor/github.com/soniakeys/graph/undir_cg.go +++ /dev/null @@ -1,659 +0,0 @@ -// Copyright 2014 Sonia Keys -// License MIT: http://opensource.org/licenses/MIT - -package graph - -// undir_RO.go is code generated from undir_cg.go by directives in graph.go. -// Editing undir_cg.go is okay. It is the code generation source. -// DO NOT EDIT undir_RO.go. -// The RO means read only and it is upper case RO to slow you down a bit -// in case you start to edit the file. - -// Bipartite determines if a connected component of an undirected graph -// is bipartite, a component where nodes can be partitioned into two sets -// such that every edge in the component goes from one set to the other. -// -// Argument n can be any representative node of the component. -// -// If the component is bipartite, Bipartite returns true and a two-coloring -// of the component. Each color set is returned as a bitmap. If the component -// is not bipartite, Bipartite returns false and a representative odd cycle. -// -// There are equivalent labeled and unlabeled versions of this method. -func (g LabeledUndirected) Bipartite(n NI) (b bool, c1, c2 Bits, oc []NI) { - b = true - var open bool - var df func(n NI, c1, c2 *Bits) - df = func(n NI, c1, c2 *Bits) { - c1.SetBit(n, 1) - for _, nb := range g.LabeledAdjacencyList[n] { - if c1.Bit(nb.To) == 1 { - b = false - oc = []NI{nb.To, n} - open = true - return - } - if c2.Bit(nb.To) == 1 { - continue - } - df(nb.To, c2, c1) - if b { - continue - } - switch { - case !open: - case n == oc[0]: - open = false - default: - oc = append(oc, n) - } - return - } - } - df(n, &c1, &c2) - if b { - return b, c1, c2, nil - } - return b, Bits{}, Bits{}, oc -} - -// BronKerbosch1 finds maximal cliques in an undirected graph. -// -// The graph must not contain parallel edges or loops. -// -// See https://en.wikipedia.org/wiki/Clique_(graph_theory) and -// https://en.wikipedia.org/wiki/Bron%E2%80%93Kerbosch_algorithm for background. -// -// This method implements the BronKerbosch1 algorithm of WP; that is, -// the original algorithm without improvements. -// -// The method calls the emit argument for each maximal clique in g, as long -// as emit returns true. If emit returns false, BronKerbosch1 returns -// immediately. -// -// There are equivalent labeled and unlabeled versions of this method. -// -// See also more sophisticated variants BronKerbosch2 and BronKerbosch3. -func (g LabeledUndirected) BronKerbosch1(emit func([]NI) bool) { - a := g.LabeledAdjacencyList - var f func(R, P, X *Bits) bool - f = func(R, P, X *Bits) bool { - switch { - case !P.Zero(): - var r2, p2, x2 Bits - pf := func(n NI) bool { - r2.Set(*R) - r2.SetBit(n, 1) - p2.Clear() - x2.Clear() - for _, to := range a[n] { - if P.Bit(to.To) == 1 { - p2.SetBit(to.To, 1) - } - if X.Bit(to.To) == 1 { - x2.SetBit(to.To, 1) - } - } - if !f(&r2, &p2, &x2) { - return false - } - P.SetBit(n, 0) - X.SetBit(n, 1) - return true - } - if !P.Iterate(pf) { - return false - } - case X.Zero(): - return emit(R.Slice()) - } - return true - } - var R, P, X Bits - P.SetAll(len(a)) - f(&R, &P, &X) -} - -// BKPivotMaxDegree is a strategy for BronKerbosch methods. -// -// To use it, take the method value (see golang.org/ref/spec#Method_values) -// and pass it as the argument to BronKerbosch2 or 3. -// -// The strategy is to pick the node from P or X with the maximum degree -// (number of edges) in g. Note this is a shortcut from evaluating degrees -// in P. -// -// There are equivalent labeled and unlabeled versions of this method. -func (g LabeledUndirected) BKPivotMaxDegree(P, X *Bits) (p NI) { - // choose pivot u as highest degree node from P or X - a := g.LabeledAdjacencyList - maxDeg := -1 - P.Iterate(func(n NI) bool { // scan P - if d := len(a[n]); d > maxDeg { - p = n - maxDeg = d - } - return true - }) - X.Iterate(func(n NI) bool { // scan X - if d := len(a[n]); d > maxDeg { - p = n - maxDeg = d - } - return true - }) - return -} - -// BKPivotMinP is a strategy for BronKerbosch methods. -// -// To use it, take the method value (see golang.org/ref/spec#Method_values) -// and pass it as the argument to BronKerbosch2 or 3. -// -// The strategy is to simply pick the first node in P. -// -// There are equivalent labeled and unlabeled versions of this method. -func (g LabeledUndirected) BKPivotMinP(P, X *Bits) NI { - return P.From(0) -} - -// BronKerbosch2 finds maximal cliques in an undirected graph. -// -// The graph must not contain parallel edges or loops. -// -// See https://en.wikipedia.org/wiki/Clique_(graph_theory) and -// https://en.wikipedia.org/wiki/Bron%E2%80%93Kerbosch_algorithm for background. -// -// This method implements the BronKerbosch2 algorithm of WP; that is, -// the original algorithm plus pivoting. -// -// The argument is a pivot function that must return a node of P or X. -// P is guaranteed to contain at least one node. X is not. -// For example see BKPivotMaxDegree. -// -// The method calls the emit argument for each maximal clique in g, as long -// as emit returns true. If emit returns false, BronKerbosch1 returns -// immediately. -// -// There are equivalent labeled and unlabeled versions of this method. -// -// See also simpler variant BronKerbosch1 and more sophisticated variant -// BronKerbosch3. -func (g LabeledUndirected) BronKerbosch2(pivot func(P, X *Bits) NI, emit func([]NI) bool) { - a := g.LabeledAdjacencyList - var f func(R, P, X *Bits) bool - f = func(R, P, X *Bits) bool { - switch { - case !P.Zero(): - var r2, p2, x2, pnu Bits - // compute P \ N(u). next 5 lines are only difference from BK1 - pnu.Set(*P) - for _, to := range a[pivot(P, X)] { - pnu.SetBit(to.To, 0) - } - // remaining code like BK1 - pf := func(n NI) bool { - r2.Set(*R) - r2.SetBit(n, 1) - p2.Clear() - x2.Clear() - for _, to := range a[n] { - if P.Bit(to.To) == 1 { - p2.SetBit(to.To, 1) - } - if X.Bit(to.To) == 1 { - x2.SetBit(to.To, 1) - } - } - if !f(&r2, &p2, &x2) { - return false - } - P.SetBit(n, 0) - X.SetBit(n, 1) - return true - } - if !pnu.Iterate(pf) { - return false - } - case X.Zero(): - return emit(R.Slice()) - } - return true - } - var R, P, X Bits - P.SetAll(len(a)) - f(&R, &P, &X) -} - -// BronKerbosch3 finds maximal cliques in an undirected graph. -// -// The graph must not contain parallel edges or loops. -// -// See https://en.wikipedia.org/wiki/Clique_(graph_theory) and -// https://en.wikipedia.org/wiki/Bron%E2%80%93Kerbosch_algorithm for background. -// -// This method implements the BronKerbosch3 algorithm of WP; that is, -// the original algorithm with pivoting and degeneracy ordering. -// -// The argument is a pivot function that must return a node of P or X. -// P is guaranteed to contain at least one node. X is not. -// For example see BKPivotMaxDegree. -// -// The method calls the emit argument for each maximal clique in g, as long -// as emit returns true. If emit returns false, BronKerbosch1 returns -// immediately. -// -// There are equivalent labeled and unlabeled versions of this method. -// -// See also simpler variants BronKerbosch1 and BronKerbosch2. -func (g LabeledUndirected) BronKerbosch3(pivot func(P, X *Bits) NI, emit func([]NI) bool) { - a := g.LabeledAdjacencyList - var f func(R, P, X *Bits) bool - f = func(R, P, X *Bits) bool { - switch { - case !P.Zero(): - var r2, p2, x2, pnu Bits - // compute P \ N(u). next lines are only difference from BK1 - pnu.Set(*P) - for _, to := range a[pivot(P, X)] { - pnu.SetBit(to.To, 0) - } - // remaining code like BK2 - pf := func(n NI) bool { - r2.Set(*R) - r2.SetBit(n, 1) - p2.Clear() - x2.Clear() - for _, to := range a[n] { - if P.Bit(to.To) == 1 { - p2.SetBit(to.To, 1) - } - if X.Bit(to.To) == 1 { - x2.SetBit(to.To, 1) - } - } - if !f(&r2, &p2, &x2) { - return false - } - P.SetBit(n, 0) - X.SetBit(n, 1) - return true - } - if !pnu.Iterate(pf) { - return false - } - case X.Zero(): - return emit(R.Slice()) - } - return true - } - var R, P, X Bits - P.SetAll(len(a)) - // code above same as BK2 - // code below new to BK3 - _, ord, _ := g.Degeneracy() - var p2, x2 Bits - for _, n := range ord { - R.SetBit(n, 1) - p2.Clear() - x2.Clear() - for _, to := range a[n] { - if P.Bit(to.To) == 1 { - p2.SetBit(to.To, 1) - } - if X.Bit(to.To) == 1 { - x2.SetBit(to.To, 1) - } - } - if !f(&R, &p2, &x2) { - return - } - R.SetBit(n, 0) - P.SetBit(n, 0) - X.SetBit(n, 1) - } -} - -// ConnectedComponentBits returns a function that iterates over connected -// components of g, returning a member bitmap for each. -// -// Each call of the returned function returns the order (number of nodes) -// and bits of a connected component. The returned function returns zeros -// after returning all connected components. -// -// There are equivalent labeled and unlabeled versions of this method. -// -// See also ConnectedComponentReps, which has lighter weight return values. -func (g LabeledUndirected) ConnectedComponentBits() func() (order int, bits Bits) { - a := g.LabeledAdjacencyList - var vg Bits // nodes visited in graph - var vc *Bits // nodes visited in current component - var nc int - var df func(NI) - df = func(n NI) { - vg.SetBit(n, 1) - vc.SetBit(n, 1) - nc++ - for _, nb := range a[n] { - if vg.Bit(nb.To) == 0 { - df(nb.To) - } - } - return - } - var n NI - return func() (o int, bits Bits) { - for ; n < NI(len(a)); n++ { - if vg.Bit(n) == 0 { - vc = &bits - nc = 0 - df(n) - return nc, bits - } - } - return - } -} - -// ConnectedComponentLists returns a function that iterates over connected -// components of g, returning the member list of each. -// -// Each call of the returned function returns a node list of a connected -// component. The returned function returns nil after returning all connected -// components. -// -// There are equivalent labeled and unlabeled versions of this method. -// -// See also ConnectedComponentReps, which has lighter weight return values. -func (g LabeledUndirected) ConnectedComponentLists() func() []NI { - a := g.LabeledAdjacencyList - var vg Bits // nodes visited in graph - var m []NI // members of current component - var df func(NI) - df = func(n NI) { - vg.SetBit(n, 1) - m = append(m, n) - for _, nb := range a[n] { - if vg.Bit(nb.To) == 0 { - df(nb.To) - } - } - return - } - var n NI - return func() []NI { - for ; n < NI(len(a)); n++ { - if vg.Bit(n) == 0 { - m = nil - df(n) - return m - } - } - return nil - } -} - -// ConnectedComponentReps returns a representative node from each connected -// component of g. -// -// Returned is a slice with a single representative node from each connected -// component and also a parallel slice with the order, or number of nodes, -// in the corresponding component. -// -// This is fairly minimal information describing connected components. -// From a representative node, other nodes in the component can be reached -// by depth first traversal for example. -// -// There are equivalent labeled and unlabeled versions of this method. -// -// See also ConnectedComponentBits and ConnectedComponentLists which can -// collect component members in a single traversal, and IsConnected which -// is an even simpler boolean test. -func (g LabeledUndirected) ConnectedComponentReps() (reps []NI, orders []int) { - a := g.LabeledAdjacencyList - var c Bits - var o int - var df func(NI) - df = func(n NI) { - c.SetBit(n, 1) - o++ - for _, nb := range a[n] { - if c.Bit(nb.To) == 0 { - df(nb.To) - } - } - return - } - for n := range a { - if c.Bit(NI(n)) == 0 { - reps = append(reps, NI(n)) - o = 0 - df(NI(n)) - orders = append(orders, o) - } - } - return -} - -// Copy makes a deep copy of g. -// Copy also computes the arc size ma, the number of arcs. -// -// There are equivalent labeled and unlabeled versions of this method. -func (g LabeledUndirected) Copy() (c LabeledUndirected, ma int) { - l, s := g.LabeledAdjacencyList.Copy() - return LabeledUndirected{l}, s -} - -// Degeneracy computes k-degeneracy, vertex ordering and k-cores. -// -// See Wikipedia https://en.wikipedia.org/wiki/Degeneracy_(graph_theory) -// -// There are equivalent labeled and unlabeled versions of this method. -func (g LabeledUndirected) Degeneracy() (k int, ordering []NI, cores []int) { - a := g.LabeledAdjacencyList - // WP algorithm - ordering = make([]NI, len(a)) - var L Bits - d := make([]int, len(a)) - var D [][]NI - for v, nb := range a { - dv := len(nb) - d[v] = dv - for len(D) <= dv { - D = append(D, nil) - } - D[dv] = append(D[dv], NI(v)) - } - for ox := range a { - // find a non-empty D - i := 0 - for len(D[i]) == 0 { - i++ - } - // k is max(i, k) - if i > k { - for len(cores) <= i { - cores = append(cores, 0) - } - cores[k] = ox - k = i - } - // select from D[i] - Di := D[i] - last := len(Di) - 1 - v := Di[last] - // Add v to ordering, remove from Di - ordering[ox] = v - L.SetBit(v, 1) - D[i] = Di[:last] - // move neighbors - for _, nb := range a[v] { - if L.Bit(nb.To) == 1 { - continue - } - dn := d[nb.To] // old number of neighbors of nb - Ddn := D[dn] // nb is in this list - // remove it from the list - for wx, w := range Ddn { - if w == nb.To { - last := len(Ddn) - 1 - Ddn[wx], Ddn[last] = Ddn[last], Ddn[wx] - D[dn] = Ddn[:last] - } - } - dn-- // new number of neighbors - d[nb.To] = dn - // re--add it to it's new list - D[dn] = append(D[dn], nb.To) - } - } - cores[k] = len(ordering) - return -} - -// Degree for undirected graphs, returns the degree of a node. -// -// The degree of a node in an undirected graph is the number of incident -// edges, where loops count twice. -// -// If g is known to be loop-free, the result is simply equivalent to len(g[n]). -// See handshaking lemma example at AdjacencyList.ArcSize. -// -// There are equivalent labeled and unlabeled versions of this method. -func (g LabeledUndirected) Degree(n NI) int { - to := g.LabeledAdjacencyList[n] - d := len(to) // just "out" degree, - for _, to := range to { - if to.To == n { - d++ // except loops count twice - } - } - return d -} - -// FromList constructs a FromList representing the tree reachable from -// the given root. -// -// The connected component containing root should represent a simple graph, -// connected as a tree. -// -// For nodes connected as a tree, the Path member of the returned FromList -// will be populated with both From and Len values. The MaxLen member will be -// set but Leaves will be left a zero value. Return value cycle will be -1. -// -// If the connected component containing root is not connected as a tree, -// a cycle will be detected. The returned FromList will be a zero value and -// return value cycle will be a node involved in the cycle. -// -// Loops and parallel edges will be detected as cycles, however only in the -// connected component containing root. If g is not fully connected, nodes -// not reachable from root will have PathEnd values of {From: -1, Len: 0}. -// -// There are equivalent labeled and unlabeled versions of this method. -func (g LabeledUndirected) FromList(root NI) (f FromList, cycle NI) { - p := make([]PathEnd, len(g.LabeledAdjacencyList)) - for i := range p { - p[i].From = -1 - } - ml := 0 - var df func(NI, NI) bool - df = func(fr, n NI) bool { - l := p[n].Len + 1 - for _, to := range g.LabeledAdjacencyList[n] { - if to.To == fr { - continue - } - if p[to.To].Len > 0 { - cycle = to.To - return false - } - p[to.To] = PathEnd{From: n, Len: l} - if l > ml { - ml = l - } - if !df(n, to.To) { - return false - } - } - return true - } - p[root].Len = 1 - if !df(-1, root) { - return - } - return FromList{Paths: p, MaxLen: ml}, -1 -} - -// IsConnected tests if an undirected graph is a single connected component. -// -// There are equivalent labeled and unlabeled versions of this method. -// -// See also ConnectedComponentReps for a method returning more information. -func (g LabeledUndirected) IsConnected() bool { - a := g.LabeledAdjacencyList - if len(a) == 0 { - return true - } - var b Bits - b.SetAll(len(a)) - var df func(NI) - df = func(n NI) { - b.SetBit(n, 0) - for _, to := range a[n] { - if b.Bit(to.To) == 1 { - df(to.To) - } - } - } - df(0) - return b.Zero() -} - -// IsTree identifies trees in undirected graphs. -// -// Return value isTree is true if the connected component reachable from root -// is a tree. Further, return value allTree is true if the entire graph g is -// connected. -// -// There are equivalent labeled and unlabeled versions of this method. -func (g LabeledUndirected) IsTree(root NI) (isTree, allTree bool) { - a := g.LabeledAdjacencyList - var v Bits - v.SetAll(len(a)) - var df func(NI, NI) bool - df = func(fr, n NI) bool { - if v.Bit(n) == 0 { - return false - } - v.SetBit(n, 0) - for _, to := range a[n] { - if to.To != fr && !df(n, to.To) { - return false - } - } - return true - } - v.SetBit(root, 0) - for _, to := range a[root] { - if !df(root, to.To) { - return false, false - } - } - return true, v.Zero() -} - -// Size returns the number of edges in g. -// -// See also ArcSize and HasLoop. -func (g LabeledUndirected) Size() int { - m2 := 0 - for fr, to := range g.LabeledAdjacencyList { - m2 += len(to) - for _, to := range to { - if to.To == NI(fr) { - m2++ - } - } - } - return m2 / 2 -} |