Using Graphs for a Flight Program

[rb737]

Hello Everyone,

I hope you are all doing well and I want to thank you in advance for any help you can offer. I'm having a tough time with this one.

I have to write a program that emulates getting a flight from one departure city to another destination city. There will be a total of 7 cities for the user to choose from for departure and 6 cities available for destination. I have to use graphs for this and I have to store the vertices, edges and weights in a text file named load.txt. When my program starts, it will use the load.txt file to load the vertices, edges and weights into my program. I get to chose all the cities and distances between them and also the through flights and connecting flights and whatever info is related to that process.

I have no idea how to start this process nor can I grasp what this load.txt file should look like. I am having trouble understanding what Vertices, Edges and Weights refer to in terms of the specific information they represent for this program use and how they should be represented in the load.txt file. I am also not sure how to represent connecting vs through flights in this load.txt file.

Any help i can get in understanding this would be greatly appreciated.

[jonnin]

you need to get on google and study this. Look for the travelling salesman problem, and try to find one in plain english as the pure theory and math and proof deep explains are tough reading for mere humans.

But I will give you a little of it.

A city might be a "node" or vertex.

An edge might be the "road between the cities" and have a value of "400 miles"

The 400 miles above is one type of weight. There may be others that you use, to prioritize paths or whatever purpose. A weight is a value, and they have various uses from coefficients of polynomials to priority in a queue to edges on a graph. The word is over-used, really.

Load text file might look like

Anchorage, Honolulu, 5000
Honolulu, Mexico City, 3000
Honolulu, London, 8000

entries can repeat, but you should not see the same pair in the same order twice (you wont see this for your problem:
Honolulu, London, 3000
Honolulu, London, 8000 )

its legal to connect to yourself, but illogical for your problem at hand, same as above.
Its ok to have inverse routes:
a,b,1
b,a,1

you are trying to create a data structure that represents many to many relationships and allows you to trace a path from one item to another through intermediates. Imagine a simple linked list? Well, a tree is a set of linked lists, if you seek a particular node the path to it really IS just a linked list, right? Graphs are another step up the chain, is all. Now imagine that every node of ONE linked list is connected to every other node (or not, they don't have to be) of another linked list and all those are all connected to all the nodes of a third linked list... that is a graph.

Graphs don't have a head or root or starting point, you can get anywhere from anywhere (or you have multiple graphs that are not connected, another can of worms). They don't have a next, or left/right, they just have "children" and "parents" and you can go either direction at any time from any node.

so... you probably want a micro class that has
edge{vertex pointer and a weight}
and a meta class
vertex {datastructure, list or vector or whatnot, of edges out of this vertex}

as a rough starter.

[rb737]

Hello Jonnin,

I really appreciate the help you given. It definitely gives me a clearer idea of how this works and what the information in the load.txt file should look like as well as how it relates to the program itself.

Ill take your suggestion and look up the traveling salesman problem and will study that the give myself further intuition on exactly how this works.

You've been a big help, thanks again for taking the time.

[dhayden]

You can probably get away with just studying "graphs" in the computer science sense. Just google "computer science graph" and start reading.

The Traveling Salesman Problem will make your head spin and send you straight to a monastery. It is a common example of a problem that is "NP complete" which means that even with parallel processing, computing the solution to a problem of size N requires O(N^k) time. For any reasonably large values of N and k, that means that a computer using every atom in the universe will take longer than the age of the universe to solve it.

Put another way, there are problems with computable solutions that cannot be computed.

[jonnin]

True, but there are a lot of partial solutions of it that are already coded up for the city / distance or city/ticket cost version, rather than more abstract terms. Ill bet a little searching would lead to some good example data structures.

I didn't say it earlier but its not a terribly bad idea to keep a side-structure with a pointer to every node in your graph that you can iterate over. It beats the heck out of tracing a path thru the thing to see if a particular item even exists or not. You don't even need to write a traversal algorithm if you do that, and those are messy :)