Documentation ¶
Index ¶
Constants ¶
const ( NodeUnsorted = -1 NodeInCurrentScc = -2 )
Variables ¶
This section is empty.
Functions ¶
func VertexFeatures ¶
Types ¶
type Graph ¶
type Graph struct {
// contains filtered or unexported fields
}
func (*Graph) Sort ¶
func (self *Graph) Sort(index adt.StringIndexer) []adt.Feature
Sort the features of the graph into a single slice.
As far as possible, a topological sort is used.
Whenever there is choice as to which feature should occur next, a lexicographical comparison is done, and minimum feature chosen.
Whenever progress cannot be made due to needing to enter into cycles, the cycle to enter into, and the node of that cycle with which to start, is selected based on:
- minimising the number of incoming edges that are violated
- chosing a node which was reachable as early as possible
- chosing a node with a smaller feature name (lexicographical)
func (*Graph) StronglyConnectedComponents ¶
func (graph *Graph) StronglyConnectedComponents() []*StronglyConnectedComponent
Calculate the Strongly Connected Components of the graph. https://en.wikipedia.org/wiki/Strongly_connected_component
The components returned are topologically sorted (forwards), and form a DAG (this is the "condensation graph").
type GraphBuilder ¶
type GraphBuilder struct {
// contains filtered or unexported fields
}
func NewGraphBuilder ¶
func NewGraphBuilder() *GraphBuilder
func (*GraphBuilder) AddEdge ¶
func (builder *GraphBuilder) AddEdge(from, to adt.Feature)
Adds an edge between the two features. Nodes for the features will be created if they don't already exist. This method is idempotent: multiple calls with the same arguments will not create multiple edges, nor error.
func (*GraphBuilder) Build ¶
func (builder *GraphBuilder) Build() *Graph
func (*GraphBuilder) EnsureNode ¶
func (builder *GraphBuilder) EnsureNode(feature adt.Feature) *Node
Ensure that a node for this feature exists. This is necessary for features that are not necessarily connected to any other feature.
type Node ¶
type StronglyConnectedComponent ¶
type StronglyConnectedComponent struct { Nodes Nodes Outgoing []*StronglyConnectedComponent Incoming []*StronglyConnectedComponent // contains filtered or unexported fields }
func (*StronglyConnectedComponent) ElementaryCycles ¶
func (scc *StronglyConnectedComponent) ElementaryCycles() []*Cycle
Calculate the Elementary Cycles (EC) within the current Strongly Connected Component (SCC).
If the component contains no cycles (by definition, this means the component contains only a single node), then the slice returned will be empty.
In general:
- If a component contains two or more nodes then it contains at least one cycle.
- A single node can be involved in many cycles.
- This method finds all cycles within a component, but does not include cycles that are merely rotations of each other. I.e. every cycle is unique, ignoring rotations.
- The cycles returned are unsorted: each cycle is itself in no particular rotation, and the complete slice of cycles is similarly unsorted.
The complexity of this algorithm is O((n+e)*c) where
- n: number of nodes in the SCC
- e: number of edges between the nodes in the SCC
- c: number of cycles discovered
Donald B Johnson: Finding All the Elementary Circuits of a Directed Graph. SIAM Journal on Computing. Volumne 4, Nr. 1 (1975), pp. 77-84.