graph

package module
Version: v0.0.1 Latest Latest
Warning

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

Go to latest
Published: Aug 20, 2021 License: BSD-3-Clause Imports: 1 Imported by: 0

README

charles/graph

builds.sr.ht status go.dev reference

This repository implements a directed graph library in Go.

Documentation

Index

Constants

This section is empty.

Variables

This section is empty.

Functions

func CheckInt64PartialOrdering

func CheckInt64PartialOrdering(l []int64, u, v int64) bool

CheckInt64PartialOrdering returns true if and only if there exists no pair of indices (i,j) in l such that l[i]=u and l[j]=v and i>j. In other words, no instance of v is allowed to occur before any instance u.

If u and v do not each occur at least once in l, this function returns false.

func CompareEdgeLists

func CompareEdgeLists(l1, l2 []Edge) bool

CompareEdgeLists returns true if and only if every edge in l1 appears in l2 at least once, and every edge in l2 appears in l1 at least once.

func CompareInt64Lists

func CompareInt64Lists(l1, l2 []int64) bool

CompareInt64Lists implements the under-the-hood logic for CompareNodeLists() and CompareEdgeLists().

func CompareNodeLists

func CompareNodeLists(l1, l2 []Node) bool

CompareNodeLists returns true if and only if every node in l1 appears in l2 at least once, and every node in l2 appears in l1 at least once.

func RemoveInt64ByValue

func RemoveInt64ByValue(l []int64, val int64) []int64

RemoveInt64ByValue removes all instances of the specified value from the given list in-place.

Types

type Edge

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

Edge represents a handle to a specific edge in the graph. Edges are immutable, and internally contain an edge ID (referencing into the underlying data store), and a pointer to the underlying graph.

func (Edge) Data

func (e Edge) Data() (interface{}, error)

Data returns the data associated with the edge.

This function may error if the edge has been removed from the graph after the handle has been obtained.

func (Edge) Delete

func (e Edge) Delete() error

Delete removes the edge from the graph. After calling this function, the edge handle will become invalid, as will all other handles to this edge. Any data attached to the edge will also be deleted.

This function can error if the edge does not exist.

func (Edge) Exists

func (e Edge) Exists() bool

Exists is used to check if this handle references an extant edge (i.e. if the edge has been deleted after the handle was obtained).

func (Edge) ID

func (e Edge) ID() int64

ID returns the edge's ID.

func (Edge) MustData

func (e Edge) MustData() interface{}

MustData is a utility wrapper around Data() which panics on error.

func (Edge) MustSink

func (e Edge) MustSink() Node

MustSink is a utility wrapper around Sink() which panics on error.

func (Edge) MustSource

func (e Edge) MustSource() Node

MustSource is a utility wrapper around Source() which panics on error.

func (Edge) ReplaceData

func (e Edge) ReplaceData(data interface{}) error

ReplaceData replaces the data attached to the specified edge.

This function may error if the edge has been deleted.

func (Edge) Sink

func (e Edge) Sink() (Node, error)

Sink returns the sink node of the edge.

This function may error if the edge has been removed from the graph after the handle has been obtained.

func (Edge) Source

func (e Edge) Source() (Node, error)

Source returns the source node of the edge.

This function may error if the edge has been removed from the graph after the handle has been obtained.

type ErrIntegrity

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

ErrIntegrity is thrown when the requested operation could result in data corruption, for example deleting a node that would leave dangling edges.

func (*ErrIntegrity) Error

func (e *ErrIntegrity) Error() string

Error implements the error interface

type ErrNoSuchEdge

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

ErrNoSuchEdge is thrown when an operation is requested on an edge which does not exist.

func (*ErrNoSuchEdge) Error

func (e *ErrNoSuchEdge) Error() string

Error implements the error interface

type ErrNoSuchNode

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

ErrNoSuchNode is thrown when an operation is requested on a node which does not exist.

func (*ErrNoSuchNode) Error

func (e *ErrNoSuchNode) Error() string

Error implements the error interface

type Graph

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

Graph implements a directed graph.

func NewGraph

func NewGraph() *Graph

NewGraph instantiates a new empty Graph object.

func (*Graph) EdgeByID

func (g *Graph) EdgeByID(id int64) (Edge, bool)

EdgeByID retrieves the given edge by its ID, and a flag indicating if the edge exists or not. If the flag is false, the returned edge handle will not be valid.

func (*Graph) Edges

func (g *Graph) Edges() []Edge

Edges is a wrapper around ForEachEdge which collects all edges in the graph into a single slice, in an arbitrary order.

func (*Graph) EdgesBetween

func (g *Graph) EdgesBetween(source, sink Node) ([]Edge, error)

EdgesBetween returns a list of all edges which have the specified source and sink. This function is directed (edges from the sink to the source are not included).

This function may error if the source or sink do not exist.

func (*Graph) ForeachEdge

func (g *Graph) ForeachEdge(callback func(Edge) bool)

