c++ boost Dijkstra’s unsure of output - Page 2

[mike_2000_17]

only another hour, I gotta say I didn't think this project would be that hard when he gave us the write up (in theory this should have only taken an hour), but the sytax is so daunting I'm not sure how we were expected to have time to do all three tiers of this project.

I think your prof assumed that the students are familiar with C++ already. A person who is already familiar with C++ syntax and has an average level of competence with the language can solve this assignment within a couple of hours, easily. I don't know if it was stated anywhere in the course pre-requisites that good C++ knowledge was necessary for the course, but if it was, then this is certainly a reasonable assignment. It is not reasonable if there was no pre-requisite of the sort. If you ignored that pre-requisite, thinking that you could just learn C++ as you go, then you are currently experiencing the consequences of that poor judgement call.

[mike_2000_17]

No, you need to do this:

while (std::getline(fin,tempString)){ // (Location1, Location2, 6)
        //remove parentheses
        tempString.erase( tempString.begin(), tempString.begin() + tempString.find('(') + 1 );
        tempString.erase( tempString.begin() + tempString.find(')'), tempString.end() );

        std::cout<<std::endl<<tempString;

        std::stringstream temp_ss(tempString);
        std::getline(temp_ss, tempName1, ',');
        { 
          std::size_t first_c = tempName1.find_first_not_of(' ');
          std::size_t last_c = tempName1.find_last_not_of(' ');
          tempName1 = tempName1.substr(first_c, last_c - first_c + 1);
        };

        std::getline(temp_ss, tempName2, ',');
        { 
          std::size_t first_c = tempName2.find_first_not_of(' ');
          std::size_t last_c = tempName2.find_last_not_of(' ');
          tempName2 = tempName2.substr(first_c, last_c - first_c + 1);
        };

        temp_ss >> weight;
        // Add edge to graph, by finding vertices associated 
        //  to tempName1 and tempName2:
        add_edge(name2v[tempName1],name2v[tempName2],EdgeProperty(weight), g);
    }

[Jed_1]

only another hour, I gotta say I didn't think this project would be that hard when he gave us the write up (in theory this should have only taken an hour), but the sytax is so daunting I'm not sure how we were expected to have time to do all three tiers of this project.

I think your prof assumed that the students are familiar with C++ already. A person who is already familiar with C++ syntax and has an average level of competence with the language can solve this assignment within a couple of hours, easily. I don't know if it was stated anywhere in the course pre-requisites that good C++ knowledge was necessary for the course, but if it was, then this is certainly a reasonable assignment. It is not reasonable if there was no pre-requisite of the sort. If you ignored that pre-requisite, thinking that you could just learn C++ as you go, then you are currently experiencing the consequences of that poor judgement call.

no, this is the college's attempt to reduce the total number of credit hours to complete the course load for an assosiates. so rather than teach a class in c++ and a class in data structure and algorithms they teach data structure and algorithms in c++. the only programing done in lecture was a hello word and some header file creation. the rest was entirly self-taught and that was how the class was desined. he reapeated that a lot like we were all supposed to complain on our class evaluation so that they would not do it again next year, which of course I did.

[squoosh54]

Evan, is this working for you? Because I can get it to run if I get rid of the lines that remove parenthesis, but the output is nonsense

[Jed_1]

yeah this works perfectly for me now! only step one completed, but hey a 70 is bettter than a 0! I have no idea why it wouldn't work for ya, is your code the same as what mike posted?I've been using that code to remove the parentheses for about 15 hours, not cause me any trouble...

[squoosh54]

Not working for me at all, and yes, I'm using what mike posted. I guess I must have changed something by accident, but whatever.

[squoosh54]

what's your final draft of your code?

[Jed_1]

The final draft of my code working up to stage 1 with no error or warnings:

#include <iostream>
#include <fstream>
#include <map>
#include <vector>
#include <string>
#include <boost/graph/adjacency_list.hpp>
#include <boost/graph/visitors.hpp>
#include <boost/graph/breadth_first_search.hpp>
#include <boost/graph/dijkstra_shortest_paths.hpp>
#include <boost/graph/metis.hpp>

