graphUtils

Graph Utilities

These are utilities to facilitate the use of sparse matrices as graphs.

Laplacians.backIndices — Method.

Same as the above, but now the graph is in adjacency list form

Laplacians.backIndices — Method.

Computes the back indices in a graph in O(M+N). works if for every edge (u,v), (v,u) is also in the graph

Laplacians.compConductance — Method.

Returns the quality of the cut for a given graph and a given cut set s. the result will be |outgoing edges| / min(|vertices in set|, |N - vertices in set|)

Laplacians.findEntries — Method.

Similar to findnz, but also returns 0 entries that have an edge in the sparse matrix

Laplacians.flipIndex — Method.

For a symmetric matrix, this gives the correspondance between pairs of entries in an ijv. So, ai[ind] = aj[flip[ind]]. For example, 

(ai,aj,av) = findnz(a);
fl = flipIndex(a)
ind = 10
@show backind = fl[10]
@show [ai[ind], aj[ind], av[ind]]
@show [ai[backind], aj[backind], av[backind]];

backind = fl[10] = 4
[ai[ind],aj[ind],av[ind]] = [2.0,4.0,0.7]
[ai[backind],aj[backind],av[backind]] = [4.0,2.0,0.7]
Laplacians.getObound — Method.

Computes the number of edges leaving s

Laplacians.getVolume — Method.

Computes the volume of subset s in an unweighted graph G

Laplacians.setValue — Method.

Sets the value of a certain edge in a sparse graph; value can be 0 without the edges dissapearing

Laplacians.wdeg — Method.

Finds the weighted degree of a vertex in the graph