src/work/akos/k_cover.cc
changeset 1064 5f0a20861a77
equal deleted inserted replaced
-1:000000000000 0:73c33b597bd2
       
     1 #include <lemon/list_graph.h>
       
     2 
       
     3 using namespace lemon;
       
     4 
       
     5 typedef ListGraph Graph;
       
     6 typedef Graph::NodeIt NodeIt;
       
     7 typedef Graph::EdgeIt EdgeIt;
       
     8 
       
     9 class MyEntity {
       
    10 public:
       
    11   Graph &g;
       
    12   Graph::NodeMap<bool> selected;
       
    13   int edges;
       
    14   int covered_edges;
       
    15 
       
    16   MyEntity(Graph &_g) : g(_g), selected(_g) {}
       
    17   MyEntity(MyEntity& e) : g(e.g), selected(e.g) {
       
    18     for (NodeIt n(g); n != INVALID; ++n) {
       
    19       selected[n] = e.selected[n];
       
    20     }
       
    21     edges = e.edges;
       
    22     covered_edges = e.covered_edges;
       
    23   }
       
    24   double getCost() {
       
    25     return (double) (edges - covered_edges);
       
    26   }
       
    27   void mutate() {
       
    28   
       
    29   }
       
    30   void revert() {
       
    31   
       
    32   }
       
    33 };
       
    34 
       
    35 int main() {
       
    36   Graph g;
       
    37   // beolvasas
       
    38   MyEntity ent(g);
       
    39 
       
    40   // kezdeti lefedes generalasa
       
    41   int nn = 0;
       
    42   for (NodeIt n(g); n != INVALID; ++n) {
       
    43     ent.selected[n] = false;
       
    44     nn++;
       
    45   }
       
    46   // k db random node kivalasztasa
       
    47 
       
    48   int i = 0, j = 0;
       
    49   for (EdgeIt e(g); e != INVALID; ++e) {
       
    50     i++;
       
    51     if ((ent.selected[g.source(e)]) || (ent.selected[g.target(e)])) {
       
    52       j++;
       
    53     }
       
    54   }
       
    55   ent.edges = i;
       
    56   ent.covered_edges = j;
       
    57 
       
    58 }