typedef boost::adjacency_list_traits<
    boost::vecS, boost::vecS, boost::undirectedS, boost::listS> GraphTraits;
// type 'Vertex' identifies each vertex uniquely:
typedef GraphTraits::vertex_descriptor Vertex;
// Property type associated to each vertex:
struct VertexProperty {
    std::string name; //name of vertex (i.e. Location)
    Vertex predecessor; //predecessor along optimal path
    double distance; //distance to the goal, along shortest path
    boost::default_color_type color; //for dijkstra

    VertexProperty(const std::string& aName = "") : name(aName) { };
};
// Property type associated to each edge:
struct EdgeProperty {
    double weight;// distance to travel along this edge.
    EdgeProperty(double aWeight = 0.0) : weight(aWeight) { };
};
// Type of the graph used:
typedef boost::adjacency_list<
    boost::vecS, // out-edges stored in vector 
    boost::vecS, // vertices stored in vector
    boost::undirectedS, // undirected graph (edge don't have a specific direction)
    VertexProperty, // properties associated to each vertex.
    EdgeProperty // properties associated to each edge.
> Graph;
// Create a global graph object 'g'
Graph g;
// This is a visitor for the dijkstra algorithm. This visitor does nothing special.
struct do_nothing_dijkstra_visitor {
    template <typename Vertex, typename Graph>
    void initialize_vertex(Vertex u, const Graph& g) const { };
    template <typename Vertex, typename Graph>
    void examine_vertex(Vertex u, const Graph& g) const { };
    template <typename Edge, typename Graph>
    void examine_edge(Edge e, const Graph& g) const { };
    template <typename Vertex, typename Graph>
    void discover_vertex(Vertex u, const Graph& g) const { };
    template <typename Edge, typename Graph>
    void edge_relaxed(Edge e, const Graph& g) const { };
    template <typename Edge, typename Graph>
    void edge_not_relaxed(Edge e, const Graph& g) const { };
    template <typename Vertex, typename Graph>
    void finish_vertex(Vertex u, const Graph& g) const { };
};

