Documentation
¶
Overview ¶
Package graph provides common graph algorithms
Index ¶
- Variables
- func IsDag(g Graph) error
- func IsTree(g Graph, root Node) error
- func Print(opt PrintOpt) string
- func ShortestPath(opt ShortestPathOpt) map[Node]int64
- func Verify(graph Graph) error
- func VisitTree(opt VisitTreeOpt) error
- type DisjointSet
- type EliminateOpt
- type Graph
- type IntSet
- type Labeler
- type LessThan
- type MakeQuotientOpt
- type Node
- type NodeSet
- type PartitionTreeOpt
- type PrintOpt
- type QGraph
- type Reachability
- type SDag
- type ShortestPathOpt
- type SimplifyOpt
- type StringGraph
- type TopoSortOpt
- type TreePartition
- type TreeVisitor
- type VisitOpt
- type VisitResult
- type VisitTreeOpt
- type Visitor
Constants ¶
This section is empty.
Variables ¶
var ( // ErrTraversalDone is a predefined error for expected early termination of a traversal ErrTraversalDone = errors.New("traversal done") // ErrNextNode is a predefined error for continuing a traversal ErrNextNode = errors.New("next node") )
Functions ¶
func IsTree ¶
IsTree returns nil if graph is a rooted tree. If not, it returns error containing a counterexample.
func ShortestPath ¶
func ShortestPath(opt ShortestPathOpt) map[Node]int64
ShortestPath implements Dijkstra's algorithm
Types ¶
type DisjointSet ¶
type DisjointSet struct {
// contains filtered or unexported fields
}
A DisjointSet efficiently stores sets of nodes
func (*DisjointSet) Find ¶
func (a *DisjointSet) Find(n Node) Node
Find returns the representative of a set
type EliminateOpt ¶
type EliminateOpt struct {
Graph Graph
In func(Node) bool // Should node be included
KeepMultiEdges bool
}
An EliminateOpt are a set of options to Eliminate
type Graph ¶
A Graph is a relation between nodes
func Eliminate ¶
func Eliminate(opt EliminateOpt) Graph
Eliminate returns the graph resulting from node elimination. Node elimination removes node n by adding edges (in(n), out(n)) for the product of incoming and outgoing neighbors.
func Reaches ¶
Reaches computes reachability over graph. A reaches B if there is a path from A to B.
func TransitiveReduction ¶
TransitiveReduction computes transitive reduction of a graph. Relatively expensive operation: O(nm).
type IntSet ¶
type IntSet struct {
// contains filtered or unexported fields
}
An IntSet is a set of integers
type Labeler ¶
type Labeler func(interface{}) string
A Labeler is a function that returns a string given an object
type MakeQuotientOpt ¶
type MakeQuotientOpt struct {
Graph Graph
Colorer func(Node) interface{}
HasColor func(Node) bool
Present func(Node) bool // Should n be included at all
KeepSelfEdges bool
}
MakeQuotientOpt are options to MakeQuotient
type Node ¶
type Node interface{}
A Node is a node in a graph
func TopoSort ¶
func TopoSort(opt TopoSortOpt) ([]Node, error)
TopoSort returns topological sort of graph. If edge (a, b) is in g, then b < a in the resulting order. Returns an error if graph contains a cycle.
type PartitionTreeOpt ¶
type PartitionTreeOpt struct {
Tree Graph
Root Node
Colors func(n Node) []int // Possible colors n may take; all nodes in graph must have at least one color
EdgeWeight func(a, b int) int64 // Weight between a and b (non-negative); depth(a) < depth(b)
NodeWeight func(a int) int // Weight of a
// contains filtered or unexported fields
}
PartitionTreeOpt is a set of options for PartitionTree
type QGraph ¶
type QGraph interface {
Graph
OrigGraph() Graph // Original graph that this graph was constructed from
NumOrigs(Node) int // Number of nodes in the original graph that this node represents
Orig(Node, int) Node // The ith node in the original graph that this node represents
}
QGraph is a quotient graph
func MakeQuotient ¶
func MakeQuotient(opt MakeQuotientOpt) QGraph
MakeQuotient returns a quotient graph. Nodes with the same color merged into a single node. A colorless node is treated as having a color distinct from any other node.
type Reachability ¶
func NewReachability ¶
func NewReachability(g Graph) Reachability
NewReachability compute the reachability matrix for the graph
type SDag ¶
An SDag is the current state of DAG scheduling
type ShortestPathOpt ¶
ShortestPathOpt is a set of options to ShortestPath
type SimplifyOpt ¶
type SimplifyOpt struct {
Graph Graph
RemoveSelfLoops bool
RemoveMultiEdges bool
RemoveNodes func(Node) bool // Should node be removed
}
A SimplifyOpt are options to Simplify
type StringGraph ¶
A StringGraph is a graph where nodes are strings
type TopoSortOpt ¶
type TopoSortOpt struct {
Graph Graph
NodeOrder LessThan // Optional argument to ensure deterministic output
}
A TopoSortOpt are options to TopoSort
type TreePartition ¶
A TreePartition is a partition of the nodes of a tree
func PartitionTree ¶
func PartitionTree(opt PartitionTreeOpt) (*TreePartition, error)
PartitionTree partitions a tree. Given a tree and a set of colors that each node may take, select a color for each node that minimizes the weight of the tree.
type TreeVisitor ¶
A TreeVisitor is a function that can be applied to nodes in a tree
type VisitOpt ¶
type VisitOpt struct {
Root Node // Root of traversal
Graph Graph // Graph to traverse
Visitor Visitor // Function to apply when node first encountered
Seen Visitor // Function applied on subsequent visits to a node
BreadthFirst bool // Visit nodes breadth first
}
VisitOpt is a set of options to Visit
type VisitResult ¶
type VisitResult struct {
Seen NodeSet
Frontiers []NodeSet // If VisitOpt.BreadthFirst, successive frontiers are placed here
}
A VisitResult is the result of Visit
func Visit ¶
func Visit(opt VisitOpt) (res *VisitResult, err error)
Visit applies a visitor to each node reachable from root in some order. Returns nodes visited. If visitor returns an error, stop traversal early and pass returned error.
type VisitTreeOpt ¶
type VisitTreeOpt struct {
Tree Graph
Root Node
PreOrder TreeVisitor // if err != TraversalDone, propagate error
PostOrder TreeVisitor // if err != TraversalDone, propagate error
}
VisitTreeOpt are a set of options to VisitTree
Source Files