gogl

README

gogl

gogl is a graph library in Go. Its goal is to provide simple, unifying interfaces and implementations of graph algorithms and datastructures that can scale from use cases for small graphs up to very large graphs.

TODO: just about everything. yay!

Documentation

Overview

gogl provides a framework for representing and working with graphs.

Index

• Constants
• func DepthFirstFromVertices(g Graph, vis DFVisitor, vertices ...Vertex) error
• type BaseEdge
  • func (e BaseEdge) Both() (Vertex, Vertex)
  • func (e BaseEdge) Source() Vertex
  • func (e BaseEdge) Target() Vertex
• type DFTslVisitor
  • func (vis *DFTslVisitor) GetTsl() []Vertex
• type DFVisitor
• type DirectedAdjacencyList
  • func NewDirectedAdjacencyList() *DirectedAdjacencyList
  • func NewDirectedAdjacencyListFromEdgeSet(set []Edge) *DirectedAdjacencyList
  • func (g *DirectedAdjacencyList) AddEdge(edge Edge) bool
  • func (g *DirectedAdjacencyList) Density() float64
  • func (g *DirectedAdjacencyList) EachAdjacent(vertex Vertex, f func(target Vertex))
  • func (g *DirectedAdjacencyList) EachEdge(f func(edge Edge))
  • func (g *DirectedAdjacencyList) EachVertex(f func(vertex Vertex))
  • func (g *DirectedAdjacencyList) EnsureVertex(vertices ...Vertex)
  • func (g *DirectedAdjacencyList) HasVertex(vertex Vertex) (exists bool)
  • func (g *DirectedAdjacencyList) InDegree(vertex Vertex) (degree int, exists bool)
  • func (g *DirectedAdjacencyList) Order() int
  • func (g *DirectedAdjacencyList) OutDegree(vertex Vertex) (degree int, exists bool)
  • func (g *DirectedAdjacencyList) RemoveEdge(edge Edge)
  • func (g *DirectedAdjacencyList) RemoveVertex(vertices ...Vertex)
  • func (g *DirectedAdjacencyList) Size() int
• type DirectedGraph
• type Edge
• type EdgeFilterer
• type EdgeList
• type Graph
• type IdentifiableVertex
• type Path
• type SimpleGraph
• type UndirectedGraph
• type Vertex
• type VertexList
• type VertexSet

Constants

const (
	E_DIRECTED, EM_DIRECTED = 1 << iota, 1<<iota - 1
	E_UNDIRECTED, EM_UNDIRECTED
	E_WEIGHTED, EM_WEIGHTED
	E_TYPED, EM_TYPED
	E_SIGNED, EM_SIGNED
	E_LOOPS, EM_LOOPS
	E_MULTIGRAPH, EM_MULTIGRAPH
)

TODO totally unclear whether or not defining capabilities in a bitfield like this will actually help us achieve the goal

Functions

func DepthFirstFromVertices

func DepthFirstFromVertices(g Graph, vis DFVisitor, vertices ...Vertex) error

Types

type BaseEdge

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

BaseEdge is a struct used internally to represent edges and meet the Edge interface requirements. It uses the standard notation, (u,v), for vertex pairs in an edge. TODO what does having non-exported fields, and no write methods, mean for mutability outside of the package?

func (BaseEdge) Both

func (e BaseEdge) Both() (Vertex, Vertex)

func (BaseEdge) Source

func (e BaseEdge) Source() Vertex

func (BaseEdge) Target

func (e BaseEdge) Target() Vertex

type DFTslVisitor

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

func (*DFTslVisitor) GetTsl

func (vis *DFTslVisitor) GetTsl() []Vertex

type DFVisitor

type DFVisitor interface {
	// contains filtered or unexported methods
}

type DirectedAdjacencyList

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

func NewDirectedAdjacencyList

func NewDirectedAdjacencyList() *DirectedAdjacencyList

Composite literal to create a new DirectedAdjacencyList.

func NewDirectedAdjacencyListFromEdgeSet

func NewDirectedAdjacencyListFromEdgeSet(set []Edge) *DirectedAdjacencyList

func (*DirectedAdjacencyList) AddEdge

func (g *DirectedAdjacencyList) AddEdge(edge Edge) bool

