How do u build a graph????

[TriniBabe]

U are given the data(startnode,end node,cost) for each edge on a separate line but u dont no how much nodes u hav b4 hand how u declare it? how do u link the nodes in an adjacency list using linked list and not d <vector>?

[TriniBabe]

I hav reached this far>>>>>>>

typedef struct Edge
{

           string d[];       //the second node in d edge
           double cost;
           double duration;

       }Edge, * EdgePtr;

struct Vertex
{
           string e;     //first node in edge
           EdgePtr firstEdge;
}Vertex

... how do i create a linked list for each of the nodes?
....how do i build a graph?

[SeeTheLite]

Heh, sorry but I'm about as useful as a hobo when it comes to graphs, as for linked lists, the basic format is:

struct list {
        int data;
        list *link;
};

basically you create a list *a and link it to another list variable with *link inside list. To create a linked list, you must link the list to each successive chain:

list *one, *head, *p;
int x;
head = one;                   //records begining of your list

for(x  = 0; x < 5; x++) {

cin>>one.data;              //takes integer value
p = new struct list;        //creates new list
one->link=p;                  //links current chain to next
one = one->link;            //moves from current chain to next

}

one = head;                 //resets one to begining

In your case, just make data a string and include your doubles as additional variables. All lists are essentially just data and a pointer. You can also make a doubley linked list with a pointer that points to the variable in front of it. I hope this makes sense to you, good luck!

[TriniBabe]

each node has to hav a linked list(i am guess).......... so it is there any way 2 create like a list like an array of linked lists

[SeeTheLite]

Well there is really nothing stopping you, although it might get confusing to access individual elements at times. Just remeber that you use -> instead of . to access variables in your list(sorry, my example was wrong >_<, but I edited it).

[TriniBabe]

so say my array is named F....so my array of linked lists is declared as list F[10]? sorry really dont no!

[SeeTheLite]

if you had a struct list,

just declare list *F[10];

for each element you would just say F[x]->data to access whatever you need, the only difference from a normal linked list is that you have to address each element when using them(you can use loops too of course).

[DemonGal711]

I had to do a program like this (and am actually doing another like this now) so hopefully I can be of some help. When I did this program, I started out with an example and used that to help build my code. Perhaps you should start there and come up with some graph and determine what the list should look like to make sure that you are getting exactly what you want.

I believe you are following the way I had (at least that's how it looks by the code) so lets see if I can explain this.

I worked with this picture and tried to change it into this picture. To explain my image a little, my list consisted of the node name (A, B, C, D) and a linked list that contained name of the nodes it connected to, the cost, and the next node in that list (or null if at end of the list). Below are the structs.

class To
{ public:
  struct Node
    { string item;  
      int cost;
      Node* next; 
    };
}

class From
{ public:
  struct NodeType
  { string item;
    To* list;
    NodeType* next;
  };
}

I used two classes for this, my From class, which contained my linked list of points (the far left nodes in my adjacency matrix image) and my To class, that contained the nodes it pointed to and the cost it was to get between them.

From there, I just wrote the classes like I was writing a regular linked list and just worried about jumping between them properly. Meaning if I wanted to add that A-E was cost 4, I had to search out A in my From list, go into the To list in that node, add a node to the end of the list that had name E and cost 4, then go search out E, make a new From node since it wasn't there, and then jump to it's To list, and add the To node after.

To help a bit more, here's a list of function that I used to design my list. All functions were used in both lists, though they were slightly different.

Constructor and destructor
bool  IsThere()      // determines if a point is already in the list
NodeType* Find ()    // if in the list, finds the node and returns it.
void Insert ()       // creates a new node if not already in the list
void  Print()        // used to make sure the list is saving properly

That should help you get started at least. Just work on writing up the inner most list and make sure it works correctly first before worrying about the outer list. The inner list should be easy cause it's just like a regular linked list. The only difference for the outer is you have another list inside it, which can be difficult when trying to go between them, but not impossible.

Hope this helps.