Maximum matching in graph

Question

I'm currently working on this problem for my own practice. It's a paintball problem where I should determine if everyone can get a unique target. The problem is as follows I get a number of pair like:

• 1 2
• 3 4
• 3 2
• 4 1

If I get 1 2 it means that 1 can see 2 and therefore 1 can target 2. It goes the other way around to so 2 can see 1 and therefore 2 can target 1.

My assignment is to determine if everyone can get an unique target. If so I should output the numbers in order so first numbers 1 target than who number 2 should target and so on.

My implementation goes as follows:

• I read in the number of players and lines.
• For each line I create an edge.
• Then I create a bool array to keep track if a player has a target and another bool array to see if a player is a target.
• Then use a recursive method to find out the path which all player gets a target.
• I also have a graph class to keep track of all the edges.

I need advice on what I'm doing wrong or any tips on the implementation.

  class Graph{
      std::list<int> graph[1000];
   public:
     void addEdge(int from, int to){
        graph[from].push_back(to);
    }
    std::list<int> getEdges(int e){
      std::list<int> myList = graph[e];
      return myList;
}

};


int n;
bool res = false;
int cnt = 0;
void checkPlayers(Graph graph,bool hasTarget[],bool isTarget[],int i,std::string myRes){
std::list<int> list = graph.getEdges(i);

std::list<int>::const_iterator iterator;
for(iterator = list.begin(); iterator != list.end(); ++iterator){
     int currentplayer = (*iterator);

     if(hasTarget[i] == false && isTarget[currentplayer] == false && currentplayer <= n){
       hasTarget[i] = true;
       isTarget[currentplayer] = true;
       cnt++;
       myRes += std::to_string(currentplayer);
       checkPlayers(graph, hasTarget, isTarget,++i,myRes);
       hasTarget[i] = false;
       isTarget[currentplayer] = false;
       cnt--;
       //myRes.erase(myRes.begin()+ st)
     }
 } 
    if(cnt == n && res == false ){
     res = true;
     std::cout << myRes << std::endl;
  }
}

     int main(){
     int m;
     int playerOne, playerTwo;
     Graph graph;
     for(std::cin >> n >> m; m; --m){
       std::cin >> playerOne >> playerTwo;
       graph.addEdge(playerOne,playerTwo);
       graph.addEdge(playerTwo,playerOne);
     }
     bool isTarget[1000] = {false};
     bool hasTarget[1000] = {false};
     checkPlayers(graph,hasTarget, isTarget,1,""); 
  }

Answer 1

If you don't know the size of your array, don't estimate it

Your graph is an array of 1000 std::list<int>. Why ? If you don't know the size, just don't use a const expr to set it. Just use any dynamic table object available (vector, hashmap, etc...). If you have only 3 edges, 997 cells of your graph will be wasted memory space, and if you have more than 1000 edges, errors will occur.

Avoid non-const global variables

n, res and cnt are declared as global. Avoid using non-const globals. Among many problems (like name conflicts or multi-threading), it greatly reduce the readability of your program, and thus it's more easy for you to make errors.

Try declaring variables in the most restrained scope as possible. In a struct for example, which is passed down to checkPlayers. Global variable are almost never required to do what you want, you can always use local variables. Plus, you should prefix your globals' name with g_ so it is clear that they are globals.

On top of that, you only use these variables into checkPlayers() ! These really should be local variable to this function.

Don't call list.end() in the `for` loop head

In your for loop, each time list.end() is called and re-evaluated. Just declare a const iterator with this value like that :

std::list<int>::const_iterator iterator;
std::list<int>::const_iterator iteratorEnd = list.end();
for(iterator = list.begin(); iterator != iteratorEnd ; ++iterator){
...
}

You also should consider using std::for_each or BOOST_FOREACH (I have a preference for the latest, as it is shorter than the former to implement).

use const reference to pass non-basic types

Passing objects by copy may be long (your graph contains a 1000 cells array !), so passing it by reference is way quicker. To ensure that the reference isn't modified though, make the reference const (const Graph & graph instead of Graph graph). The same goes for the std::string.

Create variables only where you need it

Besides the fact that the two arrays of bool could be move into a single array of struct containing the bools, four of the five arguments of checkPlayers are useless. Don't create them above is you don't need to, there's no use for that.

If you're doing this just in case you may need it later, well I think this is the wrong way to do it, because you may end up with tons of useless code difficult to maintain. Declare variables only when you need it, and if yo ulater may need to generalize, you'll do it then, not before.

main returns an int

Don't forget the return 0; at the end of your program. Error codes are important.