Problem with function implementation (recursive)

Question

The purpose of the program is to list all the possible paths that a person can take to get from station A to station L via the metro system without crossing the track more than once. I know that there are 640 possible ways, as the instructor told us, and we wrote this program as an earlier assignment in C using the adjacency matrix. Now the goal is to do the same thing as listing all the possible routes and printing each route, except to do it using classes (3 specifically: SubwaySystem, Station and Track) WITHOUT using a matrix this time. Here is a schematic representation of the metro system itself.

I had a discussion with my TP about this program and how to approach it. He gave me some ideas, such as using arrays to represent stations and tracks, and I decided to use the approach that I showed throughout the code at the bottom of the post.

Let me show you the problem areas of my code that I could not solve (recursion is new for me).

 void SubwaySystem::SearchRoute(int Current_Station_ID)
{
        if(my_station[Current_Station_ID].track_starting_ID == 33)  // Find a successful route to Station L.
//The condition is set to check for 33 because a track_starting_ID of 33 would correspond to station L.
        {
            count_routes++; //Add 1 into the variable "count_routes"
            cout << count_routes << " " << my_track[Current_Station_ID] << endl; //Print out this route
            return;
        }
        else //Get into recursive Function Body
        {
            for(int i = my_station[Current_Station_ID].track_starting_ID; i < my_station[Current_Station_ID].track_starting_ID + my_station[Current_Station_ID].track_size; i++)
            {
                if(my_track[Current_Station_ID].visited == 0)  //if this track is not visited before
                {
                    my_track[Current_Station_ID].visited = 1; //mark this track as visited
                    my_track[Current_Station_ID].node_2 = 1; //mark its corresponding track as visited
                    cout << my_track[Current_Station_ID].node_1; //save this track
                    SearchRoute(Current_Station_ID++); //Recursive
                    i--; //Backtrack this track
                    my_track[Current_Station_ID].visited = 0;//mark this track as unvisited
                    my_track[Current_Station_ID].node_2 = 0;//mark its corresponding track as unvisited
                }
            }
        }
    }
}

, :
Current_Station_ID - , i.
my_station - 12, 12 .
my_track - 34, .
track_starting_ID , my_track. , , . , , SubwaySystem . , track_starting_ID , . _ID 0 my_track [0], , "A", _ID 1 my_track (1), , "B". _ID 6 , "C" my_track [6]. . (, , ).
track_size , , . , B 5, 5 B.
_1 _2. visited - , , , - .

, , . , , . , , , , :

SearchRoute(int Current_Station_ID)
{ 
     if ( ) //Find a successful route to Station L 
     { 
         … //Add 1 into the variable "count_routes" 
         … //Print out this route 
         return; 
     } 
     else //Get into recursive Function Body 
     { 
         //Use the track array to get all of its connected stations 
         for(int i = starting_ID; i < starting_ID + current size; i++) 
         { 
             if() // if this track is not visited before 
             { 
                 … //mark this track as visited 
                 … //mark its corresponding track as visited 
                 … //save this track 
                 SearchRoute( nextStaton_ID); // Recursive 
                 … //Backtrack this track 
                 … //mark this track as unvisited 
                 … //mark its corresponding track as unvisited 
             } 
         } 
     } 
} 

, , : SearchRoute, , , , . , , , , , .

, , :

//Function Declarations
#include <iostream>
#include <string>

using namespace std;

#ifndef SUBWAY_H
#define SUBWAY_H

class Track
{
public:
    //Default Constructor
    Track();

    //Overload Constructor
    Track(char, char);

    //Destructor
    ~Track();

    //Member variables
    char node_1;  // node_1 and node_2 represent stations (for example
    char node_2;  // node_1 would be station A and node_2 would be station B)
    bool visited;
};

class Station
{
public:
    //Default Constructor
    Station();

    //Destructor
    ~Station();

    //Overload Constructor
    Station(char, int, int);

    //Member variables
    char station_name;
    int track_starting_ID;
    int track_size;
};

class SubwaySystem
{
public:
    //Default Constructor
    SubwaySystem();

    //Destructor
    ~SubwaySystem();

    //Recursive function
    void SearchRoute(int);

    //Other member functions
    friend ostream& operator<<(ostream& os, const Track& my_track);
    friend ostream& operator<<(ostream& os, const Station& my_station);


    //Member variables
    Track my_track[34];
    Station my_station[12];

    int count_routes;
    int Current_Station_ID;

    //String to save found route
};

#endif

