Route problem

[GRH]

There's an array of structs, containing the different routes between each points. For example:
http://img693.imageshack.us/img693/9682/96931372.png

Now what my program should do is, when a user inputs his starting position and the desired ending position, all possible ways are shown. For example if he starts at F and wants to go to E, then the following is shown:

//here was my previous code, look below for my new code please 

[lloydchristmas759]

I did not try to understand everything in your program, but it seems that points_visited is always 0, which you probably don't want.

In addition, a few general comments:

- Your functions all take a C-style array of Route as one of their argument, but the size of the array is a global variable. This is not a good practice; you should always give the size of the array together with the array as a separate argument. It is not a real problem in your program, but it could become one when you'll write larger programs.

- When you want to check if two std::string are the same, you should use the == operator instead of compare(), it will make your code more readable.

[GRH]

Thanks for the tips, I'll try to do that in the future.
I tried setting the points_visited to increase on each search but that doesn't help also, sigh.

[GRH]

Tried a few things but I kept running into errors so I'm back to before again.
Anyone?

[Disch]

This would be easier to follow if you outlined your logic.

One thing that is confusing me is swap_route. What is the goal of this function? It looks like when you call it you are just totally scrambling your map, which could make it impossible to find routes. I suspect this is what your problem is, but I can't say for sure because I don't quite fully understand your approach.

Can you give an overview of how this code is supposed to work? Like describe what each function is supposed to do and how that plays a role in finding the desired route. That will make it a lot easier to find the flaws in the code.

[GRH]

Ok, first the user inputs his starting position and desired finishing position.
Then it will search each route for the starting position, so that in each direction will be searched
The swap function makes sure the routes are in the correct direction, because there is only 1 route that can be travelled in both ways.

[Disch]

Then it will search each route for the starting position, so that in each direction will be searched

Well I figured this much. But HOW does it do that?

The swap function makes sure the routes are in the correct direction, because there is only 1 route that can be travelled in both ways.

Huh?

Lemme put it this way. Here's a problem I see:

Say you have the following map:

A
|
B-C
| |
+-D

And you need to find the routes from D to A. Now when you call your swap route function to swap B and D, you're left with this:

A
|
D-C
| |
+-B

IE: you changed the map. So now even if you find the D-B-A route correctly, it'll be impossible to find the D-C-A route because you scrambled your map all up.

[GRH]

omg, you're right

Argh, my code is just crap

[Disch]

Recursion might be a good approach to this problem.

Think of it this way. In order to find the route, you start at a point and look at all surrounding points. From there, the next step is to look at all surrounding points of that point, and so on until you reach the end.

If you can write a single function to take one step in the route, you can use recursion to check for entire paths.

You can also use a vector to keep track of the path so that you can print it / report it to the user once the path is found. I don't know how you're recording the path in your above code.

Here's some pseudo code to give you an idea:

void find_route(
   std::vector< Point >& path, // the path/route we are currenly examining
   const Point& endpoint // the desired end point
   )
{
  // the last point in the path is the one we're currently standing on.
  Point& currentpoint = path.back();

  // if the current point is the end point, we have a complete path!
  if(currentpoint == endpoint)
  {
    // full path found.
    // either print this path here, or make a copy of the path so that it can be printed later
  }
  else
  {
    // we didn't find the end point yet

    // check to make sure 'currentpoint' is in the path only once.  If it's in the path more than once
    //   we're going in circles and not finding a path
    for(unsigned i = 0; i < path.size() - 1; ++i)
    {
      if( path[i] == currentpoint )  // we already were at the current point
        return;            // so stop searching this path
    }

    // take a step to all neighboring points
    for( __each neighbor of currentpoint__ )
    {
      path.push_back( __neighboringpoint__ );
      find_route( path, endpoint );  // recursively call this function to continue searching this path
      path.pop_back();
    }
  }
}

[GRH]

I still can't get it to work, vectors we cannot use and I don't understand what push_back etc means. It has something to do with vectors? Is there a way to do it with string arrays?

[gcampton]

it's pseudo code, just read the comments and fill in the blanks.


push and pop basically refer to the stack, say we have a stack of cards that looks like this:

A
K
Q
J
7

Thats our stack, the stack works as "Last in, first out" so if we were to 'push' something onto the stack say a 4.

