Transformations to matrix representations

These methods convert the graph to a number of different matrix representations.

`distance`	Convert graph to a distance matrix
`adjacency`	Convert graph to an adjacency matrix
`degree`	Convert graph to a degree matrix
`incidence`	Convert graph to an incidence matrix
`laplacian`	Convert graph to a Laplacian matrix

Details

Graph.distance()[source]

Convert graph to a distance matrix

Returns:: distance matrix
Return type:: ndarray(n,n)

The elements of the distance matrix D[i,j] is the edge cost of moving from vertex i to vertex j. It is zero if the vertices are not connected.

>>> from pgraph import UGraph
>>> import numpy as np
>>> g = UGraph()
>>> for i in range(5):
...     g.add_vertex(np.random.rand(2));
Vertex[#0, coord=(0.7917, 0.5289)]
Vertex[#1, coord=(0.568, 0.9256)]
Vertex[#2, coord=(0.07104, 0.08713)]
Vertex[#3, coord=(0.02022, 0.8326)]
Vertex[#4, coord=(0.7782, 0.87)]
>>> for i, j in [(0, 1), (0, 2), (0, 3), (1, 2), (1, 3), (3, 4)]:
...     g.add_edge(g[i], g[j]);
Edge{[#0] -- [#1], cost=0.4554}
Edge{[#0] -- [#2], cost=0.8453}
Edge{[#0] -- [#3], cost=0.8291}
Edge{[#1] -- [#2], cost=0.9747}
Edge{[#1] -- [#3], cost=0.5557}
Edge{[#3] -- [#4], cost=0.7589}
>>> d = g.distance()
>>> print(d)
[[0.         0.45541762 0.84531028 0.82913891 0.        ]
 [0.45541762 0.         0.97470248 0.55566014 0.        ]
 [0.84531028 0.97470248 0.         0.         0.        ]
 [0.82913891 0.55566014 0.         0.         0.75886015]
 [0.         0.         0.         0.75886015 0.        ]]

For graphs with parallel edges or loops

If there are parallel edges the element is the cost of the cheapest of them. A self-loop gives a non-zero diagonal element equal to its cost.

Seealso:: Vertex.distance()

Graph.adjacency()[source]

Convert graph to an adjacency matrix

Returns:: adjacency matrix
Return type:: ndarray(N,N)

The elements of the adjacency matrix [i,j] are 1 if vertex i is connected to vertex j, else 0.

>>> from pgraph import UGraph
>>> import numpy as np
>>> g = UGraph()
>>> for i in range(5):
...     g.add_vertex(np.random.rand(2));
Vertex[#0, coord=(0.9786, 0.7992)]
Vertex[#1, coord=(0.4615, 0.7805)]
Vertex[#2, coord=(0.1183, 0.6399)]
Vertex[#3, coord=(0.1434, 0.9447)]
Vertex[#4, coord=(0.5218, 0.4147)]
>>> for i, j in [(0, 1), (0, 2), (0, 3), (1, 2), (1, 3), (3, 4)]:
...     g.add_edge(g[i], g[j]);
Edge{[#0] -- [#1], cost=0.5175}
Edge{[#0] -- [#2], cost=0.875}
Edge{[#0] -- [#3], cost=0.8478}
Edge{[#1] -- [#2], cost=0.3709}
Edge{[#1] -- [#3], cost=0.358}
Edge{[#3] -- [#4], cost=0.6513}
>>> A = g.adjacency()
>>> print(A)
[[0. 1. 1. 1. 0.]
 [1. 0. 1. 1. 0.]
 [1. 1. 0. 0. 0.]
 [1. 1. 0. 0. 1.]
 [0. 0. 0. 1. 0.]]

Note

vertices are numbered in their order of creation. A vertex index can be resolved to a vertex reference by graph[i].
for an undirected graph the matrix is symmetric
Eigenvalues of A are real and are known as the spectrum of the graph.
The element A[i,j] is the number of walks of length one from vertex i to vertex j, which is the number of edges between them (zero or one for a simple graph).
If Ak = A ** k the element Ak[i,j] is the number of walks of length k from vertex i to vertex j.

For graphs with parallel edges or loops

The matrix holds edge counts, so k parallel edges from i to j give A[i,j] = k and Ak = A ** k still counts walks correctly. A self-loop adds to the diagonal: 2 for a UGraph (consistent with degree()) and 1 for a DGraph. In every case each row of A sums to the degree of that vertex.

Seealso:: laplacian() incidence() degree()

Graph.degree()[source]

Convert graph to a degree matrix

Returns:: degree matrix
Return type:: ndarray(N,N)

This is a diagonal matrix where element [i,i] is the Vertex.degree of vertex i: the number of edge ends at it, so a self-loop counts twice. For a directed graph that is the edges entering plus the edges leaving.

Changed in version 1.0: For a DGraph this was the out-degree matrix, counting only the edges leaving each vertex. It is now the total, in plus out. The old matrix is np.diag([v.out_degree for v in g]), which is what laplacian() uses.

>>> from pgraph import UGraph
>>> import numpy as np
>>> g = UGraph()
>>> for i in range(5):
...     g.add_vertex(np.random.rand(2));
Vertex[#0, coord=(0.2646, 0.7742)]
Vertex[#1, coord=(0.4562, 0.5684)]
Vertex[#2, coord=(0.01879, 0.6176)]
Vertex[#3, coord=(0.6121, 0.6169)]
Vertex[#4, coord=(0.9437, 0.6818)]
>>> for i, j in [(0, 1), (0, 2), (0, 3), (1, 2), (1, 3), (3, 4)]:
...     g.add_edge(g[i], g[j]);
Edge{[#0] -- [#1], cost=0.2812}
Edge{[#0] -- [#2], cost=0.2914}
Edge{[#0] -- [#3], cost=0.3815}
Edge{[#1] -- [#2], cost=0.4401}
Edge{[#1] -- [#3], cost=0.1633}
Edge{[#3] -- [#4], cost=0.3379}
>>> d = g.degree()
>>> print(d)
[[3 0 0 0 0]
 [0 3 0 0 0]
 [0 0 2 0 0]
 [0 0 0 3 0]
 [0 0 0 0 1]]

For graphs with parallel edges or loops

Every edge is counted, so k parallel edges between two vertices add k to the degree of each end. A self-loop adds 2, for both kinds of graph, since it has two ends.

Seealso:: adjacency() incidence() laplacian() connectivity() average_degree() Vertex.degree

Graph.incidence()[source]

Convert graph to an incidence matrix

Returns:: incidence matrix
Return type:: ndarray(n,ne)

The elements of the incidence matrix I[i,j] are 1 if vertex i is connected to edge j, else 0.

>>> from pgraph import UGraph
>>> import numpy as np
>>> g = UGraph()
>>> for i in range(5):
...     g.add_vertex(np.random.rand(2));
Vertex[#0, coord=(0.3595, 0.437)]
Vertex[#1, coord=(0.6976, 0.06023)]
Vertex[#2, coord=(0.6668, 0.6706)]
Vertex[#3, coord=(0.2104, 0.1289)]
Vertex[#4, coord=(0.3154, 0.3637)]
>>> for i, j in [(0, 1), (0, 2), (0, 3), (1, 2), (1, 3), (3, 4)]:
...     g.add_edge(g[i], g[j]);
Edge{[#0] -- [#1], cost=0.5063}
Edge{[#0] -- [#2], cost=0.386}
Edge{[#0] -- [#3], cost=0.3423}
Edge{[#1] -- [#2], cost=0.6112}
Edge{[#1] -- [#3], cost=0.4921}
Edge{[#3] -- [#4], cost=0.2572}
>>> I = g.incidence()
>>> print(I)
[[1. 1. 1. 0. 0. 0.]
 [1. 0. 0. 1. 1. 0.]
 [0. 1. 0. 1. 0. 0.]
 [0. 0. 1. 0. 1. 1.]
 [0. 0. 0. 0. 0. 1.]]

Note

Vertices are numbered in their order of creation. A vertex index can be resolved to a vertex reference by graph[i].
Edges are numbered in the order they appear in edges(), which is the order they were added.
Both endpoints of every edge are marked, regardless of direction – for a DGraph this means a vertex that is only ever a target (never a source) still appears here. Iterating each vertex’s own Vertex.edges(), which are its outgoing edges, would silently drop such vertices for a directed graph.

For graphs with parallel edges or loops

Parallel edges each get their own column. For a UGraph the column of a self-loop holds a single 2 (it touches its vertex at both ends, so row sums still equal degree()); for a DGraph it holds a single 1.

Seealso:: laplacian() adjacency() degree()

Graph.laplacian()[source]

Convert graph to a Laplacian matrix

Returns:: Laplacian matrix
Return type:: NumPy ndarray

g.laplacian() is the Laplacian matrix (NxN) of the graph where N is the number of vertices.

>>> from pgraph import UGraph
>>> import numpy as np
>>> g = UGraph()
>>> for i in range(5):
...     g.add_vertex(np.random.rand(2));
Vertex[#0, coord=(0.5702, 0.4386)]
Vertex[#1, coord=(0.9884, 0.102)]
Vertex[#2, coord=(0.2089, 0.1613)]
Vertex[#3, coord=(0.6531, 0.2533)]
Vertex[#4, coord=(0.4663, 0.2444)]
>>> for i, j in [(0, 1), (0, 2), (0, 3), (1, 2), (1, 3), (3, 4)]:
...     g.add_edge(g[i], g[j]);
Edge{[#0] -- [#1], cost=0.5368}
Edge{[#0] -- [#2], cost=0.4555}
Edge{[#0] -- [#3], cost=0.203}
Edge{[#1] -- [#2], cost=0.7817}
Edge{[#1] -- [#3], cost=0.3678}
Edge{[#3] -- [#4], cost=0.187}
>>> L = g.laplacian()
>>> print(L)
[[ 3. -1. -1. -1.  0.]
 [-1.  3. -1. -1.  0.]
 [-1. -1.  2.  0.  0.]
 [-1. -1.  0.  3. -1.]
 [ 0.  0.  0. -1.  1.]]

Note

Laplacian always has at least one zero eigenvalue (each row of D_out - adjacency() sums to zero, so the all-ones vector is always a right null vector).
For an undirected graph specifically: the Laplacian is symmetric and positive-semidefinite, and the number of zero-valued eigenvalues equals the number of connected components.
For a directed graph, this computes the out-degree Laplacian (used in directed consensus/synchronization literature) – but it is generally not symmetric, its eigenvalues can be complex, and the zero-eigenvalue/component-count relationship above does not hold.

For graphs with parallel edges or loops

Both the out-degree and adjacency() count edges, so the identity L = D_out - adjacency() and the zero row sums hold unchanged. A self-loop adds the same amount to both and cancels out of the Laplacian entirely.

Note

D_out is the diagonal matrix of Vertex.out_degree. For an undirected graph that is degree(), but for a directed graph degree() is in plus out, so the Laplacian does not use it.

Seealso:: adjacency() incidence() degree()