Help us shape the future of Go! Take the 2026 Go Developer Survey

gogl

package module
v0.3.0 Latest Latest
Warning

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

 Go to latest Published: Apr 14, 2014 License: MIT Imports: 3 Imported by: 4

README

gogl

Build Status Coverage Status

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

Constants

This section is empty.

Variables

View Source 
var Graphs = make(map[string]GraphFactory, 0)

Functions

func New added in v0.2.0 

func New(name string) (graph interface{}, err error)

Creates a new graph instance.

You will need to type assert the returned graph to the interface appropriate for your use case: Graph, DirectedGraph, MutableGraph, WeightedGraph, etc.

func RegisterGraph added in v0.2.0 

func RegisterGraph(name string, factory GraphFactory) error

Types

type BaseDataEdge added in v0.3.0 

type BaseDataEdge struct {
	BaseEdge
	D interface{}
}

BaseDataEdge extends BaseEdge with arbitrary data.

func (BaseDataEdge) Data added in v0.3.0 

func (e BaseDataEdge) Data() interface{}

type BaseEdge 

type BaseEdge struct {
	U Vertex
	V Vertex
}

BaseEdge is a struct used to represent edges and meet the Edge interface requirements. It uses the standard graph notation, (U,V), for its contained vertex pair.

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 BaseLabeledEdge added in v0.2.0 

type BaseLabeledEdge struct {
	BaseEdge
	L string
}

BaseLabeledEdge extends BaseEdge with label data.

func (BaseLabeledEdge) Label added in v0.2.0 

func (e BaseLabeledEdge) Label() string

type BaseWeightedEdge added in v0.1.0 

type BaseWeightedEdge struct {
	BaseEdge
	W int
}

BaseWeightedEdge extends BaseEdge with weight data.

func (BaseWeightedEdge) Weight added in v0.1.0 

func (e BaseWeightedEdge) Weight() int

type DataEdge added in v0.3.0 

type DataEdge interface {
	Edge
	Data() interface{}
}

A DataEdge is an Edge that also carries some arbitrary data.

type DataGraph added in v0.3.0 

type DataGraph interface {
	Graph
	HasDataEdge(e DataEdge) bool
	EachDataEdge(f func(edge DataEdge))
}

A data graph is a graph subtype where the edges carry arbitrary Go data; as described by the DataEdge interface, this identifier is an interface{}.

DataGraphs have both the HasEdge() and HasDataEdge() 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 label.

HasDataEdge() should return true iff an edge exists connecting the two given vertices (respecting directed or undirected as appropriate), AND if the edge data is the same. Simple comparison will typically be used to establish data equality, which means that using noncomparables (a slice, map, or non-pointer struct containing a slice or a map) for the data will cause a panic.

type Directed added in v0.1.0 

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

func NewDirected added in v0.1.0 

func NewDirected() *Directed

Composite literal to create a new Directed.

func (*Directed) AddEdges added in v0.1.0 

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

Adds edges to the graph.

func (*Directed) Density added in v0.1.0 

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 added in v0.1.0 

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 added in v0.1.0 

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 added in v0.1.0 

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 added in v0.1.0 

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 added in v0.1.0 

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

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

func (*Directed) HasVertex added in v0.1.0 

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

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

func (*Directed) InDegree added in v0.1.0 

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 added in v0.1.0 

func (g *Directed) Order() int

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

func (*Directed) OutDegree added in v0.1.0 

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 added in v0.1.0 

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

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

func (*Directed) RemoveVertex added in v0.1.0 

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 added in v0.1.0 

func (g *Directed) Size() int

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

func (*Directed) Transpose added in v0.1.0 

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)
}

The Edge interface describes a connection between two vertices.

Edge does not have an intrinsic opinion about directionality; gogl treats that as a property of the overall Graph object in which the Edge appears rather than a property of any individual 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
	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 basic 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 GraphFactory added in v0.2.0 

type GraphFactory func() interface{}

type LabeledEdge added in v0.2.0 

type LabeledEdge interface {
	Edge
	Label() string
}

A LabeledEdge is an Edge that also has a string label.

type LabeledGraph added in v0.2.0 

type LabeledGraph interface {
	Graph
	HasLabeledEdge(e LabeledEdge) bool
	EachLabeledEdge(f func(edge LabeledEdge))
}

A labeled graph is a graph subtype where the edges have an identifier; as described by the LabeledEdge interface, this identifier is a string.

LabeledGraphs have both the HasEdge() and HasLabeledEdge() 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 label.

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

type MutableDataGraph added in v0.3.0 

type MutableDataGraph interface {
	DataGraph
	EnsureVertex(vertices ...Vertex)
	RemoveVertex(vertices ...Vertex)
	AddEdges(edges ...DataEdge)
	RemoveEdges(edges ...DataEdge)
}

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

func NewDataDirected added in v0.3.0 

func NewDataDirected() MutableDataGraph

func NewDataUndirected added in v0.3.0 

func NewDataUndirected() MutableDataGraph

type MutableGraph added in v0.1.0 

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 MutableLabeledGraph added in v0.2.0 

type MutableLabeledGraph interface {
	LabeledGraph
	EnsureVertex(vertices ...Vertex)
	RemoveVertex(vertices ...Vertex)
	AddEdges(edges ...LabeledEdge)
	RemoveEdges(edges ...LabeledEdge)
}

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

func NewLabeledDirected added in v0.2.0 

func NewLabeledDirected() MutableLabeledGraph

func NewLabeledUndirected added in v0.2.0 

func NewLabeledUndirected() MutableLabeledGraph

type MutableWeightedGraph added in v0.1.0 

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 added in v0.1.0 

func NewWeightedDirected() MutableWeightedGraph

func NewWeightedUndirected added in v0.1.0 

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 added in v0.1.0 

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

func NewUndirected added in v0.1.0 

func NewUndirected() *Undirected

func (*Undirected) AddEdges added in v0.1.0 

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

Adds edges to the graph.

func (*Undirected) Density added in v0.1.0 

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 added in v0.1.0 

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 added in v0.1.0 

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 added in v0.1.0 

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 added in v0.1.0 

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 added in v0.1.0 

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

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

func (*Undirected) HasVertex added in v0.1.0 

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

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

func (*Undirected) InDegree added in v0.1.0 

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 added in v0.1.0 

func (g *Undirected) Order() int

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

func (*Undirected) OutDegree added in v0.1.0 

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 added in v0.1.0 

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

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

func (*Undirected) RemoveVertex added in v0.1.0 

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 added in v0.1.0 

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 added in v0.1.0 

type WeightedEdge interface {
	Edge
	Weight() int
}

A WeightedEdge is an Edge that also has a numerical weight.

type WeightedGraph added in v0.1.0 

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.

Source Files

View all Source files

Directories

Path Synopsis
Contains algos and logic related to depth-first graph traversal.
 Contains algos and logic related to depth-first graph traversal.

Jump to

Keyboard shortcuts

? : This menu
/ : Search site
f or F : Jump to
y or Y : Canonical URL
go.dev uses cookies from Google to deliver and enhance the quality of its services and to analyze traffic. Learn more.