2015-05-15 3 views
12

Обновление: Проблема может быть в коде междоузлия. Если я прокомментирую звонок на brandes_betweenness_centrality, код будет скомпилирован. проблема может быть не в настройке индекса, как считалось ранее. Я награду за вознаграждение, если вы можете придумать альтернативный призыв к brandes_betweenness_centrality, который позволит сохранить индекс внешним.Добавление vertex_index в listS график «на лету» для центральности между ними

Я пытаюсь преобразовать часть моего старого кода vecS для работы с listS, в частности алгоритмом brandes_betweenness_centrality.

Я стараюсь, чтобы свойства вершин и края были очень легкими и работали в основном с внешними свойствами. Причина этого в том, что я не знаю, с чем все, что я хочу связать с ними в этот момент.

Ошибки, которые я получаю, поступают изнутри adjacency_list.hpp, поэтому я считаю, что проблема связана с нашим старым другом vertex_index_t со списком.

Следующий код показывает, как воспроизвести ошибку компиляции. В этом рабочем примере вы можете изменить определение, чтобы заполнить vertex_index в определении графика и изменить настройку метода интерполяции для полностью работающего кода (который корректно работает между ними).

Полный пример:

#include <iostream> 
#include <algorithm> 
#include <vector> 

#include <boost/graph/adjacency_list.hpp> 
#include <boost/graph/graph_traits.hpp> 
#include <boost/graph/betweenness_centrality.hpp> 

#include <boost/timer.hpp> 

using namespace std; 

enum edge_t {A,B}; 

struct VertexProperties{ 
    std::string id; 
}; 

struct EdgeProperties{ 
    edge_t type; 
}; 

//vertex_index in as internal property, switch to this graph and change below vertex map for working code 
//typedef boost::adjacency_list < boost::listS, boost::listS, boost::undirectedS, 
//  boost::property<boost::vertex_index_t,size_t,VertexProperties>, EdgeProperties > DynamicNet; 

// No internal vertex_index 
typedef boost::adjacency_list < boost::listS, boost::listS, boost::undirectedS, 
     VertexProperties, EdgeProperties > DynamicNet; 

typedef boost::graph_traits<DynamicNet>::vertex_descriptor DynamicNetVertex; 
typedef boost::graph_traits<DynamicNet>::vertex_iterator DynamicNetVI; 

typedef boost::graph_traits<DynamicNet>::edge_descriptor DynamicNetEdge; 
typedef boost::graph_traits<DynamicNet>::edge_iterator  DynamicNetEI; 


void calcBetweenness(DynamicNet &g, 
        std::vector<double> &v_centrality_vec, 
        std::vector<double> &e_centrality_vec); 


int main(int argc, char* argv[]){ 
    cout << "betweenness" << endl; 

    DynamicNet net; 

    //Fig. 1, wheen graph (a - h), modified with added z added to a 
    //http://www.boost.org/doc/libs/1_58_0/libs/graph/doc/betweenness_centrality.html 
    DynamicNetVertex a = boost::add_vertex(net); net[a].id = "a"; 
    DynamicNetVertex b = boost::add_vertex(net); net[b].id = "b"; 
    DynamicNetVertex c = boost::add_vertex(net); net[c].id = "c"; 
    DynamicNetVertex d = boost::add_vertex(net); net[d].id = "d"; 
    DynamicNetVertex e = boost::add_vertex(net); net[e].id = "e"; 
    DynamicNetVertex f = boost::add_vertex(net); net[f].id = "f"; 
    DynamicNetVertex g = boost::add_vertex(net); net[g].id = "g"; 

    //core 
    DynamicNetVertex h = boost::add_vertex(net); net[h].id = "h"; 

    boost::add_edge(a,h,net); 
    boost::add_edge(b,h,net); 
    boost::add_edge(c,h,net); 
    boost::add_edge(d,h,net); 
    boost::add_edge(e,h,net); 
    boost::add_edge(f,h,net); 
    boost::add_edge(g,h,net); 

    //add an edge to make the calculation more interesting 
    DynamicNetVertex z = boost::add_vertex(net); net[z].id = "z"; 
    boost::add_edge(a,z,net); 



    vector<double> v_centrality_vec(boost::num_vertices(net),0.0); 
    vector<double> e_centrality_vec(boost::num_edges(net),0.0); 

    boost::timer t; 
    t.restart(); 
    calcBetweenness(net,v_centrality_vec,e_centrality_vec); 
    double s = t.elapsed(); 
    cout << s << " s" << endl; 
    cout << endl; 

    cout << "Vertex betweenness" << endl; 
    DynamicNetVI vi,ve;  
    size_t i = 0; 
    for(boost::tie(vi,ve) = boost::vertices(net); vi != ve; ++vi){ 
     cout << net[*vi].id << "\t" << v_centrality_vec.at(i) << endl; 
     ++i; 
    } 

    cout << endl; 

    cout << "Edge betweenness" << endl; 
    DynamicNetEI ei,ee; 
    i = 0; 
    for(boost::tie(ei,ee) = boost::edges(net); ei != ee; ++ei){ 
     DynamicNetEdge e = *ei; 
     cout << net[boost::source(e,net)].id << "\t" 
      << net[boost::target(e,net)].id << "\t" << e_centrality_vec.at(i) << endl; 
     ++i; 
    } 

    cin.get(); 
} 

