Link to home
Start Free TrialLog in
Avatar of f15e
f15e

asked on

Problems with making this code work...PLEASE HELP

Update.  I have pasted my code below for the adjacency list .cpp and .h files and the driver file. I am having problems with the pointer array.  At least I think that is the problem.  If anyone of you could help with this I would greatly appreciate  it.  Thanks for you help.  I have posted this code on a previous post, but no replies.  I didn't have an option to assign points to it.  I am not sure how the point system or how other people see my posts, so I started a new one.  Sorry if I shouldn't do this, but I am desparate to finish this code.  See my statement at the bottom of the driver code.


The Header file:
------------------------------------

//SPECIFICATION FILE: adjacency.h

#ifndef _ADJACENCYLIST
#define _ADJACENCYLIST

#include <string>
using namespace std;

template <class NodeInfo>
class AdjacencyList
{
      
      public:
            
                   //Default constructor
            AdjacencyList();
      
            //Destructor
            ~AdjacencyList();
            
            //Constructor to create and edge with incident
                   //vertices v1 and v2, the weight of the edge
                 void AddEdge(NodeInfo, NodeInfo, int);
            
            //Returns the weight of the nodes that is being sent by user
            int WeightIs(NodeInfo);

            
      private:
            int numVertices; // index keeps track of the array size
            
            struct Vertex  // struct of type vertex
            {
                  int v1;
                  int v2;
                  int weight;
                  Vertex *next;
            };
            
            Vertex *Adjacency;  // a pointer of type vertex
            Vertex *dummy1;   // a pointer of type vertex
};


#endif
/************************************************************************************************/



The .cpp file
------------------------------------

//IMPLEMENTATION FILE: adjacency.cpp

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

//***************************************************************
// Function: Default constructor
// Description: Initializes the private member variables
// Pre: None
// Post: Constructs the disjoint set object, numberOfElements is
//       the initial number of disjoint sets.
//***************************************************************
template <class NodeInfo>
AdjacencyList<NodeInfo>::AdjacencyList()
{
      
      Adjacency = new Vertex[100];
      dummy1 = Adjacency;

                  
      numVertices= 0;
      Adjacency->v1 = 0;
      Adjacency->v2 = 0;
      Adjacency->weight= 0;
                  
}

//***************************************************************
// Function: Destructor
// Description: destroys what the constructor created
// Pre: An array exists
// Post: Destroys the Array.
//***************************************************************
template <class NodeInfo>      
AdjacencyList<NodeInfo>::~AdjacencyList()
{
      delete [] Adjacency;                  
}

//***************************************************************
// Function: AddEdge
// Description: gets the value from the user and adds them to the nodes
// Pre: An array exists
// Post: Adds the edges with the cost and connects it with other equivalent
//       edges.
//***************************************************************
template <class NodeInfo>
void AdjacencyList<NodeInfo>::AddEdge(NodeInfo vertex1,
       NodeInfo vertex2, int wgt)
{
      if(Adjacency!=NULL)
      {
            Adjacency[numVertices].v1 = vertex1;
                        
            Adjacency->v2 = vertex2;
            Adjacency->weight= wgt;
      
            Adjacency = new Vertex;
            Adjacency = Adjacency->next;
      }
      Adjacency= dummy1;            
      numVertices++;
      
}      

//***************************************************************
// Function: WeightIs
// Description: returns the weight of two nodes.
// Pre: an array has been constructed
// Post: Constructs the disjoint set object, numberOfElements is
//       the initial number of disjoint sets.
//***************************************************************      
template <class NodeInfo>
int AdjacencyList<NodeInfo>::WeightIs(NodeInfo vertex)
{
      int totalWeight;
      Adjacency = dummy1;
      
      if(Adjacency!=NULL)
      {
      for(int j=0;j<numVertices;j++)
      {      
            if(Adjacency[j].v1 == vertex)
            {
                  totalWeight = Adjacency->weight;                                    
            }
            else if(Adjacency->next != NULL)
            {
                  Adjacency = Adjacency->next;
            
            }
            j++;
      
      }
      }
      
      Adjacency= dummy1;
      return totalWeight;      
}



/******************************************************************************/

driver .cpp file
------------------------------------


#include <iostream>
#include <string>
#include "unionfind.h"
#include "adjacencylist.h"
using namespace std;

