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 for SimpleGraph
. Check Documenter's build log for details.
Missing docstring for SimpleGraphFromIterator
. Check Documenter's build log for details.
Missing docstring for SimpleDiGraph
. Check Documenter's build log for details.
Missing docstring for SimpleDiGraphFromIterator
. Check Documenter's build log for details.
Missing docstring for Edge
. Check Documenter's build log for details.
LightGraphs.add_edge!
— Functionadd_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);
julia> add_edge!(g, 1, 2)
true
julia> add_edge!(g, 2, 3)
false
LightGraphs.rem_edge!
— Functionrem_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> add_edge!(g, 1, 2);
julia> rem_edge!(g, 1, 2)
true
julia> rem_edge!(g, 1, 2)
false
LightGraphs.add_vertex!
— Functionadd_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
julia> add_vertex!(g)
true
julia> add_vertex!(g)
false
LightGraphs.add_vertices!
— Functionadd_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
julia> add_vertices!(g, 2)
2
LightGraphs.rem_vertex!
— Functionrem_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
Base.zero
— Functionzero(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
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.
LightGraphs.add_edge!
LightGraphs.add_vertex!
LightGraphs.add_vertices!
LightGraphs.rem_edge!
LightGraphs.rem_vertex!
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.