equal
deleted
inserted
replaced
1 /* -*- C++ -*- |
1 /* -*- mode: C++; indent-tabs-mode: nil; -*- |
2 * |
2 * |
3 * This file is a part of LEMON, a generic C++ optimization library |
3 * This file is a part of LEMON, a generic C++ optimization library. |
4 * |
4 * |
5 * Copyright (C) 2003-2008 |
5 * Copyright (C) 2003-2010 |
6 * Egervary Jeno Kombinatorikus Optimalizalasi Kutatocsoport |
6 * Egervary Jeno Kombinatorikus Optimalizalasi Kutatocsoport |
7 * (Egervary Research Group on Combinatorial Optimization, EGRES). |
7 * (Egervary Research Group on Combinatorial Optimization, EGRES). |
8 * |
8 * |
9 * Permission to use, modify and distribute this software is granted |
9 * Permission to use, modify and distribute this software is granted |
10 * provided that this copyright notice appears in all copies. For |
10 * provided that this copyright notice appears in all copies. For |
341 /// \return \c true if a directed cycle exists in the digraph. |
341 /// \return \c true if a directed cycle exists in the digraph. |
342 bool findCycleMean() { |
342 bool findCycleMean() { |
343 // Initialization and find strongly connected components |
343 // Initialization and find strongly connected components |
344 init(); |
344 init(); |
345 findComponents(); |
345 findComponents(); |
346 |
346 |
347 // Find the minimum cycle mean in the components |
347 // Find the minimum cycle mean in the components |
348 for (int comp = 0; comp < _comp_num; ++comp) { |
348 for (int comp = 0; comp < _comp_num; ++comp) { |
349 if (!initComponent(comp)) continue; |
349 if (!initComponent(comp)) continue; |
350 processRounds(); |
350 processRounds(); |
351 |
351 |
352 // Update the best cycle (global minimum mean cycle) |
352 // Update the best cycle (global minimum mean cycle) |
353 if ( _curr_found && (!_best_found || |
353 if ( _curr_found && (!_best_found || |
354 _curr_cost * _best_size < _best_cost * _curr_size) ) { |
354 _curr_cost * _best_size < _best_cost * _curr_size) ) { |
355 _best_found = true; |
355 _best_found = true; |
356 _best_cost = _curr_cost; |
356 _best_cost = _curr_cost; |
357 _best_size = _curr_size; |
357 _best_size = _curr_size; |
358 _best_node = _curr_node; |
358 _best_node = _curr_node; |
501 bool initComponent(int comp) { |
501 bool initComponent(int comp) { |
502 _nodes = &(_comp_nodes[comp]); |
502 _nodes = &(_comp_nodes[comp]); |
503 int n = _nodes->size(); |
503 int n = _nodes->size(); |
504 if (n < 1 || (n == 1 && _out_arcs[(*_nodes)[0]].size() == 0)) { |
504 if (n < 1 || (n == 1 && _out_arcs[(*_nodes)[0]].size() == 0)) { |
505 return false; |
505 return false; |
506 } |
506 } |
507 for (int i = 0; i < n; ++i) { |
507 for (int i = 0; i < n; ++i) { |
508 _data[(*_nodes)[i]].resize(n + 1, PathData(INF)); |
508 _data[(*_nodes)[i]].resize(n + 1, PathData(INF)); |
509 } |
509 } |
510 return true; |
510 return true; |
511 } |
511 } |
574 _data[v][k] = PathData(d, e); |
574 _data[v][k] = PathData(d, e); |
575 } |
575 } |
576 } |
576 } |
577 } |
577 } |
578 } |
578 } |
579 |
579 |
580 // Check early termination |
580 // Check early termination |
581 bool checkTermination(int k) { |
581 bool checkTermination(int k) { |
582 typedef std::pair<int, int> Pair; |
582 typedef std::pair<int, int> Pair; |
583 typename GR::template NodeMap<Pair> level(_gr, Pair(-1, 0)); |
583 typename GR::template NodeMap<Pair> level(_gr, Pair(-1, 0)); |
584 typename GR::template NodeMap<LargeCost> pi(_gr); |
584 typename GR::template NodeMap<LargeCost> pi(_gr); |
585 int n = _nodes->size(); |
585 int n = _nodes->size(); |
586 LargeCost cost; |
586 LargeCost cost; |
587 int size; |
587 int size; |
588 Node u; |
588 Node u; |
589 |
589 |
590 // Search for cycles that are already found |
590 // Search for cycles that are already found |
591 _curr_found = false; |
591 _curr_found = false; |
592 for (int i = 0; i < n; ++i) { |
592 for (int i = 0; i < n; ++i) { |
593 u = (*_nodes)[i]; |
593 u = (*_nodes)[i]; |
594 if (_data[u][k].dist == INF) continue; |
594 if (_data[u][k].dist == INF) continue; |
605 _curr_found = true; |
605 _curr_found = true; |
606 } |
606 } |
607 } |
607 } |
608 level[u] = Pair(i, j); |
608 level[u] = Pair(i, j); |
609 if (j != 0) { |
609 if (j != 0) { |
610 u = _gr.source(_data[u][j].pred); |
610 u = _gr.source(_data[u][j].pred); |
611 } |
611 } |
612 } |
612 } |
613 } |
613 } |
614 |
614 |
615 // If at least one cycle is found, check the optimality condition |
615 // If at least one cycle is found, check the optimality condition |
616 LargeCost d; |
616 LargeCost d; |