README

dag

A DAG, Directed acyclic graph implementation in golang.

Badges

License CircleCI Status Coverage Report Go Report Card CII Best Practices GoDoc

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

    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)
      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)
      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 NewDAG

      func NewDAG() *DAG

        NewDAG creates a new Directed Acyclic Graph or DAG.

        func (*DAG) AddEdge

        func (d *DAG) AddEdge(tailVertex *Vertex, headVertex *Vertex) error

          AddEdge adds a directed edge between two existing vertices to the graph.

          func (*DAG) AddVertex

          func (d *DAG) AddVertex(v *Vertex) error

            AddVertex adds a vertex to the graph.

            func (*DAG) DeleteEdge

            func (d *DAG) DeleteEdge(tailVertex *Vertex, headVertex *Vertex) error

              DeleteEdge deletes a directed edge between two existing vertices from the graph.

              func (*DAG) DeleteVertex

              func (d *DAG) DeleteVertex(vertex *Vertex) error

                DeleteVertex deletes a vertex and all the edges referencing it from the graph.

                func (*DAG) GetVertex

                func (d *DAG) GetVertex(id interface{}) (*Vertex, error)

                  GetVertex return a vertex from the graph given a vertex ID.

                  func (*DAG) Order

                  func (d *DAG) Order() int

                    Order return the number of vertices in the graph.

                    func (*DAG) Predecessors

                    func (d *DAG) Predecessors(vertex *Vertex) ([]*Vertex, error)

                      Predecessors return vertices that are parent of a given vertex.

                      func (*DAG) SinkVertices

                      func (d *DAG) SinkVertices() []*Vertex

                        SinkVertices return vertices with no children defined by the graph edges.

                        func (*DAG) Size

                        func (d *DAG) Size() int

                          Size return the number of edges in the graph.

                          func (*DAG) SourceVertices

                          func (d *DAG) SourceVertices() []*Vertex

                            SourceVertices return vertices with no parent defined by the graph edges.

                            func (*DAG) String

                            func (d *DAG) String() string

                              String implements stringer interface.

                              Prints an string representation of this instance.

                              func (*DAG) Successors

                              func (d *DAG) Successors(vertex *Vertex) ([]*Vertex, error)

                                Successors return vertices that are children of a given vertex.

                                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 NewVertex

                                  func NewVertex(id string, value interface{}) *Vertex

                                    NewVertex creates a new vertex.

                                    func (*Vertex) Degree

                                    func (v *Vertex) Degree() int

                                      Degree return the number of parents and children of the vertex

                                      func (*Vertex) InDegree

                                      func (v *Vertex) InDegree() int

                                        InDegree return the number of parents of the vertex or the number of edges entering on it.

                                        func (*Vertex) OutDegree

                                        func (v *Vertex) OutDegree() int

                                          OutDegree return the number of children of the vertex or the number of edges leaving it.

                                          func (*Vertex) String

                                          func (v *Vertex) String() string

                                            String implements stringer interface and prints an string representation of this instance.