"Fossies" - the Fresh Open Source Software Archive

Member "gdrive-2.1.1/vendor/github.com/soniakeys/graph/adj_RO.go" (28 May 2021, 10916 Bytes) of package /linux/misc/old/gdrive-2.1.1.tar.gz:


As a special service "Fossies" has tried to format the requested source page into HTML format using (guessed) Go source code syntax highlighting (style: standard) with prefixed line numbers and code folding option. Alternatively you can here view or download the uninterpreted source code file.

    1 // Copyright 2014 Sonia Keys
    2 // License MIT: http://opensource.org/licenses/MIT
    3 
    4 package graph
    5 
    6 // adj_RO.go is code generated from adj_cg.go by directives in graph.go.
    7 // Editing adj_cg.go is okay.
    8 // DO NOT EDIT adj_RO.go.  The RO is for Read Only.
    9 
   10 import (
   11     "math/rand"
   12     "time"
   13 )
   14 
   15 // ArcSize returns the number of arcs in g.
   16 //
   17 // Note that for an undirected graph without loops, the number of undirected
   18 // edges -- the traditional meaning of graph size -- will be ArcSize()/2.
   19 // On the other hand, if g is an undirected graph that has or may have loops,
   20 // g.ArcSize()/2 is not a meaningful quantity.
   21 //
   22 // There are equivalent labeled and unlabeled versions of this method.
   23 func (g AdjacencyList) ArcSize() int {
   24     m := 0
   25     for _, to := range g {
   26         m += len(to)
   27     }
   28     return m
   29 }
   30 
   31 // BoundsOk validates that all arcs in g stay within the slice bounds of g.
   32 //
   33 // BoundsOk returns true when no arcs point outside the bounds of g.
   34 // Otherwise it returns false and an example arc that points outside of g.
   35 //
   36 // Most methods of this package assume the BoundsOk condition and may
   37 // panic when they encounter an arc pointing outside of the graph.  This
   38 // function can be used to validate a graph when the BoundsOk condition
   39 // is unknown.
   40 //
   41 // There are equivalent labeled and unlabeled versions of this method.
   42 func (g AdjacencyList) BoundsOk() (ok bool, fr NI, to NI) {
   43     for fr, to := range g {
   44         for _, to := range to {
   45             if to < 0 || to >= NI(len(g)) {
   46                 return false, NI(fr), to
   47             }
   48         }
   49     }
   50     return true, -1, to
   51 }
   52 
   53 // BreadthFirst traverses a directed or undirected graph in breadth first order.
   54 //
   55 // Argument start is the start node for the traversal.  If r is nil, nodes are
   56 // visited in deterministic order.  If a random number generator is supplied,
   57 // nodes at each level are visited in random order.
   58 //
   59 // Argument f can be nil if you have no interest in the FromList path result.
   60 // If FromList f is non-nil, the method populates f.Paths and sets f.MaxLen.
   61 // It does not set f.Leaves.  For convenience argument f can be a zero value
   62 // FromList.  If f.Paths is nil, the FromList is initialized first.  If f.Paths
   63 // is non-nil however, the FromList is  used as is.  The method uses a value of
   64 // PathEnd.Len == 0 to indentify unvisited nodes.  Existing non-zero values
   65 // will limit the traversal.
   66 //
   67 // Traversal calls the visitor function v for each node starting with node
   68 // start.  If v returns true, traversal continues.  If v returns false, the
   69 // traversal terminates immediately.  PathEnd Len and From values are updated
   70 // before calling the visitor function.
   71 //
   72 // On return f.Paths and f.MaxLen are set but not f.Leaves.
   73 //
   74 // Returned is the number of nodes visited and ok = true if the traversal
   75 // ran to completion or ok = false if it was terminated by the visitor
   76 // function returning false.
   77 //
   78 // There are equivalent labeled and unlabeled versions of this method.
   79 func (g AdjacencyList) BreadthFirst(start NI, r *rand.Rand, f *FromList, v OkNodeVisitor) (visited int, ok bool) {
   80     switch {
   81     case f == nil:
   82         e := NewFromList(len(g))
   83         f = &e
   84     case f.Paths == nil:
   85         *f = NewFromList(len(g))
   86     }
   87     rp := f.Paths
   88     // the frontier consists of nodes all at the same level
   89     frontier := []NI{start}
   90     level := 1
   91     // assign path when node is put on frontier,
   92     rp[start] = PathEnd{Len: level, From: -1}
   93     for {
   94         f.MaxLen = level
   95         level++
   96         var next []NI
   97         if r == nil {
   98             for _, n := range frontier {
   99                 visited++
  100                 if !v(n) { // visit nodes as they come off frontier
  101                     return
  102                 }
  103                 for _, nb := range g[n] {
  104                     if rp[nb].Len == 0 {
  105                         next = append(next, nb)
  106                         rp[nb] = PathEnd{From: n, Len: level}
  107                     }
  108                 }
  109             }
  110         } else { // take nodes off frontier at random
  111             for _, i := range r.Perm(len(frontier)) {
  112                 n := frontier[i]
  113                 // remainder of block same as above
  114                 visited++
  115                 if !v(n) {
  116                     return
  117                 }
  118                 for _, nb := range g[n] {
  119                     if rp[nb].Len == 0 {
  120                         next = append(next, nb)
  121                         rp[nb] = PathEnd{From: n, Len: level}
  122                     }
  123                 }
  124             }
  125         }
  126         if len(next) == 0 {
  127             break
  128         }
  129         frontier = next
  130     }
  131     return visited, true
  132 }
  133 
  134 // BreadthFirstPath finds a single path from start to end with a minimum
  135 // number of nodes.
  136 //
  137 // Returned is the path as list of nodes.
  138 // The result is nil if no path was found.
  139 //
  140 // There are equivalent labeled and unlabeled versions of this method.
  141 func (g AdjacencyList) BreadthFirstPath(start, end NI) []NI {
  142     var f FromList
  143     g.BreadthFirst(start, nil, &f, func(n NI) bool { return n != end })
  144     return f.PathTo(end, nil)
  145 }
  146 
  147 // Copy makes a deep copy of g.
  148 // Copy also computes the arc size ma, the number of arcs.
  149 //
  150 // There are equivalent labeled and unlabeled versions of this method.
  151 func (g AdjacencyList) Copy() (c AdjacencyList, ma int) {
  152     c = make(AdjacencyList, len(g))
  153     for n, to := range g {
  154         c[n] = append([]NI{}, to...)
  155         ma += len(to)
  156     }
  157     return
  158 }
  159 
  160 // DepthFirst traverses a graph depth first.
  161 //
  162 // As it traverses it calls visitor function v for each node.  If v returns
  163 // false at any point, the traversal is terminated immediately and DepthFirst
  164 // returns false.  Otherwise DepthFirst returns true.
  165 //
  166 // DepthFirst uses argument bm is used as a bitmap to guide the traversal.
  167 // For a complete traversal, bm should be 0 initially.  During the
  168 // traversal, bits are set corresponding to each node visited.
  169 // The bit is set before calling the visitor function.
  170 //
  171 // Argument bm can be nil if you have no need for it.
  172 // In this case a bitmap is created internally for one-time use.
  173 //
  174 // Alternatively v can be nil.  In this case traversal still proceeds and
  175 // updates the bitmap, which can be a useful result.
  176 // DepthFirst always returns true in this case.
  177 //
  178 // It makes no sense for both bm and v to be nil.  In this case DepthFirst
  179 // returns false immediately.
  180 //
  181 // There are equivalent labeled and unlabeled versions of this method.
  182 func (g AdjacencyList) DepthFirst(start NI, bm *Bits, v OkNodeVisitor) (ok bool) {
  183     if bm == nil {
  184         if v == nil {
  185             return false
  186         }
  187         bm = &Bits{}
  188     }
  189     var df func(n NI) bool
  190     df = func(n NI) bool {
  191         if bm.Bit(n) == 1 {
  192             return true
  193         }
  194         bm.SetBit(n, 1)
  195         if v != nil && !v(n) {
  196             return false
  197         }
  198         for _, nb := range g[n] {
  199             if !df(nb) {
  200                 return false
  201             }
  202         }
  203         return true
  204     }
  205     return df(start)
  206 }
  207 
  208 // DepthFirstRandom traverses a graph depth first, but following arcs in
  209 // random order among arcs from a single node.
  210 //
  211 // If Rand r is nil, the method creates a new source and generator for
  212 // one-time use.
  213 //
  214 // Usage is otherwise like the DepthFirst method.  See DepthFirst.
  215 //
  216 // There are equivalent labeled and unlabeled versions of this method.
  217 func (g AdjacencyList) DepthFirstRandom(start NI, bm *Bits, v OkNodeVisitor, r *rand.Rand) (ok bool) {
  218     if bm == nil {
  219         if v == nil {
  220             return false
  221         }
  222         bm = &Bits{}
  223     }
  224     if r == nil {
  225         r = rand.New(rand.NewSource(time.Now().UnixNano()))
  226     }
  227     var df func(n NI) bool
  228     df = func(n NI) bool {
  229         if bm.Bit(n) == 1 {
  230             return true
  231         }
  232         bm.SetBit(n, 1)
  233         if v != nil && !v(n) {
  234             return false
  235         }
  236         to := g[n]
  237         for _, i := range r.Perm(len(to)) {
  238             if !df(to[i]) {
  239                 return false
  240             }
  241         }
  242         return true
  243     }
  244     return df(start)
  245 }
  246 
  247 // HasArc returns true if g has any arc from node fr to node to.
  248 //
  249 // Also returned is the index within the slice of arcs from node fr.
  250 // If no arc from fr to to is present, HasArc returns false, -1.
  251 //
  252 // There are equivalent labeled and unlabeled versions of this method.
  253 func (g AdjacencyList) HasArc(fr, to NI) (bool, int) {
  254     for x, h := range g[fr] {
  255         if h == to {
  256             return true, x
  257         }
  258     }
  259     return false, -1
  260 }
  261 
  262 // HasLoop identifies if a graph contains a loop, an arc that leads from a
  263 // a node back to the same node.
  264 //
  265 // If the graph has a loop, the result is an example node that has a loop.
  266 //
  267 // If g contains a loop, the method returns true and an example of a node
  268 // with a loop.  If there are no loops in g, the method returns false, -1.
  269 //
  270 // There are equivalent labeled and unlabeled versions of this method.
  271 func (g AdjacencyList) HasLoop() (bool, NI) {
  272     for fr, to := range g {
  273         for _, to := range to {
  274             if NI(fr) == to {
  275                 return true, to
  276             }
  277         }
  278     }
  279     return false, -1
  280 }
  281 
  282 // HasParallelMap identifies if a graph contains parallel arcs, multiple arcs
  283 // that lead from a node to the same node.
  284 //
  285 // If the graph has parallel arcs, the method returns true and
  286 // results fr and to represent an example where there are parallel arcs
  287 // from node fr to node to.
  288 //
  289 // If there are no parallel arcs, the method returns false, -1 -1.
  290 //
  291 // Multiple loops on a node count as parallel arcs.
  292 //
  293 // "Map" in the method name indicates that a Go map is used to detect parallel
  294 // arcs.  Compared to method HasParallelSort, this gives better asymtotic
  295 // performance for large dense graphs but may have increased overhead for
  296 // small or sparse graphs.
  297 //
  298 // There are equivalent labeled and unlabeled versions of this method.
  299 func (g AdjacencyList) HasParallelMap() (has bool, fr, to NI) {
  300     for n, to := range g {
  301         if len(to) == 0 {
  302             continue
  303         }
  304         m := map[NI]struct{}{}
  305         for _, to := range to {
  306             if _, ok := m[to]; ok {
  307                 return true, NI(n), to
  308             }
  309             m[to] = struct{}{}
  310         }
  311     }
  312     return false, -1, -1
  313 }
  314 
  315 // IsSimple checks for loops and parallel arcs.
  316 //
  317 // A graph is "simple" if it has no loops or parallel arcs.
  318 //
  319 // IsSimple returns true, -1 for simple graphs.  If a loop or parallel arc is
  320 // found, simple returns false and a node that represents a counterexample
  321 // to the graph being simple.
  322 //
  323 // See also separate methods HasLoop and HasParallel.
  324 //
  325 // There are equivalent labeled and unlabeled versions of this method.
  326 func (g AdjacencyList) IsSimple() (ok bool, n NI) {
  327     if lp, n := g.HasLoop(); lp {
  328         return false, n
  329     }
  330     if pa, n, _ := g.HasParallelSort(); pa {
  331         return false, n
  332     }
  333     return true, -1
  334 }
  335 
  336 // IsolatedNodes returns a bitmap of isolated nodes in receiver graph g.
  337 //
  338 // An isolated node is one with no arcs going to or from it.
  339 //
  340 // There are equivalent labeled and unlabeled versions of this method.
  341 func (g AdjacencyList) IsolatedNodes() (i Bits) {
  342     i.SetAll(len(g))
  343     for fr, to := range g {
  344         if len(to) > 0 {
  345             i.SetBit(NI(fr), 0)
  346             for _, to := range to {
  347                 i.SetBit(to, 0)
  348             }
  349         }
  350     }
  351     return
  352 }
  353 
  354 /*
  355 MaxmimalClique finds a maximal clique containing the node n.
  356 
  357 Not sure this is good for anything.  It produces a single maximal clique
  358 but there can be multiple maximal cliques containing a given node.
  359 This algorithm just returns one of them, not even necessarily the
  360 largest one.
  361 
  362 func (g LabeledAdjacencyList) MaximalClique(n int) []int {
  363     c := []int{n}
  364     var m bitset.BitSet
  365     m.Set(uint(n))
  366     for fr, to := range g {
  367         if fr == n {
  368             continue
  369         }
  370         if len(to) < len(c) {
  371             continue
  372         }
  373         f := 0
  374         for _, to := range to {
  375             if m.Test(uint(to.To)) {
  376                 f++
  377                 if f == len(c) {
  378                     c = append(c, to.To)
  379                     m.Set(uint(to.To))
  380                     break
  381                 }
  382             }
  383         }
  384     }
  385     return c
  386 }
  387 */