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