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