graph: Index | Files | Directories

package graph

import ""

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 Predecessors where applicable, if undirected, it will use Neighbors 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.


Package Files

doc.go graph.go

type CostDirectedGraph

type CostDirectedGraph interface {

type CostFunc

type CostFunc func(Edge) float64

A function that returns the cost of following an edge

type CostGraph

type CostGraph interface {

type Coster

type Coster interface {
    Cost(Edge) float64

A Graph that implements Coster has an actual cost between adjacent nodes, also known as a weighted graph. If a graph implements coster and a function needs to read cost (e.g. A*), this function will take precedence over the Uniform Cost function (all weights are 1) if "nil" is passed in for the function argument.

If the argument is nil, or the edge is invalid for some reason, this should return math.Inf(1)

type DirectedEdgeListGraph

type DirectedEdgeListGraph interface {

type DirectedEdgeLister

type DirectedEdgeLister interface {
    DirectedEdgeList() []Edge

Returns all directed edges in the graph.

type DirectedGraph

type DirectedGraph interface {
    // Successors gives the nodes connected by OUTBOUND edges.
    // If the graph is an undirected graph, this set is equal to Predecessors.
    Successors(Node) []Node

    // EdgeTo returns an edge between node and successor such that
    // From returns node and To returns successor, if no
    // such edge exists, this function returns nil.
    EdgeTo(node, successor Node) Edge

    // Predecessors gives the nodes connected by INBOUND edges.
    // If the graph is an undirected graph, this set is equal to Successors.
    Predecessors(Node) []Node

Directed graphs are characterized by having seperable Heads and Tails in their edges. That is, if node1 goes to node2, that does not necessarily imply that node2 goes to node1.

While it's possible for a directed graph to have fully reciprocal edges (i.e. the graph is symmetric) -- it is not required to be. The graph is also required to implement Graph because in many cases it can be useful to know all neighbors regardless of direction.

type Edge

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

Allows edges to do something more interesting that just be a group of nodes. While the methods are called From and To, they are not considered directed unless the given interface specifies otherwise.

type EdgeListGraph

type EdgeListGraph interface {

type EdgeLister

type EdgeLister interface {
    EdgeList() []Edge

Returns all undirected edges in the graph

type Graph

type Graph interface {
    // NodeExists returns true when node is currently in the graph.
    NodeExists(Node) bool

    // NodeList returns a list of all nodes in no particular order, useful for
    // determining things like if a graph is fully connected. The caller is
    // free to modify this list. Implementations should construct a new list
    // and not return internal representation.
    NodeList() []Node

    // Neighbors returns all nodes connected by any edge to this node.
    Neighbors(Node) []Node

    // EdgeBetween returns an edge between node and neighbor such that
    // From is one argument and To is the other. If no
    // such edge exists, this function returns nil.
    EdgeBetween(node, neighbor Node) Edge

A Graph implements the behavior of an undirected graph.

All methods in Graph are implicitly undirected. Graph algorithms that care about directionality will intelligently choose the DirectedGraph behavior if that interface is also implemented, even if the function itself only takes in a Graph (or a super-interface of graph).

type HeuristicCostFunc

type HeuristicCostFunc func(Node, Node) float64

Estimates the cost of travelling between two nodes

type HeuristicCoster

type HeuristicCoster interface {
    // HeuristicCost returns a heuristic cost between any two nodes.
    HeuristicCost(n1, n2 Node) float64

A graph that implements HeuristicCoster implements a heuristic between any two given nodes. Like Coster, if a graph implements this and a function needs a heuristic cost (e.g. A*), this function will take precedence over the Null Heuristic (always returns 0) if "nil" is passed in for the function argument. If HeuristicCost is not intended to be used, it can be implemented as the null heuristic (always returns 0).

type Mutable

type Mutable interface {
    // NewNode returns a node with a unique arbitrary ID.
    NewNode() Node

    // Adds a node to the graph. If this is called multiple times for the same ID, the newer node
    // overwrites the old one.

    // RemoveNode removes a node from the graph, as well as any edges
    // attached to it. If no such node exists, this is a no-op, not an error.

A Mutable is a graph that can have arbitrary nodes and edges added or removed.

Anything implementing Mutable is required to store the actual argument. So if AddNode(myNode) is called and later a user calls on the graph graph.NodeList(), the node added by AddNode must be an the exact node, not a new node with the same ID.

In any case where conflict is possible (e.g. adding two nodes with the same ID), the later call always supercedes the earlier one.

Functions will generally expect one of MutableGraph or MutableDirectedGraph and not Mutable itself. That said, any function that takes Mutable[x], the destination mutable should always be a different graph than the source.

type MutableDirectedGraph

type MutableDirectedGraph interface {

    // Like EdgeTo in DirectedGraph, AddDirectedEdge adds an edge FROM From TO To.
    // If one or both nodes do not exist, the graph is expected to add them. However,
    // if the nodes already exist it should NOT replace existing nodes with e.From() or
    // e.To(). Overwriting nodes should explicitly be done with another call to AddNode()
    AddDirectedEdge(e Edge, cost float64)

    // Removes an edge FROM e.From TO e.To. If no such edge exists, this is a no-op,
    // not an error.

MutableDirectedGraph is an interface that ensures one can construct an arbitrary directed graph. Naturally, a MutableDirectedGraph works for both undirected and directed cases, but simply using a MutableGraph may be cleaner. As the documentation for MutableGraph notes, however, a graph cannot safely implement MutableGraph and MutableDirectedGraph at the same time, because of the functionality of a EdgeTo in DirectedGraph.

type MutableGraph

type MutableGraph interface {

    // Like EdgeBetween in Graph, AddUndirectedEdge adds an edge between two nodes.
    // If one or both nodes do not exist, the graph is expected to add them. However,
    // if the nodes already exist it should NOT replace existing nodes with e.From() or
    // e.To(). Overwriting nodes should explicitly be done with another call to AddNode()
    AddUndirectedEdge(e Edge, cost float64)

    // RemoveEdge clears the stored edge between two nodes. Calling this will never
    // remove a node. If the edge does not exist this is a no-op, not an error.

MutableGraph is an interface ensuring the implementation of the ability to construct an arbitrary undirected graph. It is very important to note that any implementation of MutableGraph absolutely cannot safely implement the DirectedGraph interface.

A MutableGraph is required to store any Edge argument in the same way Mutable must store a Node argument -- any retrieval call is required to return the exact supplied edge. This is what makes it incompatible with DirectedGraph.

The reasoning is this: if you call AddUndirectedEdge(Edge{head,tail}); you are required to return the exact edge passed in when a retrieval method (EdgeTo/EdgeBetween) is called. If I call EdgeTo(tail,head), this means that since the edge exists, and was added as Edge{head,tail} this function MUST return Edge{head,tail}. However, EdgeTo requires this be returned as Edge{tail,head}. Thus there's a conflict that cannot be resolved between the two interface requirements.

type Node

type Node interface {
    ID() int

All a node needs to do is identify itself. This allows the user to pass in nodes more interesting than an int, but also allow us to reap the benefits of having a map-storable, comparable type.


networkPackage network provides network analysis functions.

Package graph is imported by 4 packages. Updated 2015-05-25. Refresh now. Tools for package owners.