Thread: Organizing and optimizing code into source and header files

  1. #1
    Registered User
    Join Date
    Sep 2011
    Posts
    18

    Organizing and optimizing code into source and header files

    I'm a new C++ programmer coming from java. I translated Dijkstra's algorithm from java into C++. I know this is not good programming practice, hence I will post the code here for optimisation suggestions.
    This is one giant source file.

    Code:
    #include <iostream>
    #include <vector>
    #include <string>
    
    using std::vector;
    
    ///////////////////////////////////////////////////////////////////////////////	
    
    //Class that holds distance and parent
    class DistPar
    {
    public:
      int distance;                         //distance from start to this vertex
      int parentVert;                       //parent of this vertex
    
    //-----------------------------------------------------------------------------
    
      DistPar(int pv, int d)                //constructor
      {
        distance = d;
        parentVert = pv;
      }
    };  //end class Distpar
    
    ///////////////////////////////////////////////////////////////////////////////	
    
    //A vertice in our graph
    class Vertex
    {
    public:
      char label;
      bool isInTree;
    
    //-----------------------------------------------------------------------------
    
      Vertex(char lab)
      {
        label = lab;
        isInTree = false;
      }
    };  //end class Vertex
    
    ///////////////////////////////////////////////////////////////////////////////	
    
    //Graph class that does the computation
    class graphCalc
    {
    public:
       
      int MAX_VERTS;                			//Need to change later to match user input
      int INFINITY;
    
      vector<Vertex> vertexList;			//list of all our vertices
      vector<vector<int> > adjMat;  		//This is our adjacency matrix for vertice layout representation
      vector<DistPar> sPath;			//shortest path array
      
      int nTree;                                //Number of vertices in our tree
      int nVerts;                               //current number of vertices
        
      int currentVert;                          //current vertex
      int startToCurrent;                       //distance to currentVert from start 
       
    //-----------------------------------------------------------------------------
      graphCalc()                                   //Needs to take input parameters later
      {
      	MAX_VERTS = 999;
      	INFINITY = 1000000;
      	
        nVerts = 0;
        nTree = 0;
    
        //Set adjMatrix to infinity
        for (int i = 0; i < 5; i++)
        	{
        		adjMat.push_back( vector<int>(1, INFINITY) );
        		
        		for ( int j = 0; j < 5; j++)
        			adjMat[i].push_back(INFINITY);
           }
      }
    
    //-----------------------------------------------------------------------------
    
      void addVertex(char lab)
      {
        nVerts++;
        vertexList.push_back( Vertex(lab) );
      }
    
    //-----------------------------------------------------------------------------
    
      void addEdge(int start, int end, int weight)
      {
        adjMat[start][end] = weight;          //directed
      }
    
    //-----------------------------------------------------------------------------
    
      //find all shortest paths
      void path()
      {
        int startTree = 0;                    //start at vertex 0 or A
        vertexList[startTree].isInTree = true;
        nTree = 1;                            //put in tree
        
        //transfer row of distances from A in adjMat to sPath
        for (int j = 0; j < nVerts; j++)
          {
    	 //Distance of 2nd object in row since we skip A, A->A = INFINITE
    	 int tempDist = adjMat[startTree][j];
    	 sPath.push_back( DistPar(startTree, tempDist));
          }
    
        //until all vertices are in tree
        while (nTree < nVerts)
          {
    	 int indexMin = getMin();           //get min from sPath
    	 int minDist = sPath[indexMin].distance;
    
    	 if (minDist == INFINITY)           //if all infinite
    	   {
    	      std::cout << "There are unreachable vertices.";
    	      break;
    	   }
    	 else
    	   {
    	      currentVert = indexMin;        //reset currentVert to closest vert
    	      startToCurrent = sPath[indexMin].distance;
    	   }
    
    	 //put current vertex in tree
    	 vertexList[currentVert].isInTree = true;
    	 nTree++;
    	 adjust_sPath();                    //update sPath[] array
        	} //end while (nTree < nVerts)
    
        displayPaths();                        //display sPath[]
    
        nTree = 0;                             //clear tree
        
        for (int j = 0; j < nVerts; j++)
          vertexList[j].isInTree = false;
      } //end path()
    
    //-----------------------------------------------------------------------------
    
      //get minimum distance in sPath and return it
      int getMin()
      {
        int minDist = INFINITY;                //assume minimum
        int indexMin = 0;
    
        //For each vertex, if it's in tree and smaller than old one
        for (int j = 1; j < nVerts; j++)
          {
    				if (!vertexList[j].isInTree && sPath[j].distance < minDist)
    					{
    						minDist = sPath[j].distance;
    						indexMin = j;
    					}
          }  //end for
    
        return indexMin;
      } //end getMin()
    
    //-----------------------------------------------------------------------------
    
      void adjust_sPath()
      {
        //adjust values in shortest-path array sPath
        int column = 1;                       //skip the starting vertex 'A'
    
        while (column < nVerts)               //loop across all vertices in array
          {
    	//if this column's vertex is in tree, skip it
    	if (vertexList[column].isInTree)
    	  {
    	     column++;;
    	     continue;
              }
    
    	 /*calculate distances*/
             //get edge from currentVert to destination vertex
    	 int currentToFringe = adjMat[currentVert][column];
    	 //add distance from start to current
             int startToFringe = startToCurrent + currentToFringe;
             //get distance of current sPath entry
             int sPathDist = sPath[column].distance;
    
    	 //compare distance from start to fringe with sPath fringe entry
             if (startToFringe < sPathDist)   //if shorter
    	   {
                  sPath[column].parentVert = currentVert;
    	      sPath[column].distance = startToFringe;
               }
    
             column++;
          }  //end while (column < nVerts)
      }  //end adjust_sPath()
    
      void displayPaths()
      {
        for (int j = 0; j < nVerts; j++)
          {
    	 std::cout << vertexList[j].label << "=";
    
    	 if (sPath[j].distance == INFINITY)
    	   std::cout << "inf";
    	 else
    	   std::cout << sPath[j].distance;
    
    				char parent = vertexList[ sPath[j].parentVert].label;
    				std::cout << "(" << parent << ") ";
          }
          
        std::cout << " ";
          
        std::cout << std::endl;
      }
    
    //-----------------------------------------------------------------------------
    
    };
      
    ///////////////////////////////////////////////////////////////////////////////	
    
    //This is the main class
    int main()
    {
      graphCalc theGraph;
    
      theGraph.addVertex('A');     //0 start
      theGraph.addVertex('B');     //1 start
      theGraph.addVertex('C');     //2 start
      theGraph.addVertex('D');     //3 start
      theGraph.addVertex('E');     //4 start
    
      theGraph.addEdge(0, 1, 50);  //A->B 50
      theGraph.addEdge(0, 3, 80);  //A->B 50
      theGraph.addEdge(1, 2, 60);  //A->B 50
      theGraph.addEdge(1, 3, 90);  //A->B 50
      theGraph.addEdge(2, 4, 40);  //A->B 50
      theGraph.addEdge(3, 2, 20);  //A->B 50
      theGraph.addEdge(3, 4, 70);  //A->B 50
      theGraph.addEdge(4, 1, 50);  //A->B 50
    
      std::cout << std::endl;
      std::cout << "Shortest paths ";
      theGraph.path();             //main function that does everything
      std::cout << std::endl;
    }  //end main class
    What I plan to do is to create 3 header files to hold each of the 3 classes. Then have a .cpp source to hold the function declarations associated with each of the header files. Finally, the source with main() would include all the header files.

    EDIT: All the line length comments are there for easy readability. They will be removed of course.
    EDIT2: Good lord the formatting got destroyed during copy/paste. Trying to fix. Sorry would take too long to fix.
    Last edited by edishuman; 01-24-2012 at 03:46 AM.

  2. #2
    C++ Witch laserlight's Avatar
    Join Date
    Oct 2003
    Location
    Singapore
    Posts
    28,413
    I suggest that you make use of constructor initialiser lists. For most of the constructors here, this does not matter, but the graphCalc default constructor can benefit:
    Code:
    graphCalc() : MAX_VERTS(999),
                  INFINITY(1000000),
                  adjMat(5, vector<int>(6, INFINITY)),
                  nVerts(0),
                  nTree(0) {}
    This is fine in a source file:
    Code:
    using std::vector;
    But in a header file, only use it within a local scope, not at file/namespace scope like what you did here.
    Quote Originally Posted by Bjarne Stroustrup (2000-10-14)
    I get maybe two dozen requests for help with some sort of programming or design problem every day. Most have more sense than to send me hundreds of lines of code. If they do, I ask them to find the smallest example that exhibits the problem and send me that. Mostly, they then find the error themselves. "Finding the smallest program that demonstrates the error" is a powerful debugging tool.
    Look up a C++ Reference and learn How To Ask Questions The Smart Way

  3. #3
    Registered User
    Join Date
    Jan 2012
    Posts
    12
    It is generally good practice to always initialise class member variables in constructor initialiser lists. This is because C++ guarantees that they are initialised to something sensible (0 for int, etc). So technically, unless the compiler optimises it away, by putting the initialisation inside the constructor you will be initialising the variables twice. (Note that, unlike in Java, local variables in functions are not guaranteed to be initialised to something sensible.)

    Functions defined inside the class body are made inline. Thus, only small things like getter and setter methods, should be defined inside the body of a class. Everything else should be declared inside the body, and defined in a cpp source file. If you would like to make these functions inline, you can do so using the inline keyword.

    There is no such thing as a "main class" in C++. The definition of main is not inside any class. Note that while C++ supports OOP, it simultaneously supports other programming paradigms such as procedural, modular, etc. On the other side, while C++ does not have a garbage collector by default, it is possible to implement one by overloading operators such as new, new[], etc (note that they are separate operators and the correct corresponding delete operator should be used).

    Also do not forget to have inclusion guards inside your headers. If you did not know already, there is nothing too intelligent about the #include statement, and it simply involves copying by the preprocessor. Without these guards, if a header includes another header which you have already included, errors will result (unlike with the Java import statement).
    Last edited by Time Traveler; 01-24-2012 at 05:43 AM.

  4. #4
    C++まいる!Cをこわせ!
    Join Date
    Oct 2007
    Location
    Inside my computer
    Posts
    24,654
    Quote Originally Posted by Time Traveler View Post
    Functions defined inside the class body are made inline. Thus, only small things like getter and setter methods, should be defined inside the body of a class. Everything else should be declared inside the body, and defined in a cpp source file. If you would like to make these functions inline, you can do so using the inline keyword.
    This is not a requirement as inline is merely a hint to the compiler. It will inline if it pleases, and ignore it if it thinks it's a bad idea.
    Quote Originally Posted by Adak View Post
    io.h certainly IS included in some modern compilers. It is no longer part of the standard for C, but it is nevertheless, included in the very latest Pelles C versions.
    Quote Originally Posted by Salem View Post
    You mean it's included as a crutch to help ancient programmers limp along without them having to relearn too much.

    Outside of your DOS world, your header file is meaningless.

Popular pages Recent additions subscribe to a feed

Similar Threads

  1. Replies: 6
    Last Post: 10-04-2011, 10:17 PM
  2. Confusion on header and source files
    By dnguyen1022 in forum C++ Programming
    Replies: 4
    Last Post: 01-17-2009, 03:42 AM
  3. compiling source files and header file at once?
    By 1jackjack in forum C Programming
    Replies: 10
    Last Post: 05-04-2007, 11:06 AM
  4. Linking header files, Source files and main program(Accel. C++)
    By Daniel Primed in forum C++ Programming
    Replies: 3
    Last Post: 01-17-2006, 11:46 AM
  5. header and source files
    By gtriarhos in forum C Programming
    Replies: 3
    Last Post: 10-02-2005, 03:16 AM