Documentation ¶
Overview ¶
Package dag implements a directed acyclic graph data structure ( DAG ), a finite directed graph with no directed cycles. A DAG consists of finitely many vertices and edges, with each edge directed from one vertex to another, such that there is no way to start at any vertex v and follow a consitently-sequence of edges that eventually loops backto v again.
A DAG is a directex graph that has a topological order, a sequence of vertices such that every edge is directed from earlier to later in the sequence.
Example
// Create the dag dag1 := dag.NewDAG() // Create the vertices. Value is nil to simplify. vertex1 := dag.NewVertex(nil) vertex2 := dag.NewVertex(nil) vertex3 := dag.NewVertex(nil) vertex4 := dag.NewVertex(nil) // Add the vertices to the dag. dag1.AddVertex(vertex1) dag1.AddVertex(vertex2) dag1.AddVertex(vertex3) dag1.AddVertex(vertex4) // Add the edges (Note that given vertices must exist before adding an // edge between them). dag1.AddEdge(vertex1, vertex2) dag1.AddEdge(vertex2, vertex3) dag1.AddEdge(vertex2, vertex4) dag1.AddEdge(vertex4, vertex3)
Index ¶
- type DAG
- func (d *DAG) AddEdge(tailVertex *Vertex, headVertex *Vertex) error
- func (d *DAG) AddVertex(v *Vertex) error
- func (d *DAG) BFS(vertex *Vertex) ([]*Vertex, error)
- func (d *DAG) DeleteEdge(tailVertex *Vertex, headVertex *Vertex) error
- func (d *DAG) DeleteVertex(vertex *Vertex) error
- func (d *DAG) GetVertex(id interface{}) (*Vertex, error)
- func (d *DAG) Order() int
- func (d *DAG) Predecessors(vertex *Vertex) ([]*Vertex, error)
- func (d *DAG) SinkVertices() []*Vertex
- func (d *DAG) Size() int
- func (d *DAG) SourceVertices() []*Vertex
- func (d *DAG) String() string
- func (d *DAG) StringNoValue() string
- func (d *DAG) Successors(vertex *Vertex) ([]*Vertex, error)
- func (d *DAG) VertexExists(id interface{}) bool
- type Vertex
Examples ¶
Constants ¶
This section is empty.
Variables ¶
This section is empty.
Functions ¶
This section is empty.
Types ¶
type DAG ¶
type DAG struct {
// contains filtered or unexported fields
}
DAG type implements a Directed Acyclic Graph data structure.
Example (Edges) ¶
package main import ( "fmt" "github.com/Che4ter/dag" ) func main() { dag1 := dag.NewDAG() vertex1 := dag.NewVertex("1", nil) vertex2 := dag.NewVertex("2", nil) vertex3 := dag.NewVertex("3", nil) vertex4 := dag.NewVertex("4", nil) err := dag1.AddVertex(vertex1) if err != nil { fmt.Printf("Can't add vertex to DAG: %s", err) panic(err) } err = dag1.AddVertex(vertex2) if err != nil { fmt.Printf("Can't add vertex to DAG: %s", err) panic(err) } err = dag1.AddVertex(vertex3) if err != nil { fmt.Printf("Can't add vertex to DAG: %s", err) panic(err) } err = dag1.AddVertex(vertex4) if err != nil { fmt.Printf("Can't add vertex to DAG: %s", err) panic(err) } // Edges err = dag1.AddEdge(vertex1, vertex2) if err != nil { fmt.Printf("Can't add edge to DAG: %s", err) panic(err) } err = dag1.AddEdge(vertex2, vertex3) if err != nil { fmt.Printf("Can't add edge to DAG: %s", err) panic(err) } err = dag1.AddEdge(vertex3, vertex4) if err != nil { fmt.Printf("Can't add edge to DAG: %s", err) panic(err) } fmt.Println(dag1.String()) }
Output: DAG Vertices: 4 - Edges: 3 Vertices: ID: 1 - Parents: 0 - Children: 1 - Value: <nil> ID: 2 - Parents: 1 - Children: 1 - Value: <nil> ID: 3 - Parents: 1 - Children: 1 - Value: <nil> ID: 4 - Parents: 1 - Children: 0 - Value: <nil>
Example (Vertices) ¶
package main import ( "fmt" "github.com/Che4ter/dag" ) func main() { dag1 := dag.NewDAG() vertex1 := dag.NewVertex("1", nil) vertex2 := dag.NewVertex("2", nil) vertex3 := dag.NewVertex("3", nil) vertex4 := dag.NewVertex("4", nil) err := dag1.AddVertex(vertex1) if err != nil { fmt.Printf("Can't add vertex to DAG: %s", err) panic(err) } err = dag1.AddVertex(vertex2) if err != nil { fmt.Printf("Can't add vertex to DAG: %s", err) panic(err) } err = dag1.AddVertex(vertex3) if err != nil { fmt.Printf("Can't add vertex to DAG: %s", err) panic(err) } err = dag1.AddVertex(vertex4) if err != nil { fmt.Printf("Can't add vertex to DAG: %s", err) panic(err) } fmt.Println(dag1.String()) }
Output: DAG Vertices: 4 - Edges: 0 Vertices: ID: 1 - Parents: 0 - Children: 0 - Value: <nil> ID: 2 - Parents: 0 - Children: 0 - Value: <nil> ID: 3 - Parents: 0 - Children: 0 - Value: <nil> ID: 4 - Parents: 0 - Children: 0 - Value: <nil>
func (*DAG) BFS ¶
BFS implements the Breadth-first algorithm to traversing all children of a given vertex, return vertices that are children of a given vertex.
func (*DAG) DeleteEdge ¶
DeleteEdge deletes a directed edge between two existing vertices from the graph.
func (*DAG) DeleteVertex ¶
DeleteVertex deletes a vertex and all the edges referencing it from the graph.
func (*DAG) Predecessors ¶
Predecessors return vertices that are parent of a given vertex.
func (*DAG) SinkVertices ¶
SinkVertices return vertices with no children defined by the graph edges.
func (*DAG) SourceVertices ¶
SourceVertices return vertices with no parent defined by the graph edges.
func (*DAG) String ¶
String implements stringer interface.
Prints an string representation of this instance.
func (*DAG) StringNoValue ¶
Prints an string representation of this instance, but hides the vertices values.
func (*DAG) Successors ¶
Successors return vertices that are children of a given vertex.
func (*DAG) VertexExists ¶
VertexExists return true if a vertex with given vertex ID exists in the graph
type Vertex ¶
type Vertex struct { ID string Value interface{} Parents *orderedset.OrderedSet Children *orderedset.OrderedSet }
Vertex type implements a vertex of a Directed Acyclic graph or DAG.
func (*Vertex) InDegree ¶
InDegree return the number of parents of the vertex or the number of edges entering on it.
func (*Vertex) OutDegree ¶
OutDegree return the number of children of the vertex or the number of edges leaving it.
func (*Vertex) String ¶
String implements stringer interface and prints an string representation of this instance.
func (*Vertex) StringKeys ¶
String implements stringer interface and prints an string representation of this instance.