void calcBetweenness(DynamicNet &g, 
        std::vector<double> &v_centrality_vec, 
        std::vector<double> &e_centrality_vec) 
{ 
    std::cout << "betweenness called" << std::endl; 

    //vertex 
    //Uncomment and change to internal vertex graph above for working code. 

/* 
    typedef std::map<DynamicNetVertex,size_t> StdVertexIndexMap; 
    StdVertexIndexMap viMap; 
    typedef boost::property_map<DynamicNet, boost::vertex_index_t>::type VertexIndexMap; 
    VertexIndexMap v_index = boost::get(boost::vertex_index,g); 
    DynamicNetVI vi,ve; 
    size_t i = 0; 
    for(boost::tie(vi,ve) = boost::vertices(g); vi != ve; ++vi){ 
     boost::put(v_index,*vi,i); 
     ++i; 
    } 
    boost::iterator_property_map< std::vector<double>::iterator, VertexIndexMap > 
     v_centrality_map(v_centrality_vec.begin(), v_index); 
*/ 

    //this code which exactly mimics the working approached used by edge results in an error 
    typedef std::map<DynamicNetVertex,size_t> StdVertexIndexMap; 
    StdVertexIndexMap viMap; 
    typedef boost::associative_property_map<StdVertexIndexMap> VertexIndexMap; 
    VertexIndexMap v_index(viMap); 
    DynamicNetVI vi,ve; 
    size_t i = 0; 
    for(boost::tie(vi,ve) = boost::vertices(g); vi != ve; ++vi){ 
     boost::put(v_index,*vi,i); 
     ++i; 
    } 
    boost::iterator_property_map< std::vector<double>::iterator, VertexIndexMap > 
     v_centrality_map(v_centrality_vec.begin(), v_index); 



    //edge, this appraoch works fine for edge 
    typedef std::map<DynamicNetEdge,size_t> StdEdgeIndexMap; 
    StdEdgeIndexMap eiMap; 
    typedef boost::associative_property_map<StdEdgeIndexMap> EdgeIndexMap; 
    EdgeIndexMap e_index(eiMap); 
    DynamicNetEI ei,ee; 
    i = 0; 
    for(boost::tie(ei,ee) = boost::edges(g); ei != ee; ++ei){ 
     boost::put(e_index,*ei,i); 
     ++i; 
    } 
    boost::iterator_property_map< std::vector<double>::iterator, EdgeIndexMap > 
     e_centrality_map(e_centrality_vec.begin(), e_index); 

    brandes_betweenness_centrality(g,v_centrality_map, e_centrality_map); 
} 

Ошибка:

Error 1 error C2182: 'reference' : illegal use of type 'void' ... \boost_1_58_0\boost\graph\detail\adjacency_list.hpp 2543 
Error 2 error C2182: 'const_reference' : illegal use of type 'void' ... \boost_1_58_0\boost\graph\detail\adjacency_list.hpp 2544 

МСВС выход:

1>------ Build started: Project: testBetweenness, Configuration: Release 