ForeachEdge runs the given callback on each edge in the graph in an arbitrary order.

The callback may return true to proceed, or false to stop iteration immediately.

func (*Graph) ForeachNode

func (g *Graph) ForeachNode(callback func(Node) bool)

ForeachNode runs the given callback on each node in the graph in an arbitrary order.

The callback may return true to proceed, or false to stop iteration immediately.

func (*Graph) MustEdgesBetween

func (g *Graph) MustEdgesBetween(source, sink Node) []Edge

MustEdgesBetween is a utility wrapper around EdgesBetween() that panics on error.

func (*Graph) MustNewEdgeWithData

func (g *Graph) MustNewEdgeWithData(source, sink Node, data interface{}) Edge

MustNewEdgeWithData is a utility wrapper around NewEdgeWithData() that panics on error.

func (*Graph) NewEdgeWithData

func (g *Graph) NewEdgeWithData(source, sink Node, data interface{}) (Edge, error)

NewEdgeWithData creates a new edge between the specified source and sink nodes, with the specified data.

This function may error if the source or sink do not exist, or if the SingleEdge tunable is asserted and an edge already exists between the given pair of nodes. In the latter case, the error will be of type ErrTunable.

func (*Graph) NewNodeWithData

func (g *Graph) NewNodeWithData(data interface{}) Node

NewNodeWithData creates a new node in the graph with the specified data, returning the node handle.

func (*Graph) NodeByID

func (g *Graph) NodeByID(id int64) (Node, bool)

NodeByID retrieves the given node by its ID, and a flag indicating if the node exists or not. If the flag is false, the returned node handle will not be valid.

func (*Graph) Nodes

func (g *Graph) Nodes() []Node

Nodes is a wrapper around ForEachNode which collects all nodes in the graph into a single slice, in an arbitrary order.

type Int64Queue

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

Int64Queue implements a simple FIFO queue for int64 data.

func NewInt64Queue

func NewInt64Queue() *Int64Queue

NewInt64Queue instantiates a new, empty queue.

func (*Int64Queue) Dequeue

func (q *Int64Queue) Dequeue() (int64, bool)

Dequeue removes the head of the queue and returns it, or else returns (-1, false) if the queue is empty.

func (*Int64Queue) Enqueue

func (q *Int64Queue) Enqueue(v int64)

Enqueue inserts a new item into the queue.

func (*Int64Queue) Len

func (q *Int64Queue) Len() int

Len returns the number of elements in the queue.

func (*Int64Queue) Peek

func (q *Int64Queue) Peek() (int64, bool)

Peek returns the head of the queue without removing it, or returns (-1, false) if the queue is empty.

type Int64Stack

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

Int64Stack implements a simple LIFO stack for int64 data.

func NewInt64Stack

func NewInt64Stack() *Int64Stack

NewInt64Stack instantiates a new, empty stack.

func (*Int64Stack) Len

func (s *Int64Stack) Len() int

Len returns the number of elements in the stack.

func (*Int64Stack) Peek

func (s *Int64Stack) Peek() (int64, bool)

Peek returns the top of the stack without removing it, or returns (-1, false) if the stack is empty.

func (*Int64Stack) Pop

func (s *Int64Stack) Pop() (int64, bool)

Pop removes and returns the top element of the stack, or (-1, false) if the stack is empty.

func (*Int64Stack) Push

func (s *Int64Stack) Push(v int64)

Push insert an item into the stack.

type Node

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

Node represents a handle to a specific node in the graph. Nodes are immutable, and internally contain a node ID (referencing into the underlying data store), and a pointer the underlying graph.

func (Node) Adjacent

func (n Node) Adjacent() ([]Node, error)

Adjacent is a utility wrapper around ForeachAdjacent() which returns a list of all nofes adjacent to the node.

func (Node) Ancestors

func (n Node) Ancestors() ([]Node, error)

Ancestors is a utility wrapper around ForeachAncestor() which returns a list of all ancestors to the node.

func (Node) BFS

func (n Node) BFS() ([]Node, error)

BFS is a wrapper around ForEachBFS which simply returns all nodes reachable from n in BFS traversal order.

func (Node) DFS

func (n Node) DFS() ([]Node, error)

DFS is a wrapper around ForEachDFS which simply returns all nodes reachable from n in DFS traversal order.

func (Node) Data

func (n Node) Data() (interface{}, error)

Data returns the data attached to the node. This method may error if the node has been deleted from the graph after this handle has been obtained.

func (Node) Delete

func (n Node) Delete() error

Delete removes the node from the graph. After calling this function, the node handle will become invalid, as will all other handles to this node. Any data attached to the node will also be deleted.

Deletion can error if the node does not exist, or if the deletion would result in dangling edges.

func (Node) Edges

func (n Node) Edges() ([]Edge, error)

Edges is a utility wrapper around ForeachEdge.

func (Node) Exists

func (n Node) Exists() bool

