Вопрос: Добавление vertex_index в список graphs на лету для центральности


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

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

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

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

Следующий код показывает, как воспроизвести ошибку компиляции. В этом рабочем примере вы можете изменить определение, чтобы заполнить 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

Выход MSVS:

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 ==========

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

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

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

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


12


источник


Ответы:


Как я сказал в обновлении, похоже, проблема заключалась в центрировании между центрами. Копаем через отправления в источник , и глядя на параметры в документы  Я обнаружил, что если 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 граф.


5