Boost.Graph - algo.is_optimal() assertion

Question

Ich versuche, ein Programm zu implementieren, das arbitrage trading Möglichkeiten mit einem minimalen Kostenfluss Algorithmus erkennt. Dieser Algorithmus ist in Boost.Graph in Form von boost::push_relabel_max_flow() gefolgt von einem Aufruf an boost::cycle_canceling() implementiert.

Das folgende ist der Code, den ich bereits habe, den boost::cycle_canceling-Teil auslassend, weil mein Programm stirbt, bevor es die Funktion erreicht.

#include <boost/graph/adjacency_list.hpp> 
    #include <boost/property_map/property_map.hpp> 
    #include <boost/graph/push_relabel_max_flow.hpp> 
    #include <boost/graph/cycle_canceling.hpp> 
    #include <boost/graph/directed_graph.hpp> 
    #include <boost/config.hpp> 
    #include <iostream> 
    #include <string> 



    typedef boost::adjacency_list_traits<boost::vecS, boost::vecS, boost::directedS> Traits; 

    struct st_order { 
     double price; 
     double amount; 
     std::string type; 
    }; 

    struct VertexProps { 
     unsigned int id; 
    }; 

    struct EdgeProps { 
     double capacity; 
     double residual_capacity; 
     double weight; 
     Traits::edge_descriptor reverse; 
    }; 

    typedef boost::adjacency_list<boost::vecS, boost::vecS, boost::directedS, VertexProps, EdgeProps > DirectedGraph; 

    int main() { 


     DirectedGraph g; 

     // ETH/BTC 
     std::vector<st_order> trades{ 
      st_order{0.0101,10.0,"SELL"}, 
      st_order{0.01,3.0,"BUY"}, 
      st_order{0.0102,5.0,"SELL"}, 
      st_order{0.2,42.0,"BUY"}, 
     }; 


     std::vector<boost::graph_traits<DirectedGraph>::vertex_descriptor> vertices; 
     for(unsigned int vertex_index = 0; vertex_index < trades.size(); vertex_index++) 
     { 
      vertices.push_back(boost::add_vertex({vertex_index}, g)); 
     } 


     std::map<DirectedGraph::vertex_descriptor, std::map<DirectedGraph::vertex_descriptor, Traits::edge_descriptor>> edges; 


int ifirst = 0; 
for(auto& first : vertices) 
{ 
    int isecond = 0; 
    for(auto& second : vertices) 
    { 

     if(first == second || trades[ifirst].type.compare(trades[isecond].type) == 0) 
     { 
      isecond++; 
      continue; 
     } 

     double amount = trades[isecond].amount; 

     if(trades[isecond].type.compare("SELL") == 0) 
      amount = amount * trades[isecond].price; 

     edges[first][second] = boost::add_edge(first, second, {amount, amount, (trades[isecond].price/trades[ifirst].price)} , g).first; 
     std::cout << "Add Edge: From " << first << " to " << second << std::endl; 

     isecond++; 
    } 
    ifirst++; 
} 


for(auto& i : vertices) 
{ 
    for(auto& j : vertices) 
    { 
     if(i == j) 
      continue; 

     if(edges.find(i) != edges.end() && edges[i].find(j) != edges[i].end()) 
     { 
      if(edges.find(j) == edges.end() || edges[j].find(i) == edges[j].end()) 
      { 
       throw std::runtime_error("No return edge found: "+std::to_string(i)+" "+std::to_string(j)); 
      } 

      auto edge = boost::edge(i,j,g).first; 
      g[edge].reverse = edges[i][j]; 

     } 
    } 
} 



     double flow = boost::push_relabel_max_flow(g, vertices[0], vertices[1], 
       boost::get(&EdgeProps::capacity, g), 
       boost::get(&EdgeProps::residual_capacity, g), 
       boost::get(&EdgeProps::reverse, g), 
       boost::get(boost::vertex_index, g) 
      ); 

// Now boost::cycle_canceling() would follow 

    std::cout << "END << std::endl; 
    return 0; 
    }; 

Die "normale" Ausgabe meines Programms ist:

Add Edge: From 0 to 1 
Add Edge: From 0 to 3 
Add Edge: From 1 to 0 
Add Edge: From 1 to 2 
Add Edge: From 2 to 1 
Add Edge: From 2 to 3 
Add Edge: From 3 to 0 
Add Edge: From 3 to 2 

Als Flussdiagramm:

Mein Programm behauptet im push_relabel_max_flow -function. Im Folgenden ist der vollständige Fehlercode (die bei Laufzeit gedruckt wird):