int main()
{    
     
     //Driver for Adjacency list class
     
     Graph<int> g;
     
     g.AddEdge(2, 3, 4);
     g.AddEdge(5, 6, 7);
     g.AddEdge(8, 5, 9);
     g.AddEdge(1, 3, 6);
     
     // When it gets here, WeightIs function, doesn't work.  Get a segmentation fault here
     cout<<"The weight of 2 is: "<<g.WeightIs(2)<<endl;
     cout<<"The weight of 5 is: "<<g.WeightIs(5)<<endl;
     cout<<"The weight of 8 is: "<<g.WeightIs(8)<<endl;
     cout<<"The weight of 1 is: "<<g.WeightIs(1)<<endl;
     
     
     
     return 0;
     
     
}


/*************************************************************************/

I am creating a list of integer arrays where each cell is a pointer, but I am not sure how to do this.  I believe this is my problem.  I would appreciate any help!!  Thanks.
Avatar of ikework
ikework
Flag of Germany image

hi  f15e, i compiled the code and had no errors, i removed/changed 2 rows:

i had to remove the #include "unionfind.h" in driver.cpp and replaced following row in main:

old:
 Graph<int> g;

replaced with:
  AdjacencyList<int> g;



output is:

bash-2.05b$ ./a.out
The weight of 2 is: 6
The weight of 5 is: 4198832
The weight of 8 is: 6
The weight of 1 is: 4198832



cheers, ike
Avatar of f15e
f15e

ASKER

Thanks.  But if I'm not mistaken, the code below from the driver:

     // the 1st param is for vertex1, 2nd for vertex2, and 3rd is the weight for the adjlist.
    // so for g.AddEdge(2, 3, 4), the weight of 2 should be 4, g.AddEdge(5, 6, 7) should be 7, so on.......
    g.AddEdge(2, 3, 4);
     g.AddEdge(5, 6, 7);  
     g.AddEdge(8, 5, 9);
     g.AddEdge(1, 3, 6);
     
     // When it gets here, WeightIs function, doesn't work.  Get a segmentation fault here
     cout<<"The weight of 2 is: "<<g.WeightIs(2)<<endl;
     cout<<"The weight of 5 is: "<<g.WeightIs(5)<<endl;
     cout<<"The weight of 8 is: "<<g.WeightIs(8)<<endl;
     cout<<"The weight of 1 is: "<<g.WeightIs(1)<<endl;


I am not very good with pointers.  But I think in the constructor, I must use a for loop to make each cell an int pointer to point to the next cell. in each array.  I don't think it is pointing back to the beginning.
Avatar of f15e

ASKER

Changing the parameter numbers for the code in the post above as follows:

        adj.AddEdge(4,5,2);
      adj.AddEdge(2,3,1);
      adj.AddEdge(1,9,3);
      adj.AddEdge(6,8,2);
      
        //Displays weight of the particular vertex in question
      cout << "Vertex 4 weight is " << adj.WeightIs(4) << endl;
      cout << "Vertex 2 weight is " << adj.WeightIs(2) << endl;
      cout << "Vertex 1 weight is " << adj.WeightIs(1) << endl;
      cout << "Vertex 6 weight is " << adj.WeightIs(6) << endl;


Has the following output:

Test for Adjacency List
-----------------------
Vertex 4 weight is 2
Vertex 2 weight is 0
Vertex 1 weight is 2
Vertex 6 weight is 0


The first two parameters of each of the g.AddEdge(NodeInfo, NodeInfo, int) functions are a vertex.  The 3rd number is the weight of these two vertex.  So for the first g.AddEdge(2.3.4), the output of g.WeightIs(2) should be 4, which is the weight of 2 and 3.  The same type of thing happens for the next three function calls.

The very first output, Vertex 4 weight is 2, is correct, but after that the values are screwed up.

I don't know what is going on.  Any ideas.  If I try to find the weight of the second parameters in each WeightIs function gives me all 0's.  

Please help!!

THANKS!!

What is it that you exactly want to do here. read a graph and create an adjancency list and matrix??

i am at a loss trying to figure out that you are doing.
when you create your adjancency list you add 100 vertex objects linked by the pointer Adjancency.

 Adjacency = new Vertex[100]; // here !!

