c++, boost, Dijkstra’s, input file is .txt

[Jed_1]

Okay, so as ussual I'm having a lot of problems with a code and I need a lot of help along the way, but I'm just going to break it down into simple questions as I go. I am taking data from an input file that is a .txt that I need to form into a graph to perform Dijkstra’s shortest path algoritum on. The input file is formatted as such:

• Vertices:
  Location1, Location2, Location3, … ,LocationN
  Edges:
  (Location1, Location2, IntegerWeightValue)
  (Location2, Location3, IntegerWeightValue)
  …
  (Location1, LocationN, IntegerWeightValue)*

1.) I know I can skip the first line with just a call of "std::getline(fin,tempString);" so that gets me past the line that is just "Vertices:" and the next line is the name of everynode, so I figured I could just take that whole line as a string and the data values already being seperated by camas call something like "enum nodes {permString};" to make them all the name of a node, but I get an error about reallocating permString from data. Followed by another "std::getline(fin,tempString);" to get past "Edges:".

2.) Next I know I can input the whole line one at a time and use the data from make edges, but I'm not sure how to remove the "()" from the outside of the statments and how to go about putting it all in a form that the boost function for Dijkstra’s shortest path algoritum can handle....

I'm acually really lost, I've tried doing all of these things I several diffrent ways, I found a code example that worked online, but I needed to know how large the file was going to be, and the ewxample didn't use input files, and all the other code examples I've found use .gr files... Any help you can throw my way would be awesome.

tl;dr: just wanna list some lines of code:
how to take in (some, stuff, num) and place that data in a graph useable by boost function for Dijkstra’s shortest path algoritum

[Jed_1]

I tried jsut inputing the data using fin >> tempString >> punc;
where punc is a char.

I assumed that would put location 1 in temp string and the cama in punc, but instead of Location1 I get ocation1, so I switch the order and did fin>>punc>>tempString and it did the same thing...

so I'm pretty lost as to how to do this, it also seems that if I while loop(fin>>tempString>>punc) it will jsut go to the end of the program and not to the end of the line which is a problem.
so I need to take the second line of the input file and all the chars between the camas need to be used as data values in a graph...

[mike_2000_17]

To input all the vertices, you should do it in two steps. First, you input the entire line into a string (using std::getline). Then, you put that string into a std::stringstream and you input each individual name using std::getline with the delimiter as ',' character. Like this:

std::string temp_str;
std::getline(std::cin, temp_str);
std::stringstream temp_ss(temp_str);
std::string temp_name;
while( std::getline(temp_ss, temp_name, ',') ) {
  std::cout << "Got name: " << temp_name << std::endl;
};

That should print every vertex name.

For the edges, you should do something similar to get the individual values (name1, name2, weight). You can eliminate the parentheses using the string's functions to find characters:

std::string temp_str;
std::getline(std::cin, temp_str);
// eliminate the parentheses:
temp_str.erase( temp_str.begin(), temp_str.begin() + temp_str.find('(') );
temp_str.erase( temp_str.begin() + temp_str.find(')'), temp_str.end() );
// then, put in string-stream:
std::stringstream temp_ss(temp_str);
std::string name1, name2;
double weight;
std::getline(temp_ss, name1, ',');
std::getline(temp_ss, name2, ',');
temp_ss >> weight;
// print results:
std::cout << "Got first name: " << name1 << std::endl;
std::cout << "Got second name: " << name2 << std::endl;
std::cout << "Got weight: " << weight << std::endl;

which should give you the names and weight of the edges.

Start by getting all that working, and then, worry about constructing the graph for calling the dijkstra algorithm in BGL.

[Jed_1]

alright, so I got both of those snippets implimented, and thank you very much, but in the second snippet, line 4 where you try to remove '(' from the begining, it does not seem to work, also I am still getting the space before the LocationN after the first one, not sure if that needs to be removed to use the data in a graph. output right now:
got name: Location1
got name: Location2
got name: Location3...

