depgraph

README

Some simple graph sorting algorithms focussed on sorting BPMN diagrams for sequence diagram & report generation

Documentation

Index

• type Graph
  • func New() *Graph
  • func (g *Graph) AddLink(linkID string, from, to any) (err error)
  • func (g *Graph) AddNode(id any, x, y float32)
  • func (g *Graph) DependOn(child, parent any) error
  • func (g *Graph) DependsOn(child, parent any) bool
  • func (g *Graph) HasDependent(parent, child any) bool
  • func (g *Graph) Leaves() (leaves []any)
  • func (g *Graph) Nodes() (nodes []any)
  • func (g *Graph) Sorted() []any
  • func (g *Graph) SortedLayers() (layers [][]any)
  • func (g *Graph) TopologicalSort() []*TopologyOrder
• type TopologyOrder

Types

type Graph

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

func New

func New() *Graph

func (*Graph) AddLink

func (g *Graph) AddLink(linkID string, from, to any) (err error)

AddLink adds a link between two nodes and records the linkID, only one linkID allowed between nodes

func (*Graph) AddNode

func (g *Graph) AddNode(id any, x, y float32)

func (*Graph) DependOn

func (g *Graph) DependOn(child, parent any) error

DependOn sets a dependency between a child and parent

func (*Graph) DependsOn

func (g *Graph) DependsOn(child, parent any) bool

DependsOn returns true if child depends on parent

func (*Graph) HasDependent

func (g *Graph) HasDependent(parent, child any) bool

HasDependent returns true if child is dependent on parent

func (*Graph) Leaves

func (g *Graph) Leaves() (leaves []any)

Leaves finds all nodes that don't have a dependency

func (*Graph) Nodes

func (g *Graph) Nodes() (nodes []any)

func (*Graph) Sorted

func (g *Graph) Sorted() []any

Sorted returns all the nodes in the graph sorted by layers

func (*Graph) SortedLayers

func (g *Graph) SortedLayers() (layers [][]any)

SortedLayers returns a slice of graph nodes in topological sort order. That is, if `B` depends on `A`, then `A` is guaranteed to come before `B` in the sorted output. The graph is guaranteed to be cycle-free because cycles are detected while building the graph. Additionally, the output is grouped into "layers", which are guaranteed to not have any dependencyMap within each layer. This is useful, e.g. when building an execution plan for some DAG, in which case each element within each layer could be executed in parallel. If you do not need this layered property, use `Graph.TopoSorted()`, which flattens all elements.

func (*Graph) TopologicalSort

func (g *Graph) TopologicalSort() []*TopologyOrder

TopologicalSort tries to prioritise the longest branch and is good for sequence diagrams Any off shoots are handled before carrying on

type TopologyOrder

type TopologyOrder struct {
	Node       any
	FromLinkID string
	Step       string
	SortedStep string
	Level      int
}