digraph

package module
v1.1.5 Latest Latest
Warning

This package is not in the latest version of its module.

 Go to latest Published: Oct 6, 2021 License: Apache-2.0 Imports: 2 Imported by: 1

README

Digraph

GoDoc Go Report

This package provides the digraph package that implements a directed graph data structure. Nodes and edges may be labeled. The graph supports application-defined structs as nodes and edges.

The graph structure is designed so that nodes know the outgoing edges, and edges know both the source and target nodes. The graph structure itself knows only "some" of the nodes, so retrieving all the nodes of the graph or accessing nodes by label requires an intermediate structure, the NodeIndex. A NodeIndex discovers all nodes when requested, and then provides indexes access to the nodes. A NodeIndex only sees the nodes that were accessible from the Graph when it is created, thus it does not provide a dynamic view of the graph.

Digraph is not thread-safe.

Example

Construct a graph, and add nodes:

g:=digraph.New()
node1:=digraph.NewBasicNode("node1",nil)
node2:=digraph.NewBasicNode("node2",nil)

Connect the nodes with edges:

// edge node1 --edge1--> node2
edge:=g.NewBasicEdge("edge1",nil)
digraph.Connect(node1,node2,edge)

Get the nodes accessible via a label:

n:=node1.Next("edge1")

If there are multiple, iterate:

edges:=node1.GetAllOutgoingEdgesWithLabel("edge1")
for edges.HasNext() {
   edge:=edges.Next()
}

The BasicNode and BasicEdge contains an application-defined Payload field. This allows for container/list style graph container. It is also possible to use application-specific node and edge objects.

type CustomNode struct {
  digraph.NodeHeader
  // other fields
}

type CustomEdge struct {
  digraph.EdgeHeader
  // other fields
}

The *CustomNode and *CustomEdge instances can be added to the graph. The embeded NodeHeader and EdgeHeader connects the object to the underlying graph.

Documentation

Index

Constants

This section is empty.

Variables

This section is empty.

Functions

func CheckIsomorphism added in v1.1.2 

func CheckIsomorphism(nodes1, nodes2 *Index, nodeEquivalenceFunc func(n1, n2 Node) bool, edgeEquivalenceFunc func(e1, e2 Edge) bool) bool

CheckIsomoprhism checks to see if graphs whose node indexes are given are equal as defined by the edge equivalence and node equivalence functions. The nodeEquivalenceFunction will be called for nodes whose labels are the same. The edgeEquivalenceFunction will be called for edges connecting equivalent nodes with the same labels.

Node isomorphism check will fail if one node is equivalent to multiple nodes

func Connect added in v1.1.1 

func Connect(from, to Node, edge Edge)

Connect two nodes with the given edge. The edge must not be connected before

func Copy added in v1.0.4 

func Copy(target *Graph, source *Index, copyNode func(Node) Node, copyEdge func(Edge) Edge) map[Node]Node

Copy creates a copy of source graph in target. If target is an empty graph, the result is a clone of the source graph. If target is not empty, after this operation target gets a subgraph that is a copy of the source

copyNode function copies the given node, and returns the new node. If it returns nil, the node is not copied. copyEdge function does the same, creates a copy of the given edge without connecting the edges to any of the nodes. The returned edge will be connected to the matching nodes.

Returns a map of nodes where the key is the node in the source graph, and value is the corresponding node in the target graph

func CopyGraph added in v1.1.2 

func CopyGraph(target, source *Graph, copyNode func(Node) Node, copyEdge func(Edge) Edge) map[Node]Node

CopyGraph creates a copy of source graph in target. If target is an empty graph, the result is a clone of the source graph. If target is not empty, after this operation target gets a subgraph that is a copy of the source

copyNode function copies the given node, and returns the new node. If it returns nil, the node is not copied. copyEdge function does the same, creates a copy of the given edge without connecting the edges to any of the nodes. The returned edge will be connected to the matching nodes.

