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.

gogl is divided chiefly into two parts: datastructures and algorithms. These components are loosely coupled; the algorithms rely strictly on gogl's various exported Graph interfaces to do their work.

Index

• type BaseEdge
  • func (e BaseEdge) Both() (Vertex, Vertex)
  • func (e BaseEdge) Source() Vertex
  • func (e BaseEdge) Target() Vertex
• type BaseWeightedEdge
  • func (e BaseWeightedEdge) Weight() int
• type Directed
  • func NewDirected() *Directed
  • func (g *Directed) AddEdges(edges ...Edge)
  • func (g *Directed) Density() float64
  • func (g *Directed) EachAdjacent(vertex Vertex, f func(target Vertex))
  • func (g *Directed) EachEdge(f func(edge Edge))
  • func (g *Directed) EachVertex(f func(vertex Vertex))
  • func (g *Directed) EnsureVertex(vertices ...Vertex)
  • func (g *Directed) HasEdge(edge Edge) bool
  • func (g *Directed) HasVertex(vertex Vertex) (exists bool)
  • func (g *Directed) InDegree(vertex Vertex) (degree int, exists bool)
  • func (g *Directed) Order() int
  • func (g *Directed) OutDegree(vertex Vertex) (degree int, exists bool)
  • func (g *Directed) RemoveEdges(edges ...Edge)
  • func (g *Directed) RemoveVertex(vertices ...Vertex)
  • func (g *Directed) Size() int
  • func (g *Directed) Transpose() DirectedGraph
• type DirectedGraph
• type Edge
• type Graph
• type MutableGraph
• type MutableWeightedGraph
  • func NewWeightedDirected() MutableWeightedGraph
  • func NewWeightedUndirected() MutableWeightedGraph
• type SimpleGraph
• type Undirected
  • func NewUndirected() *Undirected
  • func (g *Undirected) AddEdges(edges ...Edge)
  • func (g *Undirected) Density() float64
  • func (g *Undirected) EachAdjacent(vertex Vertex, f func(target Vertex))
  • func (g *Undirected) EachEdge(f func(edge Edge))
  • func (g *Undirected) EachVertex(f func(vertex Vertex))
  • func (g *Undirected) EnsureVertex(vertices ...Vertex)
  • func (g *Undirected) HasEdge(edge Edge) bool
  • func (g *Undirected) HasVertex(vertex Vertex) (exists bool)
  • func (g *Undirected) InDegree(vertex Vertex) (degree int, exists bool)
  • func (g *Undirected) Order() int
  • func (g *Undirected) OutDegree(vertex Vertex) (degree int, exists bool)
  • func (g *Undirected) RemoveEdges(edges ...Edge)
  • func (g *Undirected) RemoveVertex(vertices ...Vertex)
  • func (g *Undirected) Size() int
• type Vertex
• type WeightedEdge
• type WeightedGraph

Types

type BaseEdge

type BaseEdge struct {
	U Vertex
	V Vertex
}

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.

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 BaseWeightedEdge

type BaseWeightedEdge struct {
	BaseEdge
	W int
}

func (BaseWeightedEdge) Weight

func (e BaseWeightedEdge) Weight() int

type Directed

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

func NewDirected

func NewDirected() *Directed

Composite literal to create a new Directed.

func (*Directed) AddEdges

func (g *Directed) AddEdges(edges ...Edge)

Adds edges to the graph.

func (*Directed) Density

func (g *Directed) Density() float64

Returns the density of the graph. Density is the ratio of edge count to the number of edges there would be in complete graph (maximum edge count).

func (*Directed) EachAdjacent

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

Given a vertex present in the graph, passes each vertex adjacent to the provided vertex to the provided closure.

func (*Directed) EachEdge

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

Traverses the set of edges in the graph, passing each edge to the provided closure.

func (*Directed) EachVertex

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

Base adjacencyList methods

Traverses the graph's vertices in random order, passing each vertex to the provided closure.

func (*Directed) EnsureVertex

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

Adds the provided vertices to the graph. If a provided vertex is already present in the graph, it is a no-op (for that vertex only).

func (*Directed) HasEdge

func (g *Directed) HasEdge(edge Edge) bool

Indicates whether or not the given edge is present in the graph.

func (*Directed) HasVertex

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

Indicates whether or not the given vertex is present in the graph.

func (*Directed) InDegree

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

Returns the indegree of the provided vertex. If the vertex is not present in the graph, the second return value will be false.

Note that getting indegree is inefficient for directed adjacency lists; it requires a full scan of the graph's edge set.

func (*Directed) Order

func (g *Directed) Order() int

Returns the order (number of vertices) in the graph.

func (*Directed) OutDegree

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

Returns the outdegree of the provided vertex. If the vertex is not present in the graph, the second return value will be false.

func (*Directed) RemoveEdges

func (g *Directed) RemoveEdges(edges ...Edge)

Removes edges from the graph. This does NOT remove vertex members of the removed edges.

func (*Directed) RemoveVertex

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

