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.
No comments:
Post a Comment