graph

package module
v0.1.2-0...-9ef9a90 Latest Latest
Warning

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

 Go to latest Published: Jan 16, 2023 License: EPL-1.0 Imports: 4 Imported by: 1

Documentation

Overview

Package gographt provides interfaces and data structures that describe discrete graphs. It is inspired by the excellent JGraphT library (http://jgrapht.org/) and makes use of some applicable parts of it. Note that there are licensing constraints on JGraphT that may apply to this package as well; you may assume some risk by using it. See https://github.com/jgrapht/jgrapht/wiki/Relicensing for more information.

This package supports simple graphs, multigraphs, and pseudographs in both directed and undirected variants. Each of these variants may be weighted or unweighted.

A unique feature of this package is support for deterministic iteration; that is, each graph can retain information about the order of vertices and edges added to it, and given an immutable copy, iterate in a consistent order (not necessarily that of insertion, though). Most algorithms implemented also support deterministic iteration.

In general, public graph interfaces are immutable and the types returned by constructor methods are mutable. Algorithms that accept graphs will always use the immutable interfaces and clone the graph if needed to perform computations.

Index

Examples

Constants

View Source 
const DefaultEdgeWeight = float64(1.)

DefaultEdgeWeight is the weight of an edge connected without explicitly specifying a weight in a weighted graph.

View Source 
const DirectedGraphSupportedFeatures = DeterministicIteration

DirectedGraphSupportedFeatures are the features supported by all directed graphs.

View Source 
const UndirectedGraphSupportedFeatures = DeterministicIteration

UndirectedGraphSupportedFeatures are the features supported by all undirected graphs.

Variables

View Source 
var (
	// ErrEdgeAlreadyInGraph indicates that an edge could not be added to a
	// graph because an edge already exists in the graph.
	ErrEdgeAlreadyInGraph = errors.New("graph: edge already present")

	// ErrEdgeNotFound indicates that an operation involving an edge could not
	// be completed because that edge does not exist in the graph.
	ErrEdgeNotFound = errors.New("graph: edge does not exist")

	// ErrWouldCreateLoop indicates that the addition of an edge would create a
	// loop in the graph, and the graph does not support loops.
	ErrWouldCreateLoop = errors.New("graph: loop would be created by edge")
)

Functions

This section is empty.

Types

type DirectedGraph 

type DirectedGraph interface {
	Graph

	// InDegreeOf returns the number of edges directed toward the given vertex.
	// If the vertex does not exist in the graph, an error of type
	// VertexNotFoundError is returned. If prior knowledge ensures the vertex
	// exists in the graph, the error from this method can be safely ignored.
	InDegreeOf(vertex Vertex) (uint, error)

	// IncomingEdgesOf returns a read-only view of the edges that are directed
	// toward the given vertex. If the vertex does not exist in the graph, an
	// error of type VertexNotFoundError is returned. If prior knowledge ensures
	// the vertex exists in the graph, the error from this method can be safely
	// ignored.
	IncomingEdgesOf(vertex Vertex) (EdgeSet, error)

	// OutDegreeOf returns the number of edges directed outward from the given
	// vertex. If the vertex does not exist in the graph, an error of type
	// VertexNotFoundError is returned. If prior knowledge ensures the vertex
	// exists in the graph, the error from this method can be safely ignored.
	OutDegreeOf(vertex Vertex) (uint, error)

	// OutgoingEdgesOf returns a read-only view of the edges that are directed
	// outward from the given vertex. If the vertex does not exist in the graph,
	// an error of type VertexNotFoundError is returned. If prior knowledge
	// ensures the vertex exists in the graph, the error from this method can be
	// safely ignored.
	OutgoingEdgesOf(vertex Vertex) (EdgeSet, error)
}

A DirectedGraph is a graph for which the direction of an edge's assocation to its vertices is important.

type DirectedMultigraph 

type DirectedMultigraph struct {
	MutableDirectedGraph
}

A DirectedMultigraph is a directed graph that does not permit loops, but does permit multiple edges between any two vertices.

func NewDirectedMultigraph 

func NewDirectedMultigraph() *DirectedMultigraph

NewDirectedMultigraph creates a new directed multigraph.

func NewDirectedMultigraphWithFeatures 

func NewDirectedMultigraphWithFeatures(features GraphFeature) *DirectedMultigraph

NewDirectedMultigraphWithFeatures creates a new directed multigraph with the specified graph features.

type DirectedPseudograph 

type DirectedPseudograph struct {
	MutableDirectedGraph
}

A DirectedPseudograph is a directed graph that permits both loops and multiple edges between vertices.

func NewDirectedPseudograph 

func NewDirectedPseudograph() *DirectedPseudograph

NewDirectedPseudograph creates a new directed pseudograph.

func NewDirectedPseudographWithFeatures 

func NewDirectedPseudographWithFeatures(features GraphFeature) *DirectedPseudograph

NewDirectedPseudographWithFeatures a new directed pseudograph with the given graph features.

type DirectedWeightedMultigraph 

type DirectedWeightedMultigraph struct {
	MutableDirectedWeightedGraph
}

A DirectedWeightedMultigraph is a directed multigraph for which edges are assigned weights.

func NewDirectedWeightedMultigraph 

func NewDirectedWeightedMultigraph() *DirectedWeightedMultigraph

NewDirectedWeightedMultigraph creates a new directed weighted multigraph.

func NewDirectedWeightedMultigraphWithFeatures 

func NewDirectedWeightedMultigraphWithFeatures(features GraphFeature) *DirectedWeightedMultigraph

NewDirectedWeightedMultigraphWithFeatures creates a new directed weighted multigraph with the specified graph features.

type DirectedWeightedPseudograph 

type DirectedWeightedPseudograph struct {
	MutableDirectedWeightedGraph
}

A DirectedWeightedPseudograph is a directed pseudograph for which the edges are assigned weights.

func NewDirectedWeightedPseudograph 

func NewDirectedWeightedPseudograph() *DirectedWeightedPseudograph

NewDirectedWeightedPseudograph creates a new directed weighted pseudograph.

func NewDirectedWeightedPseudographWithFeatures 

func NewDirectedWeightedPseudographWithFeatures(features GraphFeature) *DirectedWeightedPseudograph

NewDirectedWeightedPseudographWithFeatures creates a new directed weighted pseudograph with the given graph features.

type Edge 

type Edge interface{}

An Edge is the type of a connection between vertices.

Edges may be any type; they are distinguished from interface{} only for clarity. When adding an edge to a graph, the Go language specification rules apply to determine whether the edge already exists.

func NewEdge 

func NewEdge() Edge

NewEdge creates a globally unique edge that can be added to any graph.

type EdgeSet 

type EdgeSet interface {
	// Contains returns true if the given edge exists in this set, and false
	// otherwise.
	Contains(edge Edge) bool

	// Count returns the number of edges in this set.
	Count() uint

	// AsSlice returns all the edges in this set as a slice.
	AsSlice() []Edge

	// ForEach iterates over each edge in this set, invoking the given function
	// on each iteration. If the function returns an error, iteration is stopped
	// and the error is returned.
	ForEach(fn EdgeSetIterationFunc) error
}

An EdgeSet is a read-only collection of edges.

type EdgeSetIterationFunc 

type EdgeSetIterationFunc func(edge Edge) error

EdgeSetIterationFunc is a callback function used by the ForEach method of an edge set.

This function can return datastructure.StopIteration to break from the iteration.

type Graph 

type Graph interface {
	// Features returns the graph features being used for this graph.
	Features() GraphFeature

	// EdgesBetween finds all edges that connect the given vertices and returns
	// a read-only view of them. If the DeterministicIteration feature is used
	// in this graph, the edge set will always iterate over the edges in the
	// same order.
	EdgesBetween(source, target Vertex) EdgeSet

	// EdgeBetween finds an arbitrary edge that connects the given vertices and
	// returns it. If the DeterministicIteration feature is used in this graph,
	// the returned edge will always be the same. If no edge connects the given
	// vertices, an error of type NotConnectedError is returned. If prior
	// knowledge ensures the vertices are connected by at least one edge, the
	// error from this method can be safely ignored.
	EdgeBetween(source, target Vertex) (Edge, error)

	// ContainsEdgeBetween returns true if at least one edge connects the given
	// source and target vertices, and false otherwise.
	ContainsEdgeBetween(source, target Vertex) bool

	// ContainsEdge returns true if the given edge exists in this graph, and
	// false otherwise.
	ContainsEdge(edge Edge) bool

	// ContainsVertex returns true if the given vertex exists in this graph, and
	// false otherwise.
	ContainsVertex(vertex Vertex) bool

	// Edges returns a read-only view of all edges in this graph. If the
	// DeterministicIteration feature is used in this graph, the edge set will
	// always iterate over the edges in the same order.
	Edges() EdgeSet

	// EdgesOf returns a read-only view of all edges connected to the given
	// vertex regardless of their direction. If the given vertex does not exist
	// in this graph, an error of type VertexNotFoundError is returned. If prior
	// knowledge ensures the vertex exists in the graph, the error from this
	// method can be safely ignored. If the DeterministicIteration feature is
	// used in this graph, the edge set will always iterate over the edges in
	// the same order.
	EdgesOf(vertex Vertex) (EdgeSet, error)

	// Vertices returns a read-only view of all vertices in this graph. If the
	// DeterministicIteration feature is used in this graph, the vertex set will
	// always iterate over the vertices in the same order.
	Vertices() VertexSet

	// SourceVertexOf returns the source vertex for a given edge. If the edge
	// does not exist in the graph, ErrEdgeNotFound is returned. If prior
	// knowledge ensures the edge exists in the graph, the error from this
	// method can be safely ignored.
	SourceVertexOf(edge Edge) (Vertex, error)

	// TargetVertexOf returns the target vertex for a given edge. If the edge
	// does not exist in the graph, ErrEdgeNotFound is returned. If prior
	// knowledge ensures the edge exists in the graph, the error from this
	// method can be safely ignored.
	TargetVertexOf(edge Edge) (Vertex, error)

	// WeightOf returns the weight associated with a given edge. For unweighted
	// graphs, this is always the same as DefaultEdgeWeight. If the edge does
	// not exist in the graph, ErrEdgeNotFound is returned. If prior knowledge
	// ensures the edge exists in the graph, the error from this method can be
	// safely ignored.
	WeightOf(edge Edge) (float64, error)
}

A Graph is a structure that contains a collection of vertices, some of which may be related to each other by edges.

type GraphFeature 

type GraphFeature uint

A GraphFeature is a mathematically transparent option for a graph. Graph features enable desireable application-specific functionality for a given graph (at the possible expense of performance). 

const (
	// DeterministicIteration is a graph feature that causes the insertion order
	// of vertices and edges for a graph to be retained. As a result, iteration
	// order over the vertices and edges will be the same, and many algorithms
	// will be evaluated identically for identical graph constructions.
	//
	// This feature is particularly useful for debugging or for unit tests.
	DeterministicIteration GraphFeature = 1 << iota
)

type Mutable 

type Mutable interface {
	// Connect adds an edge between the given source and target vertices. The
	// edge is created using the NewEdge function. If this graph does not
	// contain either the source or target vertices, an error of type
	// VertexNotFoundError is returned. If this graph does not permit multiple
	// edges and the source and target vertices are already connected,
	// ErrEdgeAlreadyInGraph is returned. If this graph does not permit loops
	// and the source and target vertices are the same, ErrWouldCreateLoop is
	// returned.
	Connect(source, target Vertex) error

	// AddEdge adds the given edge between the given source and target vertices.
	// If this graph already contains the given edge, ErrEdgeAlreadyInGraph is
	// returned. If this graph does not contain either the source or target
	// vertices, an error of type VertexNotFoundError is returned. If this graph
	// does not permit multiple edges and the source and target vertices are
	// already connected, ErrEdgeAlreadyInGraph is returned. If this graph does
	// not permit loops and the source and target vertices are the same,
	// ErrWouldCreateLoop is returned.
	AddEdge(source, target Vertex, edge Edge) error

	// AddVertex adds the given vertex to the graph. If the vertex already
	// exists in the graph, it is not duplicated.
	AddVertex(vertex Vertex)

	// RemoveEdges removes the given edges from the graph if they exists. It
	// returns true if the graph was modified, and false otherwise.
	RemoveEdges(edges []Edge) bool

	// RemoveEdgesBetween removes all edges that connect the given source and
	// target vertices and returns a read-only view of the removed edges. If the
	// DeterministicIteration feature is used by this graph, the edge set will
	// always iterate over the edges in the same order.
	RemoveEdgesBetween(source, target Vertex) EdgeSet

	// RemoveEdge removes the given edge from the graph if it exists. It returns
	// true if the graph was modified, and false otherwise.
	RemoveEdge(edge Edge) bool

	// RemoveEdgeBetween removes an arbitrary edge connecting the given source
	// and target vertices from the graph. If no edge connects the given
	// vertices, an error of type NotConnectedError is returned. Otherwise, the
	// removed edge is returned. If the DeterministicIteration feature is used
	// by this graph, repeated calls to this function will remove edges in the
	// same order.
	RemoveEdgeBetween(source, target Vertex) (Edge, error)

	// RemoveVertices removes the given vertices from this graph. It returns
	// true if the graph was modified, and false otherwise.
	RemoveVertices(vertices []Vertex) bool

	// RemoveVertex removes the given vertex from this graph. It returns true if
	// the graph was modified, and false otherwise.
	RemoveVertex(vertex Vertex) bool
}

Mutable is a graph mixin that allows graphs to be modified.

type MutableDirectedGraph 

type MutableDirectedGraph interface {
	DirectedGraph
	Mutable
}

A MutableDirectedGraph is a directed graph that supports modification.

type MutableDirectedWeightedGraph 

type MutableDirectedWeightedGraph interface {
	DirectedGraph
	Weighted
	Mutable
}

A MutableDirectedWeightedGraph is a directed weighted graph that supports modification.

type MutableEdgeSet 

type MutableEdgeSet interface {
	EdgeSet

	// Add adds the given edge to this set. If the edge already exists in this
	// set, it is not duplicated.
	Add(edge Edge)

	// Remove removes the given edge from this set if it exists.
	Remove(edge Edge)
}

A MutableEdgeSet is an extension of EdgeSet that additionally supports adding and removing edges.

func NewMutableEdgeSet 

func NewMutableEdgeSet(storage datastructure.Set) MutableEdgeSet

NewMutableEdgeSet creates a new mutable edge set using the given underlying set to store the edges.

type MutableUndirectedGraph 

type MutableUndirectedGraph interface {
	UndirectedGraph
	Mutable
}

A MutableUndirectedGraph is an undirected graph that supports modification.

type MutableUndirectedWeightedGraph 

type MutableUndirectedWeightedGraph interface {
	UndirectedGraph
	Weighted
	Mutable
}

A MutableUndirectedWeightedGraph is an undirected weighted graph that supports modification.

type MutableVertexSet 

type MutableVertexSet interface {
	VertexSet

	// Add adds the given vertex to this set. If the vertex already exists in
	// this set, it is not duplicated.
	Add(vertex Vertex)

	// Remove removes the given vertex from this set if it exists.
	Remove(vertex Vertex)
}

A MutableVertexSet is an extension of VertexSet that additionally supports adding and removing vertices.

type NotConnectedError 

type NotConnectedError struct {
	Source, Target Vertex
}

NotConnectedError indicates that an operation involving two vertices could not be completed because no edges connect those vertices.

func (*NotConnectedError) Error 

func (e *NotConnectedError) Error() string

type SimpleDirectedGraph 

type SimpleDirectedGraph struct {
	MutableDirectedGraph
}

A SimpleDirectedGraph is a directed graph that does not permit loops or multiple edges between vertices.

func NewSimpleDirectedGraph 

func NewSimpleDirectedGraph() *SimpleDirectedGraph

NewSimpleDirectedGraph creates a new simple directed graph.

func NewSimpleDirectedGraphWithFeatures 

func NewSimpleDirectedGraphWithFeatures(features GraphFeature) *SimpleDirectedGraph

NewSimpleDirectedGraphWithFeatures creates a new simple directed graph with the specified graph features.

type SimpleDirectedWeightedGraph 

type SimpleDirectedWeightedGraph struct {
	MutableDirectedWeightedGraph
}

A SimpleDirectedWeightedGraph is a simple directed graph for which edges are assigned weights.

func NewSimpleDirectedWeightedGraph 

func NewSimpleDirectedWeightedGraph() *SimpleDirectedWeightedGraph

NewSimpleDirectedWeightedGraph creates a new simple directed weighted graph.

func NewSimpleDirectedWeightedGraphWithFeatures 

func NewSimpleDirectedWeightedGraphWithFeatures(features GraphFeature) *SimpleDirectedWeightedGraph

NewSimpleDirectedWeightedGraphWithFeatures creates a new simple directed weighted graph with the specified graph features.

type SimpleGraph 

type SimpleGraph struct {
	MutableUndirectedGraph
}

A SimpleGraph is an undirected graph that does not permit loops or multiple edges between vertices.

Example 
g := NewSimpleGraph()
g.AddVertex("Charles")
g.AddVertex("Manson")
g.AddVertex("Marilyn")
g.AddVertex("Monroe")

g.Connect("Charles", "Manson")
g.Connect("Marilyn", "Monroe")
g.Connect("Marilyn", "Manson")

fmt.Println("Vertices:", g.Vertices().Count())
fmt.Println("Edges:", g.Edges().Count())

Output:

Vertices: 4
Edges: 3

func NewSimpleGraph 

func NewSimpleGraph() *SimpleGraph

NewSimpleGraph creates a new simple graph.

func NewSimpleGraphWithFeatures 

func NewSimpleGraphWithFeatures(features GraphFeature) *SimpleGraph

NewSimpleGraphWithFeatures creates a new simple graph with the specified graph features.

type SimpleWeightedGraph 

type SimpleWeightedGraph struct {
	MutableUndirectedWeightedGraph
}

A SimpleWeightedGraph is a simple graph for which edges are assigned weights.

func NewSimpleWeightedGraph 

func NewSimpleWeightedGraph() *SimpleWeightedGraph

NewSimpleWeightedGraph creates a new simple weighted graph.

func NewSimpleWeightedGraphWithFeatures 

func NewSimpleWeightedGraphWithFeatures(features GraphFeature) *SimpleWeightedGraph

NewSimpleWeightedGraphWithFeatures creates a new simple weighted graph with the specified graph features.

type UndirectedGraph 

type UndirectedGraph interface {
	Graph

	// DegreeOf returns the number of edges connected to the given vertex. If
	// the vertex does not exist in the graph, an error of type
	// VertexNotFoundError is returned. If prior knowledge ensures the vertex
	// exists in the graph, the error from this method can be safely ignored.
	DegreeOf(vertex Vertex) (uint, error)
}

An UndirectedGraph is a graph for which the direction of an edge's assocation to its vertices is not important.

type UndirectedMultigraph 

type UndirectedMultigraph struct {
	MutableUndirectedGraph
}

An UndirectedMultigraph is an undirected graph that does not permit loops, but does permit multiple edges between any two vertices.

func NewUndirectedMultigraph 

func NewUndirectedMultigraph() *UndirectedMultigraph

NewUndirectedMultigraph creates a new undirected multigraph.

func NewUndirectedMultigraphWithFeatures 

func NewUndirectedMultigraphWithFeatures(features GraphFeature) *UndirectedMultigraph

NewUndirectedMultigraphWithFeatures creates a new undirected multigraph with the specified graph features.

type UndirectedPseudograph 

type UndirectedPseudograph struct {
	MutableUndirectedGraph
}

An UndirectedPseudograph is an undirected graph that permits both loops and multiple edges between vertices.

func NewUndirectedPseudograph 

func NewUndirectedPseudograph() *UndirectedPseudograph

NewUndirectedPseudograph creates a new undirected pseudograph.

func NewUndirectedPseudographWithFeatures 

func NewUndirectedPseudographWithFeatures(features GraphFeature) *UndirectedPseudograph

NewUndirectedPseudographWithFeatures creates a new undirected pseudograph with the specified graph features.

type UndirectedWeightedMultigraph 

type UndirectedWeightedMultigraph struct {
	MutableUndirectedWeightedGraph
}

An UndirectedWeightedMultigraph is an undirected multigraph for which edges are assigned weights.

func NewUndirectedWeightedMultigraph 

func NewUndirectedWeightedMultigraph() *UndirectedWeightedMultigraph

NewUndirectedWeightedMultigraph creates a new undirected weighted multigraph.

func NewUndirectedWeightedMultigraphWithFeatures 

func NewUndirectedWeightedMultigraphWithFeatures(features GraphFeature) *UndirectedWeightedMultigraph

NewUndirectedWeightedMultigraphWithFeatures creates a new undirected weighted multigraph with the specified graph features.

type UndirectedWeightedPseudograph 

type UndirectedWeightedPseudograph struct {
	MutableUndirectedWeightedGraph
}

An UndirectedWeightedPseudograph is an undirected pseudograph for which edges are assigned weights.

func NewUndirectedWeightedPseudograph 

func NewUndirectedWeightedPseudograph() *UndirectedWeightedPseudograph

NewUndirectedWeightedPseudograph creates a new undirected weighted pseudograph.

func NewUndirectedWeightedPseudographWithFeatures 

func NewUndirectedWeightedPseudographWithFeatures(features GraphFeature) *UndirectedWeightedPseudograph

NewUndirectedWeightedPseudographWithFeatures creates a new undirected weighted pseudograph with the specified graph features.

type Vertex 

type Vertex interface{}

A Vertex is the type of a node used in a graph.

Vertices may be any type; they are distinguished from interface{} only for clarity. When adding a vertex to a graph, the Go language specification comparison rules apply to determine whether the vertex already exists.

func OppositeVertexOf 

func OppositeVertexOf(g Graph, e Edge, v Vertex) (Vertex, error)

OppositeVertexOf finds, for any graph, the vertex connected by the given edge that is not the given vertex.

type VertexNotFoundError 

type VertexNotFoundError struct {
	Vertex Vertex
}

VertexNotFoundError indicates that an operation involving a given vertex could not be completed because that vertex does not exist in the graph.

func (*VertexNotFoundError) Error 

func (e *VertexNotFoundError) Error() string

type VertexSet 

type VertexSet interface {
	// Contains returns true if the given vertex exists in this set, and false
	// otherwise.
	Contains(vertex Vertex) bool

	// Count returns the number of vertices in this set.
	Count() uint

	// AsSlice returns all the vertices in this set as a slice.
	AsSlice() []Vertex

	// ForEach iterates over each vertex in this set, invoking the given
	// function on each iteration. If the function returns an error, iteration
	// is stopped and the error is returned.
	ForEach(fn VertexSetIterationFunc) error
}

A VertexSet is a read-only collection of vertices.

type VertexSetIterationFunc 

type VertexSetIterationFunc func(vertex Vertex) error

VertexSetIterationFunc is a callback function used by the ForEach method of a vertex set.

This function can return datastructure.StopIteration to break from the iteration.

type Weighted 

type Weighted interface {
	// ConnectWithWeight associates the given source and target vertices with
	// each other using the same mechanism as Connect. The given weight is used
	// to label the resulting connection.
	ConnectWithWeight(source, target Vertex, weight float64) error

	// AddEdgeWithWeight associates the given source and target vertices with
	// each other using the given edge. The given weight is used to label the
	// resulting connection.
	AddEdgeWithWeight(source, target Vertex, edge Edge, weight float64) error
}

Weighted is a graph mixin that allows edges to be assigned arbitrary numerical weights. These weights can be important in evaluating certain algorithms.

Source Files

View all Source files

Directories

Path Synopsis

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.