depgraph

README

Dependency Graph ፨

A Go Implementation for a simple dependency graph with circular resolution

Overview

This package provides a simple implementation for a dependency graph with DependencyGraph into which edges and vertices can be inserted, removed, checked for inclusivity, and iterated upon. It supports circular dependency resolution and deep fetching of dependencies. DependencyGraph can also be serialized into JSON, YAML, and POLO formats and implements the engineio.DepDriver interface for go-moi

Installation

go get github.com/manishmeganathan/depgraph

Notes:

This package is still a work in progress and can be heavily extended for a lot of different use cases. If you are using this package and need some new functionality, please open an issue or a pull request.

Documentation

Index

• type DependencyGraph
  • func NewDependencyGraph() *DependencyGraph
  • func (dgraph *DependencyGraph) Contains(ptr uint64) bool
  • func (dgraph *DependencyGraph) Copy() *DependencyGraph
  • func (dgraph *DependencyGraph) Dependencies(ptr uint64) []uint64
  • func (dgraph *DependencyGraph) Depolorize(depolorizer *polo.Depolorizer) error
  • func (dgraph *DependencyGraph) Edges(ptr uint64) []uint64
  • func (dgraph *DependencyGraph) Insert(ptr uint64, deps ...uint64)
  • func (dgraph *DependencyGraph) Iter() <-chan uint64
  • func (dgraph *DependencyGraph) MarshalJSON() ([]byte, error)
  • func (dgraph *DependencyGraph) Polorize() (*polo.Polorizer, error)
  • func (dgraph *DependencyGraph) Remove(ptr uint64)
  • func (dgraph *DependencyGraph) Resolve() ([]uint64, bool)
  • func (dgraph *DependencyGraph) ResolveBatches() ([][]uint64, bool)
  • func (dgraph *DependencyGraph) Size() uint64
  • func (dgraph *DependencyGraph) String() string
  • func (dgraph *DependencyGraph) UnmarshalJSON(data []byte) error

Types

type DependencyGraph

type DependencyGraph struct {
	// contains filtered or unexported fields
}

func NewDependencyGraph

func NewDependencyGraph() *DependencyGraph

NewDependencyGraph generates and returns an empty DependencyGraph

func (*DependencyGraph) Contains

func (dgraph *DependencyGraph) Contains(ptr uint64) bool

Contains returns whether a given vertex exists in the DependencyGraph

func (*DependencyGraph) Copy

func (dgraph *DependencyGraph) Copy() *DependencyGraph

Copy creates a clone of the DependencyGraph and returns it

func (*DependencyGraph) Dependencies

func (dgraph *DependencyGraph) Dependencies(ptr uint64) []uint64

Dependencies returns all the edges (and edges of edges) for a given vertex pointer. It recursively collects all dependencies from each dependency layer and returns them (without duplicates). Note: This should only be used if the DependencyGraph can be resolved, otherwise, it will result in an infinite loop.

func (*DependencyGraph) Depolorize

func (dgraph *DependencyGraph) Depolorize(depolorizer *polo.Depolorizer) error

Depolorize implements the polo.Depolorizable interface for DependencyGraph

func (*DependencyGraph) Edges

func (dgraph *DependencyGraph) Edges(ptr uint64) []uint64

Edges returns the edges of going out of a given vertex pointer. The dependencies are returned as a mapset.Set (cardinality is zero if no dependencies for vertex)

func (*DependencyGraph) Insert

func (dgraph *DependencyGraph) Insert(ptr uint64, deps ...uint64)

Insert inserts an uint64 as a graph vertex to the DependencyGraph. It also accepts a variadic number of dependencies for the pointer and inserts them as edges.

If the vertex (and subsequently its edges) already exists, it is overwritten.

func (*DependencyGraph) Iter

func (dgraph *DependencyGraph) Iter() <-chan uint64

Iter returns a channel iterator that iterates over the vertices of the DependencyGraph is sorted order. This iteration is thread-safe, the graph being immutable during the iteration.

func (*DependencyGraph) MarshalJSON

func (dgraph *DependencyGraph) MarshalJSON() ([]byte, error)

MarshalJSON implements the json.Marshaller interface for DependencyGraph

func (*DependencyGraph) Polorize

func (dgraph *DependencyGraph) Polorize() (*polo.Polorizer, error)

Polorize implements the polo.Polorizable interface for DependencyGraph

func (*DependencyGraph) Remove

func (dgraph *DependencyGraph) Remove(ptr uint64)

Remove removes an uint64 as a graph vertex from the DependencyGraph. If such a vertex does not exist, this is a no-op.

func (*DependencyGraph) Resolve

func (dgraph *DependencyGraph) Resolve() ([]uint64, bool)

Resolve attempts to resolve the DependencyGraph into an ordered slice of element pointers. This slice represents the order of element compilation and is always deterministic. The output our Resolve is essentially a flattened output of ResolveBatches.

Returns a boolean along with the resolved elements indicating if the graph could be resolved. Graph resolution fails if there are circular or nil (non-existent) dependencies.

func (*DependencyGraph) ResolveBatches

func (dgraph *DependencyGraph) ResolveBatches() ([][]uint64, bool)

ResolveBatches attempts to resolve the DependencyGraph into batched element pointers. Each batch represents elements that need to compiled before the next batch but are independent of each other. The output of graph resolution is deterministic as each batch of pointers is sorted.

Returns a boolean along with the batches indicating if the graph could be resolved. Graph resolution fails if there are circular or nil (non-existent) dependencies.

func (*DependencyGraph) Size

func (dgraph *DependencyGraph) Size() uint64

Size returns the number of vertices in the DependencyGraph

func (*DependencyGraph) String

func (dgraph *DependencyGraph) String() string

String implements the Stringer interface for DependencyGraph.

func (*DependencyGraph) UnmarshalJSON

func (dgraph *DependencyGraph) UnmarshalJSON(data []byte) error

UnmarshalJSON implements the json.Unmarshaller interface for DependencyGraph