Returns a map of nodes where the key is the node in the source graph, and value is the corresponding node in the target graph

func DefaultDOTEdgeRender 

func DefaultDOTEdgeRender(fromNode, toNode string, edge Edge, w io.Writer) error

DefaultDOTEdgeRender renders the edge with a label if there is one, or without a label if there is not a label.

func DefaultDOTNodeRender 

func DefaultDOTNodeRender(ID string, node Node, w io.Writer) error

DefaultDOTNodeRender renders the node with the given ID. If the node has a label, it uses that label, otherwise node is not labeled.

func Iterate added in v1.1.2 

func Iterate(root Node, nodeFunc func(Node) bool, edgeFunc func(Edge) bool) bool

Iterate all nodes and edges of the graph until one of the functions returns false

func IterateGraph added in v1.1.3 

func IterateGraph(g *Graph, nodeFunc func(Node) bool, edgeFunc func(Edge) bool) bool

IterateGraph iterates all nodes and edges of the graph until one of the functions returns false

func IterateUnique added in v1.1.2 

func IterateUnique(root Node, nodeFunc func(Node) bool, edgeFunc func(Edge) bool, seen map[Node]struct{}) bool

IterateUnique iterates all nodes and edges until one of the functions returns false. It skips the nodes in the seen map

func NodesByLabelPredicate added in v1.1.1 

func NodesByLabelPredicate(id interface{}) func(Node) bool

NodesByLabelPredicate returns a predicate that select nodes by label. This is to be used in Nodes.Select

Types

type BasicEdge 

type BasicEdge struct {
	EdgeHeader
	Payload interface{}
}

BasicEdge contains an application-defined payload

func NewBasicEdge 

func NewBasicEdge(label, payload interface{}) *BasicEdge

NewBasicEdge returns a new unconnected edge with the given label and payload

type BasicNode 

type BasicNode struct {
	NodeHeader
	Payload interface{}
}

BasicNode contains an application defined payload

func NewBasicNode 

func NewBasicNode(label, payload interface{}) *BasicNode

type DOTRenderer 

type DOTRenderer struct {
	// NodeRenderer renderes a node. If the node is to be excluded, returns false.
	NodeRenderer func(string, Node, io.Writer) (bool, error)
	// EdgeRenderer renders an edge. The from and to nodes are rendered
	// if this is called. If the edge is to be excluded, returns false
	EdgeRenderer func(fromID string, toID string, edge Edge, w io.Writer) (bool, error)
}

DOTRenderer renders a graph in Graphviz dot format

func (DOTRenderer) Render 

func (d DOTRenderer) Render(g *Graph, graphName string, out io.Writer) error

Render writes a DOT graph with the given name

func (DOTRenderer) RenderEdge 

func (d DOTRenderer) RenderEdge(fromID, toID string, edge Edge, w io.Writer) (bool, error)

RenderEdge renders an edge. If edge renderer is not set, call the default rendeded

func (DOTRenderer) RenderNode 

func (d DOTRenderer) RenderNode(ID string, node Node, w io.Writer) (bool, error)

RenderNode renders a node. If node renderer is not set, calls the default renderer

type Edge 

type Edge interface {
	// Return the label of the edge. Label cannot be changed. Remove the
	// edge and add a new one with a different label
	GetLabel() interface{}
	// Return the target node
	GetTo() Node
	// Return the source node
	GetFrom() Node

	// Remove an edge
	Disconnect()
	// contains filtered or unexported methods
}

Edge represents a labeled or unlabeled directed edge between two nodes of a graph

type EdgeHeader 

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

EdgeHeader must be embedded into every edge implementation

func NewEdgeHeader added in v1.1.1 

func NewEdgeHeader(label interface{}) EdgeHeader

NewEdgeHeader returns a new constructed edge header with the given label

func (*EdgeHeader) Disconnect added in v1.1.1 

func (hdr *EdgeHeader) Disconnect()

Disconnect an edge

func (*EdgeHeader) GetFrom added in v1.1.1 