4
A
K
Q
J
7
now that's our current stack, if we let the stack now resolve itself or choose to 'pop' off the stack the top always comes off first, so "last on, first off" it could also be called. This is the basic idea behind recursion. So now lets pop 4 items off the stack, 4 pops off, A pops off, K pops off, Q pops off and we are left with

J
7

When we recursively call something, a function it works in the same way.

eg.

int multiply(int x, int y)
{
   if (y == 0)
      return 0;
   else if (y == 1)
      return x;
   else 
      return x + multiply(x, y-1);
)

note in my example I don't use push or pop, but it's still recursion. Method calls automatically push onto the stack frame, and pop off when they resolve.

[GRH]

But I'm confused to make it work without vectors. I just have a struct array like this:

Route routes [ Total_routes ] =
    { { "F", "I", 20 }, { "F", "B", 45 }, { "H", "C", 25 },
      { "B", "E", 50 }, { "I", "E", 60 }, { "F", "C", 60 },
      { "H", "G", 50 }, { "B", "G", 30 },
      { "H", "D", 45 }, { "A", "E", 40 } } ;

[gcampton]

find_route( path, endpoint ) {
  Route routes [ Total_routes ] =
    { { "F", "I", 20 }, { "F", "B", 45 }, { "H", "C", 25 },
      { "B", "E", 50 }, { "I", "E", 60 }, { "F", "C", 60 },
      { "H", "G", 50 }, { "B", "G", 30 },
      { "H", "D", 45 }, { "A", "E", 40 } } ;  // the path/route we are currently examining

   // the desired end point
  some_value;

  // the last point in the path is the one we're currently standing on.
  bool been_there ( string point , Route temp_routes[] )

  // if the current point is the end point, we have a complete path!
    if(currentpoint == endpoint)
    {
      // full path found.
      // either print this path here, or make a copy of the path so that it can be printed later
    }
    else
    {
      // we didn't find the end point yet

      // check to make sure 'currentpoint' is in the path only once.  If it's in the path more than once
      bool been_there ( string point , Route temp_routes[] ) 
      //   we're going in circles and not finding a path


      // take a step to all neighboring points
      for( __each neighbor of currentpoint__ )
      {
           find_route( path, endpoint );  // recursively call this function to continue searching this path
      }
}

I'm sorry I can't be more help with this as I am still not familiar with structs / points etc.
But the logic Disch posted looks fine to me (even better than fine, I can almost see the end result), being that you wrote the original code it shouldn't be too difficult for you.

[GRH]

Ok I started over to get a clean view, here's what I have now:

#include <iostream>
#include <string>
#include <iomanip>

using namespace std;

struct Route
{
    string   from;
    string   to;
    int       distance;
};

const int Total_routes = 10;

Route routes [ Total_routes ] =
    { { "F", "I", 20 }, { "F", "B", 45 }, { "H", "C", 25 },
      { "B", "E", 50 }, { "I", "E", 60 }, { "F", "C", 60 },
      { "H", "G", 50 }, { "B", "G", 30 },
      { "H", "D", 45 }, { "A", "E", 40 } } ;

int adjacency ( string point , Route routes[] )
{
    int adjacency = 0;
    for ( int c ( 0 ) ; c < Total_routes ; c++ )
    {
        if ( ( routes[c].from.compare(point) == 0 ) || ( routes[c].to.compare(point) == 0 ) )
        {
            adjacency++;
        }
    }
    return adjacency;
}

void find_adjacent_points ( string point , Route routes[] , string adjacent_points[] )
{
    int x = 0;
    for ( int z ( 0 ) ; z < Total_routes ; z++ )
    {
        if ( routes[z].from.compare(point) == 0 )
        {
            adjacent_points[x] = routes[z].to;
            x++;
        }
        if ( routes[z].to.compare(point) == 0 )
        {
            adjacent_points[x] = routes[z].from;
            x++;
        }
    }
}

void find_route( string currpoint , string finishpoint , Route routes[] , string temp_routes[] , int& points_visited )
{
    temp_routes[points_visited] = currpoint;
    points_visited++;
    if (currpoint.compare(finishpoint)==0)
    {
        cout << "route found" << endl;
    }
    else
    {
        string adjacent_points[10];
        for ( int i ( 0 ) ; i < points_visited-1 ; i++ )
        {
            if ( temp_routes[i] == currpoint )
            {
                return;
            }
        }
        find_adjacent_points ( currpoint , routes , adjacent_points );
        for ( int r ( 0 ) ; r < (adjacency(currpoint,routes)) ; r++ )
        {
            int temp_points_visited = points_visited;
            find_route( adjacent_points[r] , finishpoint , routes , temp_routes , points_visited );
            for ( int e ( temp_points_visited ) ; e < points_visited ; e++ )
            {
                temp_routes[e] = " ";
            }
            points_visited = temp_points_visited;
        }
    }
}

void travel ( Route routes[] , string temp_routes[] )
{
    int points_visited ( 0 );
    string startstr, finishstr;
    cout << "Input starting point: ";
    getline(cin,startstr);
    cout << "Input finishing point: ";
    getline(cin,finishstr);
    if ( startstr == finishstr )
    {
        cout << "You're already there!" << endl;
    }
    else
    {
        for ( int g ( 0 ) ; g <= ((adjacency(startstr,routes))-1) ; g++ )
        {
            find_route ( startstr , finishstr , routes , temp_routes , points_visited );
        }
    }
}

bool cont ()
{
    string answ;
    cout << "Try a new route? <Y/N> : ";
    getline(cin,answ);
    cout << endl;
    if ( answ == "Y" )
    {
        return true;
    }
    else
    {
        return false;
    }
}

int main ()
{
    string temp_routes[50];
    while ( cont() )
    {
        travel (routes,temp_routes);
    }
    return 0 ;
}

Is it better? I'm not sure it works...

[blackcoder41]

if i were to solve this i would make a struct something like this and make a recursive function searching each direction

struct Node {
    char    VALUE;
    //set the pointer to null to end a path.
    //ie. B cant go west to WEST = 0;
    Node *  NORTH;
    Node *  SOUTH;
    Node *  EAST;
    Node *  WEST;
    
    //distance
    int n;
    int s;
    int e;
    int w;
};

for example F to I. then the program check the four direction starting from F and assume to check north, south, east, west respectively so that means checking the letters I, C and B respectively since east pointer is null.

then get the distance traveled and record where it go for later printing the path. it stops after finding the right path or else recursively do the same process for example:

starting from F, it then goto north which is I, so then you've found 1 path.

now goto south, which is C, now from C it should go north right? but we should exclude it because that's where you came from so proceed to south of C which is H.

now H cant go north and south right? it goes east w/c is G. and so on.

G -> B
B -> E
E -> A dead end so
E -> I yehey i've found the way home

and please be easy on my english.

[GRH]

Hmm yes, but I can't change the struct because it's for homework. Too bad :(

[blackcoder41]

struct Route
{
    string   from;
    string   to;
    int       distance;
};

is that the struct that you can't change, well you dont have to just add the stuct i told you to and use the given struct (required) to keep track of the travel. like from A to B distance 50 something like that

trust me.

[GRH]

Can't it be done with just the struct(+code) I have? I have followed Disch's pseudo code but it just gets wrong results.. for example when I try from A->E or D->H (which are both next to eachother) it gives me the correct answer: one path.
When I try D->C it also gives me a correct answer, three paths.
But when I try D->A it says it has found 4 paths, when there are only 3 possible paths.
And I->A will produce 6 paths, when there are only 3.


A problem for later would be to show the followed path and the distance travelled, but right now I'm still confused about the above problem.

[blackcoder41]

the answers are just as expected. look closely, sometimes computers are indeed smarter if programmed correctly in this case i think the answers is just correct.

[GRH]

Well yes the computer is obviously "correct", but it's not correct in the sense that it's not the answer I'm looking for aka my programming is incorrect. But I could use some help to figure out what exactly is wrong..

I think I should clear the temp_routes[] array when a path is found, because otherwise it will run across a point which has already been visited on a previous search and stop. But I can't clear it all the way, or else it will go on endlessly.

Ok, I've updated the code above. I've added a line which (hopefully) solves the clearing of the array problem. Still running some tests to see if it has worked :)
Now, on to the next problem: displaying the travelled path. How could I best do that?