1 Replies - 142 Views - Last Post: 04 December 2017 - 04:25 AM Rate Topic: -----

#1 1girl2pups  Icon User is offline

  • New D.I.C Head

Reputation: 0
  • View blog
  • Posts: 7
  • Joined: 25-August 17

Segmentation Fault. C++ Floyd Warshall homework

Posted 04 December 2017 - 12:14 AM

The homework is to figure out the shortest path between two train stations using the Floyd Warshall algorithm, and I think I've got it mostly figured out, but I've got this segmentation fault occurring at
void Graph::setColors(int ID, string colors){
    _colors[ID] = colors;
}


the error message the pops up says this:

#0 0x45b6f4 std::string::assign(std::string const&) () (??:??)
#1 0x1b4 ?? () (??:??)
#2 0x4298e8 pthread_getspecific () (??:??)
#3 0x404336 std::basic_istream<char, std::char_traits<char> >& std::operator>><char, std::char_traits<char>, std::allocator<char> >(std::basic_istream<char, std::char_traits<char> >&, std::basic_string<char, std::char_traits<char>, std::allocator<char> >&) () (??:??)
#4 0x8 ?? () (??:??)

but I don't understand what that means.

I would really appreciate it if someone could show me what this is about. Thanks!

#include <iostream>
#include <queue>
#include <fstream>
#include <string>


using namespace std;

class Graph{
private:
    int _routes;
    int _stations;
public:
    int _adjMatrix[100][100];

    int _fwMatrix[100][100];
    string *_colors;

    Graph(int, int);
    void addRoute(int, int, int);
    void printAdjMatrix(void);
    bool isRoute(int, int);
    void calcShortestRoutes(void);
    int shortestRoute(string, string);
    int getStationID(string);
    string getColors(int);
    void setColors(int, string);
};

Graph::Graph(int routes, int stations){
    _colors = new string[stations];
    _routes = routes;
    _stations = stations;

    for(int i = 0; i < stations; i++){
        for(int j = 0; j < stations; j++){
            _adjMatrix[i][j] = 0;
        }
    }

    for( int i = 0; i < stations; i++){
        for( int j = 0; j < stations; j++){
            _fwMatrix[i][j] = 99;
        }
    }
}

void Graph::printAdjMatrix(void){
    for(int i = 0; i < _stations; i++){
        cout << i << " : ";
        for(int j = 0; j < _stations; j++){
            cout << _adjMatrix[i][j] << " -> ";
        }
        cout << " NULL " << endl;
    }

    cout<< "--FW MATRIX--" << endl;
    for( int i = 0; i < _stations; i++){
        cout << i << " : ";
        for( int j = 0; j < _stations; j++){
            cout << _fwMatrix[i][j] << " -> ";
        }
        cout << "NULL" << endl;
    }
}

void Graph::addRoute(int from, int to, int weight){
    _adjMatrix[from][to] = weight;

    _fwMatrix[from][to] = weight;
}

bool Graph::isRoute(int from, int to){
    bool isRoute = false;
    bool visited[_stations] = {false};
    queue<int> vertices;

    visited[from] = true;
    vertices.push(from);

    cout << "Checking from " << from << " to " << to << endl;

    while(!vertices.empty() && isRoute == false ){
        int current;
        current = vertices.front();
        vertices.pop();

        for ( int temp = 0; temp < _stations ; temp++ ){
            if (_adjMatrix[current][temp] != 0){
                if (temp == to){
                    isRoute = true;
                    break;
                }
                if ( visited[temp] == false){
                    visited[temp] = true;
                    vertices.push(temp);
                }
            }
        }
    }
    return isRoute;
}

void Graph::calcShortestRoutes(void){

    for( int i = 0; i < _stations; i++){
        for( int j = 0; j < _stations; j++){
            for(int k = 0; k < _stations; k++){
                if(_fwMatrix[j][k] > _fwMatrix[j][i] + _fwMatrix[i][k]){
                    _fwMatrix[j][k] = _fwMatrix[j][i] + _fwMatrix[k][j];
                }
            }
        }
    }
}

int Graph::shortestRoute(string src, string dst){
    int i = getStationID(src);
    int j = getStationID(dst);

    return _fwMatrix[i][j];
}

int Graph::getStationID(string colors){
    int ID = 0;

    for(int i = 0; i < _stations; i++){
        if(_colors[i] == colors){
            return ID;
        }
        if(ID < _stations){
            ID++;
        }
    }
}

string Graph::getColors(int ID){
    return _colors[ID];
}

void Graph::setColors(int ID, string colors){ 
    _colors[ID] = colors;               // SEGMENTATION FAULT HERE
}

int main()
{
    ifstream myFile;
    myFile.open("trains.txt");

    int a, b, c, num;
    int choice = 1;
    string color;

    myFile >> a >> b;

    Graph myGraph = Graph(a, B)/>/>/>;

    while( myFile >> a >> b >> c ){
        myGraph.addRoute(a, b, c);
    }

    ifstream myFile2;
    myFile2.open("stations.txt");

    while( myFile2 >> num >> color ){
        myGraph.setColors(num, color);
    }

    myGraph.calcShortestRoutes();

    while(choice == 1){
        cout << "-- Menu --"<< endl;

        cout << "   0 => Exit" << endl;
        cout << "   1 => Print Menu" << endl;
        cout << "   2 => Check if path exists" << endl;
        cout << "   Choice: ";

        cin >> choice;

        if( choice == 0 ){
            break;
        }

        if( choice == 2 ){
            string source;
            string destination;

            cout << endl;
            cout << "From what station are you leaving? ";
            cin >> source;

            cout << "To what station are you traveling? ";
            cin >> destination;

            int i = myGraph.getStationID(source);
            int j = myGraph.getStationID(destination);

            if( myGraph.isRoute(i,j)){
                int minRoute = myGraph.shortestRoute(source, destination);
                cout << "There is a route between " << source << " and " << destination << " with a minimum distance of " << minRoute << " miles." << endl;
                cout << endl;
                choice = 1;
            }
            else{
                cout << "There is no route between " << source << " and " << destination << endl;
                cout << endl;
                choice = 1;
            }
        }
    }

    return 0;
}



the files used to run the program look like this
trains:
5 6
0 1 7
3 1 10
4 3 12
1 4 12
4 2 32
1 2 3

stations:
0 Red
1 Green
2 Blue
3 Purple
4 Yellow

Is This A Good Question/Topic? 0
  • +

Replies To: Segmentation Fault. C++ Floyd Warshall homework

#2 snoopy11  Icon User is online

  • Engineering ● Software
  • member icon

Reputation: 1414
  • View blog
  • Posts: 4,493
  • Joined: 20-March 10

Re: Segmentation Fault. C++ Floyd Warshall homework

Posted 04 December 2017 - 04:25 AM

Line 75 you have this

bool visited[_stations] = {false};



but _stations needs to be either a constant expression or you could do this.

bool* visited = new bool[_stations];
	for(int i =0; i <_stations; i++)
	visited[i] = false;


with a delete[] before your return value like this....

	delete[] visited;
	return isRoute;
}




Line 135 not all control paths return a value even though the function is int ie int Graph::getStationID(string colors)

returning minus one at the end of the function for failure then checking later on the return value would be sensible here, which brings us onto error checking in general each time you get an input from the user you should decide if this is a valid answer, right now there is no error checking of any kind in your program and this needs to be addressed.
Was This Post Helpful? 0
  • +
  • -

Page 1 of 1