got first name: (Location1
got second name: Location2
got weight: 1

[Jed_1]

okay if I make it
tempString.erase( tempString.begin(), tempString.begin() + tempString.find('(') + 1 );
that solves the (Location1 problem

[Jed_1]

so now I need a loop to input those values for the rest of the file.

and I need to input those values into a graph.

just because I think if anyone is willing to read this it will help these are the three diffrent functions this program is supposed to be able to do with this style of input file of any reasonable size.

Level 1: Shortest Paths in a Network [70%]

Consider a data communication network that must route data packets (email or MP3 files, for
example). Such a network consists of routers connected by physical cables or links. A router can act as a source, a destination, or a forwarder of data packets. We can model a network as a graph with each router corresponding to a vertex and the link or physical connection between two routers corresponding to a pair of directed edges between the vertices.
A network that follows the OSPF (Open Shortest Path First) protocol routes packets using
Dijkstra’s shortest path algorithm. The criteria used to compute the weight corresponding to a
link can include the time taken for data transmission, reliability of the link, transmission cost, and available bandwidth. Typically each router has a complete representation of the network graph and associated information available to it.
For the purposes of this project, each link has associated with it the transmission time taken for data to get from the vertex at one end to the vertex at the other end. You will compute the best path using the criterion of minimizing the total time taken for data to reach the destination. The shortest time path minimizes the sum of the transmission times of the links along the path. The network topology can change dynamically based on the state of the links and the routers. For example, a link may go down when the corresponding cable is cut, and a vertex may go down when the corresponding router crashes. In addition to these transient changes, changes to a network occur when a link is added or removed.

Level 2: Minimum Spanning Tree Problem [85%]
Suppose we have a group of islands that we wish to link with bridges so that it is possible to travel from one island to any other in the group. Further suppose that (as usual) our government wishes to spend the absolute minimum amount on this project (because other factors like the cost of using, maintaining, etc, these bridges will probably be the responsibility of some future government). The engineers are able to produce a cost for a bridge linking each possible pair of islands. The set of bridges which will enable one to travel from any island to any other at minimum capital cost to the government is the minimum spanning tree.

Level 3: Travelling Salesman Problem [100%]
In this project you will solve the Traveling Salesman Problem using A* search algorithm with Minimum Spanning Tree heuristic.

The TSP problem is defined as follows: Given a set of cities and distances between every pair of cities, find the shortest way of visiting all the cities exactly once and returning to the starting city. You can imagine the cities as nodes in a completely connected graph and distances as edge cost between the cities. Now the problem is transformed to finding the shortest tour of the graph. This is a well known NP-Complete problem and there are many different heuristics available to obtain approximate solutions.
Program Specifications
Interface

You should write a console based interface that will read an input file containing graph information. Your program should present a menu option for each of the levels described above (along with a quit option) that you have implemented. If menu option 1 is chosen, your program must also prompt the user to enter the beginning and ending vertex for the desired path. Once the menu selection is made, console output should be provided and the user should be returned to the menu. This process should continue until the user chooses to quit the program.

[Jed_1]

current code:

#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>

int main() {
    char punc;
    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;
    }

    std::getline(fin, tempString); //Vertices:
    std::getline(fin, tempString); //Location1, Location2, ...
    std::stringstream tempSS(tempString);
    while (std::getline(tempSS,tempName1, ',')){
        //replace with what I need to do with the vertex names
        std::cout << "got name: " << tempName1 << std::endl;
    }
    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::getline(temp_ss, tempName2, ',');
        temp_ss >> weight;
        //replace with what I need to do with the edges
        std::cout << "Got first name: " << tempName1 << std::endl;
        std::cout << "Got second name: " << tempName2 << std::endl;
        std::cout << "Got weight: " << weight << std::endl;
    }


    std::system("pause");
}

and current output is that I am visiting all the data I need in the file, jsut need to know how to use it to build a graph, which honestly I am totally lost on.

[Jed_1]

soo it seems the way to build a graph to add things to is:

    typedef float Weight;
    typedef boost::property<boost::edge_weight_t, Weight> WeightProperty;
    typedef boost::property<boost::vertex_name_t, std::string> NameProperty;
    typedef boost::property<boost::vertex_index_t, int> IndexProperty;
    typedef boost::adjacency_list < boost::listS, boost::listS, boost::directedS,
    NameProperty, WeightProperty > Graph;
    typedef boost::graph_traits < Graph >::vertex_descriptor Vertex;
    typedef boost::graph_traits <Graph>::vertex_iterator Viter;
    typedef boost::property_map < Graph, boost::vertex_index_t >::type IndexMap;
    typedef boost::property_map < Graph, boost::vertex_name_t >::type NameMap;
    typedef boost::iterator_property_map < Vertex*, IndexMap, Vertex, Vertex& > PredecessorMap;
    typedef boost::iterator_property_map < Weight*, IndexMap, Weight, Weight& > DistanceMap;
    Graph g;

[Jed_1]

