Graph help please
 

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

// 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.

#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++)

        {



}

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--

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...

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

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.

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 