/usr/local/include/boost/graph/push_relabel_max_flow.hpp:707: typename 
boost::property_traits<IndexMap>::value_type 
boost::push_relabel_max_flow(Graph&, typename 
boost::graph_traits<Graph>::vertex_descriptor, typename 
boost::graph_traits<Graph>::vertex_descriptor, CapacityEdgeMap, 
ResidualCapacityEdgeMap, ReverseEdgeMap, VertexIndexMap) [with Graph = 
boost::adjacency_list<boost::vecS, boost::vecS, boost::directedS, 
VertexProps, EdgeProps>; CapacityEdgeMap = 
boost::adj_list_edge_property_map<boost::directed_tag, double, double&, long 
unsigned int, EdgeProps, double EdgeProps::*>; ResidualCapacityEdgeMap = 
boost::adj_list_edge_property_map<boost::directed_tag, double, double&, long 
unsigned int, EdgeProps, double EdgeProps::*>; ReverseEdgeMap = 
boost::adj_list_edge_property_map<boost::directed_tag, 
boost::detail::edge_desc_impl<boost::directed_tag, long unsigned int>, 
boost::detail::edge_desc_impl<boost::directed_tag, long unsigned int>&, long 
unsigned int, EdgeProps, boost::detail::edge_desc_impl<boost::directed_tag, 
long unsigned int> EdgeProps::*>; VertexIndexMap = 
boost::vec_adj_list_vertex_id_map<VertexProps, long unsigned int>; typename 
boost::property_traits<IndexMap>::value_type = double; typename 
boost::graph_traits<Graph>::vertex_descriptor = long unsigned int]: Assertion 
`algo.is_optimal()' failed. 

Ganz am Ende der Nachricht, die Sie Assertion sehen: algo.is_optimal() fehlgeschlagen. Ich habe absolut keine Ahnung, was das bedeutet.

in der Quelldatei (boost/Graph/push_relabel_max_flow.hpp) wird wie folgt definiert:

bool is_optimal() { 
     // check if mincut is saturated... 
     global_distance_update(); 
     return get(distance, src) >= n; 
     } 

ich habe gegoogelt und nichts gefunden. Habe ich meine Parameter falsch übergeben? Liegt es daran, dass ich double als Kapazität verwende (obwohl, wenn ich mich richtig erinnere, beschrieben "documentation" es als möglich, ein double für die Kapazität zu verwenden)? Auch habe ich diesen Satz in den documentation entdeckt:

Die CapacityEdgeMap Argumente Kappe jede Kante in E auf eine positive Zahl, und jede Kante in E^T auf 0 Karte muss.

Was bedeutet der fettgedruckte Teil? Bedeutet das, dass ich die Kapazität aller ausgehenden Kanten vom Senken-Vertex auf 0 setzen muss?

Answer 1

Sie müssen die Rückwärtskanten Kapazitäten auf 0

Sie müssen also gesetzt:

auto edge = boost::edge(i,j,g).first; 
g[edge].reverse = edges[i][j]; 
g[edges[i][j]].capacity = 0; 

Ich bin nicht sicher, warum dies allerdings ist. Wenn ich mir die read_dimacs.hpp anschaue, habe ich bemerkt, dass sie ihre Rückkanten erzeugen und ihnen 0 Kapazität geben. Ungefähr 3/4 des Weges nach unten:

capacity[e1] = cap; 
capacity[e2] = 0; 
reverse_edge[e1] = e2; 
reverse_edge[e2] = e1; 

Wahrscheinlich ohne diese Beschränkung, der Algorithmus wird versuchen, diese als normale Kanten zu behandeln. Der Teil der Dokumentation, den Sie angeben, beschreibt dies, aber es ist nicht ganz offensichtlich.

Es gibt einige spezielle Anforderungen für den Eingabediagramm und die Eigenschaft Kartenparameter für diesen Algorithmus. Zuerst muss der gerichtete Graph G = (V, E) , der das Netzwerk darstellt, so erweitert werden, dass er die umgekehrte Kante für jede Kante in E enthält. Das heißt, der Eingabegraph sollte Gin = (V, {EUE^T }). Das ReverseEdgeMap-Argument rev muss jede Kante in dem ursprünglichen Graphen der umgekehrten Kante zuordnen, dh (u, v) -> (v, u) für alle (u, v) in E. Der CapacityEdgeMap-Argument-Cap muss jeweils zugeordnet werden Kante in E auf eine positive Zahl, und jede Kante in E^T auf 0.

denke ich, hier E^T bedeutet Ziel transponieren nicht. Sie müssen wissen, dass die Transponierte einer gerichteten Adjazenzmatrix tatsächlich die Umkehrung aller Kanten ist. Deshalb sagen sie, dass der Eingabegraph G = {V, E U E^T} ist. Die Kanten plus die umgekehrten, die hinzugefügt werden müssen.

Seitennotiz: Ändern long zu double in der push-relable example funktionierte einwandfrei.