func (hdr *EdgeHeader) GetFrom() Node

GetFrom returns the source node of the edge

func (*EdgeHeader) GetLabel added in v1.1.1 

func (hdr *EdgeHeader) GetLabel() interface{}

GetLabel returns the edge label. Once set, label cannot be changed

func (*EdgeHeader) GetTo added in v1.1.1 

func (hdr *EdgeHeader) GetTo() Node

GetTo returns the target node of the edge

type EdgeIterator added in v1.0.3 

type EdgeIterator interface {
	// Returns if there are more edges to go through
	HasNext() bool
	// If HasNext is true, returns the next edge and advances. Otherwise panics
	Next() Edge
}

EdgeIterator iterates through a list of edges

type Edges 

type Edges struct {
	EdgeIterator
}

Edges is a wrapper around edge iterator

func NewEdges added in v1.1.2 

func NewEdges(edge ...Edge) Edges

NewEdges returns an edge iterator for the edges

func (Edges) All 

func (e Edges) All() []Edge

All returns all remaining edges

func (Edges) Select added in v1.1.2 

func (e Edges) Select(predicate func(Edge) bool) Edges

Select returns a subset of the given edges containing only those edges selected by the predicate

func (Edges) Targets 

func (e Edges) Targets() Nodes

Targets returns a node iterator that goes through the target nodes

type Graph 

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

A Graph is a labeled directed graph. The labels can be nil. Zero value of a Graph is ready to use.

A graph knows some of the nodes of the graph. The remaining nodes are discovered when needd. This allows a graph to have multiple disjoint components.

Two graphs can be merged simply by adding an edge between their two nodes. Then the graph containing the source node of the edge will include all the accessible nodes of the second graph.

func New 

func New() *Graph

New returns a new empty graph

func (*Graph) AddNode 

func (g *Graph) AddNode(node Node)

AddNode adds the node to the graph. The node can be the node of a disconnected graph.

func (*Graph) GetAllNodes added in v1.1.1 

func (g *Graph) GetAllNodes() Nodes

GetAllNodes returns an iterator over all nodes of a graph

func (*Graph) GetIndex added in v1.1.2 

func (g *Graph) GetIndex() *Index

GetIndex returns an uninitialized index for the graph

type Index added in v1.1.2 

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

Index provides indexed access to all nodes and edges of an underlying graph. The index is lazily constructed to include all nodes and edges. Index is constructed by accessible nodes and edges, thus the underlying graph should not be modified.

func (*Index) In added in v1.1.2 

func (index *Index) In(node Node) Edges

In returns the incoming edges of a node. These will include only those edges that are from the nodes included in this graph

func (*Index) InSlice added in v1.1.2 

func (index *Index) InSlice(node Node) []Edge

InSlice returns the incoming edges of a node. These will include only those edges that are from the nodes included in this graph

func (*Index) InWith added in v1.1.2 

func (index *Index) InWith(node Node, label interface{}) Edges

InWith returns the incoming edges of a node by label. These will include only those edges that are from the nodes included in this graph

func (*Index) InWithSlice added in v1.1.2 

func (index *Index) InWithSlice(node Node, label interface{}) []Edge

InWithSlice returns the incoming edges of a node by label. These will include only those edges that are from the nodes included in this graph

func (*Index) Nodes added in v1.1.2 

func (index *Index) Nodes() Nodes

Nodes returns an iterator over all nodes

func (*Index) NodesByLabel added in v1.1.2 

func (index *Index) NodesByLabel(label interface{}) Nodes

NodesByLabel returns nodes by label

func (*Index) NodesByLabelSlice added in v1.1.2 

func (index *Index) NodesByLabelSlice(label interface{}) []Node

NodesByLabel returns an iterator of nodes with the given label

func (*Index) NodesSlice added in v1.1.2 

func (index *Index) NodesSlice() []Node

NodesSlice returns all accessible nodes as a slice

