test/max_clique_test.cc
changeset 980 48e17328c155
parent 904 c279b19abc62
child 1092 dceba191c00d
equal deleted inserted replaced
0:c237b9dfd9e2 1:fa81e6f76c63
    56   "6 7    15\n";
    56   "6 7    15\n";
    57       
    57       
    58 
    58 
    59 // Check with general graphs
    59 // Check with general graphs
    60 template <typename Param>
    60 template <typename Param>
    61 void checkMaxCliqueGeneral(int max_sel, Param rule) {
    61 void checkMaxCliqueGeneral(Param rule) {
    62   typedef ListGraph GR;
    62   typedef ListGraph GR;
    63   typedef GrossoLocatelliPullanMc<GR> McAlg;
    63   typedef GrossoLocatelliPullanMc<GR> McAlg;
    64   typedef McAlg::CliqueNodeIt CliqueIt;
    64   typedef McAlg::CliqueNodeIt CliqueIt;
    65   
    65   
    66   // Basic tests
    66   // Basic tests
    67   {
    67   {
    68     GR g;
    68     GR g;
    69     GR::NodeMap<bool> map(g);
    69     GR::NodeMap<bool> map(g);
    70     McAlg mc(g);
    70     McAlg mc(g);
    71     check(mc.run(max_sel, rule) == 0, "Wrong clique size");
    71     mc.iterationLimit(50);
       
    72     check(mc.run(rule) == McAlg::SIZE_LIMIT, "Wrong termination cause");
    72     check(mc.cliqueSize() == 0, "Wrong clique size");
    73     check(mc.cliqueSize() == 0, "Wrong clique size");
    73     check(CliqueIt(mc) == INVALID, "Wrong CliqueNodeIt");
    74     check(CliqueIt(mc) == INVALID, "Wrong CliqueNodeIt");
    74 
    75 
    75     GR::Node u = g.addNode();
    76     GR::Node u = g.addNode();
    76     check(mc.run(max_sel, rule) == 1, "Wrong clique size");
    77     check(mc.run(rule) == McAlg::SIZE_LIMIT, "Wrong termination cause");
    77     check(mc.cliqueSize() == 1, "Wrong clique size");
    78     check(mc.cliqueSize() == 1, "Wrong clique size");
    78     mc.cliqueMap(map);
    79     mc.cliqueMap(map);
    79     check(map[u], "Wrong clique map");
    80     check(map[u], "Wrong clique map");
    80     CliqueIt it1(mc);
    81     CliqueIt it1(mc);
    81     check(static_cast<GR::Node>(it1) == u && ++it1 == INVALID,
    82     check(static_cast<GR::Node>(it1) == u && ++it1 == INVALID,
    82           "Wrong CliqueNodeIt");
    83           "Wrong CliqueNodeIt");
    83     
    84     
    84     GR::Node v = g.addNode();
    85     GR::Node v = g.addNode();
    85     check(mc.run(max_sel, rule) == 1, "Wrong clique size");
    86     check(mc.run(rule) == McAlg::ITERATION_LIMIT, "Wrong termination cause");
    86     check(mc.cliqueSize() == 1, "Wrong clique size");
    87     check(mc.cliqueSize() == 1, "Wrong clique size");
    87     mc.cliqueMap(map);
    88     mc.cliqueMap(map);
    88     check((map[u] && !map[v]) || (map[v] && !map[u]), "Wrong clique map");
    89     check((map[u] && !map[v]) || (map[v] && !map[u]), "Wrong clique map");
    89     CliqueIt it2(mc);
    90     CliqueIt it2(mc);
    90     check(it2 != INVALID && ++it2 == INVALID, "Wrong CliqueNodeIt");
    91     check(it2 != INVALID && ++it2 == INVALID, "Wrong CliqueNodeIt");
    91 
    92 
    92     g.addEdge(u, v);
    93     g.addEdge(u, v);
    93     check(mc.run(max_sel, rule) == 2, "Wrong clique size");
    94     check(mc.run(rule) == McAlg::SIZE_LIMIT, "Wrong termination cause");
    94     check(mc.cliqueSize() == 2, "Wrong clique size");
    95     check(mc.cliqueSize() == 2, "Wrong clique size");
    95     mc.cliqueMap(map);
    96     mc.cliqueMap(map);
    96     check(map[u] && map[v], "Wrong clique map");
    97     check(map[u] && map[v], "Wrong clique map");
    97     CliqueIt it3(mc);
    98     CliqueIt it3(mc);
    98     check(it3 != INVALID && ++it3 != INVALID && ++it3 == INVALID,
    99     check(it3 != INVALID && ++it3 != INVALID && ++it3 == INVALID,
   108     graphReader(g, input)
   109     graphReader(g, input)
   109       .nodeMap("max_clique", max_clique)
   110       .nodeMap("max_clique", max_clique)
   110       .run();
   111       .run();
   111     
   112     
   112     McAlg mc(g);
   113     McAlg mc(g);
   113     check(mc.run(max_sel, rule) == 4, "Wrong clique size");
   114     mc.iterationLimit(50);
       
   115     check(mc.run(rule) == McAlg::ITERATION_LIMIT, "Wrong termination cause");
   114     check(mc.cliqueSize() == 4, "Wrong clique size");
   116     check(mc.cliqueSize() == 4, "Wrong clique size");
   115     mc.cliqueMap(map);
   117     mc.cliqueMap(map);
   116     for (GR::NodeIt n(g); n != INVALID; ++n) {
   118     for (GR::NodeIt n(g); n != INVALID; ++n) {
   117       check(map[n] == max_clique[n], "Wrong clique map");
   119       check(map[n] == max_clique[n], "Wrong clique map");
   118     }
   120     }
   125   }
   127   }
   126 }
   128 }
   127 
   129 
   128 // Check with full graphs
   130 // Check with full graphs
   129 template <typename Param>
   131 template <typename Param>
   130 void checkMaxCliqueFullGraph(int max_sel, Param rule) {
   132 void checkMaxCliqueFullGraph(Param rule) {
   131   typedef FullGraph GR;
   133   typedef FullGraph GR;
   132   typedef GrossoLocatelliPullanMc<FullGraph> McAlg;
   134   typedef GrossoLocatelliPullanMc<FullGraph> McAlg;
   133   typedef McAlg::CliqueNodeIt CliqueIt;
   135   typedef McAlg::CliqueNodeIt CliqueIt;
   134   
   136   
   135   for (int size = 0; size <= 40; size = size * 3 + 1) {
   137   for (int size = 0; size <= 40; size = size * 3 + 1) {
   136     GR g(size);
   138     GR g(size);
   137     GR::NodeMap<bool> map(g);
   139     GR::NodeMap<bool> map(g);
   138     McAlg mc(g);
   140     McAlg mc(g);
   139     check(mc.run(max_sel, rule) == size, "Wrong clique size");
   141     check(mc.run(rule) == McAlg::SIZE_LIMIT, "Wrong termination cause");
   140     check(mc.cliqueSize() == size, "Wrong clique size");
   142     check(mc.cliqueSize() == size, "Wrong clique size");
   141     mc.cliqueMap(map);
   143     mc.cliqueMap(map);
   142     for (GR::NodeIt n(g); n != INVALID; ++n) {
   144     for (GR::NodeIt n(g); n != INVALID; ++n) {
   143       check(map[n], "Wrong clique map");
   145       check(map[n], "Wrong clique map");
   144     }
   146     }
   148   }
   150   }
   149 }
   151 }
   150 
   152 
   151 // Check with grid graphs
   153 // Check with grid graphs
   152 template <typename Param>
   154 template <typename Param>
   153 void checkMaxCliqueGridGraph(int max_sel, Param rule) {
   155 void checkMaxCliqueGridGraph(Param rule) {
   154   GridGraph g(5, 7);
   156   GridGraph g(5, 7);
   155   GridGraph::NodeMap<char> map(g);
   157   GridGraph::NodeMap<char> map(g);
   156   GrossoLocatelliPullanMc<GridGraph> mc(g);
   158   GrossoLocatelliPullanMc<GridGraph> mc(g);
   157   check(mc.run(max_sel, rule) == 2, "Wrong clique size");
   159   
       
   160   mc.iterationLimit(100);
       
   161   check(mc.run(rule) == mc.ITERATION_LIMIT, "Wrong termination cause");
       
   162   check(mc.cliqueSize() == 2, "Wrong clique size");
       
   163 
       
   164   mc.stepLimit(100);
       
   165   check(mc.run(rule) == mc.STEP_LIMIT, "Wrong termination cause");
       
   166   check(mc.cliqueSize() == 2, "Wrong clique size");
       
   167 
       
   168   mc.sizeLimit(2);
       
   169   check(mc.run(rule) == mc.SIZE_LIMIT, "Wrong termination cause");
   158   check(mc.cliqueSize() == 2, "Wrong clique size");
   170   check(mc.cliqueSize() == 2, "Wrong clique size");
   159 }
   171 }
   160 
   172 
   161 
   173 
   162 int main() {
   174 int main() {
   163   checkMaxCliqueGeneral(50, GrossoLocatelliPullanMc<ListGraph>::RANDOM);
   175   checkMaxCliqueGeneral(GrossoLocatelliPullanMc<ListGraph>::RANDOM);
   164   checkMaxCliqueGeneral(50, GrossoLocatelliPullanMc<ListGraph>::DEGREE_BASED);
   176   checkMaxCliqueGeneral(GrossoLocatelliPullanMc<ListGraph>::DEGREE_BASED);
   165   checkMaxCliqueGeneral(50, GrossoLocatelliPullanMc<ListGraph>::PENALTY_BASED);
   177   checkMaxCliqueGeneral(GrossoLocatelliPullanMc<ListGraph>::PENALTY_BASED);
   166 
   178 
   167   checkMaxCliqueFullGraph(50, GrossoLocatelliPullanMc<FullGraph>::RANDOM);
   179   checkMaxCliqueFullGraph(GrossoLocatelliPullanMc<FullGraph>::RANDOM);
   168   checkMaxCliqueFullGraph(50, GrossoLocatelliPullanMc<FullGraph>::DEGREE_BASED);
   180   checkMaxCliqueFullGraph(GrossoLocatelliPullanMc<FullGraph>::DEGREE_BASED);
   169   checkMaxCliqueFullGraph(50, GrossoLocatelliPullanMc<FullGraph>::PENALTY_BASED);
   181   checkMaxCliqueFullGraph(GrossoLocatelliPullanMc<FullGraph>::PENALTY_BASED);
   170                        
   182                        
   171   checkMaxCliqueGridGraph(50, GrossoLocatelliPullanMc<GridGraph>::RANDOM);
   183   checkMaxCliqueGridGraph(GrossoLocatelliPullanMc<GridGraph>::RANDOM);
   172   checkMaxCliqueGridGraph(50, GrossoLocatelliPullanMc<GridGraph>::DEGREE_BASED);
   184   checkMaxCliqueGridGraph(GrossoLocatelliPullanMc<GridGraph>::DEGREE_BASED);
   173   checkMaxCliqueGridGraph(50, GrossoLocatelliPullanMc<GridGraph>::PENALTY_BASED);
   185   checkMaxCliqueGridGraph(GrossoLocatelliPullanMc<GridGraph>::PENALTY_BASED);
   174                        
   186                        
   175   return 0;
   187   return 0;
   176 }
   188 }