so I tried to make const char* vertices[9999];
so I can just fill in the diffrent spots in the array with the tempName1 I generale in the while loop with vertices[i] = tempName1; i++; but that doesn't work because strings are not chars? I'm really lost at how to do this...

[Jed_1]

I made the menu to decide which of the three allgorithums is to be run:

    char x;
    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:
            shortestPath();
            break;
        case 2:
            spanningTree();
            break;
        case 3:
            traSales();
            break;
        case 'q':
            case 'Q':
                return EXIT_SUCCESS;
                break;
            default :
                goto returnQuestion;
    }

now I'm back to being stuck at taking the strings and forming a graph.

[Jed_1]

I guess I'll make a new thread since I have all new problems now.

[mike_2000_17]

I don't recommend that you use the old-style boost::property properties for your vertices and edges. You should use bundled properties instead. To run the Dijkstra algorithm, you will need properties for "predecessor", "distance", "weight" (for edges), "index", and "color". So, you could use the following structs for the vertices and edges:

typedef boost::adjacency_list_traits<
  boost::vecS, boost::vecS, boost::undirectedS, boost::listS> GraphTraits;
typedef GraphTraits::vertex_descriptor Vertex;

struct VertexProperty {
  std::string name;
  Vertex predecessor;
  double distance;
  boost::default_color_type color;

  VertexProperty(const std::string& aName = "") : name(aName) { };
};

struct EdgeProperty {
  double weight;

  EdgeProperty(double aWeight = 0.0) : weight(aWeight) { };
};

As for the "index" map, you can use the identity-map because the vertex descriptors of a graph that uses vecS for VertexListS argument will be the same as the vertex index.

The last piece of the puzzle is the dijkstra visitor class. For a simple "do nothing" visitor, you can use this one:

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 { };
};

At this point, you can also declare your graph as:

typedef boost::adjacency_list<boost::vecS, boost::vecS, boost::undirectedS, VertexProperty, EdgeProperty> Graph;

Graph g;

And, when you have filled up the graph with vertices and edges, you can invoke the dijkstra algorithm as so:

dijkstra_shortest_paths(
  g, start_vertex, 
  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));

where start_vertex would be the vertex in the graph with respect to which you wish to solve the problem. When this function returns, you can take any vertex in the graph and follow its "predecessors" until you reach the start_vertex and that path will be the shortest path between that chosen vertex and the start-vertex.

As far as filling the graph, this is just a matter of turning your "printing all vertices" loop into a loop that repeatidly calls add_vertex on the graph, i.e., add_vertex(VertexProperty(name), g). And similarly for the edges (with add_edge(u,v,g)), which is a bit harder because you need to find the vertices by name, and for that, I suggests using a std::map<std::string, Vertex> to associate the names of the vertices to their Vertex descriptor in the graph.

That should give you plenty enough hints on how to do this. You might also check out this little collection of BGL examples.

[Jed_1]

oh thank god you responded.

I looked through that collection a little bit when I started this project, but thank you for re-finding it for me.

"add_edge(u,v,g)), which is a bit harder because you need to find the vertices by name, and for that, I suggests using a std::map<std::string, Vertex> to associate the names of the vertices to their Vertex descriptor in the graph."

is pretty confusing for me, because add_edge does not seem to be a thing according to my code right now, lists it as undefined.

[Jed_1]

I've tryied a few ways to type add_edge(tempName1,tempName2,weight); using EdgeProperty and all of them say add_edge is not a thing...

[Jed_1]

#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;
typedef GraphTraits::vertex_descriptor Vertex;

struct VertexProperty {
    std::string name;
    Vertex predecessor;
    double distance;
    boost::default_color_type color;
    VertexProperty(const std::string& aName = "") : name(aName) { };
};

struct EdgeProperty {
    double weight;
    EdgeProperty(double aWeight = 0.0) : weight(aWeight) { };
};

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;

    typedef boost::adjacency_list<boost::vecS, boost::vecS, boost::undirectedS, VertexProperty, EdgeProperty> Graph;
    Graph g;

    // 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;
    }

    std::getline(fin, tempString); //Vertices:
    std::getline(fin, tempString); //Location1, Location2, ...
    std::stringstream tempSS(tempString);
    while (std::getline(tempSS,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::getline(temp_ss, tempName2, ',');
        temp_ss >> weight;
        add_edge(EdgeProperty(tempName1,tempName2,weight), g);

    }

    char x;
    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 << "please enter the node ";


        dijkstra_shortest_paths(
            g, start_vertex, 
            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));
        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");
}

