"Fossies" - the Fresh Open Source Software Archive

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

    1 // Copyright 2014 Sonia Keys
    2 // License MIT: http://opensource.org/licenses/MIT
    3 
    4 package graph
    5 
    6 // graph.go contains type definitions for all graph types and components.
    7 // Also, go generate directives for source transformations.
    8 //
    9 // For readability, the types are defined in a dependency order:
   10 //
   11 //  NI
   12 //  NodeList
   13 //  AdjacencyList
   14 //  Directed
   15 //  Undirected
   16 //  LI
   17 //  Half
   18 //  LabeledAdjacencyList
   19 //  LabeledDirected
   20 //  LabeledUndirected
   21 //  Edge
   22 //  LabeledEdge
   23 //  WeightFunc
   24 //  WeightedEdgeList
   25 
   26 //go:generate cp adj_cg.go adj_RO.go
   27 //go:generate gofmt -r "LabeledAdjacencyList -> AdjacencyList" -w adj_RO.go
   28 //go:generate gofmt -r "n.To -> n" -w adj_RO.go
   29 //go:generate gofmt -r "Half -> NI" -w adj_RO.go
   30 
   31 //go:generate cp dir_cg.go dir_RO.go
   32 //go:generate gofmt -r "LabeledDirected -> Directed" -w dir_RO.go
   33 //go:generate gofmt -r "LabeledAdjacencyList -> AdjacencyList" -w dir_RO.go
   34 //go:generate gofmt -r "n.To -> n" -w dir_RO.go
   35 //go:generate gofmt -r "Half -> NI" -w dir_RO.go
   36 
   37 //go:generate cp undir_cg.go undir_RO.go
   38 //go:generate gofmt -r "LabeledUndirected -> Undirected" -w undir_RO.go
   39 //go:generate gofmt -r "LabeledAdjacencyList -> AdjacencyList" -w undir_RO.go
   40 //go:generate gofmt -r "n.To -> n" -w undir_RO.go
   41 //go:generate gofmt -r "Half -> NI" -w undir_RO.go
   42 
   43 // NI is a "node int"
   44 //
   45 // It is a node number or node ID.  NIs are used extensively as slice indexes.
   46 // NIs typically account for a significant fraction of the memory footprint of
   47 // a graph.
   48 type NI int32
   49 
   50 // NodeList satisfies sort.Interface.
   51 type NodeList []NI
   52 
   53 func (l NodeList) Len() int           { return len(l) }
   54 func (l NodeList) Less(i, j int) bool { return l[i] < l[j] }
   55 func (l NodeList) Swap(i, j int)      { l[i], l[j] = l[j], l[i] }
   56 
   57 // An AdjacencyList represents a graph as a list of neighbors for each node.
   58 // The "node ID" of a node is simply it's slice index in the AdjacencyList.
   59 // For an AdjacencyList g, g[n] represents arcs going from node n to nodes
   60 // g[n].
   61 //
   62 // Adjacency lists are inherently directed but can be used to represent
   63 // directed or undirected graphs.  See types Directed and Undirected.
   64 type AdjacencyList [][]NI
   65 
   66 // Directed represents a directed graph.
   67 //
   68 // Directed methods generally rely on the graph being directed, specifically
   69 // that arcs do not have reciprocals.
   70 type Directed struct {
   71     AdjacencyList // embedded to include AdjacencyList methods
   72 }
   73 
   74 // Undirected represents an undirected graph.
   75 //
   76 // In an undirected graph, for each arc between distinct nodes there is also
   77 // a reciprocal arc, an arc in the opposite direction.  Loops do not have
   78 // reciprocals.
   79 //
   80 // Undirected methods generally rely on the graph being undirected,
   81 // specifically that every arc between distinct nodes has a reciprocal.
   82 type Undirected struct {
   83     AdjacencyList // embedded to include AdjacencyList methods
   84 }
   85 
   86 // LI is a label integer, used for associating labels with arcs.
   87 type LI int32
   88 
   89 // Half is a half arc, representing a labeled arc and the "neighbor" node
   90 // that the arc leads to.
   91 //
   92 // Halfs can be composed to form a labeled adjacency list.
   93 type Half struct {
   94     To    NI // node ID, usable as a slice index
   95     Label LI // half-arc ID for application data, often a weight
   96 }
   97 
   98 // A LabeledAdjacencyList represents a graph as a list of neighbors for each
   99 // node, connected by labeled arcs.
  100 //
  101 // Arc labels are not necessarily unique arc IDs.  Different arcs can have
  102 // the same label.
  103 //
  104 // Arc labels are commonly used to assocate a weight with an arc.  Arc labels
  105 // are general purpose however and can be used to associate arbitrary
  106 // information with an arc.
  107 //
  108 // Methods implementing weighted graph algorithms will commonly take a
  109 // weight function that turns a label int into a float64 weight.
  110 //
  111 // If only a small amount of information -- such as an integer weight or
  112 // a single printable character -- needs to be associated, it can sometimes
  113 // be possible to encode the information directly into the label int.  For
  114 // more generality, some lookup scheme will be needed.
  115 //
  116 // In an undirected labeled graph, reciprocal arcs must have identical labels.
  117 // Note this does not preclude parallel arcs with different labels.
  118 type LabeledAdjacencyList [][]Half
  119 
  120 // LabeledDirected represents a directed labeled graph.
  121 //
  122 // This is the labeled version of Directed.  See types LabeledAdjacencyList
  123 // and Directed.
  124 type LabeledDirected struct {
  125     LabeledAdjacencyList // embedded to include LabeledAdjacencyList methods
  126 }
  127 
  128 // LabeledUndirected represents an undirected labeled graph.
  129 //
  130 // This is the labeled version of Undirected.  See types LabeledAdjacencyList
  131 // and Undirected.
  132 type LabeledUndirected struct {
  133     LabeledAdjacencyList // embedded to include LabeledAdjacencyList methods
  134 }
  135 
  136 // Edge is an undirected edge between nodes N1 and N2.
  137 type Edge struct{ N1, N2 NI }
  138 
  139 // LabeledEdge is an undirected edge with an associated label.
  140 type LabeledEdge struct {
  141     Edge
  142     LI
  143 }
  144 
  145 // WeightFunc returns a weight for a given label.
  146 //
  147 // WeightFunc is a parameter type for various search functions.  The intent
  148 // is to return a weight corresponding to an arc label.  The name "weight"
  149 // is an abstract term.  An arc "weight" will typically have some application
  150 // specific meaning other than physical weight.
  151 type WeightFunc func(label LI) (weight float64)
  152 
  153 // WeightedEdgeList is a graph representation.
  154 //
  155 // It is a labeled edge list, with an associated weight function to return
  156 // a weight given an edge label.
  157 //
  158 // Also associated is the order, or number of nodes of the graph.
  159 // All nodes occurring in the edge list must be strictly less than Order.
  160 //
  161 // WeigtedEdgeList sorts by weight, obtained by calling the weight function.
  162 // If weight computation is expensive, consider supplying a cached or
  163 // memoized version.
  164 type WeightedEdgeList struct {
  165     Order int
  166     WeightFunc
  167     Edges []LabeledEdge
  168 }
  169 
  170 // Len implements sort.Interface.
  171 func (l WeightedEdgeList) Len() int { return len(l.Edges) }
  172 
  173 // Less implements sort.Interface.
  174 func (l WeightedEdgeList) Less(i, j int) bool {
  175     return l.WeightFunc(l.Edges[i].LI) < l.WeightFunc(l.Edges[j].LI)
  176 }
  177 
  178 // Swap implements sort.Interface.
  179 func (l WeightedEdgeList) Swap(i, j int) {
  180     l.Edges[i], l.Edges[j] = l.Edges[j], l.Edges[i]
  181 }