Adjacency Matrix
December 21, 2013 - 10:07 pm by Joss Whittle
C/C++ Daily Programmer
I decided to start taking part in some of the programming challenges over at /r/dailyprogrammer . The first of which was to read in an input file representing an edge/node graph structure of the form:

```
5 5
0 -> 1
1 -> 2
2 -> 4
3 -> 4
0 -> 3
```

And to output the Adjacency Matrix of the graph in the form:

```
0 1 0 1 0
0 0 1 0 0
0 0 0 0 1
0 0 0 0 1
0 0 0 0 0
```

Below is the code of my submission. I decided to make the challenge a little more interesting using bit level operations to store the matrix in ~approx~ `N*N`

bits rather than the usual minimum of `N*N`

bytes.

```
#include <iostream>
#include <string>
// For accessing char array as bit array
#define GET_INDEX(a,b) (a + (b * n))
#define GET_BIT(a, b) ((a[b/8] >> (b%8)) & 0x01)
#define SET_BIT(a, b) (a[b/8] |= 1 << (b%8))
using namespace std;
int main() {
// Input buffer
char in[128];
// Get NxM
cin.getline(in, 128); string input(in);
int delim = input.find_first_of(' ');
if (delim < 0) return 1;
int n = atoi(input.substr(0, delim).c_str());
int m = atoi(input.substr(delim + 1).c_str());
if (!n || !m) return 1;
// Pad NxN matrix to have enough bytes
int rn = (int)ceilf((float) (n*n) / 8.0f);
// Allocate Matrix as 1D byte array
char *adjMat = new char [rn];
memset(adjMat, 0, rn);
// For M edge rows
for (int j = 0; j < m && in[0] != '\0'; j++) {
// Get Edge information
cin.getline(in, 128); input = string(in);
// Split into x and y parts
delim = input.find_first_of('-');
if (delim <= 0 || delim + 2 > input.length()) break;
string left = input.substr(0, delim);
string rightM = input.substr(delim + 2);
// Loop over each x in x part
while (left.length() > 0) {
delim = left.find_first_of(' ');
// As long as the current first char isn't a space
if (delim != 0) {
// Parse x as int
int x = atoi(((delim < 0) ? left : left.substr(0, delim)).c_str());
if (x < 0 || x >= n) break;
// Loop over each y in y part
string right = string(rightM);
while (right.length() > 0) {
int rdelim = right.find_first_of(' ');
// As long as the current first char isn't a space
if (rdelim != 0) {
// Parse y as int
int y = atoi(((rdelim < 0) ? right : right.substr(0, rdelim)).c_str());
if (y < 0 || y >= n) break;
// Set matrix to 1 at x,y
SET_BIT(adjMat, GET_INDEX(x, y));
}
// Move to next y part or break
if (rdelim + 1 >= right.length() || rdelim < 0) break;
right = right.substr(rdelim + 1);
}
}
// Move to next x part or break
if (delim + 1 >= left.length() || delim < 0) break;
left = left.substr(delim + 1);
}
}
// Print result
for (int x = 0; x < n; x++) {
for (int y = 0; y < n; y++) {
cout << (int)GET_BIT(adjMat, GET_INDEX(x, y)) << " ";
}
cout << endl;
}
// Deallocate
delete [] adjMat;
return 0;
};
```

Tags
Reddit