Removes a vertex from the graph. Also removes any edges of which that vertex is a member.

func (*Directed) Size

func (g *Directed) Size() int

Returns the size (number of edges) in the graph.

func (*Directed) Transpose

func (g *Directed) Transpose() DirectedGraph

type DirectedGraph

type DirectedGraph interface {
	Graph
	Transpose() DirectedGraph
}

DirectedGraph describes a Graph all of whose edges are directed.

Implementing DirectedGraph is the only unambiguous signal gogl provides that a graph's edges are directed.

type Edge

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

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
	HasEdge(e Edge) bool
	Order() int
	Size() int
	InDegree(vertex Vertex) (int, bool)
	OutDegree(vertex Vertex) (int, bool)
}

Graph is gogl's most basic interface: it contains only the methods that *every* type of graph implements.

Graph is intentionally underspecified: both directed and undirected graphs implement it; simple graphs, multigraphs, weighted, labeled, or any combination thereof.

The semantics of some of these methods vary slightly from one graph type to another, but in general, the baisc Graph methods are supplemented, not superceded, by the methods in more specific interfaces.

Graph is a purely read oriented interface; the various Mutable*Graph interfaces contain the methods for writing.

type MutableGraph

type MutableGraph interface {
	Graph
	EnsureVertex(vertices ...Vertex)
	RemoveVertex(vertices ...Vertex)
	AddEdges(edges ...Edge)
	RemoveEdges(edges ...Edge)
}

MutableGraph describes a graph with basic edges (no weighting, labeling, etc.) that can be modified freely by adding or removing vertices or edges.

type MutableWeightedGraph

type MutableWeightedGraph interface {
	WeightedGraph
	EnsureVertex(vertices ...Vertex)
	RemoveVertex(vertices ...Vertex)
	AddEdges(edges ...WeightedEdge)
	RemoveEdges(edges ...WeightedEdge)
}

MutableWeightedGraph is the mutable version of a weighted graph. Its AddEdges() method is incompatible with MutableGraph, guaranteeing only weighted edges can be present in the graph.

func NewWeightedDirected

func NewWeightedDirected() MutableWeightedGraph

func NewWeightedUndirected

func NewWeightedUndirected() MutableWeightedGraph

type SimpleGraph

type SimpleGraph interface {
	Graph
	Density() float64
}

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

type Undirected

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

func NewUndirected

func NewUndirected() *Undirected

func (*Undirected) AddEdges

func (g *Undirected) AddEdges(edges ...Edge)

Adds edges to the graph.

func (*Undirected) Density

func (g *Undirected) Density() float64

Returns the density of the graph. Density is the ratio of edge count to the number of edges there would be in complete graph (maximum edge count).

func (*Undirected) EachAdjacent

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

Given a vertex present in the graph, passes each vertex adjacent to the provided vertex to the provided closure.

func (*Undirected) EachEdge

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

Traverses the set of edges in the graph, passing each edge to the provided closure.

func (*Undirected) EachVertex

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

Base adjacencyList methods

Traverses the graph's vertices in random order, passing each vertex to the provided closure.

func (*Undirected) EnsureVertex

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

Adds the provided vertices to the graph. If a provided vertex is already present in the graph, it is a no-op (for that vertex only).

func (*Undirected) HasEdge

func (g *Undirected) HasEdge(edge Edge) bool

Indicates whether or not the given edge is present in the graph.

func (*Undirected) HasVertex

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

Indicates whether or not the given vertex is present in the graph.

func (*Undirected) InDegree

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

Returns the indegree of the provided vertex. If the vertex is not present in the graph, the second return value will be false.

func (*Undirected) Order

func (g *Undirected) Order() int

Returns the order (number of vertices) in the graph.

func (*Undirected) OutDegree

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

Returns the outdegree of the provided vertex. If the vertex is not present in the graph, the second return value will be false.

func (*Undirected) RemoveEdges

func (g *Undirected) RemoveEdges(edges ...Edge)

Removes edges from the graph. This does NOT remove vertex members of the removed edges.

func (*Undirected) RemoveVertex

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

Removes a vertex from the graph. Also removes any edges of which that vertex is a member.

func (*Undirected) Size

func (g *Undirected) Size() int

Returns the size (number of edges) in the graph.

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 WeightedEdge

type WeightedEdge interface {
	Edge
	Weight() int
}

type WeightedGraph

type WeightedGraph interface {
	Graph
	HasWeightedEdge(e WeightedEdge) bool
	EachWeightedEdge(f func(edge WeightedEdge))
}

A weighted graph is a graph subtype where the edges have a numeric weight; as described by the WeightedEdge interface, this weight is a signed int.

WeightedGraphs have both the HasEdge() and HasWeightedEdge() methods. Correct implementations should treat the difference as a matter of strictness:

HasEdge() should return true as long as an edge exists connecting the two given vertices (respecting directed or undirected as appropriate), regardless of its weight.

HasWeightedEdge() should return true iff an edge exists connecting the two given vertices (respecting directed or undirected as appropriate), AND if the edge weights are the same.