631 /// mixed order in the internal data structure. |
632 /// mixed order in the internal data structure. |
632 /// In special cases, it could lead to better overall performance, |
633 /// In special cases, it could lead to better overall performance, |
633 /// but it is usually slower. Therefore it is disabled by default. |
634 /// but it is usually slower. Therefore it is disabled by default. |
634 NetworkSimplex(const GR& graph, bool arc_mixing = false) : |
635 NetworkSimplex(const GR& graph, bool arc_mixing = false) : |
635 _graph(graph), _node_id(graph), _arc_id(graph), |
636 _graph(graph), _node_id(graph), _arc_id(graph), |
|
637 _arc_mixing(arc_mixing), |
636 MAX(std::numeric_limits<Value>::max()), |
638 MAX(std::numeric_limits<Value>::max()), |
637 INF(std::numeric_limits<Value>::has_infinity ? |
639 INF(std::numeric_limits<Value>::has_infinity ? |
638 std::numeric_limits<Value>::infinity() : MAX) |
640 std::numeric_limits<Value>::infinity() : MAX) |
639 { |
641 { |
640 // Check the number types |
642 // Check the number types |
641 LEMON_ASSERT(std::numeric_limits<Value>::is_signed, |
643 LEMON_ASSERT(std::numeric_limits<Value>::is_signed, |
642 "The flow type of NetworkSimplex must be signed"); |
644 "The flow type of NetworkSimplex must be signed"); |
643 LEMON_ASSERT(std::numeric_limits<Cost>::is_signed, |
645 LEMON_ASSERT(std::numeric_limits<Cost>::is_signed, |
644 "The cost type of NetworkSimplex must be signed"); |
646 "The cost type of NetworkSimplex must be signed"); |
645 |
647 |
646 // Resize vectors |
648 // Reset data structures |
647 _node_num = countNodes(_graph); |
|
648 _arc_num = countArcs(_graph); |
|
649 int all_node_num = _node_num + 1; |
|
650 int max_arc_num = _arc_num + 2 * _node_num; |
|
651 |
|
652 _source.resize(max_arc_num); |
|
653 _target.resize(max_arc_num); |
|
654 |
|
655 _lower.resize(_arc_num); |
|
656 _upper.resize(_arc_num); |
|
657 _cap.resize(max_arc_num); |
|
658 _cost.resize(max_arc_num); |
|
659 _supply.resize(all_node_num); |
|
660 _flow.resize(max_arc_num); |
|
661 _pi.resize(all_node_num); |
|
662 |
|
663 _parent.resize(all_node_num); |
|
664 _pred.resize(all_node_num); |
|
665 _forward.resize(all_node_num); |
|
666 _thread.resize(all_node_num); |
|
667 _rev_thread.resize(all_node_num); |
|
668 _succ_num.resize(all_node_num); |
|
669 _last_succ.resize(all_node_num); |
|
670 _state.resize(max_arc_num); |
|
671 |
|
672 // Copy the graph |
|
673 int i = 0; |
|
674 for (NodeIt n(_graph); n != INVALID; ++n, ++i) { |
|
675 _node_id[n] = i; |
|
676 } |
|
677 if (arc_mixing) { |
|
678 // Store the arcs in a mixed order |
|
679 int k = std::max(int(std::sqrt(double(_arc_num))), 10); |
|
680 int i = 0, j = 0; |
|
681 for (ArcIt a(_graph); a != INVALID; ++a) { |
|
682 _arc_id[a] = i; |
|
683 _source[i] = _node_id[_graph.source(a)]; |
|
684 _target[i] = _node_id[_graph.target(a)]; |
|
685 if ((i += k) >= _arc_num) i = ++j; |
|
686 } |
|
687 } else { |
|
688 // Store the arcs in the original order |
|
689 int i = 0; |
|
690 for (ArcIt a(_graph); a != INVALID; ++a, ++i) { |
|
691 _arc_id[a] = i; |
|
692 _source[i] = _node_id[_graph.source(a)]; |
|
693 _target[i] = _node_id[_graph.target(a)]; |
|
694 } |
|
695 } |
|
696 |
|
697 // Reset parameters |
|
698 reset(); |
649 reset(); |
699 } |
650 } |
700 |
651 |
701 /// \name Parameters |
652 /// \name Parameters |
702 /// The parameters of the algorithm can be specified using these |
653 /// The parameters of the algorithm can be specified using these |
840 /// NetworkSimplex<ListDigraph> ns(graph); |
791 /// NetworkSimplex<ListDigraph> ns(graph); |
841 /// ns.lowerMap(lower).upperMap(upper).costMap(cost) |
792 /// ns.lowerMap(lower).upperMap(upper).costMap(cost) |
842 /// .supplyMap(sup).run(); |
793 /// .supplyMap(sup).run(); |
843 /// \endcode |
794 /// \endcode |
844 /// |
795 /// |
845 /// This function can be called more than once. All the parameters |
796 /// This function can be called more than once. All the given parameters |
846 /// that have been given are kept for the next call, unless |
797 /// are kept for the next call, unless \ref resetParams() or \ref reset() |
847 /// \ref reset() is called, thus only the modified parameters |
798 /// is used, thus only the modified parameters have to be set again. |
848 /// have to be set again. See \ref reset() for examples. |
799 /// If the underlying digraph was also modified after the construction |
849 /// However, the underlying digraph must not be modified after this |
800 /// of the class (or the last \ref reset() call), then the \ref reset() |
850 /// class have been constructed, since it copies and extends the graph. |
801 /// function must be called. |
851 /// |
802 /// |
852 /// \param pivot_rule The pivot rule that will be used during the |
803 /// \param pivot_rule The pivot rule that will be used during the |
853 /// algorithm. For more information, see \ref PivotRule. |
804 /// algorithm. For more information, see \ref PivotRule. |
854 /// |
805 /// |
855 /// \return \c INFEASIBLE if no feasible flow exists, |
806 /// \return \c INFEASIBLE if no feasible flow exists, |
859 /// \n \c UNBOUNDED if the objective function of the problem is |
810 /// \n \c UNBOUNDED if the objective function of the problem is |
860 /// unbounded, i.e. there is a directed cycle having negative total |
811 /// unbounded, i.e. there is a directed cycle having negative total |
861 /// cost and infinite upper bound. |
812 /// cost and infinite upper bound. |
862 /// |
813 /// |
863 /// \see ProblemType, PivotRule |
814 /// \see ProblemType, PivotRule |
|
815 /// \see resetParams(), reset() |
864 ProblemType run(PivotRule pivot_rule = BLOCK_SEARCH) { |
816 ProblemType run(PivotRule pivot_rule = BLOCK_SEARCH) { |
865 if (!init()) return INFEASIBLE; |
817 if (!init()) return INFEASIBLE; |
866 return start(pivot_rule); |
818 return start(pivot_rule); |
867 } |
819 } |
868 |
820 |
870 /// |
822 /// |
871 /// This function resets all the paramaters that have been given |
823 /// This function resets all the paramaters that have been given |
872 /// before using functions \ref lowerMap(), \ref upperMap(), |
824 /// before using functions \ref lowerMap(), \ref upperMap(), |
873 /// \ref costMap(), \ref supplyMap(), \ref stSupply(), \ref supplyType(). |
825 /// \ref costMap(), \ref supplyMap(), \ref stSupply(), \ref supplyType(). |
874 /// |
826 /// |
875 /// It is useful for multiple run() calls. If this function is not |
827 /// It is useful for multiple \ref run() calls. Basically, all the given |
876 /// used, all the parameters given before are kept for the next |
828 /// parameters are kept for the next \ref run() call, unless |
877 /// \ref run() call. |
829 /// \ref resetParams() or \ref reset() is used. |
878 /// However, the underlying digraph must not be modified after this |
830 /// If the underlying digraph was also modified after the construction |
879 /// class have been constructed, since it copies and extends the graph. |
831 /// of the class or the last \ref reset() call, then the \ref reset() |
|
832 /// function must be used, otherwise \ref resetParams() is sufficient. |
880 /// |
833 /// |
881 /// For example, |
834 /// For example, |
882 /// \code |
835 /// \code |
883 /// NetworkSimplex<ListDigraph> ns(graph); |
836 /// NetworkSimplex<ListDigraph> ns(graph); |
884 /// |
837 /// |
885 /// // First run |
838 /// // First run |
886 /// ns.lowerMap(lower).upperMap(upper).costMap(cost) |
839 /// ns.lowerMap(lower).upperMap(upper).costMap(cost) |
887 /// .supplyMap(sup).run(); |
840 /// .supplyMap(sup).run(); |
888 /// |
841 /// |
889 /// // Run again with modified cost map (reset() is not called, |
842 /// // Run again with modified cost map (resetParams() is not called, |
890 /// // so only the cost map have to be set again) |
843 /// // so only the cost map have to be set again) |
891 /// cost[e] += 100; |
844 /// cost[e] += 100; |
892 /// ns.costMap(cost).run(); |
845 /// ns.costMap(cost).run(); |
893 /// |
846 /// |
894 /// // Run again from scratch using reset() |
847 /// // Run again from scratch using resetParams() |
895 /// // (the lower bounds will be set to zero on all arcs) |
848 /// // (the lower bounds will be set to zero on all arcs) |
896 /// ns.reset(); |
849 /// ns.resetParams(); |
897 /// ns.upperMap(capacity).costMap(cost) |
850 /// ns.upperMap(capacity).costMap(cost) |
898 /// .supplyMap(sup).run(); |
851 /// .supplyMap(sup).run(); |
899 /// \endcode |
852 /// \endcode |
900 /// |
853 /// |
901 /// \return <tt>(*this)</tt> |
854 /// \return <tt>(*this)</tt> |
902 NetworkSimplex& reset() { |
855 /// |
|
856 /// \see reset(), run() |
|
857 NetworkSimplex& resetParams() { |
903 for (int i = 0; i != _node_num; ++i) { |
858 for (int i = 0; i != _node_num; ++i) { |
904 _supply[i] = 0; |
859 _supply[i] = 0; |
905 } |
860 } |
906 for (int i = 0; i != _arc_num; ++i) { |
861 for (int i = 0; i != _arc_num; ++i) { |
907 _lower[i] = 0; |
862 _lower[i] = 0; |
911 _have_lower = false; |
866 _have_lower = false; |
912 _stype = GEQ; |
867 _stype = GEQ; |
913 return *this; |
868 return *this; |
914 } |
869 } |
915 |
870 |
|
871 /// \brief Reset the internal data structures and all the parameters |
|
872 /// that have been given before. |
|
873 /// |
|
874 /// This function resets the internal data structures and all the |
|
875 /// paramaters that have been given before using functions \ref lowerMap(), |
|
876 /// \ref upperMap(), \ref costMap(), \ref supplyMap(), \ref stSupply(), |
|
877 /// \ref supplyType(). |
|
878 /// |
|
879 /// It is useful for multiple \ref run() calls. Basically, all the given |
|
880 /// parameters are kept for the next \ref run() call, unless |
|
881 /// \ref resetParams() or \ref reset() is used. |
|
882 /// If the underlying digraph was also modified after the construction |
|
883 /// of the class or the last \ref reset() call, then the \ref reset() |
|
884 /// function must be used, otherwise \ref resetParams() is sufficient. |
|
885 /// |
|
886 /// See \ref resetParams() for examples. |
|
887 /// |
|
888 /// \return <tt>(*this)</tt> |
|
889 /// |
|
890 /// \see resetParams(), run() |
|
891 NetworkSimplex& reset() { |
|
892 // Resize vectors |
|
893 _node_num = countNodes(_graph); |
|
894 _arc_num = countArcs(_graph); |
|
895 int all_node_num = _node_num + 1; |
|
896 int max_arc_num = _arc_num + 2 * _node_num; |
|
897 |
|
898 _source.resize(max_arc_num); |
|
899 _target.resize(max_arc_num); |
|
900 |
|
901 _lower.resize(_arc_num); |
|
902 _upper.resize(_arc_num); |
|
903 _cap.resize(max_arc_num); |
|
904 _cost.resize(max_arc_num); |
|
905 _supply.resize(all_node_num); |
|
906 _flow.resize(max_arc_num); |
|
907 _pi.resize(all_node_num); |
|
908 |
|
909 _parent.resize(all_node_num); |
|
910 _pred.resize(all_node_num); |
|
911 _forward.resize(all_node_num); |
|
912 _thread.resize(all_node_num); |
|
913 _rev_thread.resize(all_node_num); |
|
914 _succ_num.resize(all_node_num); |
|
915 _last_succ.resize(all_node_num); |
|
916 _state.resize(max_arc_num); |
|
917 |
|
918 // Copy the graph |
|
919 int i = 0; |
|
920 for (NodeIt n(_graph); n != INVALID; ++n, ++i) { |
|
921 _node_id[n] = i; |
|
922 } |
|
923 if (_arc_mixing) { |
|
924 // Store the arcs in a mixed order |
|
925 int k = std::max(int(std::sqrt(double(_arc_num))), 10); |
|
926 int i = 0, j = 0; |
|
927 for (ArcIt a(_graph); a != INVALID; ++a) { |
|
928 _arc_id[a] = i; |
|
929 _source[i] = _node_id[_graph.source(a)]; |
|
930 _target[i] = _node_id[_graph.target(a)]; |
|
931 if ((i += k) >= _arc_num) i = ++j; |
|
932 } |
|
933 } else { |
|
934 // Store the arcs in the original order |
|
935 int i = 0; |
|
936 for (ArcIt a(_graph); a != INVALID; ++a, ++i) { |
|
937 _arc_id[a] = i; |
|
938 _source[i] = _node_id[_graph.source(a)]; |
|
939 _target[i] = _node_id[_graph.target(a)]; |
|
940 } |
|
941 } |
|
942 |
|
943 // Reset parameters |
|
944 resetParams(); |
|
945 return *this; |
|
946 } |
|
947 |
916 /// @} |
948 /// @} |
917 |
949 |
918 /// \name Query Functions |
950 /// \name Query Functions |
919 /// The results of the algorithm can be obtained using these |
951 /// The results of the algorithm can be obtained using these |
920 /// functions.\n |
952 /// functions.\n |