Reading in data to a Linked-List

[DMG]

The input is in the following format

5
1 2 9.0
1 3 12.0
2 4 18.0
2 3 6.0
2 5 20.0
3 5 15.0
0
1 5
The first number is the number of vertexes in the graph. Then next lines up to 0 are the edges of the graph. With the first and second numbers being the vertexes and the third being how far the edge is between them. Trying to read in the data and store the edges into there locations in the List adjacency for that vertex. This example would make a graph with five vertexes with edges from 1 to 2&3. 2 to 4&3&1 etc. It also stores in the opposites ex 2 1 9.0.

When reading it in and printing it back out it seems that it is only storing the last data entered for that vertex. EX. When trying to print out the data read in i only get 1 3 12.0, 2 5 20.0, 3 5 15.0, ( 4 2 18.0, 5 3 15.0 would show up if `if(i<n)` was removed it is there so it does not show duplicate edges). Can anyone help show me what I am doing incorrect?

// CSCI 3300

#include <cstdio>
using namespace std;

struct ListCell
{
   ListCell* next;
   int vertex;
   double weight;

   ListCell(int v, double w, ListCell* nxt)
   {
      vertex = v;
      weight = w;
      next = nxt;
   }
};

typedef ListCell* List;

struct Vertex
{
   bool signaled;
   long distance;
   List adjacency;    
};

struct Graph
{
   int     numVertices;
   Vertex* vertexInfo;

   Graph(int n)
   {
      numVertices = n;
      vertexInfo  = new Vertex[n+1];
      for(int i = 1; i <= n; i++)
      {
         vertexInfo[i].signaled = false;
	      vertexInfo[i].adjacency = new ListCell(i, 0.0, 0);
      }
   }
};

//==============================================================
//                   tail
//==============================================================
// 
//==============================================================

   List tail(List L)
   {
      return L->next;
   }
//==============================================================
//                   isEmpty
//==============================================================
// 
//==============================================================

   bool isEmpty(List L)
   {
      return L == NULL;
   }
//==============================================================
//                   readIn
//==============================================================
// 
//==============================================================

Graph readIn()
{
   int g;
   int p1;
   int p2;
   float edge;
   scanf("%i ", &g);

   Graph myGraph(g);
   scanf("%i", &p1);
   while(p1 != 0)
   {
      scanf("%i", &p2);
      scanf("%f", &edge);         
      
      myGraph.vertexInfo[p1].adjacency = new ListCell 
      (p2,edge,myGraph.vertexInfo[p1].adjacency->next);
     

      myGraph.vertexInfo[p2].adjacency = new ListCell
      (p1, edge, myGraph.vertexInfo[p2].adjacency->next);
      
      scanf("%i", &p1);
   }
   return myGraph;
}

//==============================================================
//                   printOut
//==============================================================
// 
//==============================================================

void printOut(Graph myGraph)
{  
   int n;
   int length = myGraph.numVertices;
   float d;
   List p;

   printf("There are %i vertices.\n", length);
   printf("The edges are as follows. \n\n");
   for(int i=1; i<=length; i++)
   {
      p= myGraph.vertexInfo[i].adjacency;
      for(p=p; !isEmpty(p); p=tail(p))
      {
         n = myGraph.vertexInfo[i].adjacency -> vertex;
         d = myGraph.vertexInfo[i].adjacency -> weight; 
         if(i<n)
         {
            printf("%i %i %7.3f \n",i,n,d);
         }
      }
   }
}
//==============================================================
//                   main
//==============================================================

int main(int argc, char** argv)
{
   Graph myGraph = readIn();
   printOut(myGraph);
   return 0;
}

[Smac89]

You seem to be doing the same thing twice. Line 41, 87, and 91 are the same but you have already done line 87 and 91 on line 41. Choose one man, else you will run out of memory with sufficiently large input.

Also note that every time you get a new edge to connect, if a vertex is already connected to another, then this connection is lost in favor of the new edge. Example still being line 87 and 91. If you have connected say vertex 2 and 3, and you get a new connection (2, 5), the edge 2 had to 3 will be lost and it will get a new edge which is (2, 5).

To fix this, you have to create an insert method which will instead insert the new edge into the vertex' adjacency list rather than creating a new edge.

Btw your program is leaking a lot of memory, memory management is very important when dealing with graph ADT.

Off topic/
for loops don't need to have something in every single spot. These examples of for-loops are still legal:

for(;;) { ... } // infinite loop

// any combination of these are valid for loops
for(/*initialization*/; ;) { ... } // infinite loop with initialization
for(;/*condition*/;) { ... } // glorified while loop
for (;;/*assignment*/) { ... } // infinite loop with assignment