Ad:

C++ Discussion Thread
Unsolved
Views: 997

Nov 11th, 2008

Graph help please

Expand Post »

This grap is kicking my butt. I am not sure how to do it. Can someone please help explain these to me.

c++ Syntax (Toggle Plain Text)
// graph.h
// -- adjacency list representation of a weighted graph
//
 
#ifndef GRAPH_H
 
#define GRAPH_H
 
#include <string>
#include "queue.h"
using namespace std;
 
 
class FileOpenError                                 // Exception class -- cannot open input file
{
};
 
struct EdgeNode										// Structure representing an edge
{
  int			destination;						// Index of destination vertex
  int			weight;								// Edge weight
  EdgeNode*		nextPtr;							// Next edge pointer
};
 
struct VertexNode									// Structure representing a vertex
{
  string		vname;								// Name of vertex
  bool			mark;								// Marked flag
  EdgeNode*		edgePtr;							// Pointer to list of edges
};
 
 
class Graph											// Graph ADT using adjacency list representation
{
 private:		//***** Private class members below *****//
  VertexNode*	vertices;							// Array of vertex nodes
  int			numV;								// Number of vertices
 
 public:		//***** Public members below *****//
  Graph(int num);									// Constructor - creates graph with num vertices
  ~Graph();											// Destructor - deallocates all edge nodes and the vertex list
  void DeleteAllEdges();							// Deallocates all edge nodes from all vertices
  bool IsEmpty();									// Returns true if graph empty, false otherwise
  bool IsFull();									// Returns true if graph full, false otherwise
  void AddVertex(string v);							// Adds vertex to graph assuming vertex not already present
  void AddEdge(string s, string d, int w);	        // Adds edge from source S  to destination D with specified weight W
  int IndexIs(string v);							// Returns index of edge from S to D; -1 if not present
  int WeightIs(string s, string d);					// Returns weight of vertex V -- assumes V is in graph
  void GetToVertices(string s, Queue& q);			// Returns a queue Q of vertices adjacent to vertex V
  void ClearMarks();								// Clears vertex marks
  void MarkVertex(string v);						// Marks vertex V
  bool IsMarked(string v);							// Returns true if vertex V is marked, false otherwise
  void Print();										// Write graph to stdout
  Queue* DepthFirstSearch(string startVertex, string endVertex);  // Returns ptr to queue containing path or NULL if none
}; 
 
  void Load(string filename, Graph*& g, string& startVertex, string& endVertex);  	
  // Load graph from named file and values of start and end vertices
  // Note: this file attempts to open the named file for input and input all information.  
  // If the file fails to open, Load throws the FileOpenError exception
 
#endif
// graph.h
// -- adjacency list representation of a weighted graph
//

#ifndef GRAPH_H

#define GRAPH_H

#include <string>
#include "queue.h"
using namespace std;


class FileOpenError                                 // Exception class -- cannot open input file
{
};

struct EdgeNode										// Structure representing an edge
{
  int			destination;						// Index of destination vertex
  int			weight;								// Edge weight
  EdgeNode*		nextPtr;							// Next edge pointer
};

struct VertexNode									// Structure representing a vertex
{
  string		vname;								// Name of vertex
  bool			mark;								// Marked flag
  EdgeNode*		edgePtr;							// Pointer to list of edges
};


class Graph											// Graph ADT using adjacency list representation
{
 private:		//***** Private class members below *****//
  VertexNode*	vertices;							// Array of vertex nodes
  int			numV;								// Number of vertices

