| author | klao |
| Sun, 09 Jan 2005 23:21:52 +0000 | |
| changeset 1066 | 520769d825f2 |
| 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 |
} |