README
¶
dag
A DAG, Directed acyclic graph implementation in golang.
Badges
Install
go get github.com/goombaio/dag
You can also update an already installed version:
go get -u github.com/goombaio/dag
Example of use
// 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)
License
Copyright (c) 2018 Goomba project Authors.
Licensed under the Apache License, Version 2.0 (the "License"); you may not use this file except in compliance with the License. You may obtain a copy of the License at
http://www.apache.org/licenses/LICENSE-2.0
Unless required by applicable law or agreed to in writing, software distributed under the License is distributed on an "AS IS" BASIS, WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied. See the License for the specific language governing permissions and limitations under the License.
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.
Source Files