README
¶
charles/graph
This repository implements a directed graph library in Go.
Documentation
¶
Index ¶
- func CheckInt64PartialOrdering(l []int64, u, v int64) bool
- func CompareEdgeLists(l1, l2 []Edge) bool
- func CompareInt64Lists(l1, l2 []int64) bool
- func CompareNodeLists(l1, l2 []Node) bool
- func RemoveInt64ByValue(l []int64, val int64) []int64
- type Edge
- func (e Edge) Data() (interface{}, error)
- func (e Edge) Delete() error
- func (e Edge) Exists() bool
- func (e Edge) ID() int64
- func (e Edge) MustData() interface{}
- func (e Edge) MustSink() Node
- func (e Edge) MustSource() Node
- func (e Edge) ReplaceData(data interface{}) error
- func (e Edge) Sink() (Node, error)
- func (e Edge) Source() (Node, error)
- type ErrIntegrity
- type ErrNoSuchEdge
- type ErrNoSuchNode
- type Graph
- func (g *Graph) EdgeByID(id int64) (Edge, bool)
- func (g *Graph) Edges() []Edge
- func (g *Graph) EdgesBetween(source, sink Node) ([]Edge, error)
- func (g *Graph) ForeachEdge(callback func(Edge) bool)
- func (g *Graph) ForeachNode(callback func(Node) bool)
- func (g *Graph) MustEdgesBetween(source, sink Node) []Edge
- func (g *Graph) MustNewEdgeWithData(source, sink Node, data interface{}) Edge
- func (g *Graph) NewEdgeWithData(source, sink Node, data interface{}) (Edge, error)
- func (g *Graph) NewNodeWithData(data interface{}) Node
- func (g *Graph) NodeByID(id int64) (Node, bool)
- func (g *Graph) Nodes() []Node
- type Int64Queue
- type Int64Stack
- type Node
- func (n Node) Adjacent() ([]Node, error)
- func (n Node) Ancestors() ([]Node, error)
- func (n Node) BFS() ([]Node, error)
- func (n Node) DFS() ([]Node, error)
- func (n Node) Data() (interface{}, error)
- func (n Node) Delete() error
- func (n Node) Edges() ([]Edge, error)
- func (n Node) Exists() bool
- func (n Node) ForEachBFS(callback func(Node) bool) error
- func (n Node) ForEachDFS(callback func(Node) bool) error
- func (n Node) ForeachAdjacent(callback func(Node)) error
- func (n Node) ForeachAncestor(callback func(Node)) error
- func (n Node) ForeachEdge(callback func(Edge)) error
- func (n Node) ForeachInEdge(callback func(Edge)) error
- func (n Node) ForeachOutEdge(callback func(Edge)) error
- func (n Node) ForeachSuccessor(callback func(Node)) error
- func (n Node) ID() int64
- func (n Node) InEdges() ([]Edge, error)
- func (n Node) MustAdjacent() []Node
- func (n Node) MustAncestors() []Node
- func (n Node) MustBFS() []Node
- func (n Node) MustDFS() []Node
- func (n Node) MustData() interface{}
- func (n Node) MustEdges() []Edge
- func (n Node) MustInEdges() []Edge
- func (n Node) MustOutEdges() []Edge
- func (n Node) MustSuccessors() []Node
- func (n Node) OutEdges() ([]Edge, error)
- func (n Node) ReplaceData(data interface{}) error
- func (n Node) Successors() ([]Node, error)
Constants ¶
This section is empty.
Variables ¶
This section is empty.
Functions ¶
func CheckInt64PartialOrdering ¶
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 ¶
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 ¶
CompareInt64Lists implements the under-the-hood logic for CompareNodeLists() and CompareEdgeLists().
func CompareNodeLists ¶
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 ¶
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 ¶
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 ¶
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 ¶
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) MustData ¶
func (e Edge) MustData() interface{}
MustData is a utility wrapper around Data() which panics on error.
func (Edge) MustSource ¶
MustSource is a utility wrapper around Source() which panics on error.
func (Edge) ReplaceData ¶
ReplaceData replaces the data attached to the specified edge.
This function may error if the edge has been deleted.
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 (*Graph) EdgeByID ¶
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 ¶
Edges is a wrapper around ForEachEdge which collects all edges in the graph into a single slice, in an arbitrary order.
func (*Graph) EdgesBetween ¶
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 ¶
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 ¶
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 ¶
MustEdgesBetween is a utility wrapper around EdgesBetween() that panics on error.
func (*Graph) MustNewEdgeWithData ¶
MustNewEdgeWithData is a utility wrapper around NewEdgeWithData() that panics on error.
func (*Graph) NewEdgeWithData ¶
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 ¶
NewNodeWithData creates a new node in the graph with the specified data, returning the node handle.
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.
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 ¶
Adjacent is a utility wrapper around ForeachAdjacent() which returns a list of all nofes adjacent to the node.
func (Node) Ancestors ¶
Ancestors is a utility wrapper around ForeachAncestor() which returns a list of all ancestors to the node.
func (Node) BFS ¶
BFS is a wrapper around ForEachBFS which simply returns all nodes reachable from n in BFS traversal order.
func (Node) DFS ¶
DFS is a wrapper around ForEachDFS which simply returns all nodes reachable from n in DFS traversal order.
func (Node) Data ¶
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 ¶
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) Exists ¶
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 ¶
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 ¶
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 ¶
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 ¶
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 ¶
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 ¶
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 ¶
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 ¶
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) MustAdjacent ¶
MustAdjacent is a utility wrapper around Adjacent() which panics on error.
func (Node) MustAncestors ¶
MustAncestors wraps Ancestors(), but panics on error.
func (Node) MustData ¶
func (n Node) MustData() interface{}
MustData is a wrapper around Data() which panics on error.
func (Node) MustInEdges ¶
MustInEdges is a utility wrapper around InEdges which panics on error.
func (Node) MustOutEdges ¶
MustOutEdges is a utility wrapper around OutEdges which panics on error.
func (Node) MustSuccessors ¶
MustSuccessors is a utility wrapper around Successors() that panics on error.
func (Node) ReplaceData ¶
ReplaceData replaces the data attached to the specified node.
This function may error if the node has been deleted.
func (Node) Successors ¶
Successors is a utility wrapper around ForeachSuccessor() which returns a list of all successors to the node.
Source Files
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. |