Exists is used to check if this handle references an extant node (i.e. if the node has been deleted after the handle was obtained).

func (Node) ForEachBFS

func (n Node) ForEachBFS(callback func(Node) bool) error

ForEachBFS implements a breadth-first traversal of the graph, rooted at node n. Each time a node is visited, the callback is run on it. The callback may return "true" to indicate the search should continue, and "false" to indicate that the search should terminate.

This function may error if the node has been deleted since the handle was obtained.

func (Node) ForEachDFS

func (n Node) ForEachDFS(callback func(Node) bool) error

ForEachDFS implements a breadth-first traversal of the graph, rooted at node n. Each time a node is visited, the callback is run on it. The callback may return "true" to indicate the search should continue, and "false" to indicate that the search should terminate.

This function may error if the node has been deleted since the handle was obtained.

func (Node) ForeachAdjacent

func (n Node) ForeachAdjacent(callback func(Node)) error

ForeachAdjacent runs the given callback once for each node which is either an ancestor or a successor to the given node. If the same node is both an ancestor and a successor, it will only be visited once.

This function may error if the node has been deleted from the graph after the handle was obtained.

func (Node) ForeachAncestor

func (n Node) ForeachAncestor(callback func(Node)) error

ForeachAncestor will execute the given callback once for each ancestor to the given node. An ancestor v of node u is a node such that there exists some edge (v,u). Even if multiple such edges (v,u) exist, the callback will only be run once for each ancestor.

This function may error if the node has been deleted from the graph after the handle was obtained.

func (Node) ForeachEdge

func (n Node) ForeachEdge(callback func(Edge)) error

ForeachEdge runs the given callback for each edge which has this node as either a source or a sink. In the case of duplicate edges (e.g. self-edges), the callback will still only be called once per edge.

This function may error if the node has been delete from the graph after the handle was obtained.

func (Node) ForeachInEdge

func (n Node) ForeachInEdge(callback func(Edge)) error

ForeachInEdge runs the given callback once for each edge which has this node as its sink.

This function may error if the node has been delete from the graph after the handle was obtained.

func (Node) ForeachOutEdge

func (n Node) ForeachOutEdge(callback func(Edge)) error

ForeachOutEdge runs the given callback once for each edge which has this node as its source.

This function may error if the node has been delete from the graph after the handle was obtained.

func (Node) ForeachSuccessor

func (n Node) ForeachSuccessor(callback func(Node)) error

ForeachSuccessor will execute the given callback once for each successor to the given node. A successor v of node u is a node such that there exists some edge (u, v). Even if multiple such edges (u, v) exist, the callback will only be run once for each successor.

This function may error if the node has been deleted from the graph after the handle was obtained.

func (Node) ID

func (n Node) ID() int64

ID returns the ID of the node.

func (Node) InEdges

func (n Node) InEdges() ([]Edge, error)

InEdges is a utility wrapper around ForeachInEdge.

func (Node) MustAdjacent

func (n Node) MustAdjacent() []Node

MustAdjacent is a utility wrapper around Adjacent() which panics on error.

func (Node) MustAncestors

func (n Node) MustAncestors() []Node

MustAncestors wraps Ancestors(), but panics on error.

func (Node) MustBFS

func (n Node) MustBFS() []Node

MustBFS is a utility wrapper around BFS() which panics on error.

func (Node) MustDFS

func (n Node) MustDFS() []Node

MustDFS is a utility wrapper around DFS() which panics on error.

func (Node) MustData

func (n Node) MustData() interface{}

MustData is a wrapper around Data() which panics on error.

func (Node) MustEdges

func (n Node) MustEdges() []Edge

MustEdges is a utility wrapper around Edges which panics on error.

func (Node) MustInEdges

func (n Node) MustInEdges() []Edge

MustInEdges is a utility wrapper around InEdges which panics on error.

func (Node) MustOutEdges

func (n Node) MustOutEdges() []Edge

MustOutEdges is a utility wrapper around OutEdges which panics on error.

func (Node) MustSuccessors

func (n Node) MustSuccessors() []Node

MustSuccessors is a utility wrapper around Successors() that panics on error.

func (Node) OutEdges

func (n Node) OutEdges() ([]Edge, error)

OutEdges is a utility wrapper around ForeachOutEdge.

func (Node) ReplaceData

func (n Node) ReplaceData(data interface{}) error

ReplaceData replaces the data attached to the specified node.

This function may error if the node has been deleted.

func (Node) Successors

func (n Node) Successors() ([]Node, error)

Successors is a utility wrapper around ForeachSuccessor() which returns a list of all successors to the node.

Directories

Path Synopsis
Package compatible implements a wrapper around graph.Graph which is compatible with gonum/graph.
Package compatible implements a wrapper around graph.Graph which is compatible with gonum/graph.

Jump to

Keyboard shortcuts

? : This menu
/ : Search site
f or F : Jump to
y or Y : Canonical URL