Friday, August 7, 2020

Matrix Multiplication & Graph Reachable

I have been struggling to find a good way to represent graph structure. There are number of graph library where Node and Edge are defined. I found that matrix can be used to represent a graph. 

The row and column of the matrix represent the node in a graph. The element in the matrix is connection between two nodes. In a graph, this connection is called Edge. The following diagram represents a graph with 3 nodes and 3 edges. 

In a matrix representation, it can be written as a matrix. Row and column are named A, B, and C. If there is an edge between two nodes, the corresponding cell is set to 1. For example, edge AB shows 1 in cell (A, B) in the grid. We can denote this matrix as M

Matrix "multiplication" to itself can reveal if a certain node can reach the other nodes in two steps. The "multiplication" operation is different from the linear algebra matrix multiplication.  

K = M ⊗ M

 Each element b in N can be calculated by the following formula, where N is the number of the nodes (or the column number of the matrix M).

Two nodes i and j. If there j is reachable from i, either of the following two conditions are met:
  • there is a direct edge between i and j 
  • there is a node p which is reachable from i and p can reach j
Written as math language in the matrix M
  • M(i, j) = 1
  • 彐p, M(i, p) = 1 and M(p, j) = 1
Repeat the "multiplication" operation logN times, it can calculate any node in a graph can be reachable from other nodes. 

Finally, I can move away from a complicated node/edge definition into a formal math world. Hopefully the existing linear algebra can help me down the road.