Results 1 to 7 of 7

Thread: Creating a graph in C++

  1. #1
    Join Date
    Jan 2013
    Beans
    17

    Creating a graph in C++

    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

    Code:
    while (!textFile.eof())
    {        
    textFile >> startAirport >> endAirport >> milege >> cost;        
    cout << startAirport <<  " " << endAirport <<  " " << milege <<  " $" << cost << endl; 
     }


  2. #2
    Join Date
    Jun 2009
    Beans
    352

    Re: Creating a graph in C++

    The main ways to implement a graph are: 2D matrix, objects and pointers, and adjacency lists. This is pretty fundamental stuff so you should be able to find a lot of resources using your favourite search engine.

  3. #3
    Join Date
    Apr 2013
    Location
    43.49°N 7.46°E
    Beans
    117
    Distro
    Ubuntu 12.04 Precise Pangolin

    Re: Creating a graph in C++

    Perhaps mathgl tools might be somehow helpful for you.

  4. #4
    Join Date
    Apr 2010
    Location
    Slovakia
    Beans
    87
    Distro
    Ubuntu 12.04 Precise Pangolin

    Re: Creating a graph in C++

    You can use lists, you will have an airport A and from that you could get to B, C and D then in your reprezentation it would look like this:
    Create a node A -> let say a class or struct, that contain a list of airport where can you go in this case the list will contain B, C, D

    do this for every airport and you have one reprezentation of a graph
    Acer Aspire 5750G i5 2410m, 4GB ram, 640GB hdd, intel graphics

  5. #5
    Join Date
    Jan 2013
    Beans
    17

    Re: Creating a graph in C++

    Awesome! Thanks guys for your input. It shed some more light on this program and its helped me get closer to finishing. Thanks again!

  6. #6
    Join Date
    Jan 2013
    Beans
    17

    Re: Creating a graph in C++

    Thread reopened! Okay, so i've done something like this

    Code:
    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)
    
    }
    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. If you could provide me with an example or something to help me with this I would greatly appreciate it.

  7. #7
    Join Date
    Jan 2013
    Beans
    17

    Re: Creating a graph in C++

    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? How would I store it so I can ask the user for input, then do if (input = "DEN") then I would make denver node #1 and do the rest of the algorithm according to that. I just don't know how to store the information in a good way and then beable to access it when the user asks for it

Bookmarks

Posting Permissions

  • You may not post new threads
  • You may not post replies
  • You may not post attachments
  • You may not edit your posts
  •