// **cpp**

//Function Definitions
#include <iostream>
#include <string>

//#include "subway.h"

using namespace std;

Track::Track()
{
    visited = 0;
}


Track::~Track()
{
}


Track::Track(char pass_track1, char pass_track2)
{
    node_1 = pass_track1;
    node_2 = pass_track2;
    visited = false;
}


Station::Station()
{
}


Station::~Station()
{
}


Station::Station(char pass_station_name, int pass_start, int pass_size)
{
    station_name = pass_station_name;
    track_starting_ID = pass_start;
    track_size = pass_size;
}


SubwaySystem::SubwaySystem()
{
    //Initialize tracks
    //node_1, node_2
    my_track[0] = Track('a', 'b');
    my_track[1] = Track('b', 'a');
    my_track[2] = Track('b', 'c');
    my_track[3] = Track('b', 'd');
    my_track[4] = Track('b', 'e');
    my_track[5] = Track('b', 'f');
    my_track[6] = Track('c', 'b');
    my_track[7] = Track('c', 'e');
    my_track[8] = Track('d', 'b');
    my_track[9] = Track('d', 'e');
    my_track[10] = Track('e', 'b');
    my_track[11] = Track('e', 'c');
    my_track[12] = Track('e', 'd');
    my_track[13] = Track('e', 'g');
    my_track[14] = Track('e', 'h');
    my_track[15] = Track('f', 'b');
    my_track[16] = Track('f', 'h');
    my_track[17] = Track('g', 'e');
    my_track[18] = Track('g', 'k');
    my_track[19] = Track('h', 'e');
    my_track[20] = Track('h', 'f');
    my_track[21] = Track('h', 'i');
    my_track[22] = Track('h', 'j');
    my_track[23] = Track('h', 'k');
    my_track[24] = Track('i', 'h');
    my_track[25] = Track('i', 'k');
    my_track[26] = Track('j', 'h');
    my_track[27] = Track('j', 'k');
    my_track[28] = Track('k', 'g');
    my_track[29] = Track('k', 'h');
    my_track[30] = Track('k', 'i');
    my_track[31] = Track('k', 'j');
    my_track[32] = Track('k', 'l');
    my_track[33] = Track('l', 'k');
    //Initialize stations
    //station_name, track_starting_ID, track_size
    my_station[0] = Station('a', 0, 1);
    my_station[1] = Station('b', 1, 5);
    my_station[2] = Station('c', 6, 2);
    my_station[3] = Station('d', 8, 2);
    my_station[4] = Station('e', 10, 5);
    my_station[5] = Station('f', 15, 2);
    my_station[6] = Station('g', 17, 2);
    my_station[7] = Station('h', 19, 5);
    my_station[8] = Station('i', 24, 2);
    my_station[9] = Station('j', 26, 2);
    my_station[10] = Station('k', 28, 5);
    my_station[11] = Station('l', 33, 1);
    //Initiaize other members
    count_routes = 0;
    Current_Station_ID = 0;
}


SubwaySystem::~SubwaySystem()
{
}

ostream& operator<<(ostream& os, const Track& my_track)
{
    os << my_track.node_1 << '.' << my_track.node_2;
    return os;
}

ostream& operator<<(ostream& os, const Station& my_station)
{
    os << my_station.station_name << '.' << my_station.track_starting_ID << '.' << my_station.track_size;
    return os;
}


//This is where the above recursive function SearchRoute goes. I posted it separately so it easier to read.



// **main**

#include <iostream>
#include <string>

//#include "subway.h"

using namespace std;

int main()
{
    SubwaySystem findPaths;
    findPaths.SearchRoute(0);
}

Answer 1

, , 605 , , , .

// RandomTest.cpp : Defines the entry point for the console application.
//

#include "stdafx.h"


#include <iostream>
#include <string>
using namespace std;






class Track
{
public:
    //Default Constructor
    Track();

    //Overload Constructor
    Track(char, char, int station, int opposite);

    //Destructor
    ~Track();

    //Member variables
    char node_1;  // node_1 and node_2 represent stations (for example
    char node_2;  // node_1 would be station A and node_2 would be station B)
    bool visited;

    int connected_station;
    int opposite_track;
};

class Station
{
public:
    //Default Constructor
    Station();

    //Destructor
    ~Station();

    //Overload Constructor
    Station(char, int, int);

    //Member variables
    char station_name;
    int track_starting_ID;
    int track_size;
};

class SubwaySystem
{
public:
    //Default Constructor
    SubwaySystem();

