Boost.Graph - algo.is_optimal() assert

Question

Я пытаюсь реализовать программу, которая обнаруживает возможности arbitrage trading с использованием минимального расхода . алгоритм. Этот алгоритм реализован в Boost.Graph в виде boost::push_relabel_max_flow(), за которым следует звонок boost::cycle_canceling().

Ниже приведен код, который у меня уже есть, оставляя boost::cycle_canceling -part, потому что моя программа умирает до достижения функции.

#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; 
    }; 

"Нормальный" выход моей программы:

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 

В блок-схеме:

Моя программа утверждает в push_relabel_max_flow -функции. Ниже приведен полный код ошибки (который напечатан на выполнения):

/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. 

В самом конце сообщения вы можете увидеть утверждение: algo.is_optimal() не. Я совершенно не знаю, что это значит.

В исходном файле (подталкивания/график/push_relabel_max_flow.hpp) она определяется как:

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

Я гугл его и не нашел ничего. Я передал свои параметры не так? Это потому, что я использую double как емкость (хотя, если я правильно помню, «documentation» описал это как можно использовать double для емкости)? Кроме того, я обнаружил это предложение в documentation:

Аргумент крышка CapacityEdgeMap должен отображать каждое ребро в Е к положительному числа, и каждому ребру Х^Т к 0.

Что означает жирная часть? Означает ли это, что мне нужно установить емкость всех исходящих ребер из вершины-вершины в 0?

Answer 1

Вам необходимо установить возможности реверса Edges' 0.

Так что вам нужно:

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

Я не уверен, почему это все же. Заглядывая в read_dimacs.hpp Я заметил, что они создают свои обратные ребра и дают им емкость 0. О 3/4 пути вниз страницы:

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

скорее всего, без этого ограничения, алгоритм будет пытаться рассматривать их как нормальные края. Часть приведенной вами документации описывает это, но это не совсем очевидно.

На входном графике и свойстве параметров имеется несколько специальных требований к параметрам карты для этого алгоритма. Во-первых, направленный граф G = (V, E) , который представляет сеть, должен быть дополнен, чтобы включить ребро для каждого ребра в E. То есть входной график должен быть Gin = (V, {EUE^T }). Аргумент аргумента ReverseEdgeMap должен отображать каждый ребро в исходный граф на его обратный край, то есть (u, v) -> (v, u) для всех (u, v) в E. Кол-во аргументов CapacityEdgeMap должно отображать каждый ребро Е положительное число, а каждое ребро в E^T 0.

Я думаю, что здесь E^T означает транспонирование не цель. Вы должны знать, что транспонирование направленной матрицы смежности фактически является обратным для всех ребер. Вот почему говорят, что входной граф G = {V, E U E^T}. Края плюс обратные, которые необходимо добавить.

Сторона примечания: изменение long до double в push-relable example работало отлично.