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 ¶
- Constants
- Variables
- type DirectedGraph
- type DirectedMultigraph
- type DirectedPseudograph
- type DirectedWeightedMultigraph
- type DirectedWeightedPseudograph
- type Edge
- type EdgeSet
- type EdgeSetIterationFunc
- type Graph
- type GraphFeature
- type Mutable
- type MutableDirectedGraph
- type MutableDirectedWeightedGraph
- type MutableEdgeSet
- type MutableUndirectedGraph
- type MutableUndirectedWeightedGraph
- type MutableVertexSet
- type NotConnectedError
- type SimpleDirectedGraph
- type SimpleDirectedWeightedGraph
- type SimpleGraph
- type SimpleWeightedGraph
- type UndirectedGraph
- type UndirectedMultigraph
- type UndirectedPseudograph
- type UndirectedWeightedMultigraph
- type UndirectedWeightedPseudograph
- type Vertex
- type VertexNotFoundError
- type VertexSet
- type VertexSetIterationFunc
- type Weighted
Examples ¶
Constants ¶
const DefaultEdgeWeight = float64(1.)
DefaultEdgeWeight is the weight of an edge connected without explicitly specifying a weight in a weighted graph.
const DirectedGraphSupportedFeatures = DeterministicIteration
DirectedGraphSupportedFeatures are the features supported by all directed graphs.
const UndirectedGraphSupportedFeatures = DeterministicIteration
UndirectedGraphSupportedFeatures are the features supported by all undirected graphs.
Variables ¶
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.
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 ¶
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 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.
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 ¶
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.