diff options
Diffstat (limited to 'vendor/github.com/soniakeys/graph/adj_cg.go')
| -rw-r--r-- | vendor/github.com/soniakeys/graph/adj_cg.go | 387 |
1 files changed, 0 insertions, 387 deletions
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 -} -*/ |