Mercuriallemon-0.x / comparison
summary | shortlog | changelog | graph | tags | bookmarks | branches | files | changeset | file | latest | revisions | annotate | diff | comparison | raw | help
lemon/suurballe.h
changeset 1681 84e43c7ca1e3
parent 1435 8e85e6bbefdf
child 1875 98698b69a902
equal deleted inserted replaced
0:e9628cd434be 1:032da6d04442 
    37   /// The class \ref lemon::Suurballe implements
 
    37   /// The class \ref lemon::Suurballe implements
 
    38   /// an algorithm for finding k edge-disjoint paths
 
    38   /// an algorithm for finding k edge-disjoint paths
 
    39   /// from a given source node to a given target node in an
 
    39   /// from a given source node to a given target node in an
 
    40   /// edge-weighted directed graph having minimal total weight (length).
 
    40   /// edge-weighted directed graph having minimal total weight (length).
 
    41   ///
 
    41   ///
 
    42   ///\warning Length values should be nonnegative.
 
    42   ///\warning Length values should be nonnegative!
 
    43   /// 
    43   /// 
    44   ///\param Graph The directed graph type the algorithm runs on.
 
    44   ///\param Graph The directed graph type the algorithm runs on.
 
    45   ///\param LengthMap The type of the length map (values should be nonnegative).
 
    45   ///\param LengthMap The type of the length map (values should be nonnegative).
 
    46   ///
 
    46   ///
 
    47   ///\note It it questionable whether it is correct to call this method after
 
    47   ///\note It it questionable whether it is correct to call this method after
 
   119 
   119 
   120       for(typename Graph::EdgeIt e(G); e!=INVALID; ++e) 
   120       for(typename Graph::EdgeIt e(G); e!=INVALID; ++e) 
   121 	reversed[e] = min_cost_flow.getFlow()[e];
 
   121 	reversed[e] = min_cost_flow.getFlow()[e];
 
   122       
   122       
   123       paths.clear();
 
   123       paths.clear();
 
   124       //total_length=0;
 
       
   125       paths.resize(k);
 
   124       paths.resize(k);
 
   126       for (int j=0; j<i; ++j){
 
   125       for (int j=0; j<i; ++j){
 
   127 	Node n=s;
 
   126 	Node n=s;
 
   128 
   127 
   129 	while (n!=t){
 
   128 	while (n!=t){
 
   133 	  while (!reversed[e]){
 
   132 	  while (!reversed[e]){
 
   134 	    ++e;
 
   133 	    ++e;
 
   135 	  }
 
   134 	  }
 
   136 	  n = G.target(e);
 
   135 	  n = G.target(e);
 
   137 	  paths[j].push_back(e);
 
   136 	  paths[j].push_back(e);
 
   138 	  //total_length += length[e];
 
       
   139 	  reversed[e] = 1-reversed[e];
 
   137 	  reversed[e] = 1-reversed[e];
 
   140 	}
 
   138 	}
 
   141 	
   139 	
   142       }
 
   140       }
 
   143       return i;
 
   141       return i;
 
   164 
   162 
   165     ///Checks whether the complementary slackness holds.
 
   163     ///Checks whether the complementary slackness holds.
 
   166 
   164 
   167     ///This function checks, whether the given solution is optimal.
 
   165     ///This function checks, whether the given solution is optimal.
 
   168     ///Currently this function only checks optimality,
 
   166     ///Currently this function only checks optimality,
 
   169     ///doesn't bother with feasibility
 
   167     ///doesn't bother with feasibility.
 
   170     ///It is meant for testing purposes.
 
   168     ///It is meant for testing purposes.
 
   171     bool checkComplementarySlackness(){
 
   169     bool checkComplementarySlackness(){
 
   172       return min_cost_flow.checkComplementarySlackness();
 
   170       return min_cost_flow.checkComplementarySlackness();
 
   173     }
 
   171     }
 
   174 
   172 
   175     ///Read the found paths.
 
   173     ///Read the found paths.
 
   176     
   174     
   177     ///This function gives back the \c j-th path in argument p.
 
   175     ///This function gives back the \c j-th path in argument p.
 
   178     ///Assumes that \c run() has been run and nothing changed since then.
 
   176     ///Assumes that \c run() has been run and nothing has changed since then.
 
   179     /// \warning It is assumed that \c p is constructed to
 
   177     /// \warning It is assumed that \c p is constructed to
 
   180     ///be a path of graph \c G.
 
   178     ///be a path of graph \c G.
 
   181     ///If \c j is not less than the result of previous \c run,
 
   179     ///If \c j is not less than the result of previous \c run,
 
   182     ///then the result here will be an empty path (\c j can be 0 as well).
 
   180     ///then the result here will be an empty path (\c j can be 0 as well).
 
   183     ///
 
   181     ///
 
   184     ///\param Path The type of the path structure to put the result to (must meet lemon path concept).
 
   182     ///\param Path The type of the path structure to put the result to (must meet lemon path concept).
 
   185     ///\param p The path to put the result to 
   183     ///\param p The path to put the result to.
 
   186     ///\param j Which path you want to get from the found paths (in a real application you would get the found paths iteratively)
 
   184     ///\param j Which path you want to get from the found paths (in a real application you would get the found paths iteratively).
 
   187     template<typename Path>
 
   185     template<typename Path>
 
   188     void getPath(Path& p, size_t j){
 
   186     void getPath(Path& p, size_t j){
 
   189 
   187 
   190       p.clear();
 
   188       p.clear();
 
   191       if (j>paths.size()-1){
 
   189       if (j>paths.size()-1){
lemon-0.x