func (*DirectedAdjacencyList) Density

func (g *DirectedAdjacencyList) Density() float64

func (*DirectedAdjacencyList) EachAdjacent

func (g *DirectedAdjacencyList) EachAdjacent(vertex Vertex, f func(target Vertex))

func (*DirectedAdjacencyList) EachEdge

func (g *DirectedAdjacencyList) EachEdge(f func(edge Edge))

func (*DirectedAdjacencyList) EachVertex

func (g *DirectedAdjacencyList) EachVertex(f func(vertex Vertex))

func (*DirectedAdjacencyList) EnsureVertex

func (g *DirectedAdjacencyList) EnsureVertex(vertices ...Vertex)

func (*DirectedAdjacencyList) HasVertex

func (g *DirectedAdjacencyList) HasVertex(vertex Vertex) (exists bool)

func (*DirectedAdjacencyList) InDegree

func (g *DirectedAdjacencyList) InDegree(vertex Vertex) (degree int, exists bool)

Getting InDegree is inefficient for directed adjacency lists

func (*DirectedAdjacencyList) Order

func (g *DirectedAdjacencyList) Order() int

func (*DirectedAdjacencyList) OutDegree

func (g *DirectedAdjacencyList) OutDegree(vertex Vertex) (degree int, exists bool)

func (*DirectedAdjacencyList) RemoveEdge

func (g *DirectedAdjacencyList) RemoveEdge(edge Edge)

func (*DirectedAdjacencyList) RemoveVertex

func (g *DirectedAdjacencyList) RemoveVertex(vertices ...Vertex)

func (*DirectedAdjacencyList) Size

func (g *DirectedAdjacencyList) Size() int

type DirectedGraph

type DirectedGraph interface {
	Graph
	Transpose() DirectedGraph
	IsAcyclic() bool
	GetCycles() [][]Vertex
	// contains filtered or unexported methods
}

type Edge

type Edge interface {
	Source() Vertex
	Target() Vertex
	Both() (Vertex, Vertex)
}

type EdgeFilterer

type EdgeFilterer interface {
	FilterEdge(edge Edge) bool
	FilterEdges(edges []Edge) []Edge
}

type EdgeList

type EdgeList []Edge

type Graph

type Graph interface {
	EachVertex(f func(vertex Vertex))
	EachEdge(f func(edge Edge))
	EachAdjacent(vertex Vertex, f func(adjacent Vertex))
	HasVertex(vertex Vertex) bool
	Order() int
	Size() int
	InDegree(vertex Vertex) (int, bool)
	OutDegree(vertex Vertex) (int, bool)
	EnsureVertex(vertices ...Vertex)
	RemoveVertex(vertices ...Vertex)
}

type IdentifiableVertex

type IdentifiableVertex interface {
	// contains filtered or unexported methods
}

However, as a practical, internal matter, some approaches to representing graphs may benefit significantly (in terms of memory use) from having a uint that uniquely identifies each vertex. This is essentially an implementation detail, but if your use case merits it (large graph processing is busting memory), you can trade off a bit of speed for potentially nontrivial memory savings. TODO implement a datastructure that does this, and test these outlandish claims!

type Path

type Path []Edge

type SimpleGraph

type SimpleGraph interface {
	Density() float64
}

A simple graph is in opposition to a multigraph: it disallows loops and parallel edges.

type UndirectedGraph

type UndirectedGraph interface {
	Graph
	AddEdge(edge Edge) bool
	RemoveEdge(edge Edge)
}

type Vertex

type Vertex interface{}

As a rule, gogl tries to place as low a requirement on its vertices as possible. This is because, from a purely graph theoretic perspective, vertices are inert. Boring, even. Graphs are more about the topology, the characteristics of the edges connecting the points than the points themselves. Your use case cares about the content of your vertices, but gogl does not. Consequently, anything can act as a vertex.

type VertexList

type VertexList []Vertex

type VertexSet

type VertexSet map[Vertex]struct{}

VertexSet uses maps to express a value-less (empty struct), indexed unordered list. See https://groups.google.com/forum/#!searchin/golang-nuts/map/golang-nuts/H2cXpwisEUE/1X2FV-rODfIJ