CODEWITHSUNDEEP
c++matrixvectorgraph
David Corneliusen
David Corneliusen

Reputation: 49

How can I create an adjacency matrix using vectors in a templated graph class in c++?

Yes, this is a homework assignment (before you ask), but I'm having troubles and I feel like people on here are much less pretentious than my fellow CS students.

My question is, what would I need to do to create a matrix in a template graph class in c++ using a two dimensional vector. I always can visualize what I need to do, but run into troubles when it comes to typing it out.

Here is what I have so far:

using namespace std;

namespace GraphNameSpace
{

   enum isDirected {DIRECTED, UNDIRECTED};
   enum isWeighted {WEIGHTED, UNWEIGHTED};

   template <class T>
   class Graph
   {
      public:
         Graph<T>();
         Graph<T>(isDirected);
         Graph<T>(isWeighted);
         Graph<T>(isDirected, isWeighted);
         Graph<T>(isWeighted, isDirected);

         void createMatix();
         void destroy();
         bool isEmpty() const;
         bool isFull() const;
         bool isAdjacentTo(T fromVertex, T toVertex) const;
         int edgeWeight(T fromVertex, T toVertex) const;
         int edgeCount() const;
         int vertexCount() const;
         void insertVertex(T Vertex);
         void insertEdge(T fromVertex, T toVertex, int weight);
         void deleteVertex(T Vertex);
         void deleteEdge(T fromVertex, T toVertex);
         int findVertex(T Vertex) const;
         void dump() const;

      private:
         vector<int> row(100);
         int numVertices;
         int numEdges;
         static isDirected dir;
         static isWeighted wght;
   };
}

I guess the problem is with the vector row(100), but may also be with the void createMatrix(). I'm just desperately trying to understand how to do this, so an explanation with example code would be appreciated. (The rest of the code is exactly as he wants it). Thanks in advance for trying to help me, it's deeply appreciated.

Upvotes: 2

Views: 3672

Answers (1)

ravenspoint
ravenspoint

Reputation: 20472

It seems like you need a two dimensional vector of T to store your vertices

Something like this:

vector < vector < T > > Vertices;

However, this is terribly inefficient!

Perhaps the thing to do is to have a one dimensional vector of vertices and then define an edge and store all the edges in another one dimensional vector. You can generate the adjacency matrix from this on the fly if needed.

vector < T > vertices;
typedef pair <int,int> edge_t;    // Indices into vertices vector
vector < edge_t > edges;

This wastes no memory.

The problem I see is that there is no way in this scheme to store properties for the edges ( e.g. weight or length or cost ). To do that you need to template for both the edges and the vertices

 template <class V, class E>
   class Graph

So now you need a vector for the user edges, a vector for the vertices, and a vector for the three indices: source vetrex, destination vertex, and edge.

Maybe something like this:

vector < V > vertices;
vector < E > edges;
struct adjacency_s {
   int src;
   int dst;
   int edge;
};
vector < adjacency_s > adjacencies;

In reality it is a bad idea to roll your own graph code. Better to learn how to use an established library as discussed here

Upvotes: 3

Related Questions