Changeset 775:e2bdd1a988f3 in lemon for lemon/network_simplex.h
 Timestamp:
 07/02/09 17:36:29 (10 years ago)
 Branch:
 default
 Phase:
 public
 File:

 1 edited
Legend:
 Unmodified
 Added
 Removed

lemon/network_simplex.h
r774 r775 626 626 /// 627 627 /// \param graph The digraph the algorithm runs on. 628 NetworkSimplex(const GR& graph) : 628 /// \param arc_mixing Indicate if the arcs have to be stored in a 629 /// mixed order in the internal data structure. 630 /// In special cases, it could lead to better overall performance, 631 /// but it is usually slower. Therefore it is disabled by default. 632 NetworkSimplex(const GR& graph, bool arc_mixing = false) : 629 633 _graph(graph), _node_id(graph), _arc_id(graph), 630 634 INF(std::numeric_limits<Value>::has_infinity ? … … 664 668 _state.resize(max_arc_num); 665 669 666 // Copy the graph (store the arcs in a mixed order)670 // Copy the graph 667 671 int i = 0; 668 672 for (NodeIt n(_graph); n != INVALID; ++n, ++i) { 669 673 _node_id[n] = i; 670 674 } 671 int k = std::max(int(std::sqrt(double(_arc_num))), 10); 672 i = 0; 673 for (ArcIt a(_graph); a != INVALID; ++a) { 674 _arc_id[a] = i; 675 _source[i] = _node_id[_graph.source(a)]; 676 _target[i] = _node_id[_graph.target(a)]; 677 if ((i += k) >= _arc_num) i = (i % k) + 1; 675 if (arc_mixing) { 676 // Store the arcs in a mixed order 677 int k = std::max(int(std::sqrt(double(_arc_num))), 10); 678 int i = 0, j = 0; 679 for (ArcIt a(_graph); a != INVALID; ++a) { 680 _arc_id[a] = i; 681 _source[i] = _node_id[_graph.source(a)]; 682 _target[i] = _node_id[_graph.target(a)]; 683 if ((i += k) >= _arc_num) i = ++j; 684 } 685 } else { 686 // Store the arcs in the original order 687 int i = 0; 688 for (ArcIt a(_graph); a != INVALID; ++a, ++i) { 689 _arc_id[a] = i; 690 _source[i] = _node_id[_graph.source(a)]; 691 _target[i] = _node_id[_graph.target(a)]; 692 } 678 693 } 679 694
Note: See TracChangeset
for help on using the changeset viewer.