simple

Documentation

Overview

Package simple provides a suite of simple graph implementations satisfying the gonum/graph interfaces.

Index

• type DirectedAcyclicGraph
  • func NewDirectedAcyclicGraph(self, absent float64) *DirectedAcyclicGraph
  • func (g *DirectedAcyclicGraph) From(n graph.Node) []graph.Node
  • func (g *DirectedAcyclicGraph) HasEdgeFromTo(u, v graph.Node) bool
  • func (g *DirectedAcyclicGraph) To(n graph.Node) []graph.Node
  • func (g *DirectedAcyclicGraph) VisitFrom(n graph.Node, visitor func(neighbor graph.Node) (shouldContinue bool))
  • func (g *DirectedAcyclicGraph) VisitTo(n graph.Node, visitor func(neighbor graph.Node) (shouldContinue bool))
• type Edge
  • func (e Edge) From() graph.Node
  • func (e Edge) To() graph.Node
  • func (e Edge) Weight() float64
• type Node
  • func (n Node) ID() int
• type UndirectedGraph
  • func NewUndirectedGraph(self, absent float64) *UndirectedGraph
  • func (g *UndirectedGraph) AddNode(n graph.Node)
  • func (g *UndirectedGraph) Degree(n graph.Node) int
  • func (g *UndirectedGraph) Edge(u, v graph.Node) graph.Edge
  • func (g *UndirectedGraph) EdgeBetween(x, y graph.Node) graph.Edge
  • func (g *UndirectedGraph) Edges() []graph.Edge
  • func (g *UndirectedGraph) From(n graph.Node) []graph.Node
  • func (g *UndirectedGraph) Has(n graph.Node) bool
  • func (g *UndirectedGraph) HasEdgeBetween(x, y graph.Node) bool
  • func (g *UndirectedGraph) NewNodeID() int
  • func (g *UndirectedGraph) Node(id int) graph.Node
  • func (g *UndirectedGraph) Nodes() []graph.Node
  • func (g *UndirectedGraph) RemoveEdge(e graph.Edge)
  • func (g *UndirectedGraph) RemoveNode(n graph.Node)
  • func (g *UndirectedGraph) SetEdge(e graph.Edge)
  • func (g *UndirectedGraph) Weight(x, y graph.Node) (w float64, ok bool)

Types

type DirectedAcyclicGraph

type DirectedAcyclicGraph struct {
	*UndirectedGraph
}

DirectedAcyclicGraph implements graph.Directed using UndirectedGraph, which only stores one edge for any node pair.

func NewDirectedAcyclicGraph

func NewDirectedAcyclicGraph(self, absent float64) *DirectedAcyclicGraph

func (*DirectedAcyclicGraph) From

func (g *DirectedAcyclicGraph) From(n graph.Node) []graph.Node

func (*DirectedAcyclicGraph) HasEdgeFromTo

func (g *DirectedAcyclicGraph) HasEdgeFromTo(u, v graph.Node) bool

func (*DirectedAcyclicGraph) To

func (g *DirectedAcyclicGraph) To(n graph.Node) []graph.Node

func (*DirectedAcyclicGraph) VisitFrom

func (g *DirectedAcyclicGraph) VisitFrom(n graph.Node, visitor func(neighbor graph.Node) (shouldContinue bool))

func (*DirectedAcyclicGraph) VisitTo

func (g *DirectedAcyclicGraph) VisitTo(n graph.Node, visitor func(neighbor graph.Node) (shouldContinue bool))

type Edge

type Edge struct {
	F, T graph.Node
	W    float64
}

Edge is a simple graph edge.

func (Edge) From

func (e Edge) From() graph.Node

From returns the from-node of the edge.

func (Edge) To

func (e Edge) To() graph.Node

To returns the to-node of the edge.

func (Edge) Weight

func (e Edge) Weight() float64

Weight returns the weight of the edge.

type Node

type Node int

Node is a simple graph node.

func (Node) ID

func (n Node) ID() int

ID returns the ID number of the node.

type UndirectedGraph

type UndirectedGraph struct {
	// contains filtered or unexported fields
}

UndirectedGraph implements a generalized undirected graph.

func NewUndirectedGraph

func NewUndirectedGraph(self, absent float64) *UndirectedGraph

NewUndirectedGraph returns an UndirectedGraph with the specified self and absent edge weight values.

func (*UndirectedGraph) AddNode

func (g *UndirectedGraph) AddNode(n graph.Node)

AddNode adds n to the graph. It panics if the added node ID matches an existing node ID.

func (*UndirectedGraph) Degree

func (g *UndirectedGraph) Degree(n graph.Node) int

Degree returns the degree of n in g.

func (*UndirectedGraph) Edge

func (g *UndirectedGraph) Edge(u, v graph.Node) graph.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.

func (*UndirectedGraph) EdgeBetween

func (g *UndirectedGraph) EdgeBetween(x, y graph.Node) graph.Edge

EdgeBetween returns the edge between nodes x and y.

func (*UndirectedGraph) Edges

func (g *UndirectedGraph) Edges() []graph.Edge

Edges returns all the edges in the graph.

func (*UndirectedGraph) From

func (g *UndirectedGraph) From(n graph.Node) []graph.Node

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

func (*UndirectedGraph) Has

func (g *UndirectedGraph) Has(n graph.Node) bool

Has returns whether the node exists within the graph.

func (*UndirectedGraph) HasEdgeBetween

func (g *UndirectedGraph) HasEdgeBetween(x, y graph.Node) bool

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

func (*UndirectedGraph) NewNodeID

func (g *UndirectedGraph) NewNodeID() int

NewNodeID returns a new unique ID for a node to be added to g. The returned ID does not become a valid ID in g until it is added to g.

func (*UndirectedGraph) Node

func (g *UndirectedGraph) Node(id int) graph.Node

Node returns the node in the graph with the given ID.

func (*UndirectedGraph) Nodes

func (g *UndirectedGraph) Nodes() []graph.Node

Nodes returns all the nodes in the graph.

func (*UndirectedGraph) RemoveEdge

func (g *UndirectedGraph) RemoveEdge(e graph.Edge)

RemoveEdge removes e from the graph, leaving the terminal nodes. If the edge does not exist it is a no-op.

func (*UndirectedGraph) RemoveNode

func (g *UndirectedGraph) RemoveNode(n graph.Node)

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

func (*UndirectedGraph) SetEdge

func (g *UndirectedGraph) SetEdge(e graph.Edge)

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

func (*UndirectedGraph) Weight

func (g *UndirectedGraph) Weight(x, y graph.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 or there is no joining edge between the two nodes the weight value returned is either the graph's absent or self value. Weight returns true if an edge exists between x and y or if x and y have the same ID, false otherwise.