adjacency matrix in Java - edge overlapping

Question

I have a very simple question to ask.

I am using an adjacency matrix (2D array) in java to create a small graph with nodes and edges.

My problem is that when I instruct the program to iterate through the adjacency matrix, using a simple nested loop, I experience the problem of edge overlapping. To be more specific, when matrix[i][j] is true and matrix[j][i] is true as well the app will try to draw 2 edges between nodes i and j which would be a waste and ugly-looking.

How can I overcome that problem?

Answer 1

Don't iterate across the entire matrix, you can use the upper triangular half (or the lower) and that will cover all of the entries you're interested in.

Assuming the matrix is diagonally symmetric, either half will suffice. If it's not symmetric then you're using a directed graph (edges have arrows) and you would want to preserve those duplicate edges.

An easy way to iterate across a triangular half is this sort of nested loop:

for(i=0;i<n;i++){
  for(j=i;j<m;j++){
   whatever(i,j);
  }
 }

Starting j=i means the columnar iteration starts from the diagonal and skips the duplicated portion.