dag

package module
Version: v0.0.0-...-a8874b1 Latest Latest
Warning

This package is not in the latest version of its module.

Go to latest
Published: Oct 6, 2018 License: Apache-2.0 Imports: 4 Imported by: 6

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)
package main

import (
	"fmt"

	"github.com/goombaio/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/goombaio/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 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.

Jump to

Keyboard shortcuts

? : This menu
/ : Search site
f or F : Jump to
y or Y : Canonical URL