Categorygithub.com/soniakeys/graph
modulepackage
0.0.0
Repository: https://github.com/soniakeys/graph.git
Documentation: pkg.go.dev
Overview
Versions
1
Dependencies
10
Dependents
33
Files
6.9k SLOC

# README

= Graph

A graph library with goals of speed and simplicity, Graph implements graph algorithms on graphs of zero-based integer node IDs.

image:https://godoc.org/github.com/soniakeys/graph?status.svg[link=https://godoc.org/github.com/soniakeys/graph] image:http://gowalker.org/api/v1/badge[link=https://gowalker.org/github.com/soniakeys/graph] image:http://go-search.org/badge?id=github.com%2Fsoniakeys%2Fgraph[link=http://go-search.org/view?id=github.com%2Fsoniakeys%2Fgraph] image:https://travis-ci.org/soniakeys/graph.svg?branch=master[link=https://travis-ci.org/soniakeys/graph]

The library provides efficient graph representations and many methods on graph types. It can be imported and used directly in many applications that require or can benefit from graph algorithms.

The library should also be considered as library of source code that can serve as starting material for coding variant or more complex algorithms.

== Ancillary material of interest

The directory link:tutorials[tutorials] is a work in progress - there are only a few tutorials there yet - but the concept is to provide some topical walk-throughs to supplement godoc. The source-based godoc documentation remains the primary documentation.

The directory link:anecdote[anecdote] contains a stand-alone program that performs single runs of a number of methods, collecting one-off or "anecdotal" timings. It currently runs only a small fraction of the library methods but may still be of interest for giving a general idea of how fast some methods run.

The directory link:bench[bench] is another work in progress. The concept is to present some plots showing benchmark performance approaching some theoretical asymptote.

link:hacking.adoc[hacking.adoc] has some information about how the library is developed, built, and tested. It might be of interest if for example you plan to fork or contribute to the the repository.

== Test coverage 1 Jul 2017 .... graph 93.7% graph/alt 88.0% graph/dot 77.7% graph/treevis 79.4% ....

== License All files in the repository are licensed with the MIT License, https://opensource.org/licenses/MIT.

# Packages

Alternative graph algorithms Functions in this package implement alternatives to algorithms in the main graph package.
Anecdotal timings.
Package dot writes graphs from package graph in the Graphviz dot format.
Treevis draws trees with text.

# Functions

ArcDensity returns density for a simple directed graph.
ChungLu constructs a random simple undirected graph.
Density returns density for a simple undirected graph.
Euclidean generates a random simple graph on the Euclidean plane.
Geometric generates a random geometric graph (RGG) on the Euclidean plane.
Gnm3Directed constructs a random simple directed graph.
Gnm3Undirected constructs a random simple undirected graph.
GnmDirected constructs a random simple directed graph.
GnmUndirected constructs a random simple undirected graph.
GnpDirected constructs a random simple directed graph.
GnpUndirected constructs a random simple undirected graph.
KroneckerDirected generates a Kronecker-like random directed graph.
KroneckerUndirected generates a Kronecker-like random undirected graph.
LabeledEuclidean generates a random simple graph on the Euclidean plane.
LabeledGeometric generates a random geometric graph (RGG) on the Euclidean plane.
NewFromList creates a FromList object of given order.
OrderMap formats maps for testable examples.
PathTo decodes a single path from a PathEnd list.

# Structs

Bipartite represents a bipartite graph.
Directed represents a directed graph.
DirectedSubgraph represents a subgraph mapped to a supergraph.
Dominators holds immediate dominators.
Edge is an undirected edge between nodes N1 and N2.
FromList represents a rooted tree (or forest) where each node is associated with a half arc identifying an arc "from" another node.
Half is a half arc, representing a labeled arc and the "neighbor" node that the arc leads to.
LabeledBipartite represents a bipartite graph.
LabeledDirected represents a directed labeled graph.
LabeledDirectedSubgraph represents a subgraph mapped to a supergraph.
LabeledEdge is an undirected edge with an associated label.
LabeledPath is a start node and a path of half arcs leading from start.
LabeledSubgraph represents a subgraph mapped to a supergraph.
LabeledUndirected represents an undirected labeled graph.
LabeledUndirectedSubgraph represents a subgraph mapped to a supergraph.
PathEnd associates a half arc and a path length.
Subgraph represents a subgraph mapped to a supergraph.
Undirected represents an undirected graph.
UndirectedSubgraph represents a subgraph mapped to a supergraph.
WeightedEdgeList is a graph representation.

# Type aliases

An AdjacencyList represents a graph as a list of neighbors for each node.
A DistanceMatrix is a square matrix representing some distance between nodes of a graph.
DominanceFrontiers holds dominance frontiers for all nodes in some graph.
An EdgeVisitor is an argument to some traversal methods.
A Heuristic is defined on a specific end node.
A LabeledAdjacencyList represents a graph as a list of neighbors for each node, connected by labeled arcs.
A LabeledEdgeVisitor is an argument to some traversal methods.
LI is a label integer, used for associating labels with arcs.
NI is a "node int" It is a node number or node ID.
PathMatrix is a return type for FloydWarshallPaths.
WeightFunc returns a weight for a given label.