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:

Missing docstring.

Missing docstring for SimpleGraph. Check Documenter's build log for details.

Missing docstring.

Missing docstring for SimpleGraphFromIterator. Check Documenter's build log for details.

Missing docstring.

Missing docstring for SimpleDiGraph. Check Documenter's build log for details.

Missing docstring.

Missing docstring for SimpleDiGraphFromIterator. Check Documenter's build log for details.

Missing docstring.

Missing docstring for Edge. Check Documenter's build log for details.

LightGraphs.add_edge!Function
add_edge!(g, e)

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

Examples

julia> using LightGraphs

julia> g = SimpleGraph(2);

true

false
source
LightGraphs.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.

Examples

julia> using LightGraphs

julia> g = SimpleGraph(2);

julia> rem_edge!(g, 1, 2)
true

julia> rem_edge!(g, 1, 2)
false
source
LightGraphs.add_vertex!Function
add_vertex!(g)

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

Examples

julia> using LightGraphs

julia> g = SimpleGraph(Int8(typemax(Int8) - 1))
{126, 0} undirected simple Int8 graph

true

false
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.

Examples

julia> using LightGraphs

julia> g = SimpleGraph()
{0, 0} undirected simple Int64 graph

2
source
LightGraphs.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$.

Examples

julia> using LightGraphs

julia> g = SimpleGraph(2);

julia> rem_vertex!(g, 2)
true

julia> rem_vertex!(g, 2)
false
source
Base.zeroFunction
zero(G)

Return a zero-vertex, zero-edge version of the graph type G. The fallback is defined for graph values zero(g::G) = zero(G).

Examples

julia> g = SimpleDiGraph([0 1 0 0 0; 0 0 1 0 0; 1 0 0 1 0; 0 0 0 0 1; 0 0 0 1 0]);

julia> zero(typeof(g))
{0, 0} directed simple Int64 graph

julia> zero(g)
{0, 0} directed simple Int64 graph
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.