Graph with incidence lists

[ferenczi]

Hello everybody,

I would link to represent a graph with incidence lists.

This picture is what I've thought about:

http://img697.imageshack.us/img697/2640/incidence.jpg

This is what I created:

#include <cstdlib>
#include <iostream>

using namespace std;

class Edge;
class Pointer;

class Node
{
      public:
             Node* nNext;
             Pointer* incList;
             
             char First;
             
             Node(char a) : First(a), nNext(NULL), incList(NULL) {  }
};

class Pointer
{
      public:
             Pointer* pNext;
             Edge* pEdge;
             
             Pointer() : pNext(NULL) {  }
};

class Edge
{
      public:
             char First;
             char Second;
             int weight;
             
             Edge(char a, char b, int c) : First(a), Second(b), weight(c) {  }
             
};


class Graph
{
     private:
             Node* FirstNode;
             
     public:
            Graph() : FirstNode(NULL) {  }
            
            Node* findNode(char n)
            {
                   Node* pTemp = FirstNode;
                   Node* location = NULL;
                   
                   while (pTemp != NULL)
                   {
                        if (n == pTemp->First)
                        {
                              location = pTemp;
                              return location;
                        }
                        else
                            pTemp = pTemp->nNext;
                   }
                   
                   return location;
            }
            
            void insertNode(char a)
            {
                 Node* newNode = new Node(a);
                 
                 if (FirstNode == NULL)
                 {
                       FirstNode = newNode;
                       return;     
                 }
                 
                 Node* pTemp = FirstNode;
                 while (pTemp->nNext != NULL)
                       pTemp = pTemp->nNext;
                       
                 pTemp->nNext = newNode;
            }
            
            
            void insertEdge(char a, char b, int c)
            {
                 Node* loc_01;
                 Node* loc_02;
                 
                 loc_01 = findNode(a);
                 loc_02 = findNode(b);
                 
                 if (loc_01 == NULL)
                 {
                           cout << "First vertex not found.";
                           return;
                 }
                  
                 if (loc_02 == NULL)
                 {
                            cout << "Second vertex not found.";
                            return;
                 }
                  
                 Edge* newEdge = new Edge(a, b, c);
                 
                 Pointer* element = new Pointer();
                 element->pEdge = newEdge;

                 if (loc_01->incList == NULL)
                 {
                    loc_01->incList = element;
                 }
                 else
                 {
                     while (loc_01->incList != NULL)
                           loc_01->incList = loc_01->incList->pNext;
                           
                     loc_01->incList = element;
                 }
            }
            
            void printGraph()
            {
                 Node* pTemp = FirstNode;
                 Pointer* Temp;
                 
                 while (pTemp != NULL)
                 {
                      cout << pTemp->First;
                      Temp = pTemp->incList;
                      while (Temp != NULL)
                      {
                            cout << " -> " << Temp->pEdge->Second << " (weight " << Temp->pEdge->weight << ").";
                            Temp = Temp->pNext;
                      }
                      
                      cout << endl;
                      pTemp = pTemp->nNext;
                 }
            }
};

int main(int argc, char *argv[])
{
    Graph example;
    example.insertNode('a');
    example.insertNode('b');    
    example.insertEdge('a', 'b', 10);
    example.insertNode('c');
    example.insertEdge('b', 'c', 25);
    example.insertNode('z');
    example.insertEdge('b', 'z', 15);
    example.insertEdge('b', 'c', 64);
    example.insertEdge('z', 'a', 12);
    
    example.printGraph();
    
    cout << endl << endl;
    
    return EXIT_SUCCESS;
}

It seems to work but when I insert more than one edge to a vertex the new edge overwrites the first one, so I can just have an edge per vertex...

Can you help...?
Thanks!

[mbulow]

Hi ferenczi :-)

Take a look a close look at your insertEdge-function. In particular the content of the else-statement.

Consider what happens in the while-loop.

While the incList-pointer is not NULL, you make it point to the first elements next-pointer. When the while-loop completes the incList-pointer will always be NULL.

The next thing you do is set the incList-pointer to the new element.

[mbulow]

You can fix the problem like this:

else
{
    Pointer* temp;
    temp = loc_01->incList;
    while (temp->pNext != NULL)
        temp = temp->pNext;
    temp->pNext = element;
}

[ferenczi]

Thank you for your help!