"Fossies" - the Fresh Open Source Software Archive

Member "gdrive-2.1.1/vendor/github.com/soniakeys/graph/dir_cg.go" (28 May 2021, 10847 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 // dir_RO.go is code generated from dir_cg.go by directives in graph.go.
    7 // Editing dir_cg.go is okay.  It is the code generation source.
    8 // DO NOT EDIT dir_RO.go.
    9 // The RO means read only and it is upper case RO to slow you down a bit
   10 // in case you start to edit the file.
   11 
   12 // Balanced returns true if for every node in g, in-degree equals out-degree.
   13 //
   14 // There are equivalent labeled and unlabeled versions of this method.
   15 func (g LabeledDirected) Balanced() bool {
   16     for n, in := range g.InDegree() {
   17         if in != len(g.LabeledAdjacencyList[n]) {
   18             return false
   19         }
   20     }
   21     return true
   22 }
   23 
   24 // Copy makes a deep copy of g.
   25 // Copy also computes the arc size ma, the number of arcs.
   26 //
   27 // There are equivalent labeled and unlabeled versions of this method.
   28 func (g LabeledDirected) Copy() (c LabeledDirected, ma int) {
   29     l, s := g.LabeledAdjacencyList.Copy()
   30     return LabeledDirected{l}, s
   31 }
   32 
   33 // Cyclic determines if g contains a cycle, a non-empty path from a node
   34 // back to itself.
   35 //
   36 // Cyclic returns true if g contains at least one cycle.  It also returns
   37 // an example of an arc involved in a cycle.
   38 // Cyclic returns false if g is acyclic.
   39 //
   40 // Also see Topological, which detects cycles.
   41 //
   42 // There are equivalent labeled and unlabeled versions of this method.
   43 func (g LabeledDirected) Cyclic() (cyclic bool, fr NI, to Half) {
   44     a := g.LabeledAdjacencyList
   45     fr, to.To = -1, -1
   46     var temp, perm Bits
   47     var df func(NI)
   48     df = func(n NI) {
   49         switch {
   50         case temp.Bit(n) == 1:
   51             cyclic = true
   52             return
   53         case perm.Bit(n) == 1:
   54             return
   55         }
   56         temp.SetBit(n, 1)
   57         for _, nb := range a[n] {
   58             df(nb.To)
   59             if cyclic {
   60                 if fr < 0 {
   61                     fr, to = n, nb
   62                 }
   63                 return
   64             }
   65         }
   66         temp.SetBit(n, 0)
   67         perm.SetBit(n, 1)
   68     }
   69     for n := range a {
   70         if perm.Bit(NI(n)) == 1 {
   71             continue
   72         }
   73         if df(NI(n)); cyclic { // short circuit as soon as a cycle is found
   74             break
   75         }
   76     }
   77     return
   78 }
   79 
   80 // FromList transposes a labeled graph into a FromList.
   81 //
   82 // Receiver g should be connected as a tree or forest.  Specifically no node
   83 // can have multiple incoming arcs.  If any node n in g has multiple incoming
   84 // arcs, the method returns (nil, n) where n is a node with multiple
   85 // incoming arcs.
   86 //
   87 // Otherwise (normally) the method populates the From members in a
   88 // FromList.Path and returns the FromList and -1.
   89 //
   90 // Other members of the FromList are left as zero values.
   91 // Use FromList.RecalcLen and FromList.RecalcLeaves as needed.
   92 //
   93 // Unusual cases are parallel arcs and loops.  A parallel arc represents
   94 // a case of multiple arcs going to some node and so will lead to a (nil, n)
   95 // return, even though a graph might be considered a multigraph tree.
   96 // A single loop on a node that would otherwise be a root node, though,
   97 // is not a case of multiple incoming arcs and so does not force a (nil, n)
   98 // result.
   99 //
  100 // There are equivalent labeled and unlabeled versions of this method.
  101 func (g LabeledDirected) FromList() (*FromList, NI) {
  102     paths := make([]PathEnd, len(g.LabeledAdjacencyList))
  103     for i := range paths {
  104         paths[i].From = -1
  105     }
  106     for fr, to := range g.LabeledAdjacencyList {
  107         for _, to := range to {
  108             if paths[to.To].From >= 0 {
  109                 return nil, to.To
  110             }
  111             paths[to.To].From = NI(fr)
  112         }
  113     }
  114     return &FromList{Paths: paths}, -1
  115 }
  116 
  117 // InDegree computes the in-degree of each node in g
  118 //
  119 // There are equivalent labeled and unlabeled versions of this method.
  120 func (g LabeledDirected) InDegree() []int {
  121     ind := make([]int, len(g.LabeledAdjacencyList))
  122     for _, nbs := range g.LabeledAdjacencyList {
  123         for _, nb := range nbs {
  124             ind[nb.To]++
  125         }
  126     }
  127     return ind
  128 }
  129 
  130 // IsTree identifies trees in directed graphs.
  131 //
  132 // Return value isTree is true if the subgraph reachable from root is a tree.
  133 // Further, return value allTree is true if the entire graph g is reachable
  134 // from root.
  135 //
  136 // There are equivalent labeled and unlabeled versions of this method.
  137 func (g LabeledDirected) IsTree(root NI) (isTree, allTree bool) {
  138     a := g.LabeledAdjacencyList
  139     var v Bits
  140     v.SetAll(len(a))
  141     var df func(NI) bool
  142     df = func(n NI) bool {
  143         if v.Bit(n) == 0 {
  144             return false
  145         }
  146         v.SetBit(n, 0)
  147         for _, to := range a[n] {
  148             if !df(to.To) {
  149                 return false
  150             }
  151         }
  152         return true
  153     }
  154     isTree = df(root)
  155     return isTree, isTree && v.Zero()
  156 }
  157 
  158 // Tarjan identifies strongly connected components in a directed graph using
  159 // Tarjan's algorithm.
  160 //
  161 // The method calls the emit argument for each component identified.  Each
  162 // component is a list of nodes.  A property of the algorithm is that
  163 // components are emitted in reverse topological order of the condensation.
  164 // (See https://en.wikipedia.org/wiki/Strongly_connected_component#Definitions
  165 // for description of condensation.)
  166 //
  167 // There are equivalent labeled and unlabeled versions of this method.
  168 //
  169 // See also TarjanForward and TarjanCondensation.
  170 func (g LabeledDirected) Tarjan(emit func([]NI) bool) {
  171     // See "Depth-first search and linear graph algorithms", Robert Tarjan,
  172     // SIAM J. Comput. Vol. 1, No. 2, June 1972.
  173     //
  174     // Implementation here from Wikipedia pseudocode,
  175     // http://en.wikipedia.org/w/index.php?title=Tarjan%27s_strongly_connected_components_algorithm&direction=prev&oldid=647184742
  176     var indexed, stacked Bits
  177     a := g.LabeledAdjacencyList
  178     index := make([]int, len(a))
  179     lowlink := make([]int, len(a))
  180     x := 0
  181     var S []NI
  182     var sc func(NI) bool
  183     sc = func(n NI) bool {
  184         index[n] = x
  185         indexed.SetBit(n, 1)
  186         lowlink[n] = x
  187         x++
  188         S = append(S, n)
  189         stacked.SetBit(n, 1)
  190         for _, nb := range a[n] {
  191             if indexed.Bit(nb.To) == 0 {
  192                 if !sc(nb.To) {
  193                     return false
  194                 }
  195                 if lowlink[nb.To] < lowlink[n] {
  196                     lowlink[n] = lowlink[nb.To]
  197                 }
  198             } else if stacked.Bit(nb.To) == 1 {
  199                 if index[nb.To] < lowlink[n] {
  200                     lowlink[n] = index[nb.To]
  201                 }
  202             }
  203         }
  204         if lowlink[n] == index[n] {
  205             var c []NI
  206             for {
  207                 last := len(S) - 1
  208                 w := S[last]
  209                 S = S[:last]
  210                 stacked.SetBit(w, 0)
  211                 c = append(c, w)
  212                 if w == n {
  213                     if !emit(c) {
  214                         return false
  215                     }
  216                     break
  217                 }
  218             }
  219         }
  220         return true
  221     }
  222     for n := range a {
  223         if indexed.Bit(NI(n)) == 0 && !sc(NI(n)) {
  224             return
  225         }
  226     }
  227 }
  228 
  229 // TarjanForward returns strongly connected components.
  230 //
  231 // It returns components in the reverse order of Tarjan, for situations
  232 // where a forward topological ordering is easier.
  233 func (g LabeledDirected) TarjanForward() [][]NI {
  234     var r [][]NI
  235     g.Tarjan(func(c []NI) bool {
  236         r = append(r, c)
  237         return true
  238     })
  239     scc := make([][]NI, len(r))
  240     last := len(r) - 1
  241     for i, ci := range r {
  242         scc[last-i] = ci
  243     }
  244     return scc
  245 }
  246 
  247 // TarjanCondensation returns strongly connected components and their
  248 // condensation graph.
  249 //
  250 // Components are ordered in a forward topological ordering.
  251 func (g LabeledDirected) TarjanCondensation() (scc [][]NI, cd AdjacencyList) {
  252     scc = g.TarjanForward()
  253     cd = make(AdjacencyList, len(scc))              // return value
  254     cond := make([]NI, len(g.LabeledAdjacencyList)) // mapping from g node to cd node
  255     for cn := NI(len(scc) - 1); cn >= 0; cn-- {
  256         c := scc[cn]
  257         for _, n := range c {
  258             cond[n] = NI(cn) // map g node to cd node
  259         }
  260         var tos []NI // list of 'to' nodes
  261         var m Bits   // tos map
  262         m.SetBit(cn, 1)
  263         for _, n := range c {
  264             for _, to := range g.LabeledAdjacencyList[n] {
  265                 if ct := cond[to.To]; m.Bit(ct) == 0 {
  266                     m.SetBit(ct, 1)
  267                     tos = append(tos, ct)
  268                 }
  269             }
  270         }
  271         cd[cn] = tos
  272     }
  273     return
  274 }
  275 
  276 // Topological computes a topological ordering of a directed acyclic graph.
  277 //
  278 // For an acyclic graph, return value ordering is a permutation of node numbers
  279 // in topologically sorted order and cycle will be nil.  If the graph is found
  280 // to be cyclic, ordering will be nil and cycle will be the path of a found
  281 // cycle.
  282 //
  283 // There are equivalent labeled and unlabeled versions of this method.
  284 func (g LabeledDirected) Topological() (ordering, cycle []NI) {
  285     a := g.LabeledAdjacencyList
  286     ordering = make([]NI, len(a))
  287     i := len(ordering)
  288     var temp, perm Bits
  289     var cycleFound bool
  290     var cycleStart NI
  291     var df func(NI)
  292     df = func(n NI) {
  293         switch {
  294         case temp.Bit(n) == 1:
  295             cycleFound = true
  296             cycleStart = n
  297             return
  298         case perm.Bit(n) == 1:
  299             return
  300         }
  301         temp.SetBit(n, 1)
  302         for _, nb := range a[n] {
  303             df(nb.To)
  304             if cycleFound {
  305                 if cycleStart >= 0 {
  306                     // a little hack: orderng won't be needed so repurpose the
  307                     // slice as cycle.  this is read out in reverse order
  308                     // as the recursion unwinds.
  309                     x := len(ordering) - 1 - len(cycle)
  310                     ordering[x] = n
  311                     cycle = ordering[x:]
  312                     if n == cycleStart {
  313                         cycleStart = -1
  314                     }
  315                 }
  316                 return
  317             }
  318         }
  319         temp.SetBit(n, 0)
  320         perm.SetBit(n, 1)
  321         i--
  322         ordering[i] = n
  323     }
  324     for n := range a {
  325         if perm.Bit(NI(n)) == 1 {
  326             continue
  327         }
  328         df(NI(n))
  329         if cycleFound {
  330             return nil, cycle
  331         }
  332     }
  333     return ordering, nil
  334 }
  335 
  336 // TopologicalKahn computes a topological ordering of a directed acyclic graph.
  337 //
  338 // For an acyclic graph, return value ordering is a permutation of node numbers
  339 // in topologically sorted order and cycle will be nil.  If the graph is found
  340 // to be cyclic, ordering will be nil and cycle will be the path of a found
  341 // cycle.
  342 //
  343 // This function is based on the algorithm by Arthur Kahn and requires the
  344 // transpose of g be passed as the argument.
  345 //
  346 // There are equivalent labeled and unlabeled versions of this method.
  347 func (g LabeledDirected) TopologicalKahn(tr Directed) (ordering, cycle []NI) {
  348     // code follows Wikipedia pseudocode.
  349     var L, S []NI
  350     // rem for "remaining edges," this function makes a local copy of the
  351     // in-degrees and consumes that instead of consuming an input.
  352     rem := make([]int, len(g.LabeledAdjacencyList))
  353     for n, fr := range tr.AdjacencyList {
  354         if len(fr) == 0 {
  355             // accumulate "set of all nodes with no incoming edges"
  356             S = append(S, NI(n))
  357         } else {
  358             // initialize rem from in-degree
  359             rem[n] = len(fr)
  360         }
  361     }
  362     for len(S) > 0 {
  363         last := len(S) - 1 // "remove a node n from S"
  364         n := S[last]
  365         S = S[:last]
  366         L = append(L, n) // "add n to tail of L"
  367         for _, m := range g.LabeledAdjacencyList[n] {
  368             // WP pseudo code reads "for each node m..." but it means for each
  369             // node m *remaining in the graph.*  We consume rem rather than
  370             // the graph, so "remaining in the graph" for us means rem[m] > 0.
  371             if rem[m.To] > 0 {
  372                 rem[m.To]--         // "remove edge from the graph"
  373                 if rem[m.To] == 0 { // if "m has no other incoming edges"
  374                     S = append(S, m.To) // "insert m into S"
  375                 }
  376             }
  377         }
  378     }
  379     // "If graph has edges," for us means a value in rem is > 0.
  380     for c, in := range rem {
  381         if in > 0 {
  382             // recover cyclic nodes
  383             for _, nb := range g.LabeledAdjacencyList[c] {
  384                 if rem[nb.To] > 0 {
  385                     cycle = append(cycle, NI(c))
  386                     break
  387                 }
  388             }
  389         }
  390     }
  391     if len(cycle) > 0 {
  392         return nil, cycle
  393     }
  394     return L, nil
  395 }