ABSTRACT

In the implementation of a graph as a sparse matrix, the node is the key object. In fact, the nodes in the graph are indexed by the index i = 1, 2, 3, . . . , |N |, where N is the set of nodes and |N | is its cardinality (the total number of nodes). The index i of the ith node serves then as its virtual address in the list of nodes, which allows one to access the information about its role in the graph. Indeed, this information can be found in the ith row in the matrix of the graph, in which the matrix elements indicate from which nodes edges are issued towards the ith node. Furthermore, the ith row in the transpose of the matrix of the graph indicates towards which nodes edges are issued from the ith node.