"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:

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
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
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
```