Operators

a,d = adj(sddm)

Create an adjacency matrix and a diagonal vector from an SDD M-matrix. That is, from a Laplacian with added diagonal weights

d = diagmat(a)

Returns the diagonal weighted degree matrix(as a sparse matrix) of a graph

graph = disjoin(a,b)

Create a disjoint union of graphs a and b, with no edges between them.

U = edgeVertexMat(a)

The signed edge-vertex adjacency matrix

graph = floatGraph(a::SparseMatrixCSC)

Convert the nonzero entries in a graph to Float64.

graph = join_graphs!(a::IJV, b::IJV, k::Integer)

Create a disjoint union of graphs a and b, and then put k random edges between them, merging b into a.

graph = joinGraphs(a, b, k::Integer)

Create a disjoint union of graphs a and b, and then put k random edges between them

l = lap(a)

Create a Laplacian matrix from an adjacency matrix. We might want to do this differently, say by enforcing symmetry

H = line_graph(G::SparseMatrixCSC)

Let G = (V, E) be a graph. The line graph of G is the graph whose vertices are the edges of G in which two are connected if they share an endpoint in G. That is, (u, v),(w, z) is an edge of the line graph if one of {u, v} is the same as one of {w, z}

b = mapweight(a, x->rand())

Create a new graph that is the same as the original, but with f applied to each nonzero entry of a. For example, to make the weight of every edge uniform in [0,1], we could write.

plot_graph(gr,x,y,z;color=[0,0,1],dots=true,setaxis=true,number=false)

Plots graph gr with coordinates (x,y,z)

plot_graph(gr,x,y;color=[0,0,1],dots=true,setaxis=true,number=false)

Plots graph gr with coordinates (x,y)

ap = power(a::SparseMatrixCSC, k::Int)

Returns the kth power of a.

aprod = productGraph(a0, a1)

The Cartesian product of two graphs. When applied to two paths, it gives a grid.

graph = shortIntGraph(a::SparseMatrixCSC)

Convert the indices in a graph to 32-bit ints. This takes less storage, but does not speed up much.

x, y = spectral_coords(a)

Computes the spectral coordinates of a graph. If more than 2 coords are desired, you can use

    x, y, z = spectral_coords(a; k = 3)

spectral_drawing(a)

Computes spectral coordinates, and then uses plot_graph to draw

graph = subsampleEdges(a::SparseMatrixCSC, p::Float64)

Create a new graph from the old, but keeping edge edge with probability p

a_new = thicken(A,k)

Create a new graph with at least k times as many edges as A By connecting nodes with common neighbors at random. When this stops working (not enough new edges), repeat on the most recently produced graph. If k is too big, it is decreased so the average degree will not be pushed much above n/2.

When called without k, it just runs thicken_once.

For example:

a = grid2(5)
a2 = thicken(a,3)
(x,y) = grid2coords(5,5);
plotGraph(a2,x,y)

a_new = thicken_once(a)

Creates one edge for every vertex in a of degree > 1 by connecting two of its random neighbors. To use this to thicken a, return unweight(a + a_new).

a = grid2(5)
a2 = unweight(a + thicken_once(a))
(x,y) = grid2coords(5,5);
plotGraph(a2,x,y)

graph = two_lift(a, flip::AbstractArray{Bool,1})
graph = two_lift(a)
graph = two_lift(a, k::Integer)

Creats a 2-lift of a. flip is a boolean indicating which edges cross. In the third version, k is the number of edges that cross.

uniformWeight!(a)

Set the weight of every edge to random uniform [0,1]

unweight!(a)

Change the weight of every edge in a to 1

wt1 = unweight(a)

Create a new graph in that is the same as the original, but with all edge weights 1

U = wtedEdgeVertexMat(a)

The signed and weighted edge-vertex adjacency matrix, so U'*U = L