and then you lose the pointer to the stuff you declared by doing operation marked as **

     if(Adjacency!=NULL)
     {
          Adjacency[numVertices].v1 = vertex1;
                   
          Adjacency->v2 = vertex2;
          Adjacency->weight= wgt;
     
          Adjacency = new Vertex; // ** here you are losing your earlier array
          Adjacency = Adjacency->next;
     }
     Adjacency= dummy1;          
     numVertices++;
}    

in an adjancency list you have a list of vertices and you have a list of vertices connected to each vertex attached to each one in the list. Sort like this

vert 1->2->4
vert 2->1
vert 3->3->1
vert 4->1

zzray
Avatar of f15e

ASKER

Yes your right.  I am losing the array.  I am not good with pointers/linked list.  It has been a while.  I am not sure how to fix this.  I am trying to do something like you have at the bottom:

vert 1->2->4
vert 2->1
vert 3->3->1
vert 4->1

just not sure how to do it.  Any ideas on how I can do this?  I REALLY appreciate your help zzray!

Thanks

Avatar of f15e

ASKER

Just an explanation of what I am supposed to be doing.  The adjacency list class must support a graph where the edges have a cost associated with them. I should be able to ask if one edge cost more than another.  The vertices of the graph will be numbered .  That's pretty much all the information I have to work with.  

The problem is that this is due in 1 hour, must submit it electronicallly.    All the other classes I am using work perfectly except for this one.  So that's about what I am dealing with on this end.
what i would suggest is that

when you first create the adjancency list set everything to zero (btw in your constructor you are only initializing the first vertex object.  loop through and you can fix that. )

 I recommend you remove v2 from the structure Vertex doesnt serve any purpose.

I assume you want you retain the general structure of your class as is so what you can do with the current implementation is that you add a few more functions.

1. a findVertex which returns -1 if vertex is not found in the arrary adjacency and the index if its found.
2. addNode which creates a vertex in the main array.

func 1 lets you  know whether to add an edge to the main adjanceny array in addEdge. so in addEdge you will first see if vertex1 or two is present in the main adacency array.

if vert 1 is present then you look at the next pointer it its null you can create a new vertex object and point it to that something like this

int num = findVertex(vertex1)
if (num > = 0)
{
    Vertex * pos = Adajcency[num].next;
     Vertex* prev = pos;
     while(pos!=null)
     {  
         prev = pos;
         pos = pos->next;
      }
      pos = new Vertex(v2, wt);
       prev->next = pos;
}
 
then check if vertex2 is in the main array if not then add that too and that should do it.

you have to change the weightIs function accordingly.

try making the changes.




Avatar of f15e

ASKER

Thanks zzray.  I only have about 30 minutes before the code is due.  I am still finishing off the documentation for the code.  I will be using this class again for another assignment next week, so the advice and ideas you gave me to fix the mess I have, I believe will help.  Again, I appreciate all your help.

BTW, what is the deal with the point system thing.  Who gets the points?  Must I so something to give the person who helped me the points?  As you know, I am new to this, so forgive my ignorance.

Thanks zzray!!
ASKER CERTIFIED SOLUTION
Avatar of zzray
zzray

Link to home
membership
This solution is only available to members.
To access this solution, you must be a member of Experts Exchange.
Start Free Trial
Avatar of f15e

ASKER

Hmmm.   Good question.  Our teacher set the class on a flight to nowhere.  Gave us a brief explanation on what we are supposed to do, and that was it.  There are still many open question that have no answer yet.  What the WeightIs funcion is supposed to do is return the combined weight of the two nodes from the AddEdge function.
you welcome.

the points should be given to the person who lead you to the answer
or answered your problem.




#include <string>
using namespace std;

template <class NodeInfo>
class AdjacencyList
{
     
     public:
         
                 //Default constructor
          AdjacencyList();
     
          //Destructor
          ~AdjacencyList();
         
          //Constructor to create and edge with incident
                 //vertices v1 and v2, the weight of the edge
               void AddEdge(NodeInfo, NodeInfo, int);
         
          //Returns the weight of the nodes that is being sent by user
          int WeightIs(NodeInfo, NodeInfo);

         
     private:
          int numVertices; // index keeps track of the array size
         
          struct Vertex  // struct of type vertex
          {
               int v1;
               int weight;
               Vertex *next;
          };

          int findVertex(NodeInfo v);          
          int addNode(NodeInfo v, int weight);
          Vertex *Adjacency;  // a pointer of type vertex      
};



