author | alpar |
Mon, 03 Jan 2005 16:23:47 +0000 | |
changeset 1043 | 52a2201a88e9 |
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 |
} |