digraph

README

godigraph

Directed graph or "digraph" implementation, written in Go. MIT Licensed.

Full documentation for godigraph may be found on GoDoc.

Documentation

Overview

Package digraph provides an implementation of a directed graph, or "digraph"

Index

• Variables
• type AdjacencyList
  • func NewAdjacencyList() *AdjacencyList
  • func (a *AdjacencyList) Adjacent() []Vertex
  • func (a *AdjacencyList) Search(target Vertex) Vertex
• type Digraph
  • func New() *Digraph
  • func (d *Digraph) AddEdge(source Vertex, target Vertex) error
  • func (d *Digraph) AddVertex(vertex Vertex) error
  • func (d *Digraph) DepthFirstSearch(source Vertex, target Vertex) bool
  • func (d *Digraph) EdgeCount() int
  • func (d *Digraph) HasEdge(source Vertex, target Vertex) bool
  • func (d *Digraph) Print(root Vertex, all bool) (string, error)
  • func (d *Digraph) String() string
  • func (d *Digraph) VertexCount() int
• type Vertex

Variables

var (
	// ErrCycle is returned when creating an edge between two vertices would result
	// in a cycle in the digraph
	ErrCycle = errors.New("digraph: cycle between edges")

	// ErrEdgeExists is returned when an edge between two vertices already exists
	ErrEdgeExists = errors.New("digraph: edge already exists")

	// ErrVertexExists is returned when a vertex with the same value already exists
	ErrVertexExists = errors.New("digraph: vertex already exists")

	// ErrVertexNotExists is returned when a vertex is used which does not exist
	ErrVertexNotExists = errors.New("digraph: vertex does not exist")
)

Types

type AdjacencyList

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

AdjacencyList represents a linked-list of vertices connected by edges in the digraph

func NewAdjacencyList

func NewAdjacencyList() *AdjacencyList

NewAdjacencyList returns a new AdjacencyList with its internal list initialized

func (*AdjacencyList) Adjacent

func (a *AdjacencyList) Adjacent() []Vertex

Adjacent returns all vertices from the adjacency list

func (*AdjacencyList) Search

func (a *AdjacencyList) Search(target Vertex) Vertex

Search traverses the adjancency list and attempts to find a specified vertex

type Digraph

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

Digraph represents a "digraph", or directed graph data structure

func New

func New() *Digraph

New creates a new acyclic Digraph, and initializes its adjacency list

func (*Digraph) AddEdge

func (d *Digraph) AddEdge(source Vertex, target Vertex) error

AddEdge tries to add a new edge between two vertices on the adjacency list

func (*Digraph) AddVertex

func (d *Digraph) AddVertex(vertex Vertex) error

AddVertex tries to add a new vertex to the root of the adjacency list on the digraph

func (*Digraph) DepthFirstSearch

func (d *Digraph) DepthFirstSearch(source Vertex, target Vertex) bool

DepthFirstSearch searches the digraph for the target vertex, using the Depth-First Search algorithm, and returning true if a path to the target is found

func (*Digraph) EdgeCount

func (d *Digraph) EdgeCount() int

EdgeCount returns the number of edges in the digraph

func (*Digraph) HasEdge

func (d *Digraph) HasEdge(source Vertex, target Vertex) bool

HasEdge determines if the digraph has an existing edge between source and target, returning true if it does, or false if it does not

func (*Digraph) Print

func (d *Digraph) Print(root Vertex, all bool) (string, error)

Print displays a printed "tree" of the digraph to the console

func (*Digraph) String

func (d *Digraph) String() string

String retruns a string representation of the digraph, from the first vertex or "root"

func (*Digraph) VertexCount

func (d *Digraph) VertexCount() int

VertexCount returns the number of vertices in the digraph

type Vertex

type Vertex interface{}

Vertex represents a vertex or "node" in the digraph