graph

Documentation

Overview

Package graph provides interfaces and basic representations for graphs.

Sub-packages provide common graph algorithms.

Index

• func Equal(g1, g2 Graph) bool
• type BiGraph
  • func MakeBiGraph(g Graph) BiGraph
• type Edge
• type Graph
• type IntGraph
  • func (g IntGraph) NumNodes() int
  • func (g IntGraph) Out(i int) []int
• type Subgraph
  • func SubgraphKeep(g Graph, nodes []int, edges []Edge) Subgraph
  • func SubgraphRemove(g Graph, nodes []int, edges []Edge) Subgraph
• type Weighted
• type WeightedUnit
  • func (w WeightedUnit) OutWeight(i, e int) float64

Functions

func Equal

func Equal(g1, g2 Graph) bool

Equal returns true if g1 and g2 have identical nodes and edges, including the IDs of all nodes.

Types

type BiGraph

type BiGraph interface {
	Graph

	// In returns the nodes which point to node i.
	In(i int) []int
}

BiGraph extends Graph to graphs that represent both out-edges and in-edges.

func MakeBiGraph

func MakeBiGraph(g Graph) BiGraph

MakeBiGraph constructs a BiGraph from what may be a unidirectional Graph. If g is already a BiGraph, this returns g.

type Edge

type Edge struct {
	Node int // Node ID
	Edge int // Edge index
}

Edge identifies an edge in a graph. Given Graph g, Edge e represents edge g.Out(e.Node)[e.Edge].

type Graph

type Graph interface {
	// NumNodes returns the number of nodes in this graph.
	NumNodes() int

	// Out returns the nodes to which node i points.
	Out(i int) []int
}

Graph represents a directed graph. The nodes of the graph must be densely numbered starting at 0.

type IntGraph

type IntGraph [][]int

IntGraph is a basic Graph g where g[i] is the list of out-edge indexes of node i.

func (IntGraph) NumNodes

func (g IntGraph) NumNodes() int

func (IntGraph) Out

func (g IntGraph) Out(i int) []int

type Subgraph

type Subgraph interface {
	Graph

	// Underlying returns the underlying graph that this is a
	// subgraph of.
	Underlying() Graph

	// NodeMap transduces a node property map on the underlying
	// graph into a node property map on this graph.
	NodeMap(underlyingMap func(node int) interface{}) func(node int) interface{}

	// EdgeMap transduces an edge property map on the underlying
	// graph into an edge property map on this graph.
	EdgeMap(underlyingMap func(node, edge int) interface{}) func(node, edge int) interface{}
}

A Subgraph is a Graph that consists of a subset of the nodes and vertices from another, underlying Graph.

func SubgraphKeep

func SubgraphKeep(g Graph, nodes []int, edges []Edge) Subgraph

SubgraphKeep returns a subgraph of g that keeps the given nodes and edges. Subgraph node i corresponds to nodes[i] in g.

func SubgraphRemove

func SubgraphRemove(g Graph, nodes []int, edges []Edge) Subgraph

SubgraphRemove returns a subgraph of g that removes the given nodes and edges from g, as well as all edges incident to those nodes.

type Weighted

type Weighted interface {
	Graph

	// OutWeight returns the weight of the e'th edge out from node
	// i. e must be in the range [0, len(Out(i))).
	OutWeight(i, e int) float64
}

Weighted represented a weighted directed graph.

type WeightedUnit

type WeightedUnit struct {
	Graph
}

WeightedUnit wraps a graph as a weighted graph where all edges have weight 1.

func (WeightedUnit) OutWeight

func (w WeightedUnit) OutWeight(i, e int) float64

OutWeight returns 1.