"Fossies" - the Fresh Open Source Software Archive

Member "gdrive-2.1.1/vendor/github.com/soniakeys/graph/adj.go" (28 May 2021, 9326 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: https://opensource.org/licenses/MIT
    3 
    4 package graph
    5 
    6 // adj.go contains methods on AdjacencyList and LabeledAdjacencyList.
    7 //
    8 // AdjacencyList methods are placed first and are alphabetized.
    9 // LabeledAdjacencyList methods follow, also alphabetized.
   10 // Only exported methods need be alphabetized; non-exported methods can
   11 // be left near their use.
   12 
   13 import (
   14     "math"
   15     "sort"
   16 )
   17 
   18 // HasParallelSort identifies if a graph contains parallel arcs, multiple arcs
   19 // that lead from a node to the same node.
   20 //
   21 // If the graph has parallel arcs, the results fr and to represent an example
   22 // where there are parallel arcs from node fr to node to.
   23 //
   24 // If there are no parallel arcs, the method returns false -1 -1.
   25 //
   26 // Multiple loops on a node count as parallel arcs.
   27 //
   28 // "Sort" in the method name indicates that sorting is used to detect parallel
   29 // arcs.  Compared to method HasParallelMap, this may give better performance
   30 // for small or sparse graphs but will have asymtotically worse performance for
   31 // large dense graphs.
   32 func (g AdjacencyList) HasParallelSort() (has bool, fr, to NI) {
   33     var t NodeList
   34     for n, to := range g {
   35         if len(to) == 0 {
   36             continue
   37         }
   38         // different code in the labeled version, so no code gen.
   39         t = append(t[:0], to...)
   40         sort.Sort(t)
   41         t0 := t[0]
   42         for _, to := range t[1:] {
   43             if to == t0 {
   44                 return true, NI(n), t0
   45             }
   46             t0 = to
   47         }
   48     }
   49     return false, -1, -1
   50 }
   51 
   52 // IsUndirected returns true if g represents an undirected graph.
   53 //
   54 // Returns true when all non-loop arcs are paired in reciprocal pairs.
   55 // Otherwise returns false and an example unpaired arc.
   56 func (g AdjacencyList) IsUndirected() (u bool, from, to NI) {
   57     // similar code in dot/writeUndirected
   58     unpaired := make(AdjacencyList, len(g))
   59     for fr, to := range g {
   60     arc: // for each arc in g
   61         for _, to := range to {
   62             if to == NI(fr) {
   63                 continue // loop
   64             }
   65             // search unpaired arcs
   66             ut := unpaired[to]
   67             for i, u := range ut {
   68                 if u == NI(fr) { // found reciprocal
   69                     last := len(ut) - 1
   70                     ut[i] = ut[last]
   71                     unpaired[to] = ut[:last]
   72                     continue arc
   73                 }
   74             }
   75             // reciprocal not found
   76             unpaired[fr] = append(unpaired[fr], to)
   77         }
   78     }
   79     for fr, to := range unpaired {
   80         if len(to) > 0 {
   81             return false, NI(fr), to[0]
   82         }
   83     }
   84     return true, -1, -1
   85 }
   86 
   87 // Edgelist constructs the edge list rerpresentation of a graph.
   88 //
   89 // An edge is returned for each arc of the graph.  For undirected graphs
   90 // this includes reciprocal edges.
   91 //
   92 // See also WeightedEdgeList method.
   93 func (g LabeledAdjacencyList) EdgeList() (el []LabeledEdge) {
   94     for fr, to := range g {
   95         for _, to := range to {
   96             el = append(el, LabeledEdge{Edge{NI(fr), to.To}, to.Label})
   97         }
   98     }
   99     return
  100 }
  101 
  102 // FloydWarshall finds all pairs shortest distances for a simple weighted
  103 // graph without negative cycles.
  104 //
  105 // In result array d, d[i][j] will be the shortest distance from node i
  106 // to node j.  Any diagonal element < 0 indicates a negative cycle exists.
  107 //
  108 // If g is an undirected graph with no negative edge weights, the result
  109 // array will be a distance matrix, for example as used by package
  110 // github.com/soniakeys/cluster.
  111 func (g LabeledAdjacencyList) FloydWarshall(w WeightFunc) (d [][]float64) {
  112     d = newFWd(len(g))
  113     for fr, to := range g {
  114         for _, to := range to {
  115             d[fr][to.To] = w(to.Label)
  116         }
  117     }
  118     solveFW(d)
  119     return
  120 }
  121 
  122 // little helper function, makes a blank matrix for FloydWarshall.
  123 func newFWd(n int) [][]float64 {
  124     d := make([][]float64, n)
  125     for i := range d {
  126         di := make([]float64, n)
  127         for j := range di {
  128             if j != i {
  129                 di[j] = math.Inf(1)
  130             }
  131         }
  132         d[i] = di
  133     }
  134     return d
  135 }
  136 
  137 // Floyd Warshall solver, once the matrix d is initialized by arc weights.
  138 func solveFW(d [][]float64) {
  139     for k, dk := range d {
  140         for _, di := range d {
  141             dik := di[k]
  142             for j := range d {
  143                 if d2 := dik + dk[j]; d2 < di[j] {
  144                     di[j] = d2
  145                 }
  146             }
  147         }
  148     }
  149 }
  150 
  151 // HasArcLabel returns true if g has any arc from node fr to node to
  152 // with label l.
  153 //
  154 // Also returned is the index within the slice of arcs from node fr.
  155 // If no arc from fr to to is present, HasArcLabel returns false, -1.
  156 func (g LabeledAdjacencyList) HasArcLabel(fr, to NI, l LI) (bool, int) {
  157     t := Half{to, l}
  158     for x, h := range g[fr] {
  159         if h == t {
  160             return true, x
  161         }
  162     }
  163     return false, -1
  164 }
  165 
  166 // HasParallelSort identifies if a graph contains parallel arcs, multiple arcs
  167 // that lead from a node to the same node.
  168 //
  169 // If the graph has parallel arcs, the results fr and to represent an example
  170 // where there are parallel arcs from node fr to node to.
  171 //
  172 // If there are no parallel arcs, the method returns -1 -1.
  173 //
  174 // Multiple loops on a node count as parallel arcs.
  175 //
  176 // "Sort" in the method name indicates that sorting is used to detect parallel
  177 // arcs.  Compared to method HasParallelMap, this may give better performance
  178 // for small or sparse graphs but will have asymtotically worse performance for
  179 // large dense graphs.
  180 func (g LabeledAdjacencyList) HasParallelSort() (has bool, fr, to NI) {
  181     var t NodeList
  182     for n, to := range g {
  183         if len(to) == 0 {
  184             continue
  185         }
  186         // slightly different code needed here compared to AdjacencyList
  187         t = t[:0]
  188         for _, to := range to {
  189             t = append(t, to.To)
  190         }
  191         sort.Sort(t)
  192         t0 := t[0]
  193         for _, to := range t[1:] {
  194             if to == t0 {
  195                 return true, NI(n), t0
  196             }
  197             t0 = to
  198         }
  199     }
  200     return false, -1, -1
  201 }
  202 
  203 // IsUndirected returns true if g represents an undirected graph.
  204 //
  205 // Returns true when all non-loop arcs are paired in reciprocal pairs with
  206 // matching labels.  Otherwise returns false and an example unpaired arc.
  207 //
  208 // Note the requirement that reciprocal pairs have matching labels is
  209 // an additional test not present in the otherwise equivalent unlabeled version
  210 // of IsUndirected.
  211 func (g LabeledAdjacencyList) IsUndirected() (u bool, from NI, to Half) {
  212     unpaired := make(LabeledAdjacencyList, len(g))
  213     for fr, to := range g {
  214     arc: // for each arc in g
  215         for _, to := range to {
  216             if to.To == NI(fr) {
  217                 continue // loop
  218             }
  219             // search unpaired arcs
  220             ut := unpaired[to.To]
  221             for i, u := range ut {
  222                 if u.To == NI(fr) && u.Label == to.Label { // found reciprocal
  223                     last := len(ut) - 1
  224                     ut[i] = ut[last]
  225                     unpaired[to.To] = ut[:last]
  226                     continue arc
  227                 }
  228             }
  229             // reciprocal not found
  230             unpaired[fr] = append(unpaired[fr], to)
  231         }
  232     }
  233     for fr, to := range unpaired {
  234         if len(to) > 0 {
  235             return false, NI(fr), to[0]
  236         }
  237     }
  238     return true, -1, to
  239 }
  240 
  241 // NegativeArc returns true if the receiver graph contains a negative arc.
  242 func (g LabeledAdjacencyList) NegativeArc(w WeightFunc) bool {
  243     for _, nbs := range g {
  244         for _, nb := range nbs {
  245             if w(nb.Label) < 0 {
  246                 return true
  247             }
  248         }
  249     }
  250     return false
  251 }
  252 
  253 // Unlabeled constructs the unlabeled graph corresponding to g.
  254 func (g LabeledAdjacencyList) Unlabeled() AdjacencyList {
  255     a := make(AdjacencyList, len(g))
  256     for n, nbs := range g {
  257         to := make([]NI, len(nbs))
  258         for i, nb := range nbs {
  259             to[i] = nb.To
  260         }
  261         a[n] = to
  262     }
  263     return a
  264 }
  265 
  266 // WeightedEdgeList constructs a WeightedEdgeList object from a
  267 // LabeledAdjacencyList.
  268 //
  269 // Internally it calls g.EdgeList() to obtain the Edges member.
  270 // See LabeledAdjacencyList.EdgeList().
  271 func (g LabeledAdjacencyList) WeightedEdgeList(w WeightFunc) *WeightedEdgeList {
  272     return &WeightedEdgeList{
  273         Order:      len(g),
  274         WeightFunc: w,
  275         Edges:      g.EdgeList(),
  276     }
  277 }
  278 
  279 // WeightedInDegree computes the weighted in-degree of each node in g
  280 // for a given weight function w.
  281 //
  282 // The weighted in-degree of a node is the sum of weights of arcs going to
  283 // the node.
  284 //
  285 // A weighted degree of a node is often termed the "strength" of a node.
  286 //
  287 // See note for undirected graphs at LabeledAdjacencyList.WeightedOutDegree.
  288 func (g LabeledAdjacencyList) WeightedInDegree(w WeightFunc) []float64 {
  289     ind := make([]float64, len(g))
  290     for _, to := range g {
  291         for _, to := range to {
  292             ind[to.To] += w(to.Label)
  293         }
  294     }
  295     return ind
  296 }
  297 
  298 // WeightedOutDegree computes the weighted out-degree of the specified node
  299 // for a given weight function w.
  300 //
  301 // The weighted out-degree of a node is the sum of weights of arcs going from
  302 // the node.
  303 //
  304 // A weighted degree of a node is often termed the "strength" of a node.
  305 //
  306 // Note for undirected graphs, the WeightedOutDegree result for a node will
  307 // equal the WeightedInDegree for the node.  You can use WeightedInDegree if
  308 // you have need for the weighted degrees of all nodes or use WeightedOutDegree
  309 // to compute the weighted degrees of individual nodes.  In either case loops
  310 // are counted just once, unlike the (unweighted) UndirectedDegree methods.
  311 func (g LabeledAdjacencyList) WeightedOutDegree(n NI, w WeightFunc) (d float64) {
  312     for _, to := range g[n] {
  313         d += w(to.Label)
  314     }
  315     return
  316 }
  317 
  318 // More about loops and strength:  I didn't see consensus on this especially
  319 // in the case of undirected graphs.  Some sources said to add in-degree and
  320 // out-degree, which would seemingly double both loops and non-loops.
  321 // Some said to double loops.  Some said sum the edge weights and had no
  322 // comment on loops.  R of course makes everything an option.  The meaning
  323 // of "strength" where loops exist is unclear.  So while I could write an
  324 // UndirectedWeighted degree function that doubles loops but not edges,
  325 // I'm going to just leave this for now.