### dag

A DAG, Directed acyclic graph implementation in golang.

#### 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.

// Add the edges (Note that given vertices must exist before adding an
// edge between them).
``````

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.

// Add the edges (Note that given vertices must exist before adding an
// edge between them).
```

### 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 (d *DAG) AddEdge(tailVertex *Vertex, headVertex *Vertex) error`

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

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

#### 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.