 public:		//***** Public members below *****//
  Graph(int num);									// Constructor - creates graph with num vertices
  ~Graph();											// Destructor - deallocates all edge nodes and the vertex list
  void DeleteAllEdges();							// Deallocates all edge nodes from all vertices
  bool IsEmpty();									// Returns true if graph empty, false otherwise
  bool IsFull();									// Returns true if graph full, false otherwise
  void AddVertex(string v);							// Adds vertex to graph assuming vertex not already present
  void AddEdge(string s, string d, int w);	        // Adds edge from source S  to destination D with specified weight W
  int IndexIs(string v);							// Returns index of edge from S to D; -1 if not present
  int WeightIs(string s, string d);					// Returns weight of vertex V -- assumes V is in graph
  void GetToVertices(string s, Queue& q);			// Returns a queue Q of vertices adjacent to vertex V
  void ClearMarks();								// Clears vertex marks
  void MarkVertex(string v);						// Marks vertex V
  bool IsMarked(string v);							// Returns true if vertex V is marked, false otherwise
  void Print();										// Write graph to stdout
  Queue* DepthFirstSearch(string startVertex, string endVertex);  // Returns ptr to queue containing path or NULL if none
}; 

  void Load(string filename, Graph*& g, string& startVertex, string& endVertex);  	
  // Load graph from named file and values of start and end vertices
  // Note: this file attempts to open the named file for input and input all information.  
  // If the file fails to open, Load throws the FileOpenError exception

#endif

This is what I have so far but I don't think this is right. Can someone please explain these functions I just don't get it.

c++ Syntax (Toggle Plain Text)
#include <iostream>
#include <new>
#include <cstddef>
#include <string>
#include "graph.h"
 
using namespace std;
 
Graph::Graph(int num)
{
	numV = 0;
	vertices[num];
}
 
Graph::~Graph()
{
	delete [] vertices;
}
 
bool Graph::IsEmpty()
{
	return (numV == 0);
}
 
bool Graph::IsFull()
{
	EdgeNode* tempPtr;
	try
	{
		tempPtr = new EdgeNode;
	}
	catch (bad_alloc)
	{
		return true;
	}
    delete tempPtr;
	return false;
}
 