func (*Index) Out added in v1.1.2 

func (index *Index) Out(node Node) Edges

Out returns the outgoing edges of a node

func (*Index) OutSlice added in v1.1.2 

func (index *Index) OutSlice(node Node) []Edge

Out returns the outgoing edges of a node

func (*Index) OutWith added in v1.1.2 

func (index *Index) OutWith(node Node, label interface{}) Edges

OutWith returns the outgoing edges of a node with a label

func (*Index) OutWithSlice added in v1.1.2 

func (index *Index) OutWithSlice(node Node, label interface{}) []Edge

OutWithSlice returns the outgoing edges of a node with a label

type Node 

type Node interface {
	GetLabel() interface{}
	SetLabel(interface{})

	// Returns if the node has any outgoing edges
	HasOut() bool
	// Returns all outgoing edges of the node
	Out() Edges
	// Returns the outgoing edges with the given label
	OutWith(interface{}) Edges

	// Returns all directly accessible nodes
	Next() []Node

	// Returns all directly accessible nodes with label
	NextWith(interface{}) []Node
	// contains filtered or unexported methods
}

Node of a directed graph. The node can contain a label

func Sinks 

func Sinks(index *Index) []Node

Sinks returns all nodes that have no outgoing edges.

func Sources 

func Sources(index *Index) []Node

Sources returns all nodes that have no incoming edges.

type NodeHeader 

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

NodeHeader must be embedded into every node

func (*NodeHeader) GetLabel added in v1.1.1 

func (hdr *NodeHeader) GetLabel() interface{}

GetLabel returns the node label

func (*NodeHeader) HasOut added in v1.1.2 

func (hdr *NodeHeader) HasOut() bool

HasOut returns true if the node has outgoing edges

func (*NodeHeader) Next added in v1.1.1 

func (hdr *NodeHeader) Next() []Node

Next returns all next nodes

func (*NodeHeader) NextWith added in v1.1.2 

func (hdr *NodeHeader) NextWith(label interface{}) []Node

NextWith returns all next nodes reachable with label

func (*NodeHeader) Out added in v1.1.2 

func (hdr *NodeHeader) Out() Edges

Out returns all outgoing edges of the node

func (*NodeHeader) OutWith added in v1.1.2 

func (hdr *NodeHeader) OutWith(label interface{}) Edges

OutWith returns all edges with the given label

func (*NodeHeader) SetLabel 

func (hdr *NodeHeader) SetLabel(label interface{})

SetLabel sets the node label

type NodeIterator added in v1.0.3 

type NodeIterator interface {
	// Returns if there are more nodes to go through
	HasNext() bool
	// If HasNext is true, returns the next node and advances. Otherwise, panics
	Next() Node
}

NodeIterator iterates through a list of nodes

type Nodes 

type Nodes struct {
	NodeIterator
}

Nodes is a convenience wrapper aroung NodeItr for chained methods

func NewNodeSliceIterator added in v1.1.2 

func NewNodeSliceIterator(nodes ...Node) Nodes

NewNodeSliceIterator returns a Nodes for the given array of nodes

func NewNodeWalkIterator added in v1.1.2 

func NewNodeWalkIterator(nodes ...Node) Nodes

NewNodeWalkIterator returns a Nodes that walks through all the nodes accessible from the given nodes

func (Nodes) All 

func (n Nodes) All() []Node

All returns all remaining nodes

func (Nodes) Select added in v1.0.3 

func (n Nodes) Select(predicate func(Node) bool) Nodes

Select returns a subset of the given nodes containing only those nodes selected by the predicate

func (Nodes) Unique added in v1.1.1 

func (n Nodes) Unique() Nodes

Unique filters the nodes so only unique nodes are returned

Source Files

View all Source files

Jump to

Keyboard shortcuts

? : This menu
/ : Search site
f or F : Jump to
y or Y : Canonical URL
go.dev uses cookies from Google to deliver and enhance the quality of its services and to analyze traffic. Learn more.