### Creating a graph

So I have been trying to find a good place to learn how to implement a graph, but I have been unable to find one.

I have to create a program that reads in the data about airports and the airports that they are connected to. And the goal of the program is to find the least expense way to go from point A to point B. My question is, how do I put in the data from a file and make a graph out of it? Below is my code to read in the file.

Thanks a bunch for looking over this. I just don't really understand how to input data into a graph and be able to get information from it. Thanks again

 ``123456`` `````` while (!textFile.eof()) { textFile >> startAirport >> endAirport >> milege >> cost; cout << startAirport << " " << endAirport << " " << milege << " \$" << cost << endl; }``````
hey
there it no really a graph policy.
There are ways how you can set it up. Graph can be in 2 D array or adj.list.
so you pick 1 or 2 way.

then load info into a struct of arrays...and then create a new struct with some system how the nodes are connected...

if it's a complete graph then you would have a loop...simular to this for adj.list

I hope this helps!

 ``123456789101112`` ``````//the space between is > > is important: this is because >> means shift right in C/C++ vector > adjList; /*Create adjacency list*/ int edgecounter = 0; for (int n=0; n< graph.size(); ++n) { for ( int k=0; k

which will have
ex: 5 nodes will be stored like
1 2
1 3
1 4
1 5

2 1
2 3
2 4
2 5

3 1
3 2
3 4
3 5

and etc.
and the first struct would need to be like this
struct flight
{
string startAirport;
string endAirport;
int milege;
int cost;

}
int main ()
{
flight f;

vector <flight> sky;
//read data from file
textFile>>f.startAirport >> f.endAirport >>f.milege>> f.cost;
sky.push_back (f)

}

//after this - there will be a new struct for adj.list or 2 d array that will represent the graph (see above)
After! thanks for the help so far. You are a godsend.

So 'sky.push_back (f)' puts all the information read into the vector? Sorry if I seem like an idiot... because with nodes and stuff its true. Hah. Like, I understand that I will be identifying the startAirport as node 1, and then check all the other nodes for the cheapest flight. Basically, I don't know how to manage/organize the information I get. Like what to do with it after it is in the vector/list to make it all connected.
So would I not create this at the start? Because the user has to enter in which airport they want to start the flight. Then the rest of the information will be displayed about all possible routes and which one is the cheapest. So wouldn't I have to store all the info and then put it in the 'struct flight' according to the user input?
bump

So 'sky.push_back (f)' puts all the information read into the vector? - it puts all the airport into the array of structs. Each struct has string startAirport;
string endAirport;
int milege;
int cost;

I understand that I will be identifying the startAirport as node 1, and then check all the other nodes for the cheapest flight. -

Basically, I don't know how to manage/organize the information I get. Like what to do with it after it is in the vector/list to make it all connected. - check out priority queue, it can be organized by min.cost.

So wouldn't I have to store all the info and then put it in the 'struct flight' according to the user input? - I think you need to store all the info into struct since the data needs to be loaded in order - to be searched later per user's request.
you will traverse the vector to find the desired flight for user.
Last edited on
Topic archived. No new replies allowed.