Creating the Adjacency Matrix

We are now able to construct an adjacency matrix of the network. As Anastasia explained in a previous post, we will use the adjacency matrix in silhouette index to find the shortest path between all pairs of vertices.

Our matrix construction uses the structures firstNeighborIndex, neighbors, and edgeWeight2.

The arrays edgeWeight2, neighbors, and firstNeighborIndex represent the example network. a) The network is undirected and unweighted. b) Edges of the network index into edgeWeight2 and neighbors. The highlighted indices correspond to the edges that connect a start vertex to its first neighboring vertex. Let these edges be called the first edges. c) The arrays are separated into chunks, where each chunk corresponds to a start vertex. d) The array firstNeighborIndex keeps track of the first edge of a start vertex.

Arrays neighbors and edgeWeight2 correspond to each other. Given some edge e = (s, d), edgeWeight2 at e gives the weight of e, and neighbors at e gives the destination vertex d incident to e. The arrays are ordered by the start vertices s. That is, the first k_0 indices are incident to start vertex 0, the next k_1 indices are incident to start vertex 1, and so on, where the last k_{n-1} indices are incident to start vertex n – 1. Each “chunk” is labeled by the corresponding start vertex.

Given this array structuring, the first index of each chunk s corresponds to the edge from vertex s to its first neighboring vertex. To quickly access these first neighbors, the code maintains an additional array called firstNeighborIndex. The indices of firstNeighborIndex are the start vertices. The elements are the edges from vertex s to its first neighboring vertex.

We’ve also included and tested an existing Java implementation of the Floyd–Warshall algorithm for the all-pairs shortest path problem.

Currently, Anastasia and I are re-writing the C++ code for silhouette index, and Christina is working on the performance metric. Our next steps are to incorporate the matrix construction into the code, finish implementing our respective metrics, and begin running the test suites.