Graph Utilities

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

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

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

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

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]

Computes the number of edges leaving s

Computes the volume of subset s in an unweighted graph G

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

Finds the weighted degree of a vertex in the graph