"Fossies" - the Fresh Open Source Software Archive

Member "gdrive-2.1.1/vendor/github.com/soniakeys/graph/doc.go" (28 May 2021, 6724 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 // Graph algorithms: Dijkstra, A*, Bellman Ford, Floyd Warshall;
    5 // Kruskal and Prim minimal spanning tree; topological sort and DAG longest
    6 // and shortest paths; Eulerian cycle and path; degeneracy and k-cores;
    7 // Bron Kerbosch clique finding; connected components; and others.
    8 //
    9 // This is a graph library of integer indexes.  To use it with application
   10 // data, you associate data with integer indexes, perform searches or other
   11 // operations with the library, and then use the integer index results to refer
   12 // back to your application data.
   13 //
   14 // Thus it does not store application data, pointers to application data,
   15 // or require you to implement an interface on your application data.
   16 // The idea is to keep the library methods fast and lean.
   17 //
   18 // Representation overview
   19 //
   20 // The package defines a type for a node index (NI) which is just an integer
   21 // type.  It defines types for a number of number graph representations using
   22 // NI.  The fundamental graph type is AdjacencyList, which is the
   23 // common "list of lists" graph representation.  It is a list as a slice
   24 // with one element for each node of the graph.  Each element is a list
   25 // itself, a list of neighbor nodes, implemented as an NI slice.  Methods
   26 // on an AdjacencyList generally work on any representable graph, including
   27 // directed or undirected graphs, simple graphs or multigraphs.
   28 //
   29 // The type Undirected embeds an AdjacencyList adding methods specific to
   30 // undirected graphs.  Similarly the type Directed adds methods meaningful
   31 // for directed graphs.
   32 //
   33 // Similar to NI, the type LI is a "label index" which labels a
   34 // node-to-neighbor "arc" or edge.  Just as an NI can index arbitrary node
   35 // data, an LI can index arbitrary arc or edge data.  A number of algorithms
   36 // use a "weight" associated with an arc.  This package does not represent
   37 // weighted arcs explicitly, but instead uses the LI as a more general
   38 // mechanism allowing not only weights but arbitrary data to be associated
   39 // with arcs.  While AdjacencyList represents an arc with simply an NI,
   40 // the type LabeledAdjacencyList uses a type that pairs an NI with an LI.
   41 // This type is named Half, for half-arc.  (A full arc would represent
   42 // both ends.)  Types LabeledDirected and LabeledUndirected embed a
   43 // LabeledAdjacencyList.
   44 //
   45 // In contrast to Half, the type Edge represents both ends of an edge (but
   46 // no label.)  The type LabeledEdge adds the label.  The type WeightedEdgeList
   47 // bundles a list of LabeledEdges with a WeightFunc.  WeightedEdgeList is
   48 // currently only used by Kruskal methods.
   49 //
   50 // FromList is a compact rooted tree (or forest) respresentation.  Like
   51 // AdjacencyList and LabeledAdjacencyList, it is a list with one element for
   52 // each node of the graph.  Each element contains only a single neighbor
   53 // however, its parent in the tree, the "from" node.
   54 //
   55 // Code generation
   56 //
   57 // A number of methods on AdjacencyList, Directed, and Undirected are
   58 // applicable to LabeledAdjacencyList, LabeledDirected, and LabeledUndirected
   59 // simply by ignoring the label.  In these cases code generation provides
   60 // methods on both types from a single source implementation. These methods
   61 // are documented with the sentence "There are equivalent labeled and unlabeled
   62 // versions of this method" and examples are provided only for the unlabeled
   63 // version.
   64 //
   65 // Terminology
   66 //
   67 // This package uses the term "node" rather than "vertex."  It uses "arc"
   68 // to mean a directed edge, and uses "from" and "to" to refer to the ends
   69 // of an arc.  It uses "start" and "end" to refer to endpoints of a search
   70 // or traversal.
   71 //
   72 // The usage of "to" and "from" is perhaps most strange.  In common speech
   73 // they are prepositions, but throughout this package they are used as
   74 // adjectives, for example to refer to the "from node" of an arc or the
   75 // "to node".  The type "FromList" is named to indicate it stores a list of
   76 // "from" values.
   77 //
   78 // A "half arc" refers to just one end of an arc, either the to or from end.
   79 //
   80 // Two arcs are "reciprocal" if they connect two distinct nodes n1 and n2,
   81 // one arc leading from n1 to n2 and the other arc leading from n2 to n1.
   82 // Undirected graphs are represented with reciprocal arcs.
   83 //
   84 // A node with an arc to itself represents a "loop."  Duplicate arcs, where
   85 // a node has multiple arcs to another node, are termed "parallel arcs."
   86 // A graph with no loops or parallel arcs is "simple."  A graph that allows
   87 // parallel arcs is a "multigraph"
   88 //
   89 // The "size" of a graph traditionally means the number of undirected edges.
   90 // This package uses "arc size" to mean the number of arcs in a graph.  For an
   91 // undirected graph without loops, arc size is 2 * size.
   92 //
   93 // The "order" of a graph is the number of nodes.  An "ordering" though means
   94 // an ordered list of nodes.
   95 //
   96 // A number of graph search algorithms use a concept of arc "weights."
   97 // The sum of arc weights along a path is a "distance."  In contrast, the
   98 // number of nodes in a path, including start and end nodes, is the path's
   99 // "length."  (Yes, mixing weights and lengths would be nonsense physically,
  100 // but the terms used here are just distinct terms for abstract values.
  101 // The actual meaning to an application is likely to be something else
  102 // entirely and is not relevant within this package.)
  103 //
  104 // Finally, this package documentation takes back the word "object" in some
  105 // places to refer to a Go value, especially a value of a type with methods.
  106 //
  107 // Shortest path searches
  108 //
  109 // This package implements a number of shortest path searches.  Most work
  110 // with weighted graphs that are directed or undirected, and with graphs
  111 // that may have loops or parallel arcs.  For weighted graphs, "shortest"
  112 // is defined as the path distance (sum of arc weights) with path length
  113 // (number of nodes) breaking ties.  If multiple paths have the same minimum
  114 // distance with the same minimum length, search methods are free to return
  115 // any of them.
  116 //
  117 //  Type name      Description, methods
  118 //  BreadthFirst   Unweigted arcs, traversal, single path search or all paths.
  119 //  BreadthFirst2  Direction-optimizing variant of BreadthFirst.
  120 //  Dijkstra       Non-negative arc weights, single or all paths.
  121 //  AStar          Non-negative arc weights, heuristic guided, single path.
  122 //  BellmanFord    Negative arc weights allowed, no negative cycles, all paths.
  123 //  DAGPath        O(n) algorithm for DAGs, arc weights of any sign.
  124 //  FloydWarshall  all pairs distances, no negative cycles.
  125 //
  126 // These searches typically have one method that is full-featured and
  127 // then a convenience method with a simpler API targeting a simpler use case.
  128 package graph