graph

package
v0.2.0 Latest Latest
Warning

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

 Go to latest Published: Apr 21, 2021 License: MIT Imports: 13 Imported by: 0

Documentation

Index

Constants

This section is empty.

Variables

This section is empty.

Functions

func AdjacencyMatrixEncode 

func AdjacencyMatrixEncode(g Graph) string

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 

func AllMaximalCliques(g Graph, c chan []int)

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 

func BiconnectedComponents(g Graph) ([][]int, []int)

BiconnectedComponents returns the biconnected components and the articulation vertices.

func CanonicalIsomorph 

func CanonicalIsomorph(g Graph) []int

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 

func CanonicalIsomorphFull(g Graph, vertexClasses [][]int) ([]int, disjoint.Set, [][]int)

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 

func ChromaticIndex(g Graph) (chromaticIndex int, colouredEdges []byte)

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 

func ChromaticNumber(g Graph) (chromaticNumber int, colouring []int)

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 

func CliqueNumber(g Graph) int

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 

func ConnectedComponent(g Graph, v int) []int

ConnectedComponent returns the connected component in g containing v.

func ConnectedComponents 

func ConnectedComponents(g Graph) [][]int

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 

func Degeneracy(g Graph) (d int, order []int)

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 

func Diameter(g Graph) int

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 

func Distance(g Graph, i, j int) int

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 

func Eccentricity(g Graph) []int

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 

func Equal(g, h Graph) bool

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 

func Girth(g Graph) int

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 

func Graph6Encode(g Graph) string

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 

func GreedyColor(g Graph, order []int) (int, []int)

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 

func IndependenceNumber(g Graph) int

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 

func IsKColorable(g Graph, k int) (ok bool, colouring []int)

IsKColorable returns true if there is a proper colouring with k colours and an example colouring, else it returns false, nil.

func IsPlanar 

func IsPlanar(g Graph) bool

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 

func IsProperColouring(g Graph, colouring []int) bool

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 MaxDegree 

func MaxDegree(g Graph) int

MaxDegree returns the maximum degree of g.

func MinDegree 

func MinDegree(g Graph) int

MinDegree returns the minimum degree of g.

func MulticodeEncode 

func MulticodeEncode(g Graph) []byte

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 

func NumberOfInducedCycles(g Graph, maxLength int) []int

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 

func NumberOfInducedPaths(g Graph, maxLength int) []int

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 

func PruferEncode(g Graph) []int

PruferEncode returns the Prüfer code of the labelled tree g. https://en.wikipedia.org/wiki/Pr%C3%BCfer_sequence

func Radius 

func Radius(g Graph) int

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 

func RandomMaximalClique(g Graph, seed int64) []int

RandomMaximalClique builds a random maximal clique by iteratively choosing an allowed vertex uniformly at random and adding it to the clique.

func Sparse6Encode 

func Sparse6Encode(g Graph) string

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 

type DenseGraph struct {
	NumberOfVertices int
	NumberOfEdges    int
	DegreeSequence   []int
	Edges            []byte
}

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 Cycle 

func Cycle(n int) *DenseGraph

Cycle returns a copy of the cycle on n vertices.

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 Path 

func Path(n int) *DenseGraph

Path returns a copy of the path on n vertices.

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 Star 

func Star(n int) *DenseGraph

Star returns a copy of the star on n vertices.

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

func (g DenseGraph) M() int

M returns the number of vertices in the graph.

func (DenseGraph) N 

func (g DenseGraph) N() int

N returns the number of vertices in the graph.

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 

func Complement(g Graph) Graph

Complement returns the complement of a graph. Updating the original graph, changes the complement.

func InducedSubgraph 

func InducedSubgraph(g Graph, V []int) Graph

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

func (g SparseGraph) M() int

M returns the number of edges in g.

func (SparseGraph) N 

func (g SparseGraph) N() int

N returns the number of vertices in g.

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.

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.