Making and Modifying Graphs

Making and Modifying Graphs

LightGraphs.jl provides a number of methods for creating a graph object, including tools for building and modifying graph objects, a wide array of graph generator functions, and the ability to read and write graphs from files (using GraphIO.jl).

Modifying graphs

LightGraphs.jl offers a range of tools for modifying graphs, including:

LightGraphs.SimpleGraphs.SimpleGraph — Type.
SimpleGraph{T}

A type representing an undirected graph.

source
LightGraphs.SimpleGraphs.SimpleDiGraph — Type.
SimpleDiGraph{T}

A type representing a directed graph.

source
LightGraphs.Edge — Type.
Edge

A datastruture representing an edge between two vertices in a Graph or DiGraph.

source
LightGraphs.SimpleGraphs.add_edge! — Function.
add_edge!(g, e)

Add an edge e to graph g. Return true if edge was added successfully, otherwise return false.

source
LightGraphs.SimpleGraphs.rem_edge! — Function.
rem_edge!(g, e)

Remove an edge e from graph g. Return true if edge was removed successfully, otherwise return false.

Implementation Notes

If rem_edge! returns false, the graph may be in an indeterminate state, as there are multiple points where the function can exit with false.

source
LightGraphs.SimpleGraphs.add_vertex! — Function.
add_vertex!(g)

Add a new vertex to the graph g. Return true if addition was successful.

source
LightGraphs.add_vertices! — Function.
add_vertices!(g, n)

Add n new vertices to the graph g. Return the number of vertices that were added successfully.

source
LightGraphs.SimpleGraphs.rem_vertex! — Function.
rem_vertex!(g, v)

Remove the vertex v from graph g. Return false if removal fails (e.g., if vertex is not in the graph); true otherwise.

Performance

Time complexity is $\mathcal{O}(k^2)$, where $k$ is the max of the degrees of vertex $v$ and vertex $|V|$.

Implementation Notes

This operation has to be performed carefully if one keeps external data structures indexed by edges or vertices in the graph, since internally the removal is performed swapping the vertices v and $|V|$, and removing the last vertex $|V|$ from the graph. After removal the vertices in g will be indexed by $1:|V|-1$.

source
Base.zero — Function.
zero(g)

Return a zero-vertex, zero-edge version of the same type of graph as g.

source

In addition to these core functions, more advanced operators can be found in Operators.

Graph Generators

LightGraphs.jl implements numerous graph generators, including random graph generators, constructors for classic graphs, numerous small graphs with familiar topologies, and random and static graphs embedded in Euclidean space.

Datasets

Other notorious graphs and integration with the MatrixDepot.jl package are available in the Datasets submodule of the companion package LightGraphsExtras.jl. Selected graphs from the Stanford Large Network Dataset Collection may be found in the SNAPDatasets.jl package.

All Generators