problem at line 85, where add_edge seems to not be a thing.
problem at line 104, where I need to deal with start_vertex.

[Jed_1]

http://programmingexamples.net/wiki/CPP/Boost/BGL/DijkstraComputePath

following this example

    std::stringstream temp_ss(tempString);
    std::getline(temp_ss, tempName1, ',');
    std::getline(temp_ss, tempName2, ',');
    temp_ss >> weight;
    add_edge(tempName1,tempName2,weight, g);

should work, but it says add_edge is undefined anyway I try to use Edge Property like you showed me for vertex, and as it is right here it tells me add_edge does not match the argument list.

[mike_2000_17]

The problem with add_edge(tempName1, tempName2, weight, g); is that the strings tempName1 and tempName2 are not vertex descriptors and weight is not an edge-property. These two problems make it so that the compiler does not find a function like that one (that takes two strings and a double).

The edge-property part is easy to solve, just do EdgeProperty(weight) instead of just weight.

The other problem is a bit harder (as I tried to explain earlier). The problem here is that you cannot refer to vertices by their name, you need to refer to them by vertex-descriptors (i.e., the Vertex type in your code), which is what the BGL uses to identify vertices of a graph (these are actually indices or pointers to a vertex, but that's not important). When you do add_vertex, it returns a vertex-descriptor to the newly created vertex. You need to record all those vertex-descriptors and associate them with the correct name. For that, just use a std::map<std::string, Vertex>. Then, all you'll have to do to create the edges is to retrieve, through that map, the vertex-descriptors corresponding to the names tempName1 and tempName2.

[Jed_1]

I really want to thank you, and I feel I should give you some context.
this is my first class using c++ and we are not being taught c++, it's a data structure and algorithm class. so all of the c++ I've learned has been self taught. my teacher then told us Thursday we need to use boost to do this project, which is due Sunday. I have very little idea what I'm doing for sytex already, so adding boost into the equation is making this a little hard on me.

it's not that I'm trying to get you to write my code for me, it's that I have little to no idea what I'm doing. (I've been told this is a senior level project and it's only my third programing class, the other two were in java)

I know what I want the program to do more or less, but I have no idea the sytex of it. through other programs using Dijkstra’s with boost I've amassed this list of typedef lines that I thought I might need:

typedef double Weight;
typedef boost::adjacency_list_traits<
    boost::vecS, boost::vecS, boost::undirectedS, boost::listS> GraphTraits;
typedef GraphTraits::vertex_descriptor Vertex;
typedef boost::property<boost::edge_weight_t, Weight> WeightProperty;
typedef boost::property<boost::vertex_name_t, std::string> NameProperty;
typedef boost::property_map < Graph, boost::vertex_index_t >::type IndexMap;
typedef boost::property_map < Graph, boost::vertex_name_t >::type NameMap;
typedef boost::adjacency_list<boost::vecS, boost::vecS, boost::undirectedS, VertexProperty, EdgeProperty> Graph;
Graph g;
typedef boost::iterator_property_map < Vertex*, IndexMap, Vertex, Vertex& > PredecessorMap;
typedef boost::iterator_property_map < Weight*, IndexMap, Weight, Weight& > DistanceMap;

so I assume the NameMap needs to have information added to it when I am doing my add_vertex while loop so I added a NameMap(tempName1); line to it, and no sytex error, so leaving that for now, I tried to do:
add_edge(NameMap(tempName1),NameMap(tempName2),EdgeProperty(weight), g);
but add_edge didn't like NameMap, and tempName1 and 2 did not like being called into NameMap there either.

I am trying things, every time you respond to my post I spend a good hour trying to figure it out, I'm not just waiting for you to write it.

I'm starting to feel like I'm being anoying or something, but there is not much I can do, the example code I can find doesn't have to deal with the sytex of having a text input file. The code I can find that uses Dijkstra’s and an input file uses .gr files that are already in the right format. so it's the syntex of how to use these varibles now that I've gotten them from the files that confuses me.

[Jed_1]

I've seen other people who are not using input files use an array for the weight, and a pair<string,string> for the location1,location2 and make an edge with that, is that the type of thing I need to do. I know I need to name the vertex that I make like:
Vertex tempVertex = add_vertex(VertexProperty(tempName1), g);
so that I can go back to it, but you can't increment the name in a loop or anything to get back to it, so I have to map it while in the loop so I can search for it again and get the information back out? I'm not really sure, I just know making it so this program can handle any size set is making this step overly hard.

[mike_2000_17]

Alright, I feel generous today. Here's the code for the part that constructs 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, ',')){
    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::getline(temp_ss, tempName2, ',');
    temp_ss >> weight;
    add_edge(name2v[tempName1], name2v[tempName2], EdgeProperty(weight), g);
}

