title: Problem implementing the  graph_coloring - m coloring problem
body: <p>I have to write C++ program, which will determine how many colors I should use to color undirected graph.</p>
  
  <p>Also, I have to do this using algorithm from book "Foundations of Algorithms using C++ pseudocode".</p>
  
  <p><strong>Problem description:</strong> Determine all ways in which the vertices in an undirected graph can be colored, using only m colors, so that adjacent vertices are not the same color.</p>
  
  <p><strong>Input:</strong> positive integers n and m, and an undirected graph containing n vertices. The graph is represented by a two-dimensional array W, which has both its rows and columns indexed from 1 to n, where W [i] [j] is true if there is an edge between ith vertex and the jth vertex and false otherwise.</p>
  
  <p><strong>Output:</strong> all possible colorings of the graph, using at most m colors, so that no two adjacent vertices are the same color. The output for each coloring is an array vcolor indexed from 1 to n, where vcolor [i] is the color (an integer between 1 and m) assigned to the ith vertex.</p>
  
  <p><strong>There we have algorithm:</strong></p>
  
  <pre><code>void m_coloring (index i)
  {
      int color;
      if (promising (i))
          if (i == n)
              cout &lt;&lt; vcolor [1] through vcolor [n];
          else
              for (color = 1; color &lt;= m; color++){ // Try every
                  vcolor [i + 1] = color;           // color for
                  m_coloring (i + 1);               // next vertex.
              }
  }
  
  bool promising (index i)
  {
      index j;
      bool switch;
  
      switch = true;
      j = 1;
      while (j &amp;&amp; switch){                       // Check if an
          if (W[i][j] &amp;&amp; vcolor[i] == vcolor[j]) // adjacent vertex
              switch = false;                    // is already
          j++;                                   // this color.
      }
      return switch;
  }
  </code></pre>
  
  <p><strong>And comment at the end:</strong> Following our usual convention, n, m, W, and vcolor are not inputs to either routine. In an implementation of the algorithm, the routines would be defined locally in a simple procedure that had n, m, and W as inputs, and vcolor defined locally. The top level call to m_coloring would be <strong>m_coloring( 0 )</strong></p>
  
  <p>I start to write my own implementation. First I want to say, that I'm not good C++ programmer, what is more, I usually use JS and PHP, weakly typed languages, so I'm sure there is a lot things I could do better. But it isn't main problem. </p>
  
  <p><strong>Problem is:</strong> the program above start to work, I write simple graph:</p>
  
  <blockquote>
    <p>4 vertexes, 4 edges</p>
    
    <p>1 2<br>
    1 3
    2 3
    3 4</p>
  </blockquote>
  
  <p>Next, program start to use <strong>checkFor()</strong> (I planned to use it at for() for the every next number of colors, but for test purposes, I use it at static way, so I used 4.</p>
  
  <p>Unfortunately, program launch m_coloring(), next launch promising() and... this is the end. I spend last three hours to find out, what I do wrong, maybe any more experienced programmer is able to explain me what I should do and / or what I do wrong...</p>
  
  <p>Pleas help, thank you a lot.</p>
  
  <p><strong>My program code:</strong></p>
  
  <pre><code>#include &lt;iostream&gt;
  
  using namespace std;
  
  bool **W;
  int n, m = 0;
  int v, e = 0;
  int x, y = 0;
  int *vcolor;
  
  bool promising (int i)
  {
      int j = 1;
      bool switcher = true;
  
      while (j &amp;&amp; switcher)
      {   
          if ( W[i][j] &amp;&amp; vcolor[i] == vcolor[j] )
          {
              switcher = false;
          }
  
          j++;
      }
  
      return switcher;
  }
  
  void m_coloring (int i)
  {
      int color;
      if ( promising (i) )
      {
          if (i == n)
          {
              cout &lt;&lt; vcolor [1] &lt;&lt; " through " &lt;&lt; vcolor [n];
          }
          else
          {
              for (color = 1; color &lt;= m; color++)
              {      
                  vcolor [i + 1] = color;
                  m_coloring(i + 1);
              }
          }
      }
  }
  
  void initArrays()
  {
      for( int i = 0; i &lt; n; i++ )
      {
          W[ i ] = new bool[ n ];
          vcolor[ i ] = 0;
      }
  }
  
  void fillW()
  {
      for( int i = 0; i &lt; n; i++ )
      {
          for( int j = 0; j &lt; n; j++ )
          {
              if( !W[i][j] )
              {
                  W[i][j] = false;
              }
          }
      }
  }
  
  void askForEdges()
  {
      cout &lt;&lt; "How many edges? ";
      cin &gt;&gt; e;
      cout &lt;&lt; endl &lt;&lt; "Write edges with pattern: [vertex_x][space][vertex_y]:" &lt;&lt; endl;
  
      for( int i = 0; i &lt; e; i++ )
      {
          cin &gt;&gt; x &gt;&gt; y;
  
          W[x][y] = true;
          W[y][x] = true;
      }
  }
  
  void specialMatrixPrint()
  {
      cout &lt;&lt; endl;
      int i, j;
      for( i = 0; i &lt; n; i++ )
      {
          for( int j = 0; j &lt; n; j++ )
          {
              cout &lt;&lt; W[i][j] &lt;&lt; " ";
          }
          cout &lt;&lt; endl;
      }
  }
  
  void showEdgesMatrix()
  {
      int i, j = 0;
  
      cout &lt;&lt; endl &lt;&lt; "    "; for( i = 1; i &lt; n; i++ ) { cout &lt;&lt; i &lt;&lt; " "; } cout &lt;&lt; endl;
      cout &lt;&lt; endl &lt;&lt; "    "; for( i = 1; i &lt; n; i++ ) { cout &lt;&lt; "# "; } cout &lt;&lt; endl;
  
      for( i = 1; i &lt; n; i++ )
      {
          cout &lt;&lt; i &lt;&lt; " # ";
          for( int j = 1; j &lt; n; j++ )
          {
              if( W[i][j] == true ) { cout &lt;&lt; "1 "; }
              else { cout &lt;&lt; "0 "; }
          }
  
          cout &lt;&lt; endl;
      }
  }
  
  void showVcolor()
  {
      cout &lt;&lt; endl;
      for( int i = 1; i &lt; n; i++ )
      {
          cout &lt;&lt; i &lt;&lt; ": " &lt;&lt; vcolor[ i ] &lt;&lt; endl;
      }
  }
  
  void checkFor( int i )
  {
      m = i;
      m_coloring( 0 );
  }
  
  int main()
  {
      cout &lt;&lt; "How many vertexes? " ;
      cin &gt;&gt; n;
  
      n += 1;
  
      W = new bool *[ n ];
      vcolor = new int[ n ];
  
      initArrays();
      askForEdges();
      showEdgesMatrix();
  
      checkFor( 4 );
      showVcolor();
  
      cin &gt;&gt; y;
  
      return 0;
  }
  </code></pre>