API reference

SimpleWeightedGraphs

A package for graphs with edge weights and no self-loops, stored as sparse adjacency matrices.

AbstractSimpleWeightedEdge{T}

Abstract type for weighted edges with endpoints of type T.

AbstractSimpleWeightedGraph

An abstract type representing a simple graph structure with edge weights.

The only requirement for concrete subtypes is that they should implement a method Graphs.weights(g) which returns the weighted adjacency matrix.

SWGFormat

The storage format of SimpleWeightedGraph files. Multiple graphs may be present in one file.

For each graph, the file contains a one line header:

"LightGraphs.SimpleWeightedGraph", <num_vertices>, <num_edges>, {"d" | "u"}, <name>[, <ver>, <vdatatype>, <wdatatype>, <graphcode>]

• "LightGraphs.SimpleWeightedGraph" is a fixed string
• <num_vertices> is an integer
• <num_edges> is an integer
• "d" for directed graph, "u" for undirected (note that this option does not perform any additional edge construction, it's merely used to return the correct type of graph)
• <name> is a string
• <ver> is an int
• <vdatatype> is a string ("UInt8", etc.)
• <wdatatype> is a string describing the data type of the weights
• <graphcode> is a string.

The header is followed by a list of (comma-delimited) edges, each on a separate line:

<src>,<dst>,<weight>

• <src> is an int giving the source of the edge
• <dst> is an int giving the destination of the edge
• <weight> is a real giving the weight of the edge

SimpleWeightedDiGraph{T,U}

A type representing a directed weighted graph with vertices of type T and edge weights of type U.

Fields

• weights::SparseMatrixCSC{U,T}: weighted adjacency matrix, indexed by (dst, src)

Basic constructors

SimpleWeightedDiGraph()  # empty
SimpleWeightedDiGraph(n)  # n vertices, no edges
SimpleWeightedDiGraph(graph)  # from graph
SimpleWeightedDiGraph(adjmx; permute)  # from adjacency matrix, possibly transposed
SimpleWeightedDiGraph(sources, destinations, weights)  # from list of edges

Use methods(SimpleWeightedDiGraph) for the full list of constructors. When building a new graph from a list of edges, be aware that repeating (src, dst) pairs may lead to undefined behavior (e.g. due to floating point errors during weight addition).

SimpleWeightedDiGraphEdge

Alias for SimpleWeightedEdge.

SimpleWeightedEdge{T,U}

Concrete struct for a weighted edge with endpoints of type T and a weight of type U<:Real.

Fields

• src::T: edge source
• dst::T: edge destination
• weight::U: edge weight

SimpleWeightedEdge(u, v)

Construct a SimpleWeightedEdge from u to v with a default weight of 1.0.

SimpleWeightedEdge(u => v)

Construct a SimpleWeightedEdge from u to v with a default weight of 1.0.

SimpleWeightedEdge((u, v, w))

Construct a SimpleWeightedEdge from u to v with a weight of w.

SimpleWeightedEdge((u, v))

Construct a SimpleWeightedEdge from u to v with a default weight of 1.0.

SimpleWeightedGraph{T, U}

A type representing an undirected weighted graph with vertices of type T and edge weights of type U.

Fields

• weights::SparseMatrixCSC{U,T}: weighted adjacency matrix, indexed by (dst, src)

Basic constructors

SimpleWeightedGraph()  # empty
SimpleWeightedGraph(n)  # n vertices, no edges
SimpleWeightedGraph(graph)  # from graph
SimpleWeightedGraph(adjmx)  # from adjacency matrix
SimpleWeightedGraph(sources, destinations, weights)  # from list of edges

Use methods(SimpleWeightedGraph) for the full list of constructors. When building a new graph from a list of edges, be aware that repeating (src, dst) pairs may lead to undefined behavior (e.g. due to floating point errors during weight addition).

SimpleWeightedGraphEdge

Alias for SimpleWeightedEdge.

WDiGraph

Alias for SimpleWeightedDiGraph.

WGraph

Alias for SimpleWeightedGraph.

g[e, Val(:weight)]

Return the weight of edge e.

g[i, j, Val(:weight)]

Return the weight of edge (i, j).

g[e, :weight]

Return the weight of edge e.

g[i, j, :weight]

Return the weight of edge (i, j).

Graphs.adjacency_matrix(g, T; dir)

Construct the weighted adjacency matrix, filled with element type T and considering edge direction dir ∈ [:in, :out, :both] (default is :out).

Graphs.laplacian_matrix(g, T; dir)

Subtract the adjacency matrix to the degree matrix, both filled with element type T and considering edge direction dir ∈ [:in, :out, :both] (unlike in Graphs.jl, default is :out).

Graphs.add_edge!(g, u, v, w)

Add the edge (u, v) to the graph with a weight of w.

Graphs.add_edge!(g, u, v)

Add the edge (u, v) to the graph with a default weight of 1.

Graphs.add_edge!(g, e)

Add the edge e to the graph, where e is any object that can be converted into edgetype(g).

Graphs.rem_edge!(g, e)

Remove the edge e from the graph.

Graphs.rem_edge!(g, e)

Remove the edge e from the graph.

Graphs.rem_edge!(g, u, v)

Remove the edge (u, v) from the graph.

rem_vertex!(g::SimpleWeightedDiGraph, v)

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

rem_vertex!(g::SimpleWeightedGraph, v)

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

Graphs.cartesian_product(g, h)

Compute the weighted cartesian product of two weighted graphs.

Graphs.connected_components(g)

Compute the connected components of a weighted graph. Note that an edge with weight 0 will still be counted as an edge if it exists in the sparse weights matrix.

Graphs.has_edge(g, u, v)

Check the existence of the edge (u, v) in the graph.

Graphs.has_edge(g, e)

Check the existence of the edge e in the graph, where e is any object that can be converted into edgetype(g).

Graphs.induced_subgraph(g, vlist)

Compute the weighted subgraph induced by a list of vertices.

Return a tuple containing the new graph and the list of vertices.

Graphs.inneighbors(g::SimpleWeightedDiGraph, v)

Return the vector of inneighbors of vertex v.

Graphs.loadgraph(io, gname, SWGFormat())

Return a single graph with name gname loaded from the IO stream io using SWGFormat.

Graphs.loadgraphs(io, SWGFormat())

Return a dictionary of name => graph pairs loaded from the IO stream io using SWGFormat.

Graphs.outneighbors(g::SimpleWeightedDiGraph, v)

Return the vector of outneighbors of vertex v.

Graphs.pagerank(g, α=0.85, n=100, ϵ=1.0e-6)

Apply the page rank algorithm on a weighted graph.

Graphs.savegraph(fn, g, gname)

Graphs.savegraph(io, g, SWGFormat())

Write a graph g with default name "graph" to the IO stream io using SWGFormat, and return 1 (number of graphs written).

Graphs.savegraph(io, g, gname, SWGFormat())

Write a graph g with name gname to the IO stream io using SWGFormat, and return 1 (number of graphs written).

Graphs.savegraph(io, d, SWGFormat())

Write a dictionary d of name => graph pairs to the IO stream io using SWGFormat, and return the number of graphs written.

Graphs.savegraph(fn, d)

Graphs.weights(g::SimpleWeightedDiGraph)

Return the weighted adjacency matrix, stored as an Adjoint.

Graphs.weights(g::SimpleWeightedGraph)

Return the weighted adjacency matrix.

_get_nz_index!(mat::SparseMatrixCSC, i, j)

Return the index in nzval of mat[i, j]. We assume bounds are already checked

See https://github.com/JuliaSparse/SparseArrays.jl/blob/fa547689947fadd6c2f3d09ddfcb5f26536f18c8/src/sparsematrix.jl#L2492 for implementation

degree_matrix(g, T; dir)

Construct the weighted diagonal degree matrix, filled with element type T and considering edge direction dir ∈ [:in, :out, :both] (default is :out).

get_weight(g, u, v)
get_weight(g, e)

Retrieve the weight of edge (u, v) or e.

loadswg(io, gname)

Return a single graph with name gname loaded from the IO stream io using SWGFormat.

loadswg_mult(io)

Return a dictionary of name => graph pairs loaded from the IO stream io using SWGFormat.

saveswg(io, g, gname)

Write a graph g with name gname to the IO stream io using SWGFormat, and return 1 (number of graphs written).

saveswg_mult(io, d)

Write a dictionary d of name => graph pairs to the IO stream io using SWGFormat, and return the number of graphs written.

weight(e)

Return the weight of a weighted edge.

weighttype(g)

Return the subtype of Real used to represent edge weights.