graph: github.com/gonum/graph Index | Files | Directories

package graph

import "github.com/gonum/graph"

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

Package Files

doc.go graph.go undirect.go

func Copy

func Copy(dst Builder, src Graph)

Copy copies nodes and edges as undirected edges from the source to the destination without first clearing the destination. Copy will panic if a node ID in the source graph matches a node ID in the destination.

If the source is undirected and the destination is directed both directions will be present in the destination after the copy is complete.

If the source is a directed graph, the destination is undirected, 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. If there is a defined function to resolve such conflicts, an Undirect may be used to do this.

type Builder

type Builder interface {
    NodeAdder
    EdgeSetter
}

Builder is a graph that can have nodes and edges added.

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 DirectedBuilder

type DirectedBuilder interface {
    Directed
    Builder
}

DirectedBuilder is a directed graph builder.

type Edge

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

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

type EdgePair

type EdgePair struct {
    E   [2]Edge
    W   float64
}

EdgePair is an opposed pair of directed edges.

func (EdgePair) From

func (e EdgePair) From() Node

From returns the from node of the first non-nil edge, or nil.

func (EdgePair) To

func (e EdgePair) To() Node

To returns the to node of the first non-nil edge, or nil.

func (EdgePair) Weight

func (e EdgePair) Weight() float64

Weight returns the merged edge weights of the two edges.

type EdgeRemover

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

EdgeRemover is an interface for removing nodes from a graph.

type EdgeSetter

type EdgeSetter interface {
    // SetEdge adds an edge from one node to another.
    // If the graph supports node addition the nodes
    // will be added if they do not exist, otherwise
    // SetEdge will panic.
    // If the IDs returned by e.From and e.To are
    // equal, SetEdge will panic.
    SetEdge(e Edge)
}

EdgeSetter is an interface for adding edges to a graph.

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

    // HasEdgeBeteen returns whether an edge exists between
    // nodes x and y without considering direction.
    HasEdgeBetween(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 Node

type Node interface {
    ID() int
}

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

type NodeAdder

type NodeAdder 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)
}

NodeAdder is an interface for adding arbitrary nodes to a graph.

type NodeRemover

type NodeRemover interface {
    // 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)
}

NodeRemover is an interface for removing nodes from a graph.

type Undirect

type Undirect struct {
    G   Directed

    // Absent is the value used to
    // represent absent edge weights
    // passed to Merge if the reverse
    // edge is present.
    Absent float64

    // Merge defines how discordant edge
    // weights in G are resolved. A merge
    // is performed if at least one edge
    // exists between the nodes being
    // considered. The edges corresponding
    // to the two weights are also passed,
    // in the same order.
    // The order of weight parameters
    // passed to Merge is not defined, so
    // the function should be commutative.
    // If Merge is nil, the arithmetic
    // mean is used to merge weights.
    Merge func(x, y float64, xe, ye Edge) float64
}

Undirect converts a directed graph to an undirected graph, resolving edge weight conflicts.

func (Undirect) Edge

func (g Undirect) Edge(u, v Node) Edge

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. If an edge exists, the Edge returned is an EdgePair. The weight of the edge is determined by applying the Merge func to the weights of the edges between u and v.

func (Undirect) EdgeBetween

func (g Undirect) EdgeBetween(x, y Node) Edge

EdgeBetween returns the edge between nodes x and y. If an edge exists, the Edge returned is an EdgePair. The weight of the edge is determined by applying the Merge func to the weights of edges between x and y.

func (Undirect) From

func (g Undirect) From(u Node) []Node

From returns all nodes in g that can be reached directly from u.

func (Undirect) Has

func (g Undirect) Has(n Node) bool

Has returns whether the node exists within the graph.

func (Undirect) HasEdgeBetween

func (g Undirect) HasEdgeBetween(x, y Node) bool

HasEdgeBetween returns whether an edge exists between nodes x and y.

func (Undirect) Nodes

func (g Undirect) Nodes() []Node

Nodes returns all the nodes in the graph.

func (Undirect) Weight

func (g Undirect) Weight(x, y Node) (w float64, ok bool)

Weight returns the weight for the edge between x and y if Edge(x, y) returns a non-nil Edge. If x and y are the same node the internal node weight is returned. If there is no joining edge between the two nodes the weight value returned is zero. Weight returns true if an edge exists between x and y or if x and y have the same ID, false otherwise.

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 UndirectedBuilder

type UndirectedBuilder interface {
    Undirected
    Builder
}

UndirectedBuilder is an undirected graph builder.

type Weighter

type Weighter interface {
    // Weight returns the weight for the edge between
    // x and y if Edge(x, y) returns a non-nil Edge.
    // If x and y are the same node or there is no
    // joining edge between the two nodes the weight
    // value returned is implementation dependent.
    // Weight returns true if an edge exists between
    // x and y or if x and y have the same ID, false
    // otherwise.
    Weight(x, y Node) (w float64, ok bool)
}

Weighter defines graphs that can report edge weights.

Directories

PathSynopsis
communityPackage community provides graph community detection functions.
encoding/dotPackage dot implements GraphViz DOT marshaling of graphs.
graphs/genPackage gen provides random graph generation functions.
internal/linearPackage linear provides common linear data structures.
internal/orderedPackage ordered provides common sort ordering types.
internal/setPackage set provides integer and graph.Node sets.
networkPackage network provides network analysis functions.
path
path/dynamic
path/internal
path/internal/testgraphs
simplePackage simple provides a suite of simple graph implementations satisfying the gonum/graph interfaces.
topo
traversePackage traverse provides basic graph traversal primitives.

Package graph imports 1 packages (graph) and is imported by 41 packages. Updated 2016-02-07. Refresh now. Tools for package owners.