Question

In this assignment we are not allowed to make changes to Graph.h it cannot be changed! I need help with the Graph.cpp and the Driver.cpp.

Your assignment is to implement a sparse adjacency matrix data structure Graph that is defined in the header file Graph.h. The Graph class provides two iterators. One iterator produces the neighbors for a given vertex. The second iterator produces each edge of the graph once.

Additionally, you must implement a test program that fully exercises your implementation of the Graph member functions. Place this program in the main() function in a file named Driver.cpp.

The purpose of an iterator is to provide programmers a uniform way to iterate through all items of a data structure using a forloop. For example, using the Graph class, we can iterate thru the neighbors of vertex 4 using:

Graph::NbIterator nit ; for (nit = G.nbBegin(4); nit != G.nbEnd(4) ; nit++) { cout << *nit << " " ; } cout << endl ;

The idea is that nit (for neighbor iterator) starts at the beginning of the data for vertex 4 in nz and is advanced to the next neighbor by the ++ operator. The for loop continues as long as we have not reached the end of the data for vertex 4. We check this by comparing against a special iterator for the end, nbEnd(4). This requires the NbIterator class to implement the ++, !=and * (dereference) operators.

Similarly, the Graph class allows us to iterate through all edges of a graph using a for loop like:

Graph::EgIterator eit ; tuple<int,int,int> edge ; for (eit = G.egBegin() ; eit != G.egEnd() ; eit++) { edge = *eit ; // get current edge cout << "(" << get<0>(edge) << ", " << get<1>(edge) << ", " << get<2>(edge) << ") " ; } cout << endl ;

Note that each edge should be printed only once, even though it is represented twice in the sparse adjacency matrix data structure.

Since a program may use many data structures and each data structure might provide one or more iterators, it is common to make the iterator class for a data structure an inner class. Thus, in the code fragments above, nit and eit are declared asGraph::NbIterator and Graph::EgIterator objects, not just NbIterator and EgIterator objects.

Here are the specifics of the assignment, including a description for what each member function must accomplish.

Requirement: your implementation must dynamically resize the m_nz and m_ci arrays. See the descriptions of Graph(constructor) and addEdge, below.

Requirement: other than the templated tuple class, you must not use any classes from the Standard Template Library or other sources, including vector and list. All of the data structure must be implemented by your own code.

Requirement: your code must compile with the original Graph.h header file. You are not allowed to make any changes to this file. Yes, this prevents you from having useful helper functions. This is a deliberate limitation of this project. You may have to duplicate some code.

Requirement: a program fragment with a for loop that uses your NbIterator must have worst case running time that is proportional to the number of neighbors of the given vertex.

Requirement: a program fragment with a for loop that uses your EgIterator must have worst case running time that is proportional to the number of vertices in the graph plus the number of edges in the graph.

Graph.h:

#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 outline:

#include "Graph.h"

Graph::Graph(int n) {
}

Graph::Graph(const Graph& G) {
}

Graph::~Graph() {
}

const Graph& Graph::operator= (const Graph& rhs) {
  
}
// This Function will return the number of vertices in the graph
int Graph::numVert() {
  
}

int Graph::numEdge() {
  
}

void Graph::addEdge(int u, int v, int x) {
  
}

void Graph::dump() {
  
}

Graph::EgIterator::EgIterator(Graph *Gptr = nullptr, int index = 0) {
  
}

bool Graph::EgIterator::operator!= (const EgIterator& rhs) {
  
}

void Graph::EgIterator::operator ++(int dummy) {
  
}

std::tuple<int, int, int> Graph::EgIterator::operator *() {
  
}

Graph::EgIterator Graph::egBegin() {
  
}

Graph::EgIterator Graph::egEnd() {
  
}

Graph::NbIterator::NbIterator(Graph *Gptr = nullptr, int v = 0, int indx = 0) {
  
}

bool Graph::NbIterator::operator !=(const NbIterator& rhs) {
  
}

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

int Graph::NbIterator::operator *() {
  
}

Graph::NbIterator Graph::nbBegin(int v) {
  
}

Graph::NbIterator Graph::nbEnd(int v) {
  
}

Answer 1

test1.cpp

#include <iostream>

// need this for pair template
//
#include <tuple>
using namespace std ;

#include "Graph.h"

int main() {

   // G has 5 vertices numbered 0 thru 4
   Graph G(5) ;

   // add some edges
   G.addEdge(3,4,11);
   //   G.dump();
   G.addEdge(1,4,12);
   //   G.dump();
   G.addEdge(0,3,13);
   //   G.dump();
   G.addEdge(0,4,14);
   //   G.dump();
   G.addEdge(0,1,15);
   //   G.dump();
   G.addEdge(1,2,16);
   //   G.dump();
   G.addEdge(2,4,17);
   //   G.dump();

   // dump out data structure
   G.dump();

   // Test neighbor iterator

   Graph::NbIterator nit ;

   cout << "\nThe neighbors of vertex 4 are:\n" ;
   for (nit = G.nbBegin(4); nit != G.nbEnd(4) ; nit++) {
      cout << *nit << " " ;
   }
   cout << endl ;

   // Test edge iterator

   Graph::EgIterator eit ;
   std::tuple<int,int,int> edge ;

   cout << "\nThe edges in the graph are:\n" ;
   for (eit = G.egBegin() ; eit != G.egEnd() ; eit++) {

     edge = *eit ;   // get current edge

     // the two data members of a pair are first and second
     //
     cout << "(" << get<0>(edge) << ", "
      << get<1>(edge) << ", "
      << get<2>(edge) << ") " ;

   }
   cout << endl ;
}

Graph.cpp

using namespace std;
#include "Graph.h"
#include <iostream>
//#include <stdexcept>
//#include <tuple>
int Graph::debug_count = 0;

/*
* Method: Graph::Graph()
*   Descr: Create a new Graph with n vertices
*/
Graph::Graph(int n) : m_numVert(n),
m_cap(n),
m_numEdge(0),
m_nz(new int[n]),
m_re(new int[n + 1]),
m_ci(new int[n]) {
    if (n <= 0) {
        throw std::out_of_range("Must have a positive number of vertices");
    }
    //    m_nz = new int[n];
    //    m_re = new int[n + 1];
    //    m_ci = new int[n];
}

/*
* Method: Graph::Graph()
*   Descr: Copy constructor for Graph, create deep copy
*/
Graph::Graph(const Graph &G) : m_cap(G.m_cap),
m_numEdge(G.m_numEdge),
m_numVert(G.m_numVert),
m_nz(new int[G.m_cap]),
m_re(new int[G.m_numVert + 1]),
m_ci(new int[G.m_cap]) {
    for (int i = 0; i < m_numEdge << 1; i++) {
        cout << debug_count++ << endl;
        if (i < m_numVert + 1)
            m_re[i] = G.m_re[i];
        m_ci[i] = G.m_ci[i];
        m_nz[i] = G.m_nz[i];
    }
}

/*
* Method: Graph::~Graph()
*   Descr: Destructor for Graph, deallocate memory
*/
Graph::~Graph() {
}

/*
* Method: Graph::operator=()
*   Descr: Assignment operator for Graph set one equal to the other
*/
const Graph &Graph::operator=(const Graph &rhs) {
    m_numEdge = rhs.m_numEdge;
    m_numVert = rhs.m_numVert;
    m_cap = rhs.m_cap;
    m_ci = new int[m_cap];
    m_re = new int[m_numVert + 1];
    m_nz = new int[m_cap];
    for (int i = 0; i < m_numEdge << 1; i++) {
        if (i < m_numVert + 1)
            m_re[i] = rhs.m_re[i];
        m_ci[i] = rhs.m_ci[i];
        m_nz[i] = rhs.m_nz[i];
    }
}

/*
* Method: Graph::numVert()
*   Descr: Getter for m_numVert
*/
int Graph::numVert() {
    return m_numVert; // return the number of vertices in graph
}

/*
* Method: Graph::numEdge()
*   Descr: Getter for m_numEdge
*/
int Graph::numEdge() {
    return m_numEdge; // return number of edges in graph
}

/*
* Method: Graph::addEdge()
*   Descr: Add an edge between vertices u and v with weight x
*/
void Graph::addEdge(int u, int v, int x) {
    // Determine which index is higher
    int max = u, min = v;
    if (u < v)
        min = u, max = v;

    // Determine if vertices are in graph
    if (max >= m_numVert || min < 0)
        throw out_of_range("Vertex index is out of range");

    int i = m_re[min];
    // Loop through to see if the edge is already in the graph
    for (; i < m_numEdge * 2 && i < m_re[min + 1] && m_ci[i] < max; i++)

        // If the edge is already in the graph change the weight and do the same for the transposed coordinates
        if (m_ci[i] == max) {
            m_ci[i] = x;
            for (int j = m_re[max]; j < m_re[max + 1]; j++) {
                if (m_ci[j] == min) {
                    m_ci[j] = x;
                    return;
                }
            }
        }

    m_numEdge++; // Increment the total number of edges

    // Expand column index and nonzero arrays if necessary
    if (m_numEdge << 1 > m_cap) {
        m_cap <<= 1;
        int *new_nz = new int[m_cap], *new_ci = new int[m_cap];
        for (int k = 0; k < m_numEdge << 1; k++) {
            new_nz[k] = m_nz[k];
            new_ci[k] = m_ci[k];
        }
        //        delete m_nz;
        //        delete m_ci;
        m_nz = new_nz;
        m_ci = new_ci;
    }

    // First element in Graph, special case
    if (m_numEdge == 1) {
        m_nz[0] = m_nz[1] = x;
        m_ci[0] = max;
        m_ci[1] = min;
        //        return;
    } else {
        // Update the column index and non-zero arrays
        //    i--;
        bool max_added = false; // Prevent adding value multiple times
        for (int j = m_numEdge * 2 - 1, slider = 2; j > i; j--) {
            cout << debug_count++ << endl;
            if (!max_added && ((j - 1 > m_re[max] && j - 1 <= m_re[max + 1] && m_ci[j - slider] < min) || j - 1 == m_re[max])) {
                m_ci[j] = min;
                m_nz[j] = x;
                max_added = !0;
                slider--;
                continue;
            }
            m_ci[j] = m_ci[j - slider];
            m_nz[j] = m_nz[j - slider];
        }
        m_ci[i] = max;
        m_nz[i] = x;
    }

    // Update the row extent array
    for (int j = min; j < m_numVert + 1; j++) {
        m_re[j + 1] += j >= max ? 2 : 1;
    }
}

/*
* Method: Graph::dump()
*   Descr: Debug Graph by displaying number of edges, vertices, and contents of three arrays
*/
void Graph::dump() {
  
    cout << "Dump of graph (numVert = " << m_numVert << ", numEdge = " << m_numEdge << ", m_cap = " << m_cap << ")\n" << endl;

    // Print out row extent array
    cout << "m_re: ";
    for (int i = 0; i < m_numVert + 1; i++)
        cout << m_re[i] << " ";
    cout << endl;

    // Print out nonzero array
    cout << "m_nz: ";
    for (int i = 0; i < m_numEdge << 1; i++)
        cout << m_nz[i] << " ";
    cout << endl;

    // Print out column index array
    cout << "m_ci: ";
    for (int i = 0; i < m_numEdge << 1; i++)
        cout << m_ci[i] << " ";
    cout << endl;
}

/*
* Method: Graph::EgIterator::EgIterator()
*   Descr: Create an iterator that shows all the edges
*/
Graph::EgIterator::EgIterator(Graph *Gptr, int indx) : m_Gptr(Gptr), m_indx(indx) {
    if (Gptr) {

        for (m_row = 0; (indx >= Gptr->m_re[m_row + 1] || (indx == Gptr->m_re[m_row] && indx == Gptr->m_re[m_row + 1])) && m_row < Gptr->m_numVert; m_row++);
    }

}

/*
* Method: Graph::EgIterator::operator!=()
*   Descr: Override iterator comparison operator
*/
bool Graph::EgIterator::operator!=(const EgIterator &rhs) {

    return m_Gptr != rhs.m_Gptr || m_row != rhs.m_row || m_indx != rhs.m_indx;
}

/*
* Method: Graph::EgIterator::operator++()
*   Descr: Override iterator increment operator
*/
void Graph::EgIterator::operator++(int dummy) {

    for (m_indx++; m_indx < m_Gptr->m_numEdge << 1 && m_row >= m_Gptr->m_ci[m_indx]; m_indx++);
    for (; (m_indx >= m_Gptr->m_re[m_row + 1] || (m_indx == m_Gptr->m_re[m_row] && m_indx == m_Gptr->m_re[m_row + 1])) && m_row < m_Gptr->m_numVert; m_row++);
}

/*
* Method: Graph::EgIterator::operator*()
*   Descr: Override iterator dereference operator
*/
std::tuple<int, int, int> Graph::EgIterator::operator*() {
    //    printf("[%i]:<%i, %i, %i>",m_indx,m_row,m_Gptr->m_ci[m_indx],m_Gptr->m_nz[m_indx]);
    if (m_indx >= m_Gptr->m_numEdge << 1)
        throw out_of_range("EgIterator is at end of Graph");

    return make_tuple(m_row, m_Gptr->m_ci[m_indx], m_Gptr->m_nz[m_indx]);
}

/*
* Method: Graph::egBegin()
*   Descr: Create a EgIterator at beginning of graph
*/
Graph::EgIterator Graph::egBegin() {
    return EgIterator(this);
}

/*
* Method: Graph::egEnd()
*   Descr: Create a EgIterator at end of graph
*/
Graph::EgIterator Graph::egEnd() {
    return EgIterator(this, m_numEdge * 2);
}

/*
* Method: Graph::NbIterator::NbIterator()
*   Descr: Loop through all the vertices that share an edge with a specified vertex
*/
Graph::NbIterator::NbIterator(Graph *Gptr, int v, int indx) : m_Gptr(Gptr), m_indx(indx || !Gptr ? indx : Gptr->m_re[v]), m_row(v) {

}

/*
* Method: Graph::NbIterator::operator!=()
*   Descr: Override iterator comparison operator
*/
bool Graph::NbIterator::operator!=(const NbIterator &rhs) {

    return m_Gptr != rhs.m_Gptr || m_row != rhs.m_row || m_indx != rhs.m_indx;
}

/*
* Method: Graph::NbIterator::operator++()
*   Descr: Override iterator increment operator
*/
void Graph::NbIterator::operator++(int dummy) {

    if (++m_indx > m_Gptr->m_re[m_row + 1])
        m_indx--;
}

/*
* Method: Graph::NbIterator::operator*()
*   Descr: Override iterator dereference operator
*/
int Graph::NbIterator::operator*() {
    if (m_indx == m_Gptr->m_re[m_row + 1])
        throw out_of_range("NbIterator is already at end of row");

    return m_Gptr->m_ci[m_indx];
}

/*
* Method: Graph::nbBegin()
*   Descr: Create a NbIterator at beginning of row for specified vertex
*/
Graph::NbIterator Graph::nbBegin(int v) {

    return NbIterator(this, v);
}

/*
* Method: Graph::nbEnd()
*   Descr: Create a NbIterator at end of row for specified vertex
*/
Graph::NbIterator Graph::nbEnd(int v) {
    return NbIterator(this, v, m_re[v + 1]);
}

/*------------------------------------------------------------------------------*/

Graph.h

#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

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

};

#endif