"Fossies" - the Fresh Open Source Software Archive

Member "gdrive-2.1.1/vendor/github.com/soniakeys/graph/random.go" (28 May 2021, 9415 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 2016 Sonia Keys
    2 // License MIT: https://opensource.org/licenses/MIT
    3 
    4 package graph
    5 
    6 import (
    7     "errors"
    8     "math"
    9     "math/rand"
   10     "time"
   11 )
   12 
   13 // Euclidean generates a random simple graph on the Euclidean plane.
   14 //
   15 // Nodes are associated with coordinates uniformly distributed on a unit
   16 // square.  Arcs are added between random nodes with a bias toward connecting
   17 // nearer nodes.
   18 //
   19 // Unfortunately the function has a few "knobs".
   20 // The returned graph will have order nNodes and arc size nArcs.  The affinity
   21 // argument controls the bias toward connecting nearer nodes.  The function
   22 // selects random pairs of nodes as a candidate arc then rejects the candidate
   23 // if the nodes fail an affinity test.  Also parallel arcs are rejected.
   24 // As more affine or denser graphs are requested, rejections increase,
   25 // increasing run time.  The patience argument controls the number of arc
   26 // rejections allowed before the function gives up and returns an error.
   27 // Note that higher affinity will require more patience and that some
   28 // combinations of nNodes and nArcs cannot be achieved with any amount of
   29 // patience given that the returned graph must be simple.
   30 //
   31 // If Rand r is nil, the method creates a new source and generator for
   32 // one-time use.
   33 //
   34 // Returned is a directed simple graph and associated positions indexed by
   35 // node number.
   36 //
   37 // See also LabeledEuclidean.
   38 func Euclidean(nNodes, nArcs int, affinity float64, patience int, r *rand.Rand) (g Directed, pos []struct{ X, Y float64 }, err error) {
   39     a := make(AdjacencyList, nNodes) // graph
   40     // generate random positions
   41     if r == nil {
   42         r = rand.New(rand.NewSource(time.Now().UnixNano()))
   43     }
   44     pos = make([]struct{ X, Y float64 }, nNodes)
   45     for i := range pos {
   46         pos[i].X = r.Float64()
   47         pos[i].Y = r.Float64()
   48     }
   49     // arcs
   50     var tooFar, dup int
   51 arc:
   52     for i := 0; i < nArcs; {
   53         if tooFar == nArcs*patience {
   54             err = errors.New("affinity not found")
   55             return
   56         }
   57         if dup == nArcs*patience {
   58             err = errors.New("overcrowding")
   59             return
   60         }
   61         n1 := NI(r.Intn(nNodes))
   62         var n2 NI
   63         for {
   64             n2 = NI(r.Intn(nNodes))
   65             if n2 != n1 { // no graph loops
   66                 break
   67             }
   68         }
   69         c1 := &pos[n1]
   70         c2 := &pos[n2]
   71         dist := math.Hypot(c2.X-c1.X, c2.Y-c1.Y)
   72         if dist*affinity > r.ExpFloat64() { // favor near nodes
   73             tooFar++
   74             continue
   75         }
   76         for _, nb := range a[n1] {
   77             if nb == n2 { // no parallel arcs
   78                 dup++
   79                 continue arc
   80             }
   81         }
   82         a[n1] = append(a[n1], n2)
   83         i++
   84     }
   85     g = Directed{a}
   86     return
   87 }
   88 
   89 // LabeledEuclidean generates a random simple graph on the Euclidean plane.
   90 //
   91 // Arc label values in the returned graph g are indexes into the return value
   92 // wt.  Wt is the Euclidean distance between the from and to nodes of the arc.
   93 //
   94 // Otherwise the function arguments and return values are the same as for
   95 // function Euclidean.  See Euclidean.
   96 func LabeledEuclidean(nNodes, nArcs int, affinity float64, patience int, r *rand.Rand) (g LabeledDirected, pos []struct{ X, Y float64 }, wt []float64, err error) {
   97     a := make(LabeledAdjacencyList, nNodes) // graph
   98     wt = make([]float64, nArcs)             // arc weights
   99     // generate random positions
  100     if r == nil {
  101         r = rand.New(rand.NewSource(time.Now().UnixNano()))
  102     }
  103     pos = make([]struct{ X, Y float64 }, nNodes)
  104     for i := range pos {
  105         pos[i].X = r.Float64()
  106         pos[i].Y = r.Float64()
  107     }
  108     // arcs
  109     var tooFar, dup int
  110 arc:
  111     for i := 0; i < nArcs; {
  112         if tooFar == nArcs*patience {
  113             err = errors.New("affinity not found")
  114             return
  115         }
  116         if dup == nArcs*patience {
  117             err = errors.New("overcrowding")
  118             return
  119         }
  120         n1 := NI(r.Intn(nNodes))
  121         var n2 NI
  122         for {
  123             n2 = NI(r.Intn(nNodes))
  124             if n2 != n1 { // no graph loops
  125                 break
  126             }
  127         }
  128         c1 := &pos[n1]
  129         c2 := &pos[n2]
  130         dist := math.Hypot(c2.X-c1.X, c2.Y-c1.Y)
  131         if dist*affinity > r.ExpFloat64() { // favor near nodes
  132             tooFar++
  133             continue
  134         }
  135         for _, nb := range a[n1] {
  136             if nb.To == n2 { // no parallel arcs
  137                 dup++
  138                 continue arc
  139             }
  140         }
  141         wt[i] = dist
  142         a[n1] = append(a[n1], Half{n2, LI(i)})
  143         i++
  144     }
  145     g = LabeledDirected{a}
  146     return
  147 }
  148 
  149 // Geometric generates a random geometric graph (RGG) on the Euclidean plane.
  150 //
  151 // An RGG is an undirected simple graph.  Nodes are associated with coordinates
  152 // uniformly distributed on a unit square.  Edges are added between all nodes
  153 // falling within a specified distance or radius of each other.
  154 //
  155 // The resulting number of edges is somewhat random but asymptotically
  156 // approaches m = πr²n²/2.   The method accumulates and returns the actual
  157 // number of edges constructed.
  158 //
  159 // If Rand r is nil, the method creates a new source and generator for
  160 // one-time use.
  161 //
  162 // See also LabeledGeometric.
  163 func Geometric(nNodes int, radius float64, r *rand.Rand) (g Undirected, pos []struct{ X, Y float64 }, m int) {
  164     // Expected degree is approximately nπr².
  165     a := make(AdjacencyList, nNodes)
  166     if r == nil {
  167         r = rand.New(rand.NewSource(time.Now().UnixNano()))
  168     }
  169     pos = make([]struct{ X, Y float64 }, nNodes)
  170     for i := range pos {
  171         pos[i].X = r.Float64()
  172         pos[i].Y = r.Float64()
  173     }
  174     for u, up := range pos {
  175         for v := u + 1; v < len(pos); v++ {
  176             vp := pos[v]
  177             if math.Hypot(up.X-vp.X, up.Y-vp.Y) < radius {
  178                 a[u] = append(a[u], NI(v))
  179                 a[v] = append(a[v], NI(u))
  180                 m++
  181             }
  182         }
  183     }
  184     g = Undirected{a}
  185     return
  186 }
  187 
  188 // LabeledGeometric generates a random geometric graph (RGG) on the Euclidean
  189 // plane.
  190 //
  191 // Edge label values in the returned graph g are indexes into the return value
  192 // wt.  Wt is the Euclidean distance between nodes of the edge.  The graph
  193 // size m is len(wt).
  194 //
  195 // See Geometric for additional description.
  196 func LabeledGeometric(nNodes int, radius float64, r *rand.Rand) (g LabeledUndirected, pos []struct{ X, Y float64 }, wt []float64) {
  197     a := make(LabeledAdjacencyList, nNodes)
  198     if r == nil {
  199         r = rand.New(rand.NewSource(time.Now().UnixNano()))
  200     }
  201     pos = make([]struct{ X, Y float64 }, nNodes)
  202     for i := range pos {
  203         pos[i].X = r.Float64()
  204         pos[i].Y = r.Float64()
  205     }
  206     for u, up := range pos {
  207         for v := u + 1; v < len(pos); v++ {
  208             vp := pos[v]
  209             if w := math.Hypot(up.X-vp.X, up.Y-vp.Y); w < radius {
  210                 a[u] = append(a[u], Half{NI(v), LI(len(wt))})
  211                 a[v] = append(a[v], Half{NI(u), LI(len(wt))})
  212                 wt = append(wt, w)
  213             }
  214         }
  215     }
  216     g = LabeledUndirected{a}
  217     return
  218 }
  219 
  220 // KroneckerDirected generates a Kronecker-like random directed graph.
  221 //
  222 // The returned graph g is simple and has no isolated nodes but is not
  223 // necessarily fully connected.  The number of of nodes will be <= 2^scale,
  224 // and will be near 2^scale for typical values of arcFactor, >= 2.
  225 // ArcFactor * 2^scale arcs are generated, although loops and duplicate arcs
  226 // are rejected.
  227 //
  228 // If Rand r is nil, the method creates a new source and generator for
  229 // one-time use.
  230 //
  231 // Return value ma is the number of arcs retained in the result graph.
  232 func KroneckerDirected(scale uint, arcFactor float64, r *rand.Rand) (g Directed, ma int) {
  233     a, m := kronecker(scale, arcFactor, true, r)
  234     return Directed{a}, m
  235 }
  236 
  237 // KroneckerUndirected generates a Kronecker-like random undirected graph.
  238 //
  239 // The returned graph g is simple and has no isolated nodes but is not
  240 // necessarily fully connected.  The number of of nodes will be <= 2^scale,
  241 // and will be near 2^scale for typical values of edgeFactor, >= 2.
  242 // EdgeFactor * 2^scale edges are generated, although loops and duplicate edges
  243 // are rejected.
  244 //
  245 // If Rand r is nil, the method creates a new source and generator for
  246 // one-time use.
  247 //
  248 // Return value m is the true number of edges--not arcs--retained in the result
  249 // graph.
  250 func KroneckerUndirected(scale uint, edgeFactor float64, r *rand.Rand) (g Undirected, m int) {
  251     al, s := kronecker(scale, edgeFactor, false, r)
  252     return Undirected{al}, s
  253 }
  254 
  255 // Styled after the Graph500 example code.  Not well tested currently.
  256 // Graph500 example generates undirected only.  No idea if the directed variant
  257 // here is meaningful or not.
  258 //
  259 // note mma returns arc size ma for dir=true, but returns size m for dir=false
  260 func kronecker(scale uint, edgeFactor float64, dir bool, r *rand.Rand) (g AdjacencyList, mma int) {
  261     if r == nil {
  262         r = rand.New(rand.NewSource(time.Now().UnixNano()))
  263     }
  264     N := NI(1 << scale)                  // node extent
  265     M := int(edgeFactor*float64(N) + .5) // number of arcs/edges to generate
  266     a, b, c := 0.57, 0.19, 0.19          // initiator probabilities
  267     ab := a + b
  268     cNorm := c / (1 - ab)
  269     aNorm := a / ab
  270     ij := make([][2]NI, M)
  271     var bm Bits
  272     var nNodes int
  273     for k := range ij {
  274         var i, j NI
  275         for b := NI(1); b < N; b <<= 1 {
  276             if r.Float64() > ab {
  277                 i |= b
  278                 if r.Float64() > cNorm {
  279                     j |= b
  280                 }
  281             } else if r.Float64() > aNorm {
  282                 j |= b
  283             }
  284         }
  285         if bm.Bit(i) == 0 {
  286             bm.SetBit(i, 1)
  287             nNodes++
  288         }
  289         if bm.Bit(j) == 0 {
  290             bm.SetBit(j, 1)
  291             nNodes++
  292         }
  293         r := r.Intn(k + 1) // shuffle edges as they are generated
  294         ij[k] = ij[r]
  295         ij[r] = [2]NI{i, j}
  296     }
  297     p := r.Perm(nNodes) // mapping to shuffle IDs of non-isolated nodes
  298     px := 0
  299     rn := make([]NI, N)
  300     for i := range rn {
  301         if bm.Bit(NI(i)) == 1 {
  302             rn[i] = NI(p[px]) // fill lookup table
  303             px++
  304         }
  305     }
  306     g = make(AdjacencyList, nNodes)
  307 ij:
  308     for _, e := range ij {
  309         if e[0] == e[1] {
  310             continue // skip loops
  311         }
  312         ri, rj := rn[e[0]], rn[e[1]]
  313         for _, nb := range g[ri] {
  314             if nb == rj {
  315                 continue ij // skip parallel edges
  316             }
  317         }
  318         g[ri] = append(g[ri], rj)
  319         mma++
  320         if !dir {
  321             g[rj] = append(g[rj], ri)
  322         }
  323     }
  324     return
  325 }