That's it.

[Jed_1]

Thank you again! I'll do my best to take it from here. I'm sure now that I can get a graph built I can look up how to use it for the desired results.

I was under the impression there was no way to name things created in loops uniquely, I'll be sure to remeber this in all my coding from now on!

[Jed_1]

current number of errors: 28
line 18: 5 errors
typedef boost::property_map < Graph, boost::vertex_index_t >::type IndexMap;
'Graph' undeclared identifier
line 19: 6 errors
typedef boost::property_map < Graph, boost::vertex_name_t >::type NameMap;
'Graph' undeclared identifier
line 20: 4 errors
typedef boost::adjacency_list<boost::vecS, boost::vecS, boost::undirectedS, VertexProperty, EdgeProperty> Graph;
lines 22,23,26,27,28,87,99

std::vector<Vertex> predecessors(boost::num_vertices(g)); // To store parents
  std::vector<Weight> distances(boost::num_vertices(g)); // To store distances
  IndexMap indexMap = boost::get(boost::vertex_index, g);
    PredecessorMap predecessorMap(&predecessors[0], indexMap);
  DistanceMap distanceMap(&distances[0], indexMap);

'IndexMap' is not a valid template type argument for parameter 'IndexMap'
'VertexProperty' is not a valid template type argument for parameter 'VertexProperty'
'EdgeProperty' is not a valid template type argument for parameter 'EdgeProperty'

and I get errors where I used name2v[tempName1]
name2v[tempName1] = add_vertex(VertexProperty(tempName1), g);
cannot convert parameter 1 from 'VertexProperty' to 'const int&'
add_edge(name2v[tempName1],name2v[tempName2],EdgeProperty(weight), g);
none of the 2 overlaods could convert all the argument types
I made the classic new programer mistake of editing my code a lot without compiling inbetween...

[Jed_1]

changed the order of what is called when, so I tell it what graph is before I use graph to make index map and things like that.

down to 10 errors

[Jed_1]

changed the order a few more times and cleared up those errors, down to only two left and those are concerning...
error in adjacency_list.hpp line 2539 error c2182: 'reference' :illegal use of the type 'void'
error in adjacency_list.hpp line 2540 error c2182: 'const_reference' :illegal use of the type 'void'

[Jed_1]

in looking online, "The actual error is not in the Boost header, it's how you use Boost. Somewhere you use the dereference operator on a Boost smart pointer which has the type void"

so I have huge problem, in that I have no idea where these errors occured.

[Jed_1]

I commented things out until I found where the errors were:

typedef boost::property_map < Graph, boost::vertex_index_t >::type IndexMap;
typedef boost::property_map < Graph, boost::vertex_name_t >::type NameMap;

seem to be the issue

[Jed_1]

someone posted online that it was the way the graph is built, so I went from using typedef boost::adjacency_list<boost::vecS, boost::vecS, boost::undirectedS, VertexProperty, EdgeProperty> Graph; to thier sugested fix of:

typedef boost::adjacency_list <boost::listS, boost::listS, boost::directedS,
  boost::property<boost::vertex_name_t, std::string, boost::property<boost::vertex_index_t, int> >,
  boost::property<boost::edge_weight_t, Weight> > Graph;

and that caused more errors...

[Jed_1]

totally removed them and now I just have to impliment the

dijkstra_shortest_paths(
            g, name2v[tempName1], 
            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));

function you provided me.
which complies and runs, but I am not real sure what I need to cout after it runs to display the data...

[mike_2000_17]

After having called dijkstra the function, you should be able to just walk through the graph via the predecessor records. Something like this:

std::string start_name;
std::cout << "Enter start location: ";
std::cin >> start_name;
std::cout << "The shortest path is:" << std::endl;
Vertex cur_v = name2v[start_name];
while( cur_v != name2v[tempName1] ) {
  std::cout << g[cur_v].name << std::endl;
  cur_v = g[cur_v].predecessor;
};
std::cout << g[cur_v].name << std::endl;

That should print the sequence of location names between the given start-point and the goal point (which is the one passed to the dijkstra function, i.e., name2v[tempName1]).