Win32 ------ 
1>Compiling... 
1>testBetweenness.cpp 
1>...\boost_1_58_0\boost/graph/detail/adjacency_list.hpp(2543) : error C2182: 'reference' : illegal use of type 'void' 
1>  ...\boost_1_58_0\boost/graph/detail/adjacency_list.hpp(2619) : see reference to class template instantiation 'boost::adj_list_any_vertex_pa::bind_<Tag,Graph,Property>' being compiled 
1>  with 
1>  [ 
1>   Tag=boost::vertex_index_t, 
1>   Graph=boost::adjacency_list<boost::listS,boost::listS,boost::undirectedS,pintk::VertexProperties,pintk::EdgeProperties>, 
1>   Property=pintk::VertexProperties 
1>  ] 
1>  ...\boost_1_58_0\boost/graph/detail/adjacency_list.hpp(2752) : see reference to class template instantiation 'boost::detail::adj_list_choose_vertex_pa<Tag,Graph,Property>' being compiled 
1>  with 
1>  [ 
1>   Tag=boost::vertex_index_t, 
1>   Graph=boost::adjacency_list<boost::listS,boost::listS,boost::undirectedS,pintk::VertexProperties,pintk::EdgeProperties>, 
1>   Property=pintk::VertexProperties 
1>  ] 
1>  ...\boost_1_58_0\boost/graph/properties.hpp(208) : see reference to class template instantiation 'boost::adj_list_vertex_property_selector::bind_<Graph,Property,Tag>' being compiled 
1>  with 
1>  [ 
1>   Graph=boost::adjacency_list<boost::listS,boost::listS,boost::undirectedS,pintk::VertexProperties,pintk::EdgeProperties>, 
1>   Property=pintk::VertexProperties, 
1>   Tag=boost::vertex_index_t 
1>  ] 
1>  ...\boost_1_58_0\boost/graph/properties.hpp(217) : see reference to class template instantiation 'boost::detail::vertex_property_map<Graph,PropertyTag>' being compiled 
1>  with 
1>  [ 
1>   Graph=boost::adjacency_list<boost::listS,boost::listS,boost::undirectedS,pintk::VertexProperties,pintk::EdgeProperties>, 
1>   PropertyTag=boost::vertex_index_t 
1>  ] 
1>  ...\boost_1_58_0\boost/graph/betweenness_centrality.hpp(562) : see reference to class template instantiation 'boost::property_map<Graph,Property,Enable>' being compiled 
1>  with 
1>  [ 
1>   Graph=boost::adjacency_list<boost::listS,boost::listS,boost::undirectedS,pintk::VertexProperties,pintk::EdgeProperties>, 
1>   Property=boost::vertex_index_t, 
1>   Enable=void 
1>  ] 
1>  ...\Visual Studio 2008\Projects\yapnl\yapnl\ProteinNetworks.h(82) : see reference to function template instantiation 'void boost::brandes_betweenness_centrality<pintk::DynamicNet,boost::iterator_property_map<RandomAccessIterator,IndexMap>,boost::iterator_property_map<RandomAccessIterator,EdgeIndexMap>>(const Graph &,CentralityMap,EdgeCentralityMap,boost::graph::detail::no_parameter)' being compiled 
1>  with 
1>  [ 
1>   RandomAccessIterator=std::_Vector_iterator<double,std::allocator<double>>, 
1>   IndexMap=VertexIndexMap, 
1>   Graph=pintk::DynamicNet, 
1>   CentralityMap=boost::iterator_property_map<std::_Vector_iterator<double,std::allocator<double>>,VertexIndexMap>, 
1>   EdgeCentralityMap=boost::iterator_property_map<std::_Vector_iterator<double,std::allocator<double>>,EdgeIndexMap> 
1>  ] 
1>...\boost_1_58_0\boost/graph/detail/adjacency_list.hpp(2544) : error C2182: 'const_reference' : illegal use of type 'void' 
1>Build log was saved at "file://...\Visual Studio 2008\Projects\yapnl\testBetweenness\Release\BuildLog.htm" 
1>testBetweenness - 2 error(s), 0 warning(s) 
========== Build: 0 succeeded, 1 failed, 0 up-to-date, 0 skipped ========== 

Это answer, помогли мне добавить boost::vertex_index_t свойство в определении графика, который позволил кода для использования с использованием boost::property<boost::vertex_index_t,size_t,VertexProperties>.

Я бы хотел, чтобы vertex_index_t был полностью внешним от графика и добавлял его непосредственно перед тем, как запустить алгоритм.

Фактически идентичный код для настройки edge_index позволяет это. Я что-то упустил или это вещь MSVS, или это может быть ошибка?

Мой конкретный вопрос:: Что мне нужно изменить, чтобы сохранить vertex_index из определения графика, добавить его на лету и все еще запустить алгоритм?

ответ

5

Как я сказал в обновлении, похоже, проблема заключалась в центрировании между центрами. Копаясь через отправления в source и глядя на параметры в docs, я обнаружил, что если vertex_index_map не передается алгоритму, по умолчанию он равен get(vertex_index, g), который, как известно, не существует на этом конкретном графике.

После некоторого времени, обертывающего мою голову вокруг имени bgl_named_params, я понял, что могу передать переменную v_index в качестве именованного параметра.

Следующий код сделал трюк:

brandes_betweenness_centrality(g, 
      boost::centrality_map(v_centrality_map).edge_centrality_map(e_centrality_map).vertex_index_map(v_index)); 

Я думаю, что ошибка была в brandes_betweenness_centrality попытке вызвать get(vertex_index,g) и неудачу на listS графике.

+0

Я думаю, что это отвечает на ваш собственный вопрос, не так ли? Вам все еще нужна помощь? – sehe

+1

@sehe, нет, это исправлено. Спасибо хоть. Если бы только я работал немного сложнее, прежде чем публиковать щедрость. Я принял его, чтобы другие не теряли времени, пытаясь получить щедрость. – pbible