    //Destructor
    ~SubwaySystem();

    //Recursive function
    void SearchRoute(int);

    //Other member functions
    friend ostream& operator<<(ostream& os, const Track& my_track);
    friend ostream& operator<<(ostream& os, const Station& my_station);


    //Member variables
    Track my_track[34];
    Station my_station[12];

    int count_routes;
    int Current_Station_ID;

    //String to save found route

    void SearchRoute(int Current_Station_ID, int from_track_id, Track **currentPath, int pathCount);
};





// **cpp**


//#include "subway.h"

using namespace std;

Track::Track()
{
    visited = 0;
}


Track::~Track()
{
}


Track::Track(char pass_track1, char pass_track2, int station, int opposite)
{
    node_1 = pass_track1;
    node_2 = pass_track2;
    connected_station = station;
    opposite_track = opposite;

    visited = false;
}


Station::Station()
{
}


Station::~Station()
{
}


Station::Station(char pass_station_name, int pass_start, int pass_size)
{
    station_name = pass_station_name;
    track_starting_ID = pass_start;
    track_size = pass_size;
}


SubwaySystem::SubwaySystem()
{
    //Initialize tracks
    //node_1, node_2
    my_track[0] = Track('a', 'b', 1, 1);
    my_track[1] = Track('b', 'a', 0, 0);
    my_track[2] = Track('b', 'c', 2, 6);
    my_track[3] = Track('b', 'd', 3, 8);
    my_track[4] = Track('b', 'e', 4, 10);
    my_track[5] = Track('b', 'f', 5, 15);
    my_track[6] = Track('c', 'b', 1, 2);
    my_track[7] = Track('c', 'e', 4, 11);
    my_track[8] = Track('d', 'b', 1, 3);
    my_track[9] = Track('d', 'e', 4, 12);
    my_track[10] = Track('e', 'b', 1, 4);
    my_track[11] = Track('e', 'c', 2, 7);
    my_track[12] = Track('e', 'd', 3, 9);
    my_track[13] = Track('e', 'g', 6, 17);
    my_track[14] = Track('e', 'h', 7, 19);
    my_track[15] = Track('f', 'b', 1, 5);
    my_track[16] = Track('f', 'h', 7, 20);
    my_track[17] = Track('g', 'e', 4, 13);
    my_track[18] = Track('g', 'k', 10, 28);
    my_track[19] = Track('h', 'e', 4, 14);
    my_track[20] = Track('h', 'f', 5, 16);
    my_track[21] = Track('h', 'i', 8, 24);
    my_track[22] = Track('h', 'j', 9, 26);
    my_track[23] = Track('h', 'k', 10, 29);
    my_track[24] = Track('i', 'h', 7, 21);
    my_track[25] = Track('i', 'k', 10, 30);
    my_track[26] = Track('j', 'h', 7, 22);
    my_track[27] = Track('j', 'k', 10, 30);
    my_track[28] = Track('k', 'g', 6, 18);
    my_track[29] = Track('k', 'h', 7, 23);
    my_track[30] = Track('k', 'i', 8, 25);
    my_track[31] = Track('k', 'j', 9, 27);
    my_track[32] = Track('k', 'l', 11, 33);
    my_track[33] = Track('l', 'k', 10, 32);
    //Initialize stations
    //station_name, track_starting_ID, track_size
    my_station[0] = Station('a', 0, 1);
    my_station[1] = Station('b', 1, 5);
    my_station[2] = Station('c', 6, 2);
    my_station[3] = Station('d', 8, 2);
    my_station[4] = Station('e', 10, 5);
    my_station[5] = Station('f', 15, 2);
    my_station[6] = Station('g', 17, 2);
    my_station[7] = Station('h', 19, 5);
    my_station[8] = Station('i', 24, 2);
    my_station[9] = Station('j', 26, 2);
    my_station[10] = Station('k', 28, 5);
    my_station[11] = Station('l', 33, 1);
    //Initiaize other members
    count_routes = 0;
    Current_Station_ID = 0;
}


SubwaySystem::~SubwaySystem()
{
}



