[Help] Linked List Graph Implentation

[Mokraton]

Hello!

I've been assigned a project where we have to code a graph using linked list implementation. I think I understand the idea behind it, but I am having trouble writing the code for it.


Problem:
I am having trouble writing a constructor, destructor, and adding vertexes and edges to my graph (with this method of writing a graph, my textbook explains how to write it in array based adjacency matrix)

I have searched the internet and found many solutions, but all of them include using an array with adjacency lists, and we are not allowed to use an array in this assignment.

I am actively working on it and will post the solution if I find it before anyone else does, but I'm sure I'll run into more problems will all the additional functions I have to write.

Here is the code thus far:

Header File (this code can't be changed as it was provided by our instructor)

  (Include Files / header definitions)

  struct VertexNode;  // Forward Declaration of VertexNode type

struct EdgeNode                                 // Structure representing an edge
{
  VertexNode*   destination;                    // Pointer to destination vertex
  int           weight;                         // Edge weight
  EdgeNode*     nextEdge;                       // Pointer to next edge
}

struct VertexNode          // Structure representing a vertex
{
  string        vname;                          // Name of vertex
  bool          mark;                           // Marked flag
  EdgeNode*     edgePtr;                  // Pointer to list of outgoing edges
  VertexNode*   nextVertex;               // Pointer to next vertex in vertices list
};
class Graph		// Graph ADT using adjacency list representation
{
 private:		//***** Private class members below *****//
  VertexNode*	vertices;		// Linked list of vertex nodes

 public:		   //***** Public members below *****//
  Graph();									
  // Graph()
  // Constructor initializes vertices linked list to empty
	
  ~Graph();	
  // ~Graph()
  // For each VertexNode in the vertices list, Destructor deallocates all EdgeNodes before
  // deallocating the VertexNode itself
	
  void AddVertex(string v);		
  // AddVertex()
  // Adds vertex to graph assuming vertex not already present

  void AddEdge(string s, string d, int w);		
  // AddEdge()
  // Adds edge from source S  to destination D with specified weight W.
  // If there is not enough memory to add the edge, throw the GraphFull exception

(More function prototypes that I haven't gotten to)

		*edit forgot to include the print file code
// Print -- write graph to stdout.  DO NOT MODIFY THIS FUNCTION!!!
void Print()
	{
		EdgeNode* eptr;
        VertexNode* vptr = vertices;
		const int FIELDWIDTH = 6;
		string STARS = "**********";
		STARS = STARS + STARS + STARS; 
		
		cout << endl << STARS << endl;
		
		cout << setw(FIELDWIDTH) << "Vertex" << " : " << "Adjacent Vertices" << endl;
		cout << "------------------------------" << endl;
		
        while(vptr != NULL)
		{
			cout << setw(FIELDWIDTH) << vptr->vname << " : ";
			
			eptr = vptr->edgePtr;
			while (eptr != NULL)
			{
				cout << eptr->destination->vname << eptr->weight << " ";
				eptr = eptr->nextEdge;
			}
			cout << endl;
            vptr = vptr->nextVertex;
		}
		cout << STARS << endl << endl;
	} // Graph::Print()
}; 
   

My .cpp file so far

#include "graph.h"

Graph::Graph()	/* Default Constructor */
{	
	vertices = NULL;
}

Graph::~Graph() /* Default Destructor*/
{
	delete [] vertices;
}

void Graph::AddVertex(string v)
{
       /* So here, I believe what I"m doing is correct except that I do not know how to set nextVertex
       I'm assuming some kind of recursive function.   */

	vertices = new VertexNode;
	vertices->nextVertex = NULL;
	vertices->vname = v;
}

void Graph::AddEdge(string s, string d, int w)
{
        /* I don't have any idea how to code this actually, I'll update this function as I think about it more.
        I just wanted to post this so I can be thinking while other are too. */ 

	vertices = new VertexNode;
	vertices->vname = s;
	vertices->edgePtr->destination->vname = d;
	vertices->edgePtr->weight = w;
	
}

If I (or anyone else) can figure this out, I think the rest of the project should be pretty straight forward if these core functions are implemented correctly.

I did my best to keep this post easy to read and understand, but if their is any additional code you want to see or information you need, I will provide. I am a beginner (as per the thread I posted in) so please keep that in mind.

[ne555]

> I think I understand the idea behind it,
explain it.

> Pointer to next edge
¿what's "next" edge?

[Mokraton]

Question 1:

From my understanding, a graph is similar to a binary search tree except there is no limit to the number of parents and number of children a node can have. So its a a bunch of nodes linked together with a bunch of edges each carrying a weight, like a flight schedule between cities with each node representing a city and each edge representing the number of miles to that city.

This is my current up to date algorithm

AddVertex(string v)

if statement to check if vertex already exists, if it does don't add another vertex else
set vname = string v
set nextVertex = NULL if graph is empty, else nextVertex will be the vertex added before this.

AddEdge(string s, string d, int w)

if statement is edge already exists between two nodes with same weight, don't add same edge else
figure out starting vertex (string s)
declare new EdgeNode variable
set var->destination->vname = string d
set var->weight = w
point nextEdge to another edge coming from same vertex

Question 2:
From what I read (in my book) the red box in the following picture is the first edge, and the orange box in the picture is the second edge and so on and so forth for each vertex.

http://imgur.com/a2kd1ES

Also, I've made no real progress on my own, just been writing new code and still get seg faults.

[ne555]

I mean that you explain how the graph is represented.
Each edge knows the destination vertex and the weight (it does not not the origin vertex)
Each node hold a list of edges for which it is the origin.


I would suggest you to encapsulate the list behaviour with a list class (std::list is good for that)

struct Edge{
    Vertex *destination;
    int weight;
};

struct Vertex{
   std::list<Edge> incident;
   std::string name;
};

class Graph{
private:
   std::list<Vertex> vertices; //you may use std::vector if change the Edge to hold an index instead of a pointer
public:
   Graph() = default; //good enough
   ~Graph() = default; //good enough
   void AddVertex(std::string name){
      for( auto &v : vertices )
         if( v.name == name ) return; //vertex already exists
      vertices.push_back( Vertex(name) ); //need to create the Vertex constructor
   }
};