Sparse Adjacency Matrices in C++

Sparse Adjacency Matrices in C++ Homework Sample

A graph is a collection of nodes and links, and may be represented with an adjacency matrix. Imagine all the students in the university, you can represent whether they have exchanged emails with a 2D matrix, with a 0 indicating no email and a 1 representing an email exchange. This is very wasteful as the vast majority of the matrix is a 0 value and there are many less 1s, since most people do not exchange emails with all the other students. We use a compact representation that uses 3 arrays, the first gives the non zero weights, the second gives the number of elements in each row, and the third gives the column index for each row. You need to provide an iterator that accesses elements using the compact format of data. You need to add methods to copy a matrix, to add an edge, and to access the data present. For more C++ programming assignments contact us for a quote.

Solution:

Driver.cpp

#include “Graph.h”
#include <iostream>
#include <exception>
#include <tuple>

using namespace std;

int main(int argc, char **argv)
{
// lets create an empty graph
try
{
cout << “# Trying to create a graph with 0 nodes” << endl;
Graph *g1 = new Graph(0);
cout << “ERROR: Empty graph created!” << endl;
return -1;
}
catch (exception &e)
{
cout << “Can not create an empty graph.” << endl;
}

// lets create a graph with 5 nodes
Graph *g2 = new Graph(5);

// dump it
cout << “# Dumping new graph without any edge” << endl;
g2->dump();

// adding 2 edges
cout << “# Adding 2 edges (2,3), (3,4)” << endl;
g2->addEdge(2, 3, 13);
g2->addEdge(3, 4, 5);
cout << “-> Edge Count: ” << g2->numEdge() << endl;
cout << “-> Vertex Count: ” << g2->numVert() << endl;
g2->dump();

// add a duplicate edge
cout << “# Adding a duplicate edge (2,3)” << endl;
g2->addEdge(2, 3, 45);
cout << “-> Edge Count: ” << g2->numEdge() << endl;
cout << “-> Vertex Count: ” << g2->numVert() << endl;
g2->dump();

// iterate through all edges
cout << “# Iterating through all edges” << endl;
int count = 1;
for (Graph::EgIterator it = g2->egBegin(); it != g2->egEnd(); it++)
{
tuple<int, int, int> edge = *it;
cout << “-> Edge #” << count++ << “: ”
<< get<0>(edge) << “, ”
<< get<1>(edge) << “, ”
<< get<2>(edge) << endl;
}

// iterate through the neighbours of node 2
cout << “# Iterating through the neighbours of node 2” << endl;
count = 1;
for (Graph::NbIterator it = g2->nbBegin(2); it != g2->nbEnd(2); it++)
{
cout << “-> #” << count++ << “: ” << *it << endl;
}

return 0;
}

Graph.h

// File: Graph.h
//
// CMSC 341 Spring 2019
//
// Header file for Graph class
//

#ifndef _GRAPH_H_
#define _GRAPH_H_

#include <stdexcept> // for throwing out_of_range exceptions
#include <tuple> // for tuple template

class Graph {

public:

// Graph constructor; must give number of vertices
Graph(int n);

// Graph copy constructor
Graph(const Graph& G);

// Graph destructor
~Graph();

// Graph assignment operator
const Graph& operator= (const Graph& rhs);

// return number of vertices
int numVert();

// return number of edges
int numEdge();

// add edge between u and v with weight x
void addEdge(int u, int v, int x);

// print out data structure for debugging
void dump();

// Edge Iterator inner class
class EgIterator {

public:
// Edge Iterator constructor; indx can be used to
// set m_indx for begin and end iterators.
EgIterator(Graph *Gptr = nullptr, int indx = 0);

// Compare iterators; only makes sense to compare with
// end iterator
bool operator!= (const EgIterator& rhs);

// Move iterator to next printable edge
void operator++(int dummy); // post increment

// return edge at iterator location
std::tuple<int,int,int> operator*();

private:
Graph *m_Gptr; // pointer to associated Graph
int m_indx; // index of current edge in m_nz
int m_row; // corresponding row of m_nz[m_indx]
};

// Make an initial edge Iterator
EgIterator egBegin();

// Make an end iterator for edge iterator
EgIterator egEnd();

// Neighbor Iterator inner class
class NbIterator {

public:
// Constructor for iterator for vertices adjacent to vertex v;
// indx can be used to set m_indx for begin and end iterators
NbIterator(Graph *Gptr = nullptr, int v = 0, int indx = 0);

// Compare iterators; only makes sense to compare with
// end iterator
bool operator!=(const NbIterator& rhs);

// Move iterator to next neighbor
void operator++(int dummy);

// Return neighbor at current iterator position
int operator*();

private:
Graph *m_Gptr; // pointer to the associated Graph
int m_row; // row (source) for which to find neighbors
int m_indx; // current index into m_nz of Graph
};

// Make an initial neighbor iterator
NbIterator nbBegin(int v);

// Make an end neighbor iterator
NbIterator nbEnd(int v);

private:

int *m_nz; // non-zero elements array
int *m_re; // row extent array
int *m_ci; // column index array
int m_cap; // capacity of m_nz and m_ci

int m_numVert; // number of vertices
int m_numEdge; // number of edges

};

