Documentation ¶
Index ¶
- func AdjacencyMatrixEncode(g Graph) string
- func AllMaximalCliques(g Graph, c chan []int)
- func BiconnectedComponents(g Graph) ([][]int, []int)
- func CanonicalIsomorph(g Graph) []int
- func CanonicalIsomorphAllocated(n, m int, neighbours [][]int, op *CanonicalOrderedPartition, ...) ([]int, disjoint.Set, [][]int)
- func CanonicalIsomorphFull(g Graph, vertexClasses [][]int) ([]int, disjoint.Set, [][]int)
- func ChromaticIndex(g Graph) (chromaticIndex int, colouredEdges []byte)
- func ChromaticNumber(g Graph) (chromaticNumber int, colouring []int)
- func ChromaticPolynomial(g EditableGraph) []int
- func CliqueNumber(g Graph) int
- func ConnectedComponent(g Graph, v int) []int
- func ConnectedComponents(g Graph) [][]int
- func Contract(g EditableGraph, i, j int)
- func Degeneracy(g Graph) (d int, order []int)
- func Diameter(g Graph) int
- func Distance(g Graph, i, j int) int
- func Eccentricity(g Graph) []int
- func Equal(g, h Graph) bool
- func Girth(g Graph) int
- func Graph6Encode(g Graph) string
- func GreedyColor(g Graph, order []int) (int, []int)
- func IndependenceNumber(g Graph) int
- func IsKColorable(g Graph, k int) (ok bool, colouring []int)
- func IsPlanar(g Graph) bool
- func IsProperColouring(g Graph, colouring []int) bool
- func MaxDegree(g Graph) int
- func MinDegree(g Graph) int
- func MulticodeEncode(g Graph) []byte
- func NumberOfCycles(g EditableGraph) []int
- func NumberOfInducedCycles(g Graph, maxLength int) []int
- func NumberOfInducedPaths(g Graph, maxLength int) []int
- func PruferEncode(g Graph) []int
- func Radius(g Graph) int
- func RandomMaximalClique(g Graph, seed int64) []int
- func Sparse6Encode(g Graph) string
- func SplitEdge(g EditableGraph, i, j int)
- type CanonicalOptions
- type CanonicalOrderedPartition
- type CanonicalStorage
- type DenseGraph
- func BipartiteKneserGraph(n, k int) *DenseGraph
- func CirculantBipartiteGraph(n int, m int, diffs ...int) *DenseGraph
- func CirculantGraph(n int, diffs ...int) *DenseGraph
- func ComplementDense(g Graph) *DenseGraph
- func CompleteGraph(n int) *DenseGraph
- func CompletePartiteGraph(nums ...int) *DenseGraph
- func Cycle(n int) *DenseGraph
- func FlowerSnark(n int) *DenseGraph
- func FoldedHypercubeGraph(dim int) *DenseGraph
- func FriendshipGraph(n int) *DenseGraph
- func GeneralisedPetersenGraph(n, k int) *DenseGraph
- func Graph6Decode(s string) (*DenseGraph, error)
- func HypercubeGraph(dim int) *DenseGraph
- func KneserGraph(n, k int) *DenseGraph
- func LineGraphDense(g Graph) *DenseGraph
- func MulticodeDecode(s []byte) *DenseGraph
- func MulticodeDecodeMultiple(s []byte) []*DenseGraph
- func NewDense(n int, edges []byte) *DenseGraph
- func Path(n int) *DenseGraph
- func PruferDecode(p []int) *DenseGraph
- func RandomGraph(n int, p float64, seed int64) *DenseGraph
- func RandomTree(n int, seed int64) *DenseGraph
- func RookGraph(n, m int) *DenseGraph
- func Star(n int) *DenseGraph
- func (g *DenseGraph) AddEdge(i, j int)
- func (g *DenseGraph) AddVertex(neighbours []int)
- func (g *DenseGraph) Copy() EditableGraph
- func (g DenseGraph) Degrees() []int
- func (g *DenseGraph) InducedSubgraph(V []int) EditableGraph
- func (g DenseGraph) IsEdge(i, j int) bool
- func (g DenseGraph) M() int
- func (g DenseGraph) N() int
- func (g DenseGraph) Neighbours(v int) []int
- func (g *DenseGraph) RemoveEdge(i, j int)
- func (g *DenseGraph) RemoveVertex(v int)
- type EditableGraph
- type Graph
- type SparseGraph
- func (g *SparseGraph) AddEdge(i, j int)
- func (g *SparseGraph) AddVertex(neighbours []int)
- func (g SparseGraph) Copy() EditableGraph
- func (g SparseGraph) Degrees() []int
- func (g SparseGraph) InducedSubgraph(V []int) EditableGraph
- func (g SparseGraph) IsEdge(i, j int) bool
- func (g SparseGraph) M() int
- func (g SparseGraph) N() int
- func (g SparseGraph) Neighbours(v int) []int
- func (g *SparseGraph) RemoveEdge(i, j int)
- func (g *SparseGraph) RemoveVertex(i int)
Constants ¶
This section is empty.
Variables ¶
This section is empty.
Functions ¶
func AdjacencyMatrixEncode ¶
AdjacencyMatrixEncode returns an encoding of the adjacency matrix of g suitable for copying into MATLAB. The matrix starts with a [ and ends with a ]. Elements on the same row are separated by , and rows are separated by ;
func AllMaximalCliques ¶
AllMaximalCliques returns every maximal clique in g. This uses the Bron–Kerbosch algorithm with pivots chosen to reduce the number of branches at each point and currently doesn't use a vertex ordering for the first pass.
func BiconnectedComponents ¶
BiconnectedComponents returns the biconnected components and the articulation vertices.
func CanonicalIsomorph ¶
CanonicalIsomorph returns a permutation which gives the canonical isomorph when applied to the graph. The actual canonical isomorph can be obtained by running InducedSubgraph(CanonicalIsomorph(g)). The canonical isomorph is the chosen representation of the isomorphism class containing g. In particular, the canonical isomorph of two graphs is the same if and only if they are isomorphic.
func CanonicalIsomorphAllocated ¶
func CanonicalIsomorphAllocated(n, m int, neighbours [][]int, op *CanonicalOrderedPartition, storage *CanonicalStorage, options *CanonicalOptions) ([]int, disjoint.Set, [][]int)
CanonicalIsomorphAllocated returns the same values as CanonicalIsomorphFull but requires more setup. This means that the CanonicalStorage and CanonicalOrderedPartition can be resued to reduce the number of allocations when calling this for many graphs. This function is also currently the only function which allows the setting of options. It is not recommended to call this function unless you know you need to reduce the allocations or you need to set options. See the source for CanonicalIsomorphFull for an example of how to call this function. Note that op, storage and options may be modified when calling this function and modifying storage may modify the output of this function.
func CanonicalIsomorphFull ¶
CanonicalIsomorphFull returns the permutation which when applied to g gives the canonical isomorph, a disjoint.Set giving the vertex orbits and a set of generators for the autmorphism group of g.
func ChromaticIndex ¶
ChromaticIndex returns the minimum number of colours needed in a proper edge colouring of g (known as the Chromatic Index χ') and a colouring that uses this many colours ([1, ..., χ']). The colouring is returned in the form of an edge array with 0 for non-edges and a colour in [1, 2,..., χ'] for the edges. Note that a colouring with the minimum number of colours is not necessarily unique and the colouring returned here is arbitrary.
func ChromaticNumber ¶
ChromaticNumber returns the minimum number of colours needed in a proper vertex colouring of g (known as the Chromatic Number χ) and a colouring that uses this many colours ([0, 1, ..., χ -1]). Note that a colouring with the minimum number of colours is not necessarily unique and the colouring returned here is arbitrary.
func ChromaticPolynomial ¶
func ChromaticPolynomial(g EditableGraph) []int
ChromaticPolynomial returns the coefficients of the chromatic polynomial. This is a very basic implementation.
func CliqueNumber ¶
CliqueNumber returns the size of the largest clique in g. This effectively finds all maximal cliques by using the Bron–Kerbosch algorithm with pivots chosen to reduce the number of branches at each point. This doesn't currently use a vertex ordering for the first pass.
func ConnectedComponent ¶
ConnectedComponent returns the connected component in g containing v.
func ConnectedComponents ¶
ConnectedComponents returns all the connected components of g.
func Contract ¶
func Contract(g EditableGraph, i, j int)
Contract modifies g by adding edges from i to all the neighbours of j and then removing the vertex j. The main use case will be contracting an edge although this doesn't require the edge (i,j) to be present. One may wish to consider the order of i and j for performance reasons e.g. in a DenseGraph removing the vertex of larger index requires fewer copies and is likely to be quicker.
func Degeneracy ¶
Degeneracy returns the smallest integer d such that every ordering of the vertices contains a vertex preceded by at least d neighbours. It also returns an ordering where no vertex is proceeded by d + 1 neighbours.
func Diameter ¶
Diameter returns the diameter of a graph or -1 for a disconnected graph. The diameter is the maximum eccentricity of the vertices of the graph i.e. it is the length of the longest shortest path in g.
func Distance ¶
Distance returns the length of the shortest path from i to j in g and -1 if there is no path It finds this by doing a BFS search.
func Eccentricity ¶
Eccentricity returns a slice giving the eccentricity of each vertex and a slice of -1s if the graph is disconnected. The eccentricity of a vertex v is the maximum over vertices u of the length of the shortest path from v to u.
func Equal ¶
Equal returns true if the two lablled graphs are exactly equal and false otherwise. To test is two graphs are isomorphic the graphs need to be transformed into their canonical isomorphs first (e.g. by using g.InducedSubgraph(g.CanonicalIsomorph()))
func Girth ¶
Girth returns the size of the shortest cycle in g. It finds the shortest cycle by using a BFS algorithm to find the shortest cycle containing each vertex v. This is probably not the most efficient way. Directed graps are currently not supported.
func Graph6Encode ¶
Graph6Encode returns the Graph6 encoding of g. For the definition of the format see: https://users.cecs.anu.edu.au/~bdm/data/formats.txt
func GreedyColor ¶
GreedyColor greedily colours the graph G colouring the vertices in the given order. That is, this reads the vertices in the given order and assigns to each vertex the minimum colour such that none of its neighbour have this colour.
func IndependenceNumber ¶
IndependenceNumber returns the size of the largest independent set in g. The independence number of g is the clique number of the complement of g and this is how it is calculated here.
func IsKColorable ¶
IsKColorable returns true if there is a proper colouring with k colours and an example colouring, else it returns false, nil.
func IsPlanar ¶
IsPlanar returns true if the graph is a planar graph and false otherwise. The current implementation is simple but runs in O(n^2) while linear time algorithms are known. TODO Which algorithm does this use? TODO Can we make it output a planar embedding?
func IsProperColouring ¶
IsProperColouring checks if the vertex colouring is a proper colouring of the graph g. It assumes that all colours are \geq 0 and that a colour <0 is a mistake. This is because the colour -1 is often used to indicate no colour.
func MulticodeEncode ¶
MulticodeEncode returns the Multicode encoding of g.
func NumberOfCycles ¶
func NumberOfCycles(g EditableGraph) []int
NumberOfCycles returns a slice where the ith element contains the number of cycles of length i. Any cycle is contained in a biconnected component so the algorithm first splits the graph into biconnected components. The algorithm involves finding a spanning tree and this implementation doesn't check it finds every vertex so splitting into at least components is necessary. Spliting into biconnected components should help prevent unnecessary XORing when checking all the cycles. We find a set of fundamental cycles according to the paper K. Paton, An algorithm for finding a fundamental set of cycles for an undirected linear graph, Comm. ACM 12 (1969), pp. 514-518. We can then find all cycles XORing together every combination of fundamental cycles and ignoring ones which are made of copies of 2 or more disjoing cycles. This is done according to Gibb's Algorithm from ALGORITHMIC APPROACHES TO CIRCUIT ENUMERATION PROBLEMS AND APPLICATIONS by Boon Chai Lee avaible here: http://dspace.mit.edu/bitstream/handle/1721.1/68106/FTL_R_1982_07.pdf. This effectively finds every cycle in the graph and could be adapted to output every cycle if required. Remember to switch from the labels in the biconnected component to the labels of the graph and that the edges are not stored in the order in the cycle.
func NumberOfInducedCycles ¶
NumberOfInducedCycles returns a slice of length n containing the number of induced cycles in g which are of length at most k. The length of a cycle is the number of edges in the cycle, or equivalently, the number of vertices in the cycle.
func NumberOfInducedPaths ¶
NumberOfInducedPaths returns a slice of length n containing the number of induced paths in g which are of length at most k. The length of a path is the number of edges in the path.
func PruferEncode ¶
PruferEncode returns the Prüfer code of the labelled tree g. https://en.wikipedia.org/wiki/Pr%C3%BCfer_sequence
func Radius ¶
Radius returns the raidus of a graph or -1 for a disconnected graph. The radius is the minimum eccentricity of the vertices of the graph.
func RandomMaximalClique ¶
RandomMaximalClique builds a random maximal clique by iteratively choosing an allowed vertex uniformly at random and adding it to the clique.
func Sparse6Encode ¶
Sparse6Encode returns an encoding of g. Note that the encoding is not unique but this should align with the format used by showg, geng, nauty etc. For the definition of the format see: https://users.cecs.anu.edu.au/~bdm/data/formats.txt
func SplitEdge ¶
func SplitEdge(g EditableGraph, i, j int)
SplitEdge modifies the graph G by removing the edge ij (if it is present) and adding a new vertex connected to i and j.
Types ¶
type CanonicalOptions ¶
type CanonicalOptions struct { CheckViability bool //If CheckViability is true, the first call to equitableRefinementPartition will check that the last vertex (n-1) is in the same bin as the earliest vertex in ViableBits. If the vertex is in a different bin, CanonicalIsomorphAllocated returns nil, nil, nil (and this is the only time it does so). No guess has been made at this point so if two vertices are in different bins, they are in different orbits. This is useful for a canonical deletion search. Note that since ViableBits is a uint, this setting is valid for small-ish graphs. ViableBits uint //Put a one in bit i (starting from the low bits) if you want the function to return early if the vertex i is in an earlier bin than the vertex n - 1. }
CanonicalOptions is a struct containing the options for a call to CanonicalIsomorphAllocated. The zero value gives the default settings.
type CanonicalOrderedPartition ¶
type CanonicalOrderedPartition struct {
// contains filtered or unexported fields
}
CanonicalOrderedPartition contains the current ordered partition used in the canonical isomorph function. A CanonicalOrderedPartition should be generated using the function NewOrderedPartition and can be reset for a second use by calling the function Reslice. It will be modified when used.
func NewOrderedPartition ¶
func NewOrderedPartition(n, m int, vertexClasses [][]int) *CanonicalOrderedPartition
NewOrderedPartition creates a new ordered partition which is large enough for a graph with n vertices and m edges and initialises it with the given vertexClasses. If the vertexClasses is nil, all the vertices are treated as being in the same vertex class. A CanonicalOrderedPartition can be reset for smaller graphs but not larger graphs so searches may want to initialise a large CanonicalOrderedPartition at the start.
func (*CanonicalOrderedPartition) Reset ¶
func (op *CanonicalOrderedPartition) Reset(n, m int, vertexClasses [][]int)
Reset resets the CanonicalOrderedPartition to the initial state for a graph with n vertices, m edges and using the given vertex classes. A CanonicalOrderedPartition can be reset to handle a smaller graph but will panic if reset for a larger graph. TODO: The case of 0.
type CanonicalStorage ¶
type CanonicalStorage struct {
// contains filtered or unexported fields
}
CanonicalStorage contains the working space for the CanonicalIsomorphAllocated function and can be reused multiple times. It will be suitably reset by the call to CanonicalIsomorphAllocated. To create the storage space for a graph on at most n vertices and with at most m edges, call NewStorage(n, m)
func NewStorage ¶
func NewStorage(n, m int) *CanonicalStorage
NewStorage creates the necessary storage space for a call to CanonicalIsomorphAllocated with a graph with at most n vertices and m edges.
type DenseGraph ¶
DenseGraph is a data structure representing a simple undirected labelled graph. DenseGraph stores the number of vertices, the number of edges, the degree sequence of the graph and stores the edges in a []byte array which has an indicator of an edge being present. The edges are in the order 01, 02, 12, 03, 13, 23... so the edge ij with i < j is in the (j*(j-1))/2 + i place. Adding or removing edges are quick operations. Adding a vertex may be quick if the backing array doesn't have to grow but may require copying the entire adjacency matrix. Removing a vertex is generally slow. *DenseGraph implements the Graph interface.
func BipartiteKneserGraph ¶
func BipartiteKneserGraph(n, k int) *DenseGraph
BipartiteKneserGraph returns the a bipartite graph vertices [n]^{(k)} on one side and [n]^{(n-k)} on the other and an edge between two sets if they are on different sides and one is a subset of the other.
func CirculantBipartiteGraph ¶
func CirculantBipartiteGraph(n int, m int, diffs ...int) *DenseGraph
CirculantBipartiteGraph creates a bipartite graph with vertices a_1, \dots, a_n in one class, b_1, \dots, b_m in the other and a edge between a_i and b_j if j - i is in diffs (mod m).
func CirculantGraph ¶
func CirculantGraph(n int, diffs ...int) *DenseGraph
CirculantGraph generates a graph on n vertices where there is an edge between i and j if j-i is in diffs.
func ComplementDense ¶
func ComplementDense(g Graph) *DenseGraph
ComplementDense returns the graph on the same vertices as g where an edge is present if and only if it isn't present in g.
func CompleteGraph ¶
func CompleteGraph(n int) *DenseGraph
CompleteGraph returns a copy of the complete graph on n vertices.
func CompletePartiteGraph ¶
func CompletePartiteGraph(nums ...int) *DenseGraph
CompletePartiteGraph returns the complete partite graph where the ith part has nums[i] elements.
func FlowerSnark ¶
func FlowerSnark(n int) *DenseGraph
FlowerSnark returns the flower snark on 4n vertices for n odd. See https://en.wikipedia.org/wiki/Flower_snark
func FoldedHypercubeGraph ¶
func FoldedHypercubeGraph(dim int) *DenseGraph
FoldedHypercubeGraph returns a hypergraph on 2^{(dim - 1)} vertices except each point is joined with its antipodal point.
func FriendshipGraph ¶
func FriendshipGraph(n int) *DenseGraph
FriendshipGraph returns the graph woth 2n + 1 vertices and 3n edges which is n copies of C_3 which share a common vertex.
func GeneralisedPetersenGraph ¶
func GeneralisedPetersenGraph(n, k int) *DenseGraph
GeneralisedPetersenGraph returns the graph with vertices {u_0,...u_{n-1}, v_0,...v_{n-1}} with edges {u_i u_{i+1}, u_i v_i, v_i v_{i+k}: i = 0,...,n − 1} where subscripts are to be read modulo n. n must be at least 3 and k must be between 1 and floor((n-1)/2). The Petersen graph is GeneralisedPetersenGraph(5,2) and several other named graphs are generalised Petersen graphs.
func Graph6Decode ¶
func Graph6Decode(s string) (*DenseGraph, error)
Graph6Decode returns the graph with Graph6 encoding s or an error. For the definition of the format see: https://users.cecs.anu.edu.au/~bdm/data/formats.txt The empty string decodes as the empty graph.
func HypercubeGraph ¶
func HypercubeGraph(dim int) *DenseGraph
HypercubeGraph returns the dim-dimensional hypercube graph on 2^(dim) vertices.
func KneserGraph ¶
func KneserGraph(n, k int) *DenseGraph
KneserGraph returns the Kneser graph with parameters n and k. It has a vertex for each unordered subset of {0,...,n-1} of size k and an edge between two subsets if they are disjoint. The subsets are ordered in co-lexicographic.
func LineGraphDense ¶
func LineGraphDense(g Graph) *DenseGraph
LineGraphDense returns a graph L which has the edges of g as its vertices and two vertices are joined in L iff the corresponding edges in g share a vertex.
func MulticodeDecode ¶
func MulticodeDecode(s []byte) *DenseGraph
MulticodeDecode returns the graph with Multicode encoding s.
func MulticodeDecodeMultiple ¶
func MulticodeDecodeMultiple(s []byte) []*DenseGraph
MulticodeDecodeMultiple returns an array of graphs encoded in s.
func NewDense ¶
func NewDense(n int, edges []byte) *DenseGraph
NewDense returns a pointer to a DenseGraph representation of the graph with n vertices and the edges as given in edges. The edges are in the order 01, 02, 12, 03, 13, 23... so the edge ij with i < j is in the (j*(j-1))/2 + i place. The *DenseGraph uses its own copy of edges and modifications to edges won't change the current graph. *DenseGraph implements the Graph interface.
func PruferDecode ¶
func PruferDecode(p []int) *DenseGraph
PruferDecode returns the labelled tree given by the Prüfer code p.
func RandomGraph ¶
func RandomGraph(n int, p float64, seed int64) *DenseGraph
RandomGraph returns an Erdős–Rényi graph with n vertices and edge probability p. The pseudorandomness is determined by the seed.
func RandomTree ¶
func RandomTree(n int, seed int64) *DenseGraph
RandomTree returns a tree chosen uniformly at random from all trees on n vertices. This constructs a random Prufer code and converts into a tree.
func RookGraph ¶
func RookGraph(n, m int) *DenseGraph
RookGraph returns the n x m Rook graph i.e. the graph representing the moves of a rook on an n x m chessboard. If m = n, the graph is also called a Latin square graph.
func (*DenseGraph) AddEdge ¶
func (g *DenseGraph) AddEdge(i, j int)
AddEdge modifies the graph by adding the edge (i, j) if it is not already present. If the edge is already present (or i == j), this does nothing.
func (*DenseGraph) AddVertex ¶
func (g *DenseGraph) AddVertex(neighbours []int)
AddVertex modifies the graph by appending one new vertex with edges from the new vertex to the vertices in neighbours.
func (*DenseGraph) Copy ¶
func (g *DenseGraph) Copy() EditableGraph
Copy returns a deep copy of the graph g.
func (DenseGraph) Degrees ¶
func (g DenseGraph) Degrees() []int
Degrees returns the slice containing the degrees (number of edges incident with the vertex) of each vertex.
func (*DenseGraph) InducedSubgraph ¶
func (g *DenseGraph) InducedSubgraph(V []int) EditableGraph
InducedSubgraph returns a deep copy of the induced subgraph of g with vertices given in order by V. This can also be used to return relabellings of the graph if len(V) = g.N().
func (DenseGraph) IsEdge ¶
func (g DenseGraph) IsEdge(i, j int) bool
IsEdge returns true if the undirected edge (i, j) is present in the graph and false otherwise.
func (DenseGraph) Neighbours ¶
func (g DenseGraph) Neighbours(v int) []int
Neighbours returns the neighbours of v i.e. the vertices u such that (u,v) is an edge.
func (*DenseGraph) RemoveEdge ¶
func (g *DenseGraph) RemoveEdge(i, j int)
RemoveEdge modifies the graph by removing the edge (i, j) if it is present. If the edge is not already present, this does nothing.
func (*DenseGraph) RemoveVertex ¶
func (g *DenseGraph) RemoveVertex(v int)
RemoveVertex modifies the graph by removing the speicified vertex. The index of a vertex u > v becomes u - 1 while the index of u < v is unchanged.
type EditableGraph ¶
type EditableGraph interface { Graph //AddVertex modifies the graph by appending one new vertex with edges from the new vertex to the vertices in neighbours. AddVertex(neighbours []int) //RemoveVertex modifies the graph by removing the speicified vertex. The index of a vertex u > v becomes u - 1 while the index of u < v is unchanged. RemoveVertex(i int) //AddEdge modifies the graph by adding the edge (i, j) if it is not already present. AddEdge(i, j int) //RemoveEdge modifies the graph by removing the edge (i, j) if it is present. RemoveEdge(i, j int) //InducedSubgraph returns a deep copy of the induced subgraph of g with vertices given in order by V. This must not modify g. InducedSubgraph(V []int) EditableGraph //Copy returns a deep copy of the graph g. Copy() EditableGraph }
EditableGraph is the interface which represent a graph which can be copied and edited.
type Graph ¶
type Graph interface { //N() returns the number of vertices in the graph. N() int //M() returns the number of edges in the graph. M() int //IsEdge returns true if the edge is in the graph and false otherwise. It may panic if i or j are not in the appropriate range (although one could argue the correct response is really false). IsEdge(i, j int) bool //Neighbours returns the neighbours of the vertex v. Neighbours(v int) []int //Degrees returns the degree sequence of g. Degrees() []int }
Graph is the interface that represents a graph which cannot be copied or edited.
func Complement ¶
Complement returns the complement of a graph. Updating the original graph, changes the complement.
func InducedSubgraph ¶
InducedSubgraph returns a graph which represents the subgraph of g induced by the vertices in V in the order they are in V. The properties of the induced subgraph are calculated from g when called and reflect the current state of g. If a vertex in V is no longer in the graph, the behaviour of this function is unspecified.
type SparseGraph ¶
type SparseGraph struct { NumberOfVertices int NumberOfEdges int Neighbourhoods []sortints.SortedInts DegreeSequence []int }
SparseGraph is a data structure for representing a simple undirected graph. *SparseGraph implements the graph insterface. SparseGraph stores the number of vertices, the number of edges, the degree sequence of the graph and the neighbourhood of edge vertex. Most modifications are slow as the edges are stored as SortedInts and not a data structure with log(n) modifications but sparse graphs take up relatively little space. Checking if an individual edge is present is logarithmic in the degree of the vertices but returning the neighbours is quick so most algorithms run fairly quickly. TODO Do we want to switch the neighbourhoods to using some kind of heap with quicker insertions and deletions?
func NewSparse ¶
func NewSparse(n int, neighbourhoods []sortints.SortedInts) *SparseGraph
NewSparse create the graph on n vertices with the specified neighbours. If neighbourhoods is nil, the empty graph is created. TODO Check that this is a graph. Check SortedInts are in fact sorted.
func Sparse6Decode ¶
func Sparse6Decode(s string) (*SparseGraph, error)
Sparse6Decode decode returns the graph with Sparse6 encoding s or an error if no such graph exists. For the definition of the format see: https://users.cecs.anu.edu.au/~bdm/data/formats.txt
func (*SparseGraph) AddEdge ¶
func (g *SparseGraph) AddEdge(i, j int)
AddEdge modifies the graph by adding the edge (i, j) if it is not already present. If the edge is already present (or i == j), this does nothing.
func (*SparseGraph) AddVertex ¶
func (g *SparseGraph) AddVertex(neighbours []int)
AddVertex adds a vertex to the graph with the specified neighbours.
func (SparseGraph) Copy ¶
func (g SparseGraph) Copy() EditableGraph
Copy returns a deep copy of the graph g.
func (SparseGraph) Degrees ¶
func (g SparseGraph) Degrees() []int
Degrees returns the degree sequence of the graph.
func (SparseGraph) InducedSubgraph ¶
func (g SparseGraph) InducedSubgraph(V []int) EditableGraph
InducedSubgraph returns a deep copy of the induced subgraph of g with vertices given in order by V. This can also be used to return relabellings of the graph if len(V) = g.N().
func (SparseGraph) IsEdge ¶
func (g SparseGraph) IsEdge(i, j int) bool
IsEdge returns if there is an edge between i and j in the graph.
func (SparseGraph) Neighbours ¶
func (g SparseGraph) Neighbours(v int) []int
Neighbours returns the neighbours of the given vertex.
func (*SparseGraph) RemoveEdge ¶
func (g *SparseGraph) RemoveEdge(i, j int)
RemoveEdge modifies the graph by removing the edge (i, j) if it is present. If the edge is not already present, this does nothing.
func (*SparseGraph) RemoveVertex ¶
func (g *SparseGraph) RemoveVertex(i int)
RemoveVertex removes the specified vertex. The index of a vertex u > v becomes u - 1 while the index of u < v is unchanged.