void SubwaySystem::SearchRoute(int Current_Station_ID, int from_track_id, Track **currentPath, int pathCount)
{
    if(my_station[Current_Station_ID].track_starting_ID == 33)
    {
        count_routes++; //Add 1 into the variable "count_routes"
        cout << count_routes << " ";
        for(int i= 0; i < pathCount; i++)
        {
            cout << *currentPath[i]; 
        }
        cout << endl;
        return;
    }
    else //Get into recursive Function Body
    {
        for(int i = my_station[Current_Station_ID].track_starting_ID; i < my_station[Current_Station_ID].track_starting_ID + my_station[Current_Station_ID].track_size; i++)
        {
                    //check all the tracks that we have visited before
            bool visited = false;
            for(int n = 0; n < pathCount; n++)
            {
                if(currentPath[n] == &my_track[i] || i == currentPath[n]->opposite_track) visited = true;
            }


            if(!visited)
            {
                int nextStation = my_track[i].connected_station;
                currentPath[pathCount] = &my_track[i];
                SearchRoute(nextStation, i, currentPath, pathCount + 1); 
            }
        }  
    }
}




ostream& operator<<(ostream& os, const Track& my_track)
{
    os << my_track.node_1 << '.' << my_track.node_2;
    return os;
}

ostream& operator<<(ostream& os, const Station& my_station)
{
    os << my_station.station_name << '.' << my_station.track_starting_ID << '.' << my_station.track_size;
    return os;
}


//This is where the above recursive function SearchRoute goes. I posted it separately so it easier to read.



// **main**


//#include "subway.h"






int _tmain(int argc, _TCHAR* argv[])
{

    Track *tempTracks[34];
    SubwaySystem findPaths;
    findPaths.SearchRoute(0, -1, tempTracks, 0);

    getchar();

    return 0;
}

Answer 2

, :

my_track[Current_Station_ID].visited = 1; //mark this track as visited
my_track[Current_Station_ID].node_2 = 1; //mark its corresponding track as visited
cout << my_track[Current_Station_ID].node_1; //save this track
SearchRoute(Current_Station_ID++); <<<<<<<< PROBLEM 
i--; //Backtrack this track  <<<<<<< Also this will do nothing
my_track[Current_Station_ID].visited = 0; <<<<<<< Now Current_Station_ID is 1 more than you are expecting it to be.
my_track[Current_Station_ID].node_2 = 0;//mark its corresponding track as unvisited

Current_Station_ID ++ , , , , ++ Current_Station_ID 1.

for. :

void SubwaySystem::SearchRoute(int Current_Station_ID, int from_track_id, Track *currentPath, int pathCount)
{
    if(my_station[Current_Station_ID].track_starting_ID == 33)
    {
        count_routes++; //Add 1 into the variable "count_routes"
        cout << count_routes << " ";
        for(int i= 0; i < pathCount; i++)
        {
             cout << my_track[i]; 
        }
        cout << endl;
        return;
    }
    else //Get into recursive Function Body
    {

         if(from_track_id >= 0) my_track[from_track_id].visited = 1; 

        for(int i = my_station[Current_Station_ID].track_starting_ID; i < my_station[Current_Station_ID].track_starting_ID + my_station[Current_Station_ID].track_size; i++)
        {
            int nextStation = my_track[i].node_2;   ///<<<<<<< But you will need to change node_2 to be an int, and use the station number, not letter when you set them up
            if(my_track[i].visited == 0)
            {
                currentPath[pathCount] = my_track[i];
                SearchRoute(nextStation, i, currentPath, pathCount + 1); 


            }
        }

       if(from_track_id >= 0) my_track[from_track_id].visited = 0; 
    }
}

:

int main()
{
    Track tempTracks[34];
    SubwaySystem findPaths;
    findPaths.SearchRoute(0, -1, tempTracks, 0);
}

Answer 3

I found 640 routes:

#include <stdio.h>

const char *connectom[] = {
"B",            // A
"ACDEF",        // B
"BE",           // C
"BE",           // D
"CDBGH",        // E
"BH",           // F
"EK",           // G
"EFJKI",        // H
"HK",           // I
"HK",           // J
"HIJGL",        // K
"K"             // L
};

char tracks[0x100];
char strout[0x100];

void path(char x, char *s) {
  *s++ = x;
  if(x == 'L') {
    *s = 0;
    printf("path=%s\n", strout);
  } else {
    for(const char *p = connectom[x - 'A']; *p; p++) {
       unsigned char track_ndx = x > *p? (x << 4) ^ *p : (*p << 4) ^ x;
       if(tracks[track_ndx] == 0) {
         tracks[track_ndx] = 1;
         path(*p, s);
         tracks[track_ndx] = 0;
       } // if
    } // for
  } // else
} // path

int main(int argc, char **argv) {
  path('A', strout);
} // main