How to transform C program into classes

Question

so I've been working on this program and its objective was to use recursion and an adjacency matrix to find how many possible routes a person could take to get through a subway system without going over a track more than once. That was self explanatory for me but now I'm lost on program 2 which is to do the same problem from program 1 in C++ and using three classes and recursion. The classes are suppose to be SubwaySystem, Station, and Track. I don't really know how to go about the transition from a simple adjacency matrix into three classes? It seems counterproductive since it seems more complicated. I have been working on it for a while know and I can't seem to utilize all three classes.

What I have tried: My approach was I created 1 Subway System with 12 Stations, and each station with an array of Tracks. For example, Station A has one station it can go to which is B. In Station A there is an array of 12 tracks but only 1 track is activated. However I keep running to errors since I tried to initialize the arrays in the Track class and then use them in the SubwaySystem class. Then trying to use recursion to get all possible routes makes it that much more difficult. I really don't know how to figure this out.

The adjacency matrix in the my code pretty much maps out the entire connection from station to station. The station are A - L corresponding to each row/column. I don't know how to represent this in c++ without using an adjacency matrix.

My code in C (program 1):

#include <stdio.h>

void routesFinder(int row, int col);

char station[13] = "ABCDEFGHIJKL";
char order[25] = "A";
int subway[12][12] = {{0,1,0,0,0,0,0,0,0,0,0,0},
                 {1,0,1,1,1,1,0,0,0,0,0,0},
                 {0,1,0,0,1,0,0,0,0,0,0,0},
                 {0,1,0,0,1,0,0,0,0,0,0,0},
                 {0,1,1,1,0,0,1,1,0,0,0,0},
                 {0,1,0,0,0,0,0,1,0,0,0,0},
                 {0,0,0,0,1,0,0,0,0,0,1,0},
                 {0,0,0,0,1,1,0,0,1,1,1,0},
                 {0,0,0,0,0,0,0,1,0,0,1,0},
                 {0,0,0,0,0,0,0,1,0,0,1,0},
                 {0,0,0,0,0,0,1,1,1,1,0,1},
                 {0,0,0,0,0,0,0,0,0,0,1,0}};

int paths = 0, i = 1;

int main(){
     routesFinder(0, 0); //start with first station row, first column
     printf("\n%d days before repeating a route.\n", paths);
     return 0;
}

void routesFinder(int row, int col) {
     while (col < 12) { //go through columns of a row
         if (subway[row][col] == 0) { // if no station is found in row
            if (row == 11) { // station found
               paths++;
               printf("Route %d: %s.\n", paths, order);
               return;
            }
            col++;
            if (row != 11 && col == 12) { //backtracking from deadend
               return;
            }
         }
         if (subway[row][col] == 1) {
            order[i] = station[col]; //add station to route
            i++; //increment, prepare for next route
            subway[row][col] = 0; //no track forward
            subway[col][row] = 0; // or backward
            routesFinder(col, 0); //recursion, look for path in new row
            order[i] = '\0'; //remove route
            i--; //decrement, prepare for next route
            subway[row][col] = 1; //restore path
            subway[col][row] = 1; // restore path
            col++; //returning from deadend, check for next open path
            if (row != 11 && col == 12) { //return from deadend
                return;
            }
         }
     }
}

Answer 1

In general I can tell you that in c++ in particular and in object oriented in general, each object should have its unique role in the system. Each is encapsulating a behavior and a knowledge that are its own and sole responsibility. As for you specific problem - Without getting too deeply into the problem, I think the idea would be:

#include <iostream>
#include <string>
#include <vector>

class Track;
typedef std::vector<Track*> TrackList;

class Station
{

    public:
        Station( std::string name ) : _name( name ){};
        ~Station(){}

    public:
        const std::string& GetName() const
        { return _name; }

        TrackList& GetTrackList()  
        { return _trackList; }

        void AddTrack( Track& track )
        { _trackList.push_back( &track );  }

    private:
        std::string _name;
        TrackList _trackList;
};

class Track
{
    public:
        Track( Station& edgeA, Station& edgeB )
            : 
                _edgeA( edgeA ),
                _edgeB( edgeB ),
                _wasVisited( false )
        { 
            edgeA.AddTrack( *this );
            edgeB.AddTrack( *this );
        }
        ~Track(){}

    public:
        bool WasVisited() const
        { return _wasVisited; }

        void SetVisited()
        { _wasVisited = true; }

    public:
        Station& GetEdgeA()
        { return _edgeA; }

        Station& GetEdgeB()
        { return _edgeB; }

    private:
        Station& _edgeA;
        Station& _edgeB;
        bool _wasVisited;
};

class SubwaySystem
{
    public:
        SubwaySystem() {}
        ~SubwaySystem() {}

    public:
       void Traverse( Station& start )
       {
           TrackList& tracks = start.GetTrackList();
           TrackList::iterator it = tracks.begin();

           while ( it != tracks.end() )
           {
               if ( ! (*it)->WasVisited() )
               {
                   std::cout << (*it)->GetEdgeA().GetName() << "-->" << (*it)->GetEdgeB().GetName() << ",";
                   (*it)->SetVisited();
                   Traverse( (*it)->GetEdgeB() ); 
               } 

               ++ it;
           } 
           std::cout << std::endl;
       }

};

int main()
{
    Station A( "A" );
    Station B( "B" );
    Station C( "C" );
    Station D( "D" );
    Station E( "E" );

    Track AB( A, B );
    Track BC( B, C );
    Track CA( C, A );
    Track CD( C, D );
    Track CE( C, E );
    Track AE( A, E );


    SubwaySystem subway;
    subway.Traverse( A ); 
}

The output to this is

A-->B,B-->C,C-->A,A-->E,C-->E,


C-->D,

Surly you can 'play' with the Traverse function and put the printings in other places, select another end-recursion condition, etc.

Notice how clean main() is. You just declare the Stations and the Tracks and the voodoo happens. Adding more tracks is simple, just describe the link and that's all, the track wad 'added' to the subway.

Other parts of the applications are also very clean, as each class knows exactly what it should and nothing more.