1.2.4 Node-arc matrix

For a directed graph, if n is the number of nodes and m is the number of arcs of the graph, the node-arc matrix  A is a $n\times m$ matrix:
if A(i,j)=+1, then node i is the tail of arc j
if A(i,j)=-1, then node i is the head of arc i.
If the graph is undirected and m is the number of edges, the node-arc matrix A is also a $n\times m$ matrix and:
if A(i,j)=1, then node i is an end of edge j.

With this type of representation, it is impossible to have loops.

This matrix is represented in Scilab as a sparse matrix.

For instance, the node-arc matrix corresponding to figure 1, with loop arc number 4 deleted is :

$$\left(\begin{array}{rrr} 1 & 1 & -1 \\ -1 & 0 & 1 \\ 0 & -1 & 0 \\ 0 & 0 & 0 \\ \end{array}\right)$$

If the same graph is undirected, the matrix is:

$$\left(\begin{array}{ccc} 1 & 1 & 1 \\ 1 & 0 & 1 \\ 0 & 1 & 0 \\ 0 & 0 & 0 \\ \end{array}\right)$$

The functions used to compute the node-arc matrix of a graph, and to come back to a graph from the node-arc matrix are graph_2_mat and mat_2_graph.