graphAlgs

Graph Algorithms

These are basic graph algorithms.

Function list

Laplacians.biggestComp — Method.

Return the biggest component in a graph, as a graph

Laplacians.components — Method.

Computes the connected components of a graph. Returns them as a vector of length equal to the number of vertices. The vector numbers the components from 1 through the maximum number. For example,

gr = ErdosRenyi(10,11)
c = components(gr)

10-element Array{Int64,1}:
 1
 1
 1
 1
 2
 1
 1
 1
 3
 2
Laplacians.isConnected — Method.

Returns true if graph is connected. Calls components.

Laplacians.kruskal — Method.

(kruskal::SparseMatrixCSC; kind=:max) Uses Kruskal's algorithm to compute a minimum (or maximum) spanning tree. Set kind=:min if you want the min spanning tree. It returns it a a graph

Laplacians.prim — Method.

prim(mat::SparseMatrixCSC; kind=:max) Compute a maximum spanning tree of the matrix mat. If kind=:min, computes a minimum spanning tree.

Laplacians.shortestPathTree — Method.

Computes the shortest path tree, and returns it as a sparse matrix. Treats edge weights as reciprocals of lengths. For example:

a = [0 2 1; 2 0 3; 1 3 0]
tr = full(shortestPathTree(sparse(a),1))

3x3 Array{Float64,2}:
 0.0  2.0  0.0
 2.0  0.0  3.0
 0.0  3.0  0.0
Laplacians.shortestPaths — Method.

Computes the lenghts of shortest paths from start. Returns both a vector of the lenghts, and the parent array in the shortest path tree.

This algorithm treats edge weights as reciprocals of distances. DOC BETTER

Laplacians.vecToComps — Method.

This turns a component vector, like that generated by components, into an array of arrays of indices of vertices in each component. For example,

comps = vecToComps(c)

3-element Array{Array{Int64,1},1}:
 [1,2,3,4,6,7,8]
 [5,10]
 [9]