toposort

Documentation

Index

• type Graph
  • func NewGraph() *Graph
  • func (g *Graph) AddEdge(from, to string) int
  • func (g *Graph) AddNode(name string) bool
  • func (g *Graph) AddNodes(names ...string) bool
  • func (g *Graph) BreadthSort() []string
  • func (g *Graph) Copy() *Graph
  • func (g *Graph) DebugDump() string
  • func (g *Graph) FindChildren(from string) []string
  • func (g *Graph) FindCycle(seed string) []string
  • func (g *Graph) FindParents(to string) []string
  • func (g *Graph) ReindexNode(node string)
  • func (g *Graph) RemoveEdge(from, to string) bool
  • func (g *Graph) Serialize(sorted []string) string
  • func (g *Graph) Toposort() ([]string, bool)

Types

type Graph

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

Graph represents a directed acyclic graph.

func NewGraph

func NewGraph() *Graph

NewGraph initializes a new Graph.

func (*Graph) AddEdge

func (g *Graph) AddEdge(from, to string) int

AddEdge inserts the link from "from" node to "to" node.

func (*Graph) AddNode

func (g *Graph) AddNode(name string) bool

AddNode inserts a new node into the graph.

func (*Graph) AddNodes

func (g *Graph) AddNodes(names ...string) bool

AddNodes inserts multiple nodes into the graph at once.

func (*Graph) BreadthSort

func (g *Graph) BreadthSort() []string

BreadthSort sorts the nodes in the graph in BFS order.

func (*Graph) Copy

func (g *Graph) Copy() *Graph

Copy clones the graph and returns the independent copy.

func (*Graph) DebugDump

func (g *Graph) DebugDump() string

DebugDump converts the graph to a string. As the name suggests, useful for debugging.

func (*Graph) FindChildren

func (g *Graph) FindChildren(from string) []string

FindChildren returns the other ends of outgoing edges.

func (*Graph) FindCycle

func (g *Graph) FindCycle(seed string) []string

FindCycle returns the cycle in the graph which contains "seed" node.

func (*Graph) FindParents

func (g *Graph) FindParents(to string) []string

FindParents returns the other ends of incoming edges.

func (*Graph) ReindexNode

func (g *Graph) ReindexNode(node string)

ReindexNode updates the internal representation of the node after edge removals.

func (*Graph) RemoveEdge

func (g *Graph) RemoveEdge(from, to string) bool

RemoveEdge deletes the link from "from" node to "to" node. Call ReindexNode(from) after you finish modifying the edges.

func (*Graph) Serialize

func (g *Graph) Serialize(sorted []string) string

Serialize outputs the graph in Graphviz format.

func (*Graph) Toposort

func (g *Graph) Toposort() ([]string, bool)

Toposort sorts the nodes in the graph in topological order.