graph

README

Gonum Graph

This is a generalized graph package for the Go language. It aims to provide a clean, transparent API for common algorithms on arbitrary graphs such as finding the graph's strongly connected components, dominators, or searces.

The package is currently in testing, and the API is "semi-stable". The signatures of any functions like AStar are unlikely to change much, but the Graph, Node, and Edge interfaces may change a bit.

Issues

If you find any bugs, feel free to file an issue on the github issue tracker. Discussions on API changes, added features, code review, or similar requests are preferred on the Gonum-dev Google Group.

https://groups.google.com/forum/#!forum/gonum-dev

License

Please see github.com/gonum/license for general license information, contributors, authors, etc on the Gonum suite of packages.

Documentation

Overview

Package graph implements functions and interfaces to deal with formal discrete graphs. It aims to be first and foremost flexible, with speed as a strong second priority.

In this package, graphs are taken to be directed, and undirected graphs are considered to be a special case of directed graphs that happen to have reciprocal edges. Graphs are, by default, unweighted, but functions that require weighted edges have several methods of dealing with this. In order of precedence:

1. These functions have an argument called Cost (and in some cases, HeuristicCost). If this is present, it will always be used to determine the cost between two nodes.

2. These functions will check if your graph implements the Coster (and/or HeuristicCoster) interface. If this is present, and the Cost (or HeuristicCost) argument is nil, these functions will be used.

3. Finally, if no user data is supplied, it will use the functions UniformCost (always returns 1) and/or NulLHeuristic (always returns 0).

For information on the specification for Cost functions, please see the Coster interface.

Finally, although the functions take in a Graph -- they will always use the correct behavior. If your graph implements DirectedGraph, it will use Successors and To where applicable, if undirected, it will use From instead. If it implements neither, it will scan the edge list for successors and predecessors where applicable. (This is slow, you should always implement either Directed or Undirected)

This package will never modify a graph that is not Mutable (and the interface does not allow it to do so). However, return values are free to be modified, so never pass a reference to your own edge list or node list. It also guarantees that any nodes passed back to the user will be the same nodes returned to it -- that is, it will never take a Node's ID and then wrap the ID in a new struct and return that. You'll always get back your original data.

Index

• func CopyDirected(dst MutableDirected, src Graph)
• func CopyUndirected(dst MutableUndirected, src Graph)
• func UniformCost(e Edge) float64
• type Directed
• type Edge
• type Graph
• type Mutable
• type MutableDirected
• type MutableUndirected
• type Node
• type Undirected
• type WeightFunc
• type Weighter

Functions

func CopyDirected

func CopyDirected(dst MutableDirected, src Graph)

CopyDirected copies nodes and edges as directed edges from the source to the destination without first clearing the destination. CopyDirected will panic if a node ID in the source graph matches a node ID in the destination. If the source is undirected both directions will be present in the destination after the copy is complete. If the source does not implement Weighter, UniformCost is used to define edge weights.

func CopyUndirected

func CopyUndirected(dst MutableUndirected, src Graph)

CopyUndirected copies nodes and edges as undirected edges from the source to the destination without first clearing the destination. CopyUndirected will panic if a node ID in the source graph matches a node ID in the destination. If the source does not implement Weighter, UniformCost is used to define edge weights.

Note that if the source is a directed graph and a fundamental cycle exists with two nodes where the edge weights differ, the resulting destination graph's edge weight between those nodes is undefined.

func UniformCost

func UniformCost(e Edge) float64

UniformCost is a WeightFunc that returns an edge cost of 1 for a non-nil Edge and Inf for a nil Edge.

Types

type Directed

type Directed interface {
	Graph

	// HasEdgeFromTo returns whether an edge exists
	// in the graph from u to v.
	HasEdgeFromTo(u, v Node) bool

	// To returns all nodes that can reach directly
	// to the given node.
	To(Node) []Node
}

Directed is a directed graph.

type Edge

type Edge interface {
	From() Node
	To() Node
}

Edge is a graph edge. In directed graphs, the direction of the edge is given from -> to, otherwise the edge is semantically unordered.

type Graph

type Graph interface {
	// Has returns whether the node exists within the graph.
	Has(Node) bool

	// Nodes returns all the nodes in the graph.
	Nodes() []Node

	// From returns all nodes that can be reached directly
	// from the given node.
	From(Node) []Node

	// HasEdge returns whether an edge exists between
	// nodes x and y without considering direction.
	HasEdge(x, y Node) bool

	// Edge returns the edge from u to v if such an edge
	// exists and nil otherwise. The node v must be directly
	// reachable from u as defined by the From method.
	Edge(u, v Node) Edge
}

Graph is a generalized graph.

type Mutable

type Mutable interface {
	// NewNodeID returns a new unique arbitrary ID.
	NewNodeID() int

	// Adds a node to the graph. AddNode panics if
	// the added node ID matches an existing node ID.
	AddNode(Node)

	// RemoveNode removes a node from the graph, as
	// well as any edges attached to it. If the node
	// is not in the graph it is a no-op.
	RemoveNode(Node)

	// SetEdge adds an edge from one node to another.
	// If the nodes do not exist, they are added.
	// SetEdge will panic if the IDs of the e.From
	// and e.To are equal.
	SetEdge(e Edge, cost float64)

	// RemoveEdge removes the given edge, leaving the
	// terminal nodes. If the edge does not exist it
	// is a no-op.
	RemoveEdge(Edge)
}

Mutable is an interface for generalized graph mutation.

type MutableDirected

type MutableDirected interface {
	Directed
	Mutable
}

MutableDirected is a directed graph that can be arbitrarily altered.

type MutableUndirected

type MutableUndirected interface {
	Undirected
	Mutable
}

MutableUndirected is an undirected graph that can be arbitrarily altered.

type Node

type Node interface {
	ID() int
}

Node is a graph node. It returns a graph-unique integer ID.

type Undirected

type Undirected interface {
	Graph

	// EdgeBetween returns the edge between nodes x and y.
	EdgeBetween(x, y Node) Edge
}

Undirected is an undirected graph.

type WeightFunc

type WeightFunc func(Edge) float64

WeightFunc is a mapping between an edge and an edge weight.

type Weighter

type Weighter interface {
	// Weight returns the weight for the given edge.
	Weight(Edge) float64
}

Weighter defines graphs that can report edge weights.