//IMPLEMENTATION FILE: adjacency.cpp


//***************************************************************
// Function: Default constructor
// Description: Initializes the private member variables
// Pre: None
// Post: Constructs the disjoint set object, numberOfElements is
//      the initial number of disjoint sets.
//***************************************************************
template <class NodeInfo>
AdjacencyList<NodeInfo>::AdjacencyList()
{
     
     Adjacency = new Vertex[100];
               
     numVertices= 0;
     for(int i = 0; i<100; i++)
     {
       Adjacency[i].v1 = 0;
       Adjacency[i].weight= 0;
     }      
}

//***************************************************************
// Function: Destructor
// Description: destroys what the constructor created
// Pre: An array exists
// Post: Destroys the Array.
//***************************************************************
template <class NodeInfo>    
AdjacencyList<NodeInfo>::~AdjacencyList()
{
     delete [] Adjacency;              
}

//***************************************************************
// Function: AddEdge
// Description: gets the value from the user and adds them to the nodes
// Pre: An array exists
// Post: Adds the edges with the cost and connects it with other equivalent
//       edges.
//***************************************************************
template <class NodeInfo>
int AdjacencyList<NodeInfo>::addNode(NodeInfo vertex1, int wgt)
{
    Adjacency[numVertices].v1 = vertex1;
    Adjacency[numVertices].weight = wgt;
    Adjacency[numVertices].next = 0;
    numVertices++;    
    return numVertices-1;
}    

template <class NodeInfo>
int AdjacencyList<NodeInfo>::findVertex(NodeInfo vertex1)
{
    for(int i = 0; i<numVertices; i++)
      if ( Adjacency[i].v1 == vertex1 )
          return i;
    return -1;
}    
     
template <class NodeInfo>
void AdjacencyList<NodeInfo>::AddEdge(NodeInfo vertex1,
      NodeInfo vertex2, int wgt)
{
    int num1 = findVertex(vertex1);
    if (num1 == -1) //edge not found
      num1 = addNode(vertex1, 0);
       
    Vertex* pos = Adjacency[num1].next;
    Vertex* prev = &Adjacency[num1];
    while(pos!=0)      
    {
      prev = pos;
      pos = pos->next;      
    }
   
    pos = prev->next = new Vertex;
    pos->v1 = vertex2;
    pos->weight = wgt;
    pos->next=0;
   
    int num2 = findVertex(vertex2);
    if (num2 == -1) //edge not found
       addNode(vertex2, 0);      
}    

//***************************************************************
// Function: WeightIs
// Description: returns the weight of two nodes.
// Pre: an array has been constructed
// Post: Constructs the disjoint set object, numberOfElements is
//      the initial number of disjoint sets.
//***************************************************************    
template <class NodeInfo>
int AdjacencyList<NodeInfo>::WeightIs(NodeInfo vertex1, NodeInfo vertex2)
{
    int num = findVertex(vertex1);
    if (num == -1)
      return 0;
   
    Vertex * pos = Adjacency[num].next;
    while(pos!= 0)
    {
      if( pos->v1 == vertex2)
          return pos->weight;
        pos = pos->next;
    }
    return 0;
}





int main()
{    
     
     //Driver for Adjacency list class
     
     AdjacencyList<int> g;
     
     g.AddEdge(4, 3, 2);
     g.AddEdge(2, 3, 1);
     g.AddEdge(1, 9, 3);
     g.AddEdge(1, 3, 6);
     
     cout<<"The weight of 4,3 is "<<g.WeightIs(4,3)<<endl;
     cout<<"The weight of 2,3 is "<<g.WeightIs(2,3)<<endl;
     cout<<"The weight of 1,3 is "<<g.WeightIs(1,9)<<endl;          
     cout<<"The weight of 1,9 is "<<g.WeightIs(1,3)<<endl;

     
     return 0;          
}

just rewrote as i suggested earlier in my understanding of what should be happening. i dont know if thats what you need really but here it is
Avatar of f15e

ASKER

Thank you very much zzray.  You have no idea how much I appreciate that.  At least now I can go through your code and see  how it is supposed to work.  What you have above is what I needed.  I already submitted the code and hopefully not too many points will be deducted, but it will be useful for the next assignment.

If you lived around here I would buy you lunch.  LOL!!

Thanks again!!
i'll take an IOU for the lunch ;)

You are most welcome :)......