void Graph::AddVertex(string v)
{
	verticies[numV] = v;
 
	for(int index = 0; index < numV; index++)
	{
 
}
#include <iostream>
#include <new>
#include <cstddef>
#include <string>
#include "graph.h"

using namespace std;

Graph::Graph(int num)
{
	numV = 0;
	vertices[num];
}

Graph::~Graph()
{
	delete [] vertices;
}

bool Graph::IsEmpty()
{
	return (numV == 0);
}

bool Graph::IsFull()
{
	EdgeNode* tempPtr;
	try
	{
		tempPtr = new EdgeNode;
	}
	catch (bad_alloc)
	{
		return true;
	}
    delete tempPtr;
	return false;
}

void Graph::AddVertex(string v)
{
	verticies[numV] = v;
	
	for(int index = 0; index < numV; index++)
	{

}

Similar Threads

'directed acyclic word graph'?? in Java
Directed Graph Problem in Computer Science
Ms Graph Control in Visual Basic 4 / 5 / 6
source code of graph create in C
Graph in Computer Science

JustLearning

Reputation Points: 10

Solved Threads: 0

Light Poster

Offline

31 posts
since Sep 2008

Permalink

Nov 12th, 2008

Re: Graph help please

It might help if you explain what your Graph-class is supposed to do.

By the way, what is your constructor definition supposed to do?

You assign numV to be 0 then you de-reference an uninitialized array of vertices.

You probably meant to do something like this--

c++ Syntax (Toggle Plain Text)
Graph::Graph(int num) : numV(num), vertices(new VertexNode[num]){
 
      memset (vertices, 0, sizeof(VertexNode) * num);
}
Graph::Graph(int num) : numV(num), vertices(new VertexNode[num]){

      memset (vertices, 0, sizeof(VertexNode) * num);
}

-- the numV looks like it represents the total number of VertexNodes (or vertices) and it is initialized via pre-initialization, along with your pointer to VertextNodes.

The memset in the constructor body is necessary because by calling new you are invoking the default constructor of an instance of a class ( or struct or union in C++ ) in which it is typically the responsibility of the that constructor to initialize members of the object. However, because your struct of type VertexNode has no constructor you have to explicitly set the values inside the struct. A good way of doing so is by using memset. In the above code the memset sets the bit-value of every byte for each VertexNode to zero, so everything has a value of 0 in your struct.

So this means...

c++ Syntax (Toggle Plain Text)
struct VertexNode									// Structure representing a vertex
{
  string		vname;								// Name of vertex
  bool			mark;								// Marked flag
  EdgeNode*		edgePtr;							// Pointer to list of edges
};
struct VertexNode									// Structure representing a vertex
{
  string		vname;								// Name of vertex
  bool			mark;								// Marked flag
  EdgeNode*		edgePtr;							// Pointer to list of edges
};

*string's members are set to zero (the backing char-pointer a string has is likely to point to null),
as well as any other members in the string object.

*bool is set to false (because 0 is false and any other number is true)

*EdgeNode points to null (size of pointer is typically 4-8 bytes, depending on the machine (might be more on some machines but lets assume 8 bytes), so lets assume each byte's character determines where the EdgeNode is pointing to. If the bytes are set to zero, then the only location EdgeNode is pointing to is NULL, or location 0x00000000 where each 0 (except the first one followed by an x) represents the value of the location in bytes via hexidecimal).

This should happen to each element in your array sense memory is being set for not just one VertexNode, but the amount that is pre-initialized.

That's probably overkill for an explanation of the choice of initialization for your array of values but hopefully it helps @_@.

Note: It may be better to migrate the initialization of your numV and VertexNode pointer to the body of the constructor so you can catch an out-of-memory error. This way if an error occurs and memory cant be assigned to the VertexNode pointer, your application wont crash for attempting to 'initialize' memory that may not belong to it.

Linkage

Last edited by Alex Edwards; Nov 12th, 2008 at 12:37 am.

Alex Edwards

Reputation Points: 392

Solved Threads: 108

Posting Shark

Offline

971 posts
since Jun 2008

Permalink

Nov 12th, 2008

Re: Graph help please

Sorry to be so vague but here are my instructions.

I understand what a graph is but I just dont know how to impliment it.

C++ Syntax (Toggle Plain Text)
Your main function must perform all of the following tasks.
(1) Declare a string variable and initialize it with the value argv[1].
(2) Invoke the Load function to input graph data from file along with the search start and end vertices.
Since Load may throw an exception, you should use a try-catch pair to trap the exception.
(3) Once the graph loads, use the Graph class Print function to print out the graph
(4) Perform a Depth-First Search using the start and end vertices input from the file by the Load
function. The path, if found, is stored in a queue (whose address is returned by the DFS function) so
use the Queue class Print function to print out the path. If no path is found, a NULL pointer is
returned by the DFS function.
(5) Compute the weight of the path found by DFS and output to monitor.
Your program must also contain appropriate comments in order to receive full credit.
Your goal is to EXACTLY match the output of your program to that of the sample solution.
Fall 2008 CPE212 Project Assignment Project 8
Page 4 of 5
<Project08 Input File Format>
Use the extraction operator for all inputs!!!
First line of file contains an integer specifying the total number of vertices in the graph.
Use this value when you call the constructor to create the graph.
‘v’  followed by vertex_name (vertex names are always single-word strings)
‘u’  an UNDIRECTED EDGE followed by vertex1 vertex2 edge_weight
‘d’  a DIRECTED EDGE followed by source_vertex destination_vertex edge_weight
‘s‘  name of dfs_start_vertex
‘e’  name of dfs_end_vertex
Hints:
- Use the extraction operator for all inputs!!!
- An UNDIRECTED EDGE may be simulated by two DIRECTED EDGES going in
opposite directions with the same weights
<Project 8 Graph Class Description>
The Graph class uses an Adjacency List Representation to store the graph information.
 Inline functions are not allowed in this course and will result in no credit (0) 
[Note: An inline function is a function whose definition appears within the class declaration]
Attribute Name Data Type Purpose
vertices VertexNode* Stores address of dynamically allocated array of VertexNodes
numV int Number of vertices
Function Name Return
Type
Purpose
Graph N/A Constructor that allocates an array of VertexNodes just large
enough to hold incoming graph
DeleteAllEdges void Deallocates all EdgeNodes connected to all vertices
IsEmpty bool Returns true if Graph is empty, false otherwise
IsFull bool Returns true if Graph is full, false otherwise
AddVertex void Adds vertex name V to vertex array
AddEdge void Adds edge from Source to Destination with specified Weight
IndexIs int Scans vertex array to locate named vertex and returns array index
WeightIs int Returns weight of edge from Source to Destination
GetToVertices void Returns a queue of vertices adjacent to specified vertex
ClearMarks void Sets all vertex marks to false
Fall 2008 CPE212 Project Assignment Project 8
Page 5 of 5
MarkVertex void Sets mark of specified vertex to true
IsMarked bool Returns mark status of specified vertex
Print void Prints Graph contents in specified format (see sample solution)
DepthFirstSearch Queue* Returns pointer to a queue containing the path if found. If not
found, returns NULL pointer
~Graph N/A Deallocates all edge nodes and the vertex array
Note: Load function described in “graph.h”
 See the file graph.h for additional details regarding the function interfaces 
Your main function must perform all of the following tasks.
(1) Declare a string variable and initialize it with the value argv[1].
(2) Invoke the Load function to input graph data from file along with the search start and end vertices.
Since Load may throw an exception, you should use a try-catch pair to trap the exception.
(3) Once the graph loads, use the Graph class Print function to print out the graph
(4) Perform a Depth-First Search using the start and end vertices input from the file by the Load
function. The path, if found, is stored in a queue (whose address is returned by the DFS function) so
use the Queue class Print function to print out the path. If no path is found, a NULL pointer is
returned by the DFS function.
(5) Compute the weight of the path found by DFS and output to monitor.
Your program must also contain appropriate comments in order to receive full credit.
Your goal is to EXACTLY match the output of your program to that of the sample solution.
Fall 2008 CPE212 Project Assignment Project 8
Page 4 of 5
<Project08 Input File Format>
Use the extraction operator for all inputs!!!
First line of file contains an integer specifying the total number of vertices in the graph.
Use this value when you call the constructor to create the graph.
‘v’  followed by vertex_name (vertex names are always single-word strings)
‘u’  an UNDIRECTED EDGE followed by vertex1 vertex2 edge_weight
‘d’  a DIRECTED EDGE followed by source_vertex destination_vertex edge_weight
‘s‘  name of dfs_start_vertex
‘e’  name of dfs_end_vertex
Hints:
- Use the extraction operator for all inputs!!!
- An UNDIRECTED EDGE may be simulated by two DIRECTED EDGES going in
opposite directions with the same weights
<Project 8 Graph Class Description>
The Graph class uses an Adjacency List Representation to store the graph information.
 Inline functions are not allowed in this course and will result in no credit (0) 
[Note: An inline function is a function whose definition appears within the class declaration]
Attribute Name Data Type Purpose
vertices VertexNode* Stores address of dynamically allocated array of VertexNodes
numV int Number of vertices
Function Name Return
Type
Purpose
Graph N/A Constructor that allocates an array of VertexNodes just large
enough to hold incoming graph
DeleteAllEdges void Deallocates all EdgeNodes connected to all vertices
IsEmpty bool Returns true if Graph is empty, false otherwise
IsFull bool Returns true if Graph is full, false otherwise
AddVertex void Adds vertex name V to vertex array
AddEdge void Adds edge from Source to Destination with specified Weight
IndexIs int Scans vertex array to locate named vertex and returns array index
WeightIs int Returns weight of edge from Source to Destination
GetToVertices void Returns a queue of vertices adjacent to specified vertex
ClearMarks void Sets all vertex marks to false
Fall 2008 CPE212 Project Assignment Project 8
Page 5 of 5
MarkVertex void Sets mark of specified vertex to true
IsMarked bool Returns mark status of specified vertex
Print void Prints Graph contents in specified format (see sample solution)
DepthFirstSearch Queue* Returns pointer to a queue containing the path if found. If not
found, returns NULL pointer
~Graph N/A Deallocates all edge nodes and the vertex array
Note: Load function described in “graph.h”
 See the file graph.h for additional details regarding the function interfaces 

JustLearning

Reputation Points: 10

Solved Threads: 0

Light Poster

Offline

31 posts
since Sep 2008

This thread is more than three months old

No one has posted to this discussion for at least three months. Please let old threads die and do not reply to them unless you feel you have something new and valuable to contribute that absolutely must be added to make the discussion complete. Otherwise, please start a new thread in this forum instead.

Previous Thread in C++ Forum Timeline: Search Array

Next Thread in C++ Forum Timeline: quantisation of image colours

DaniWeb Message

Cancel Changes

User Name
Password