#endif

Graph.cpp

#include “Graph.h”
#include <iostream>
#include <cstring>
#include <tuple>

using namespace std;

Graph::Graph(int n)
{
if (n <= 0)
{
throw out_of_range(“n must be greater than 0”);
}

// allocate memory
m_nz = (int *)malloc(2 * n * sizeof(int));
m_re = (int *)malloc((n + 1) * sizeof(int));
m_ci = (int *)malloc(2 * n * sizeof(int));

// check allocations
if (m_nz == NULL || m_re == NULL || m_ci == NULL)
{
throw runtime_error(“could now allocate enough memory”);
}

m_cap = 2 * n;
m_numEdge = 0;
m_numVert = n;

// initialize the m_re
for (int i = 0; i <= m_numVert; i++)
{
m_re[i] = i;
}

// initialize m_nz, m_ci
for (int i = 0; i < 2 * n; i++)
{
m_nz[i] = 0;
m_ci[i] = -1;
}
}

Graph::Graph(const Graph &G)
{
// allocate memory
m_nz = (int *)malloc(G.m_cap * sizeof(int));
m_re = (int *)malloc((G.m_numVert + 1) * sizeof(int));
m_ci = (int *)malloc(G.m_cap * sizeof(int));

// check allocations
if (m_nz == NULL || m_re == NULL || m_ci == NULL)
{
throw runtime_error(“could now allocate enough memory”);
}

// copy memories
memcpy(m_nz, G.m_nz, G.m_cap * sizeof(int));
memcpy(m_re, G.m_re, (G.m_numVert + 1) * sizeof(int));
memcpy(m_ci, G.m_ci, G.m_cap * sizeof(int));

// copy the states
m_cap = G.m_cap;
m_numVert = G.m_numVert;
m_numEdge = G.m_numEdge;
}

Graph::~Graph()
{
// free up memories
free(m_nz);
free(m_re);
free(m_ci);
}

const Graph &Graph::operator=(const Graph &rhs)
{
// free up already allocated memory
if (m_nz != NULL)
free(m_nz);
if (m_re != NULL)
free(m_re);
if (m_ci != NULL)
free(m_ci);

// allocate memory
m_nz = (int *)malloc(rhs.m_cap * sizeof(int));
m_re = (int *)malloc((rhs.m_numVert + 1) * sizeof(int));
m_ci = (int *)malloc(rhs.m_cap * sizeof(int));

// check allocations
if (m_nz == NULL || m_re == NULL || m_ci == NULL)
{
throw runtime_error(“could now allocate enourhsh memory”);
}

// copy memories
memcpy(m_nz, rhs.m_nz, rhs.m_cap * sizeof(int));
memcpy(m_re, rhs.m_re, (rhs.m_numVert + 1) * sizeof(int));
memcpy(m_ci, rhs.m_ci, rhs.m_cap * sizeof(int));

// copy the states
m_cap = rhs.m_cap;
m_numVert = rhs.m_numVert;
m_numEdge = rhs.m_numEdge;

return *this;
}

int Graph::numVert() { return m_numVert; }

int Graph::numEdge() { return m_numEdge; }

void Graph::addEdge(int u, int v, int x)
{
if (u >= m_numVert || v >= m_numVert || u < 0 || v < 0)
{
throw out_of_range(“(u, v) must lower than number of vertices and >= 0”);
}

// check for already existing data
for (int i = m_re[u]; i < m_re[u + 1]; i++)
{
if (m_ci[i] == v)
{
m_nz[i] = x;

// do it for (v,u) as well
for (int j = m_re[v]; j < m_re[v + 1]; j++)
{
if (m_ci[j] == u)
{
m_nz[j] = x;
break;
}
}
return; // no need to proceed further
}
}

// check for reallocation
if ((m_numEdge + 2) >= m_cap)
{
m_nz = (int *)realloc(m_nz, (m_cap + 2 * m_numVert) * sizeof(int));
m_ci = (int *)realloc(m_ci, (m_cap + 2 * m_numVert) * sizeof(int));

if (m_nz == NULL || m_ci == NULL)
{
throw runtime_error(“could not allocate enough memory”);
}

// update the new values as well
for (int i = m_cap; i < (m_cap + 2 * m_numVert); i++)
{
m_nz[i] = 0;
m_ci[i] = -1;
}

m_cap += 2 * m_numVert;
}

// check for first edge for the node u
if (m_ci[m_re[u]] == -1)
{
m_ci[m_re[u]] = v;
m_nz[m_re[u]] = x;
}
else
{
int i_idx = m_re[u];
// push back the old data
int prev_nz = m_nz[m_re[u]];
int prev_ci = m_ci[m_re[u]];
for (int i = m_re[u] + 1; i < m_cap; i++)
{
int tmp = m_nz[i];
m_nz[i] = prev_nz;
prev_nz = tmp;

tmp = m_ci[i];
m_ci[i] = prev_ci;
prev_ci = tmp;
}
for (int i = u + 1; i <= m_numVert; i++)
{
m_re[i]++;
}

// add the u,v edge
m_nz[i_idx] = x;
m_ci[i_idx] = v;
}

// do the same for v
if (m_ci[m_re[v]] == -1)
{
m_ci[m_re[v]] = u;
m_nz[m_re[v]] = x;
}
else
{
int i_idx = m_re[v];
// push back the old data
int prev_nz = m_nz[m_re[v]];
int prev_ci = m_ci[m_re[v]];
for (int i = m_re[v] + 1; i < m_cap; i++)
{
int tmp = m_nz[i];
m_nz[i] = prev_nz;
prev_nz = tmp;

tmp = m_ci[i];
m_ci[i] = prev_ci;
prev_ci = tmp;
}
for (int i = v + 1; i <= m_numVert; i++)
{
m_re[i]++;
}

// add the v,v edge
m_nz[i_idx] = x;
m_ci[i_idx] = u;
}

m_numEdge += 2;
}

