Documentation
¶
Index ¶
- func StronglyConnected(g *Graph) [][]Vertex
- func VertexName(raw Vertex) string
- type AcyclicGraph
- func (g *AcyclicGraph) Ancestors(v Vertex) (*Set, error)
- func (g *AcyclicGraph) Cycles() [][]Vertex
- func (g *AcyclicGraph) DepthFirstWalk(start []Vertex, f DepthWalkFunc) error
- func (g *AcyclicGraph) Descendents(v Vertex) (*Set, error)
- func (g *AcyclicGraph) ReverseDepthFirstWalk(start []Vertex, f DepthWalkFunc) error
- func (g *AcyclicGraph) Root() (Vertex, error)
- func (g *AcyclicGraph) TransitiveReduction()
- func (g *AcyclicGraph) Validate() error
- func (g *AcyclicGraph) Walk(cb WalkFunc) error
- type DepthWalkFunc
- type Edge
- type Graph
- func (g *Graph) Add(v Vertex) Vertex
- func (g *Graph) Connect(edge Edge)
- func (g *Graph) DownEdges(v Vertex) *Set
- func (g *Graph) Edges() []Edge
- func (g *Graph) Remove(v Vertex) Vertex
- func (g *Graph) RemoveEdge(edge Edge)
- func (g *Graph) Replace(original, replacement Vertex) bool
- func (g *Graph) String() string
- func (g *Graph) UpEdges(v Vertex) *Set
- func (g *Graph) Vertices() []Vertex
- type Hashable
- type NamedVertex
- type Set
- type Vertex
- type WalkFunc
Constants ¶
This section is empty.
Variables ¶
This section is empty.
Functions ¶
func StronglyConnected ¶
func StronglyConnected(g *Graph) [][]Vertex
StronglyConnected returns the list of strongly connected components within the Graph g. This information is primarily used by this package for cycle detection, but strongly connected components have widespread use.
Types ¶
type AcyclicGraph ¶
type AcyclicGraph struct {
Graph
}
AcyclicGraph is a specialization of Graph that cannot have cycles. With this property, we get the property of sane graph traversal.
func (*AcyclicGraph) Ancestors ¶
func (g *AcyclicGraph) Ancestors(v Vertex) (*Set, error)
Returns a Set that includes every Vertex yielded by walking down from the provided starting Vertex v.
func (*AcyclicGraph) DepthFirstWalk ¶ added in v0.5.0
func (g *AcyclicGraph) DepthFirstWalk(start []Vertex, f DepthWalkFunc) error
depthFirstWalk does a depth-first walk of the graph starting from the vertices in start. This is not exported now but it would make sense to export this publicly at some point.
func (*AcyclicGraph) Descendents ¶
func (g *AcyclicGraph) Descendents(v Vertex) (*Set, error)
Returns a Set that includes every Vertex yielded by walking up from the provided starting Vertex v.
func (*AcyclicGraph) ReverseDepthFirstWalk ¶ added in v0.5.0
func (g *AcyclicGraph) ReverseDepthFirstWalk(start []Vertex, f DepthWalkFunc) error
reverseDepthFirstWalk does a depth-first walk _up_ the graph starting from the vertices in start.
func (*AcyclicGraph) Root ¶
func (g *AcyclicGraph) Root() (Vertex, error)
Root returns the root of the DAG, or an error.
Complexity: O(V)
func (*AcyclicGraph) TransitiveReduction ¶
func (g *AcyclicGraph) TransitiveReduction()
TransitiveReduction performs the transitive reduction of graph g in place. The transitive reduction of a graph is a graph with as few edges as possible with the same reachability as the original graph. This means that if there are three nodes A => B => C, and A connects to both B and C, and B connects to C, then the transitive reduction is the same graph with only a single edge between A and B, and a single edge between B and C.
The graph must be valid for this operation to behave properly. If Validate() returns an error, the behavior is undefined and the results will likely be unexpected.
Complexity: O(V(V+E)), or asymptotically O(VE)
type DepthWalkFunc ¶ added in v0.5.0
type DepthWalkFunc func(Vertex, int) error
DepthWalkFunc is a walk function that also receives the current depth of the walk as an argument
type Edge ¶
type Edge interface {
Source() Vertex
Target() Vertex
Hashable
}
Edge represents an edge in the graph, with a source and target vertex.
type Graph ¶
type Graph struct {
// contains filtered or unexported fields
}
Graph is used to represent a dependency graph.
func (*Graph) Add ¶
func (g *Graph) Add(v Vertex) Vertex
Add adds a vertex to the graph. This is safe to call multiple time with the same Vertex.
func (*Graph) Connect ¶
func (g *Graph) Connect(edge Edge)
Connect adds an edge with the given source and target. This is safe to call multiple times with the same value. Note that the same value is verified through pointer equality of the vertices, not through the value of the edge itself.
func (*Graph) DownEdges ¶
func (g *Graph) DownEdges(v Vertex) *Set
DownEdges returns the outward edges from the source Vertex v.
func (*Graph) Edges ¶
func (g *Graph) Edges() []Edge
Edges returns the list of all the edges in the graph.
func (*Graph) Remove ¶
func (g *Graph) Remove(v Vertex) Vertex
Remove removes a vertex from the graph. This will also remove any edges with this vertex as a source or target.
func (*Graph) RemoveEdge ¶
func (g *Graph) RemoveEdge(edge Edge)
RemoveEdge removes an edge from the graph.
func (*Graph) Replace ¶
func (g *Graph) Replace(original, replacement Vertex) bool
Replace replaces the original Vertex with replacement. If the original does not exist within the graph, then false is returned. Otherwise, true is returned.
func (*Graph) String ¶
func (g *Graph) String() string
String outputs some human-friendly output for the graph structure.
type Hashable ¶
type Hashable interface {
Hashcode() interface{}
}
Hashable is the interface used by set to get the hash code of a value. If this isn't given, then the value of the item being added to the set itself is used as the comparison value.
type NamedVertex ¶
type NamedVertex interface {
Vertex
Name() string
}
NamedVertex is an optional interface that can be implemented by Vertex to give it a human-friendly name that is used for outputting the graph.
type Set ¶
type Set struct {
// contains filtered or unexported fields
}
Set is a set data structure.
func (*Set) Include ¶
func (s *Set) Include(v interface{}) bool
Include returns true/false of whether a value is in the set.
func (*Set) Intersection ¶
func (s *Set) Intersection(other *Set) *Set
Intersection computes the set intersection with other.
type Vertex ¶
type Vertex interface{}
Vertex of the graph.
func AsVertexList ¶ added in v0.5.0
func AsVertexList(s *Set) []Vertex
simple convenience helper for converting a dag.Set to a []Vertex
Source Files