int main() {
    std::string tempName1;
    std::string tempName2;
    std::string tempString;
    std::string data2;
    double weight;
    std::cout <<"please enter the data file name: ";
    char strFileName[256];
    std::cin >> strFileName;

    // preparing the data
    std::ifstream fin;
    fin.open(strFileName);
    if(!fin) {
        std::cerr << "Can't open data file, leaving...\n";
        return EXIT_FAILURE;
    }
    else{
        std::cout<< "file loaded."<< std::endl << std::endl;
    }
    // Create a map to associate names to vertices of the graph:
    std::map<std::string, Vertex> name2v;

    std::getline(fin, tempString); //Vertices:
    std::getline(fin, tempString); //Location1, Location2, ...
    std::stringstream tempSS(tempString);
    while (std::getline(tempSS,tempName1, ',')){
        // Add vertex to graph, with name 'tempName1' and 
        //  record the associated Vertex in the name2v map:
        name2v[tempName1] = add_vertex(VertexProperty(tempName1), g);
    }

    std::getline(fin,tempString); //Edges:
    while (std::getline(fin,tempString)){ // (Location1, Location2, 6)
        //remove parentheses
        tempString.erase( tempString.begin(), tempString.begin() + tempString.find('(') + 1 );
        tempString.erase( tempString.begin() + tempString.find(')'), tempString.end() );
        std::stringstream temp_ss(tempString);
        std::getline(temp_ss, tempName1, ',');
        { 
            std::size_t first_c = tempName1.find_first_not_of(' ');
            std::size_t last_c = tempName1.find_last_not_of(' ');
            tempName1 = tempName1.substr(first_c, last_c - first_c + 1);
        };
        std::getline(temp_ss, tempName2, ',');
        { 
            std::size_t first_c = tempName2.find_first_not_of(' ');
            std::size_t last_c = tempName2.find_last_not_of(' ');
            tempName2 = tempName2.substr(first_c, last_c - first_c + 1);
        };
        temp_ss >> weight;
        // Add edge to graph, by finding vertices associated 
        //  to tempName1 and tempName2:
        add_edge(name2v[tempName1],name2v[tempName2],EdgeProperty(weight), g);
    }
    char x;
    Vertex cur_v;
    Vertex start_v;
    Vertex goal_v;
    std::cout<<std::endl << "How would you like to process your data file?"<<std::endl;
    std::cout << "1.) shortest path"<<std::endl;
    std::cout << "2.) minimum spanning tree" << std::endl;
    std::cout << "3.) Travelling Salesman" <<std::endl << std::endl;
returnQuestion:
    std::cout << "please enter 1,2,3 or Q to quit: ";
    std::cin >>x;


    switch (x){
    case '1': //do the work for shortest path
        std::cout<<std::endl << "please enter the location name to start from: ";
        std::cin >>tempName1;
        std::cout<<std::endl << "please enter the location name for the destination: ";
        std::cin >>tempName2;
        // Retrieve the vertices for the start and goal:
        start_v = name2v[tempName1];
        goal_v  = name2v[tempName2];
        dijkstra_shortest_paths(
            g, goal_v, //<-- solve to goal 
            get(&VertexProperty::predecessor, g),
            get(&VertexProperty::distance, g),
            get(&EdgeProperty::weight, g),
            boost::identity_property_map(), // index-map
            std::less<double>(), // compare
            std::plus<double>(), // combine 
            std::numeric_limits<double>::infinity(), // infinity
            0.0, // zero
            do_nothing_dijkstra_visitor(),
            get(&VertexProperty::color, g));

        std::cout << "places visited in order:" << std::endl;
        // Traverse the vertices from the start to goal,
        //  through the "predecessor" links:
        cur_v = start_v;
        while( cur_v != goal_v ) {
            std::cout << g[cur_v].name << " " <<std::endl;
            cur_v = g[cur_v].predecessor;
        };
        std::cout << g[goal_v].name << " " << std::endl;
        std::cout<< std::endl << "Total distance traveled: "<< g[start_v].distance << std::endl<<std::endl;

        break;
    case '2': //do the work for minimum spanning

        break;
    case '3': //do the work for travelling salesman

        break;
    case 'q':
    case 'Q':
        return EXIT_SUCCESS;
        break;
    default :
        goto returnQuestion;
    }

    std::system("pause");
} 

Honestly I'm interested when we go to class on Tuesday for the final exam how many people got even stage one to work for them. I was emailing with Dustin and he only got stage one working at about 3:00PM today (2 hours before it was due) and he is by far the best programmer in the class. I only finished at all thanks to Mike! I emailed Dustin to see if he got stage 2 or 3 working, but he did not respond. he may have crashed.

[Jed_1]

I was working on the write up for the project, which I pretty much jsut BSed

[Jed_1]

and subission for the project is closed! that's all folks.

[mike_2000_17]

I hope you guys realize you might be putting yourself in danger of being accused of plagarism. Just saying.

BTW, to solve the minimum-spanning-tree (which is actually just the same as the Dijkstra algorithm) you can do:

boost::prim_minimum_spanning_tree(
   g, goal_v, 
   get(&VertexProperty::predecessor, g),
   get(&VertexProperty::distance, g),
   get(&EdgeProperty::weight, g),
   boost::identity_property_map(),
   do_nothing_dijkstra_visitor());

which also sets the predecessors to make up the minimum-spanning-tree.

As for the traveling salesman problem, you can create a vector to hold the tour, and call the BGL function for an approximate TSP solution, as follows:

std::vector<Vertex> tsp_tour;

boost::metric_tsp_approx_tour_from_vertex(
  g, start_v,
  get(&EdgeProperty::weight, g), 
  back_inserter(tsp_tour));

And then, the vector tsp_tour will contain the list of vertices visited by a TSP tour.

[Jed_1]

we know better than you turn in the saqme code without stating the source code, teacher said we can get code from anywhere as like as we tell him it's not our code and where we got it, less points the less you changed, but something is better than nothing.

thanks for stage 2 and 3, already turned it in, but it's still nice to know, thank you again!