?
Solved

Problems with making this code work...PLEASE HELP

Posted on 2005-03-16
14
Medium Priority
?
314 Views
Last Modified: 2008-03-10
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.
0
Comment
Question by:f15e
[X]
Welcome to Experts Exchange

Add your voice to the tech community where 5M+ people just like you are talking about what matters.

  • Help others & share knowledge
  • Earn cash & points
  • Learn & ask questions
  • 7
  • 6
14 Comments
 
LVL 20

Expert Comment

by:ikework
ID: 13559454
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
0
 

Author Comment

by:f15e
ID: 13560041
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.
0
 

Author Comment

by:f15e
ID: 13561237
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!!

0
Industry Leaders: We Want Your Opinion!

We value your feedback.

Take our survey and automatically be enter to win anyone of the following:
Yeti Cooler, Amazon eGift Card, and Movie eGift Card!

 
LVL 2

Expert Comment

by:zzray
ID: 13561667
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
0
 

Author Comment

by:f15e
ID: 13561705
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

0
 

Author Comment

by:f15e
ID: 13561748
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.
0
 
LVL 2

Expert Comment

by:zzray
ID: 13561816
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.




0
 

Author Comment

by:f15e
ID: 13561876
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!!
0
 
LVL 2

Accepted Solution

by:
zzray earned 1500 total points
ID: 13561880
just asking what is your weight is function doing?
is it asking the weight between two nodes. it seems to take only one argument..
0
 

Author Comment

by:f15e
ID: 13561903
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.
0
 
LVL 2

Expert Comment

by:zzray
ID: 13562136
you welcome.

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




0
 
LVL 2

Expert Comment

by:zzray
ID: 13562350
#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
0
 

Author Comment

by:f15e
ID: 13563168
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!!
0
 
LVL 2

Expert Comment

by:zzray
ID: 13563213
i'll take an IOU for the lunch ;)

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

Featured Post

Free Tool: ZipGrep

ZipGrep is a utility that can list and search zip (.war, .ear, .jar, etc) archives for text patterns, without the need to extract the archive's contents.

One of a set of tools we're offering as a way to say thank you for being a part of the community.

Question has a verified solution.

If you are experiencing a similar issue, please ask a related question

IntroductionThis article is the second in a three part article series on the Visual Studio 2008 Debugger.  It provides tips in setting and using breakpoints. If not familiar with this debugger, you can find a basic introduction in the EE article loc…
This article shows you how to optimize memory allocations in C++ using placement new. Applicable especially to usecases dealing with creation of large number of objects. A brief on problem: Lets take example problem for simplicity: - I have a G…
The goal of the tutorial is to teach the user how to use functions in C++. The video will cover how to define functions, how to call functions and how to create functions prototypes. Microsoft Visual C++ 2010 Express will be used as a text editor an…
The viewer will learn how to use the return statement in functions in C++. The video will also teach the user how to pass data to a function and have the function return data back for further processing.
Suggested Courses

764 members asked questions and received personalized solutions in the past 7 days.

Join the community of 500,000 technology professionals and ask your questions.

Join & Ask a Question