Index: CMakeLists.txt =================================================================== --- CMakeLists.txt (revision 744) +++ CMakeLists.txt (revision 902) @@ -3,4 +3,6 @@ SET(PROJECT_NAME "LEMON") PROJECT(${PROJECT_NAME}) + +INCLUDE(FindPythonInterp) IF(EXISTS ${PROJECT_SOURCE_DIR}/cmake/version.cmake) @@ -10,4 +12,11 @@ ELSE() EXECUTE_PROCESS( + COMMAND ${PYTHON_EXECUTABLE} ./scripts/chg-len.py + WORKING_DIRECTORY ${PROJECT_SOURCE_DIR} + OUTPUT_VARIABLE HG_REVISION_PATH + ERROR_QUIET + OUTPUT_STRIP_TRAILING_WHITESPACE + ) + EXECUTE_PROCESS( COMMAND hg id -i WORKING_DIRECTORY ${PROJECT_SOURCE_DIR} @@ -17,7 +26,13 @@ ) IF(HG_REVISION STREQUAL "") - SET(HG_REVISION "hg-tip") + SET(HG_REVISION_ID "hg-tip") + ELSE() + IF(HG_REVISION_PATH STREQUAL "") + SET(HG_REVISION_ID ${HG_REVISION}) + ELSE() + SET(HG_REVISION_ID ${HG_REVISION_PATH}.${HG_REVISION}) + ENDIF() ENDIF() - SET(LEMON_VERSION ${HG_REVISION} CACHE STRING "LEMON version string.") + SET(LEMON_VERSION ${HG_REVISION_ID} CACHE STRING "LEMON version string.") ENDIF() @@ -32,11 +47,78 @@ FIND_PACKAGE(COIN) +IF(DEFINED ENV{LEMON_CXX_WARNING}) + SET(CXX_WARNING $ENV{LEMON_CXX_WARNING}) +ELSE() + IF(CMAKE_COMPILER_IS_GNUCXX) + SET(CXX_WARNING "-Wall -W -Wunused -Wformat=2 -Wctor-dtor-privacy -Wnon-virtual-dtor -Wno-char-subscripts -Wwrite-strings -Wno-char-subscripts -Wreturn-type -Wcast-qual -Wcast-align -Wsign-promo -Woverloaded-virtual -ansi -fno-strict-aliasing -Wold-style-cast -Wno-unknown-pragmas") + SET(CMAKE_CXX_FLAGS_DEBUG CACHE STRING "-ggdb") + SET(CMAKE_C_FLAGS_DEBUG CACHE STRING "-ggdb") + ELSEIF(MSVC) + # This part is unnecessary 'casue the same is set by the lemon/core.h. + # Still keep it as an example. + SET(CXX_WARNING "/wd4250 /wd4355 /wd4503 /wd4800 /wd4996") + # Suppressed warnings: + # C4250: 'class1' : inherits 'class2::member' via dominance + # C4355: 'this' : used in base member initializer list + # C4503: 'function' : decorated name length exceeded, name was truncated + # C4800: 'type' : forcing value to bool 'true' or 'false' + # (performance warning) + # C4996: 'function': was declared deprecated + ELSE() + SET(CXX_WARNING "-Wall -W") + ENDIF() +ENDIF() +SET(LEMON_CXX_WARNING_FLAGS ${CXX_WARNING} CACHE STRING "LEMON warning flags.") + +SET(CMAKE_CXX_FLAGS "${CMAKE_CXX_FLAGS} ${LEMON_CXX_WARNING_FLAGS}") + +SET( CMAKE_CXX_FLAGS_MAINTAINER "-Werror -ggdb" CACHE STRING + "Flags used by the C++ compiler during maintainer builds." + FORCE ) +SET( CMAKE_C_FLAGS_MAINTAINER "-Werror" CACHE STRING + "Flags used by the C compiler during maintainer builds." + FORCE ) +SET( CMAKE_EXE_LINKER_FLAGS_MAINTAINER + "-Wl,--warn-unresolved-symbols,--warn-once" CACHE STRING + "Flags used for linking binaries during maintainer builds." + FORCE ) +SET( CMAKE_SHARED_LINKER_FLAGS_MAINTAINER + "-Wl,--warn-unresolved-symbols,--warn-once" CACHE STRING + "Flags used by the shared libraries linker during maintainer builds." + FORCE ) +MARK_AS_ADVANCED( + CMAKE_CXX_FLAGS_MAINTAINER + CMAKE_C_FLAGS_MAINTAINER + CMAKE_EXE_LINKER_FLAGS_MAINTAINER + CMAKE_SHARED_LINKER_FLAGS_MAINTAINER ) + +IF(CMAKE_CONFIGURATION_TYPES) + LIST(APPEND CMAKE_CONFIGURATION_TYPES Maintainer) + LIST(REMOVE_DUPLICATES CMAKE_CONFIGURATION_TYPES) + SET(CMAKE_CONFIGURATION_TYPES "${CMAKE_CONFIGURATION_TYPES}" CACHE STRING + "Add the configurations that we need" + FORCE) + endif() + +IF(NOT CMAKE_BUILD_TYPE) + SET(CMAKE_BUILD_TYPE "Release") +ENDIF() + +SET( CMAKE_BUILD_TYPE "${CMAKE_BUILD_TYPE}" CACHE STRING + "Choose the type of build, options are: None(CMAKE_CXX_FLAGS or CMAKE_C_FLAGS used) Debug Release RelWithDebInfo MinSizeRel Maintainer." + FORCE ) + + INCLUDE(CheckTypeSize) CHECK_TYPE_SIZE("long long" LONG_LONG) SET(LEMON_HAVE_LONG_LONG ${HAVE_LONG_LONG}) -INCLUDE(FindPythonInterp) - ENABLE_TESTING() + +IF(${CMAKE_BUILD_TYPE} STREQUAL "Maintainer") + ADD_CUSTOM_TARGET(check ALL COMMAND ${CMAKE_CTEST_COMMAND}) +ELSE() + ADD_CUSTOM_TARGET(check COMMAND ${CMAKE_CTEST_COMMAND}) +ENDIF() ADD_SUBDIRECTORY(lemon) @@ -65,5 +147,5 @@ ENDIF() -IF(${CMAKE_SOURCE_DIR} STREQUAL ${PROJECT_SOURCE_DIR} AND WIN32) +IF(${CMAKE_SOURCE_DIR} STREQUAL ${PROJECT_SOURCE_DIR}) SET(CPACK_PACKAGE_NAME ${PROJECT_NAME}) SET(CPACK_PACKAGE_VENDOR "EGRES") Index: lemon/network_simplex.h =================================================================== --- lemon/network_simplex.h (revision 889) +++ lemon/network_simplex.h (revision 896) @@ -167,6 +167,7 @@ typedef std::vector ValueVector; typedef std::vector CostVector; - typedef std::vector BoolVector; - // Note: vector is used instead of vector for efficiency reasons + typedef std::vector CharVector; + // Note: vector is used instead of vector and + // vector for efficiency reasons // State constants for arcs @@ -177,7 +178,9 @@ }; - typedef std::vector StateVector; - // Note: vector is used instead of vector for - // efficiency reasons + // Direction constants for tree arcs + enum ArcDirection { + DIR_DOWN = -1, + DIR_UP = 1 + }; private: @@ -218,13 +221,11 @@ IntVector _succ_num; IntVector _last_succ; + CharVector _pred_dir; + CharVector _state; IntVector _dirty_revs; - BoolVector _forward; - StateVector _state; int _root; // Temporary data used in the current pivot iteration int in_arc, join, u_in, v_in, u_out, v_out; - int first, second, right, last; - int stem, par_stem, new_stem; Value delta; @@ -251,5 +252,5 @@ const IntVector &_target; const CostVector &_cost; - const StateVector &_state; + const CharVector &_state; const CostVector &_pi; int &_in_arc; @@ -303,5 +304,5 @@ const IntVector &_target; const CostVector &_cost; - const StateVector &_state; + const CharVector &_state; const CostVector &_pi; int &_in_arc; @@ -342,5 +343,5 @@ const IntVector &_target; const CostVector &_cost; - const StateVector &_state; + const CharVector &_state; const CostVector &_pi; int &_in_arc; @@ -415,5 +416,5 @@ const IntVector &_target; const CostVector &_cost; - const StateVector &_state; + const CharVector &_state; const CostVector &_pi; int &_in_arc; @@ -518,5 +519,5 @@ const IntVector &_target; const CostVector &_cost; - const StateVector &_state; + const CharVector &_state; const CostVector &_pi; int &_in_arc; @@ -571,9 +572,11 @@ // Check the current candidate list int e; + Cost c; for (int i = 0; i != _curr_length; ++i) { e = _candidates[i]; - _cand_cost[e] = _state[e] * - (_cost[e] + _pi[_source[e]] - _pi[_target[e]]); - if (_cand_cost[e] >= 0) { + c = _state[e] * (_cost[e] + _pi[_source[e]] - _pi[_target[e]]); + if (c < 0) { + _cand_cost[e] = c; + } else { _candidates[i--] = _candidates[--_curr_length]; } @@ -585,7 +588,7 @@ for (e = _next_arc; e != _search_arc_num; ++e) { - _cand_cost[e] = _state[e] * - (_cost[e] + _pi[_source[e]] - _pi[_target[e]]); - if (_cand_cost[e] < 0) { + c = _state[e] * (_cost[e] + _pi[_source[e]] - _pi[_target[e]]); + if (c < 0) { + _cand_cost[e] = c; _candidates[_curr_length++] = e; } @@ -634,9 +637,10 @@ /// /// \param graph The digraph the algorithm runs on. - /// \param arc_mixing Indicate if the arcs have to be stored in a + /// \param arc_mixing Indicate if the arcs will be stored in a /// mixed order in the internal data structure. - /// In special cases, it could lead to better overall performance, - /// but it is usually slower. Therefore it is disabled by default. - NetworkSimplex(const GR& graph, bool arc_mixing = false) : + /// In general, it leads to similar performance as using the original + /// arc order, but it makes the algorithm more robust and in special + /// cases, even significantly faster. Therefore, it is enabled by default. + NetworkSimplex(const GR& graph, bool arc_mixing = true) : _graph(graph), _node_id(graph), _arc_id(graph), _arc_mixing(arc_mixing), @@ -914,5 +918,5 @@ _parent.resize(all_node_num); _pred.resize(all_node_num); - _forward.resize(all_node_num); + _pred_dir.resize(all_node_num); _thread.resize(all_node_num); _rev_thread.resize(all_node_num); @@ -928,5 +932,5 @@ if (_arc_mixing) { // Store the arcs in a mixed order - int k = std::max(int(std::sqrt(double(_arc_num))), 10); + const int skip = std::max(_arc_num / _node_num, 3); int i = 0, j = 0; for (ArcIt a(_graph); a != INVALID; ++a) { @@ -934,5 +938,5 @@ _source[i] = _node_id[_graph.source(a)]; _target[i] = _node_id[_graph.target(a)]; - if ((i += k) >= _arc_num) i = ++j; + if ((i += skip) >= _arc_num) i = ++j; } } else { @@ -1117,5 +1121,5 @@ _state[e] = STATE_TREE; if (_supply[u] >= 0) { - _forward[u] = true; + _pred_dir[u] = DIR_UP; _pi[u] = 0; _source[e] = u; @@ -1124,5 +1128,5 @@ _cost[e] = 0; } else { - _forward[u] = false; + _pred_dir[u] = DIR_DOWN; _pi[u] = ART_COST; _source[e] = _root; @@ -1144,5 +1148,5 @@ _last_succ[u] = u; if (_supply[u] >= 0) { - _forward[u] = true; + _pred_dir[u] = DIR_UP; _pi[u] = 0; _pred[u] = e; @@ -1154,5 +1158,5 @@ _state[e] = STATE_TREE; } else { - _forward[u] = false; + _pred_dir[u] = DIR_DOWN; _pi[u] = ART_COST; _pred[u] = f; @@ -1185,5 +1189,5 @@ _last_succ[u] = u; if (_supply[u] <= 0) { - _forward[u] = false; + _pred_dir[u] = DIR_DOWN; _pi[u] = 0; _pred[u] = e; @@ -1195,5 +1199,5 @@ _state[e] = STATE_TREE; } else { - _forward[u] = true; + _pred_dir[u] = DIR_UP; _pi[u] = -ART_COST; _pred[u] = f; @@ -1238,4 +1242,5 @@ // Initialize first and second nodes according to the direction // of the cycle + int first, second; if (_state[in_arc] == STATE_LOWER) { first = _source[in_arc]; @@ -1247,12 +1252,15 @@ delta = _cap[in_arc]; int result = 0; - Value d; + Value c, d; int e; - // Search the cycle along the path form the first node to the root + // Search the cycle form the first node to the join node for (int u = first; u != join; u = _parent[u]) { e = _pred[u]; - d = _forward[u] ? - _flow[e] : (_cap[e] >= MAX ? INF : _cap[e] - _flow[e]); + d = _flow[e]; + if (_pred_dir[u] == DIR_DOWN) { + c = _cap[e]; + d = c >= MAX ? INF : c - d; + } if (d < delta) { delta = d; @@ -1261,9 +1269,13 @@ } } - // Search the cycle along the path form the second node to the root + + // Search the cycle form the second node to the join node for (int u = second; u != join; u = _parent[u]) { e = _pred[u]; - d = _forward[u] ? - (_cap[e] >= MAX ? INF : _cap[e] - _flow[e]) : _flow[e]; + d = _flow[e]; + if (_pred_dir[u] == DIR_UP) { + c = _cap[e]; + d = c >= MAX ? INF : c - d; + } if (d <= delta) { delta = d; @@ -1290,8 +1302,8 @@ _flow[in_arc] += val; for (int u = _source[in_arc]; u != join; u = _parent[u]) { - _flow[_pred[u]] += _forward[u] ? -val : val; + _flow[_pred[u]] -= _pred_dir[u] * val; } for (int u = _target[in_arc]; u != join; u = _parent[u]) { - _flow[_pred[u]] += _forward[u] ? val : -val; + _flow[_pred[u]] += _pred_dir[u] * val; } } @@ -1308,5 +1320,4 @@ // Update the tree structure void updateTreeStructure() { - int u, w; int old_rev_thread = _rev_thread[u_out]; int old_succ_num = _succ_num[u_out]; @@ -1314,122 +1325,127 @@ v_out = _parent[u_out]; - u = _last_succ[u_in]; // the last successor of u_in - right = _thread[u]; // the node after it - - // Handle the case when old_rev_thread equals to v_in - // (it also means that join and v_out coincide) - if (old_rev_thread == v_in) { - last = _thread[_last_succ[u_out]]; + // Check if u_in and u_out coincide + if (u_in == u_out) { + // Update _parent, _pred, _pred_dir + _parent[u_in] = v_in; + _pred[u_in] = in_arc; + _pred_dir[u_in] = u_in == _source[in_arc] ? DIR_UP : DIR_DOWN; + + // Update _thread and _rev_thread + if (_thread[v_in] != u_out) { + int after = _thread[old_last_succ]; + _thread[old_rev_thread] = after; + _rev_thread[after] = old_rev_thread; + after = _thread[v_in]; + _thread[v_in] = u_out; + _rev_thread[u_out] = v_in; + _thread[old_last_succ] = after; + _rev_thread[after] = old_last_succ; + } } else { - last = _thread[v_in]; - } - - // Update _thread and _parent along the stem nodes (i.e. the nodes - // between u_in and u_out, whose parent have to be changed) - _thread[v_in] = stem = u_in; - _dirty_revs.clear(); - _dirty_revs.push_back(v_in); - par_stem = v_in; - while (stem != u_out) { - // Insert the next stem node into the thread list - new_stem = _parent[stem]; - _thread[u] = new_stem; - _dirty_revs.push_back(u); - - // Remove the subtree of stem from the thread list - w = _rev_thread[stem]; - _thread[w] = right; - _rev_thread[right] = w; - - // Change the parent node and shift stem nodes - _parent[stem] = par_stem; - par_stem = stem; - stem = new_stem; - - // Update u and right - u = _last_succ[stem] == _last_succ[par_stem] ? - _rev_thread[par_stem] : _last_succ[stem]; - right = _thread[u]; - } - _parent[u_out] = par_stem; - _thread[u] = last; - _rev_thread[last] = u; - _last_succ[u_out] = u; - - // Remove the subtree of u_out from the thread list except for - // the case when old_rev_thread equals to v_in - // (it also means that join and v_out coincide) - if (old_rev_thread != v_in) { - _thread[old_rev_thread] = right; - _rev_thread[right] = old_rev_thread; - } - - // Update _rev_thread using the new _thread values - for (int i = 0; i != int(_dirty_revs.size()); ++i) { - u = _dirty_revs[i]; - _rev_thread[_thread[u]] = u; - } - - // Update _pred, _forward, _last_succ and _succ_num for the - // stem nodes from u_out to u_in - int tmp_sc = 0, tmp_ls = _last_succ[u_out]; - u = u_out; - while (u != u_in) { - w = _parent[u]; - _pred[u] = _pred[w]; - _forward[u] = !_forward[w]; - tmp_sc += _succ_num[u] - _succ_num[w]; - _succ_num[u] = tmp_sc; - _last_succ[w] = tmp_ls; - u = w; - } - _pred[u_in] = in_arc; - _forward[u_in] = (u_in == _source[in_arc]); - _succ_num[u_in] = old_succ_num; - - // Set limits for updating _last_succ form v_in and v_out - // towards the root - int up_limit_in = -1; - int up_limit_out = -1; - if (_last_succ[join] == v_in) { - up_limit_out = join; - } else { - up_limit_in = join; + // Handle the case when old_rev_thread equals to v_in + // (it also means that join and v_out coincide) + int thread_continue = old_rev_thread == v_in ? + _thread[old_last_succ] : _thread[v_in]; + + // Update _thread and _parent along the stem nodes (i.e. the nodes + // between u_in and u_out, whose parent have to be changed) + int stem = u_in; // the current stem node + int par_stem = v_in; // the new parent of stem + int next_stem; // the next stem node + int last = _last_succ[u_in]; // the last successor of stem + int before, after = _thread[last]; + _thread[v_in] = u_in; + _dirty_revs.clear(); + _dirty_revs.push_back(v_in); + while (stem != u_out) { + // Insert the next stem node into the thread list + next_stem = _parent[stem]; + _thread[last] = next_stem; + _dirty_revs.push_back(last); + + // Remove the subtree of stem from the thread list + before = _rev_thread[stem]; + _thread[before] = after; + _rev_thread[after] = before; + + // Change the parent node and shift stem nodes + _parent[stem] = par_stem; + par_stem = stem; + stem = next_stem; + + // Update last and after + last = _last_succ[stem] == _last_succ[par_stem] ? + _rev_thread[par_stem] : _last_succ[stem]; + after = _thread[last]; + } + _parent[u_out] = par_stem; + _thread[last] = thread_continue; + _rev_thread[thread_continue] = last; + _last_succ[u_out] = last; + + // Remove the subtree of u_out from the thread list except for + // the case when old_rev_thread equals to v_in + if (old_rev_thread != v_in) { + _thread[old_rev_thread] = after; + _rev_thread[after] = old_rev_thread; + } + + // Update _rev_thread using the new _thread values + for (int i = 0; i != int(_dirty_revs.size()); ++i) { + int u = _dirty_revs[i]; + _rev_thread[_thread[u]] = u; + } + + // Update _pred, _pred_dir, _last_succ and _succ_num for the + // stem nodes from u_out to u_in + int tmp_sc = 0, tmp_ls = _last_succ[u_out]; + for (int u = u_out, p = _parent[u]; u != u_in; u = p, p = _parent[u]) { + _pred[u] = _pred[p]; + _pred_dir[u] = -_pred_dir[p]; + tmp_sc += _succ_num[u] - _succ_num[p]; + _succ_num[u] = tmp_sc; + _last_succ[p] = tmp_ls; + } + _pred[u_in] = in_arc; + _pred_dir[u_in] = u_in == _source[in_arc] ? DIR_UP : DIR_DOWN; + _succ_num[u_in] = old_succ_num; } // Update _last_succ from v_in towards the root - for (u = v_in; u != up_limit_in && _last_succ[u] == v_in; - u = _parent[u]) { - _last_succ[u] = _last_succ[u_out]; - } + int up_limit_out = _last_succ[join] == v_in ? join : -1; + int last_succ_out = _last_succ[u_out]; + for (int u = v_in; u != -1 && _last_succ[u] == v_in; u = _parent[u]) { + _last_succ[u] = last_succ_out; + } + // Update _last_succ from v_out towards the root if (join != old_rev_thread && v_in != old_rev_thread) { - for (u = v_out; u != up_limit_out && _last_succ[u] == old_last_succ; + for (int u = v_out; u != up_limit_out && _last_succ[u] == old_last_succ; u = _parent[u]) { _last_succ[u] = old_rev_thread; } - } else { - for (u = v_out; u != up_limit_out && _last_succ[u] == old_last_succ; + } + else if (last_succ_out != old_last_succ) { + for (int u = v_out; u != up_limit_out && _last_succ[u] == old_last_succ; u = _parent[u]) { - _last_succ[u] = _last_succ[u_out]; + _last_succ[u] = last_succ_out; } } // Update _succ_num from v_in to join - for (u = v_in; u != join; u = _parent[u]) { + for (int u = v_in; u != join; u = _parent[u]) { _succ_num[u] += old_succ_num; } // Update _succ_num from v_out to join - for (u = v_out; u != join; u = _parent[u]) { + for (int u = v_out; u != join; u = _parent[u]) { _succ_num[u] -= old_succ_num; } } - // Update potentials + // Update potentials in the subtree that has been moved void updatePotential() { - Cost sigma = _forward[u_in] ? - _pi[v_in] - _pi[u_in] - _cost[_pred[u_in]] : - _pi[v_in] - _pi[u_in] + _cost[_pred[u_in]]; - // Update potentials in the subtree, which has been moved + Cost sigma = _pi[v_in] - _pi[u_in] - + _pred_dir[u_in] * _cost[in_arc]; int end = _thread[_last_succ[u_in]]; for (int u = u_in; u != end; u = _thread[u]) { Index: test/CMakeLists.txt =================================================================== --- test/CMakeLists.txt (revision 904) +++ test/CMakeLists.txt (revision 905) @@ -119,6 +119,11 @@ FOREACH(TEST_NAME ${TESTS}) - ADD_EXECUTABLE(${TEST_NAME} ${TEST_NAME}.cc) + IF(${CMAKE_BUILD_TYPE} STREQUAL "Maintainer") + ADD_EXECUTABLE(${TEST_NAME} ${TEST_NAME}.cc) + ELSE() + ADD_EXECUTABLE(${TEST_NAME} EXCLUDE_FROM_ALL ${TEST_NAME}.cc) + ENDIF() TARGET_LINK_LIBRARIES(${TEST_NAME} lemon) ADD_TEST(${TEST_NAME} ${TEST_NAME}) + ADD_DEPENDENCIES(check ${TEST_NAME}) ENDFOREACH()