void Graph::dump()
{
cout << “Dump of graph (numVert = ” << m_numVert << “, numEdge = ” << m_numEdge << “, m_cap = ” << m_cap << “)” << endl;
cout << “m_re:”;
for (int i = 0; i < m_numVert; i++)
{
cout << ” ” << m_re[i];
}
cout << endl;

cout << “m_nz:”;
for (int i = 0; i < m_cap; i++)
{
if (m_nz[i] > 0)
{
cout << ” ” << m_nz[i];
}
}
cout << endl;

cout << “m_ci:”;
for (int i = 0; i < m_cap; i++)
{
if (m_ci[i] >= 0)
{
cout << ” ” << m_ci[i];
}
}
cout << endl;
}

Graph::EgIterator::EgIterator(Graph *Gptr, int indx)
{
m_row = indx;
m_indx = indx;
m_Gptr = Gptr;

if (m_Gptr == nullptr)
{
return;
}
// find the proper index
for (;;)
{
bool take_next = false;
for (int rx = 0; rx < m_Gptr->m_numVert – 1; rx++)
{
if (m_indx >= m_Gptr->m_re[rx] && m_indx < m_Gptr->m_re[rx + 1])
{
m_row = rx;
int cix = m_Gptr->m_ci[m_indx];
if (cix == -1)
{
take_next = true;
}

break;
}
}

if (!take_next)
{
break;
}

m_indx++;
}
}

bool Graph::EgIterator::operator!=(const Graph::EgIterator &rhs)
{
if (rhs.m_Gptr == nullptr)
{
return true;
}
return rhs.m_Gptr->m_re[m_row + 1] > m_indx;
}

void Graph::EgIterator::operator++(int dummy)
{
if (m_Gptr == nullptr)
{
return;
}

for (;;)
{
m_indx++;

// find the row index and filter out duplicate
bool is_duplicate = false;
for (int rx = 0; rx < m_Gptr->m_numVert – 1; rx++)
{
if (m_indx >= m_Gptr->m_re[rx] && m_indx < m_Gptr->m_re[rx + 1])
{
m_row = rx;
int cix = m_Gptr->m_ci[m_indx];
if (cix == -1)
{
// no edge
is_duplicate = true; //alows to iterate next one
break;
}
for (int check = m_Gptr->m_re[cix]; check < m_Gptr->m_re[cix + 1]; check++)
{
// int vv = m_Gptr->m_ci[check];
if (rx == m_Gptr->m_ci[check] && rx > cix)
{
is_duplicate = true;
break;
}
}
break;
}
}

if (!is_duplicate)
{
break;
}
}
}

tuple<int, int, int> Graph::EgIterator::operator*()
{
return make_tuple(
m_row,
m_Gptr->m_ci[m_indx],
m_Gptr->m_nz[m_indx]);
}

Graph::EgIterator Graph::egBegin()
{
return EgIterator(this);
}

Graph::EgIterator Graph::egEnd()
{
return EgIterator(this);
}

Graph::NbIterator::NbIterator(Graph *Gptr, int v, int indx)
{
m_Gptr = Gptr;
m_row = v;
m_indx = indx;
}

bool Graph::NbIterator::operator!=(const Graph::NbIterator &rhs)
{
return (rhs.m_Gptr->m_re[m_row] + m_indx) < rhs.m_Gptr->m_re[m_row + 1];
}

void Graph::NbIterator::operator++(int dummy)
{
m_indx++;
}

int Graph::NbIterator::operator*()
{
int cix = m_Gptr->m_re[m_row] + m_indx;

if (cix >= m_Gptr->m_re[m_row + 1])
{
throw out_of_range(“index out of range”);
}

return m_Gptr->m_ci[cix];
}

Graph::NbIterator Graph::nbBegin(int v)
{
return NbIterator(this, v);
}

Graph::NbIterator Graph::nbEnd(int v)
{
return NbIterator(this, v);
}