GitHub

API reference

Index

Docstrings

SimpleWeightedGraphs.AbstractSimpleWeightedGraph — Type
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.

source
SimpleWeightedGraphs.SWGFormat — Type
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
source
SimpleWeightedGraphs.SimpleWeightedDiGraph — Type
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)
Performance

Iteratively adding/removing vertices or edges is not very efficient for this type of graph: better construct the graph in one shot if possible.

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

source
SimpleWeightedGraphs.SimpleWeightedEdge — Type
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
source
SimpleWeightedGraphs.SimpleWeightedGraph — Type
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)
Performance

Iteratively adding/removing vertices or edges is not very efficient for this type of graph: better construct the graph in one shot if possible.

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

source
Graphs.LinAlg.adjacency_matrix — Function
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).

source
Graphs.LinAlg.laplacian_matrix — Function
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).

source
Graphs.SimpleGraphs.rem_vertex! — Method
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.

Correctness

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 results in all vertices with indices greater than v being shifted down one.

source
Graphs.SimpleGraphs.rem_vertex! — Method
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.

Correctness

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 results in all vertices with indices greater than v being shifted down one.

source
Graphs.cartesian_product — Method

Graphs.cartesian_product(g, h)

Compute the weighted cartesian product of two weighted graphs.

Warning

It is possible that this is suboptimal, but it is the most trivial extension of the implementation used in Graphs.jl.

source
Graphs.connected_components — Method
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.

source
Graphs.has_edge — Method
Graphs.has_edge(g, u, v)

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

source
Graphs.has_edge — Method
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).

source
Graphs.induced_subgraph — Method
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.

source
Graphs.inneighbors — Method
Graphs.inneighbors(g::SimpleWeightedDiGraph, v)

Return the vector of inneighbors of vertex v.

Performance

This function is less efficient than outneighbors for directed weighted graphs (it allocates a new vector).

source
Graphs.loadgraph — Method
Graphs.loadgraph(io, gname, SWGFormat())

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

source
Graphs.loadgraphs — Method
Graphs.loadgraphs(io, SWGFormat())

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

source
Graphs.outneighbors — Method
Graphs.outneighbors(g::SimpleWeightedDiGraph, v)

Return the vector of outneighbors of vertex v.

Performance

This function is more efficient than inneighbors for directed weighted graphs.

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

Apply the page rank algorithm on a weighted graph.

source
Graphs.savegraph — Method
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).

source
Graphs.savegraph — Method
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).

source
Graphs.savegraph — Method
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.

source
Graphs.weights — Method
Graphs.weights(g::SimpleWeightedDiGraph)

Return the weighted adjacency matrix, stored as an Adjoint.

source
Graphs.weights — Method
Graphs.weights(g::SimpleWeightedGraph)

Return the weighted adjacency matrix.

source
SimpleWeightedGraphs._get_nz_index! — Method
_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

source
SimpleWeightedGraphs.degree_matrix — Function
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).

source
SimpleWeightedGraphs.saveswg — Method
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).

source