Boost Graph с пользовательскими вершинами и ребрами

Я создаю собственный график повышения с моими собственными свойствами узла и ребер. Я определил график следующим образом:

class NavGraph : public boost::adjacency_list < boost::vecS, boost::vecS, boost::undirectedS, NodeInfo, EdgeInfo > {

public:
  typedef boost::graph_traits<NavGraph>::vertex_descriptor Vertex;
  typedef boost::graph_traits<NavGraph>::edge_descriptor Edge;

  NavGraph(){}

      void init(const std::vector<NodeInfo>& nodes, const std::vector<EdgeInfo>& edges);
}

Сейчас я пытаюсь инициализировать этот граф из списка свойств узлов и ребер (в методе init). NodeInfo и EdgeInfo — это простые структуры с примитивными типами. До сих пор я сделал это:

void NavGraph::init(const std::vector<NodeInfo>& nodes, const std::vector<EdgeInfo>& edges){

  //Add the Vertices
    for (std::vector<NodeInfo>::const_iterator it = nodes.begin() ; it != nodes.end(); ++it){

        Vertex u = boost::add_vertex(*this);
        (*this)[u].nodeIndex = (*it).nodeIndex;
        (*this)[u].x = (*it).x;
        (*this)[u].y = (*it).y;
        (*this)[u].z = (*it).z;

    }

    //Add the edges
    for (std::vector<EdgeInfo>::const_iterator it = edges.begin() ; it != edges.end(); ++it){

    //To be implemented
    }

 }

Итак, мне удалось добавить вершины и установить свойства (надеюсь, это правильно). Теперь каждый EdgeInfo имеет идентификатор источника и цели, которые идентифицируют два узла ребра. Проблема в том, что мне нужно получить их по Id из графа (со свойством nodeIndex, которое я установил ранее), чтобы я мог вызвать метод add_edge. Я действительно не знаю, как это сделать. Надеюсь, вы, ребята, можете мне помочь.


c++ boost-graph
person Pablo Arias    schedule 23.04.2014    source источник

Ответы (1)


arrow_upward
3
arrow_downward

Начнем сверху: НЕ рекомендуется специализировать список смежности и добавлять в него собственные методы.

Вместо этого вам следует создать экземпляр класса boost::adjacency_list в качестве члена нового класса, для которого вы затем сможете написать методы.

class cNavGraph {
  public:
  boost::adjacency_list < boost::vecS,
  boost::vecS,
  boost::undirectedS, 
  NodeInfo, EdgeInfo > myNavGraph;

...

Теперь, чтобы получить вершины из графа по свойству вершины nodeIndex, у вас есть два варианта:

  1. Найдите вершины для нужного nodeIndex. Это просто, но будет медленно, если график очень большой.

  2. Создайте карту из nodeIndex в вершину по мере добавления вершин, а затем выполните поиск на карте, когда вам нужно получить вершину из nodeIndex. Это требует больше кода и памяти, но будет намного быстрее для больших графиков.

В качестве более радикального предложения я предлагаю перепроектировать вещи так, чтобы вы сделали NodeIndex и дескриптор вершины идентичными, как это

for (std::vector<EdgeInfo>::const_iterator it = edges.begin() ;
   it != edges.end(); ++it)
{
   add_edge( it->first_node_index,
             it->second_node_index,
             myGraph );

Обратите внимание, в ответ на ваш комментарий, что вызов add_edge автоматически добавит две вершины, если они еще не присутствуют, с дескрипторами вершин, равными указанным индексам узлов. Не вызывайте add_vertex!

Когда вы завершили добавление всех ребер, вы можете перебирать узлы, добавляя свойства (сколько хотите).

person ravenspoint    schedule 23.04.2014
comment
Большое спасибо за эти замечательные предложения. Прямо сейчас я использую вариант номер два с картой, и он, кажется, работает. Что касается третьего варианта, работает ли он, если у меня есть более одного свойства в моем NodeInfo? Как я могу изменить дескриптор вершины, чтобы установить его равным моему nodeIndex? - person Pablo Arias; 30.04.2014
comment
Ответ в теле ответа. - person ravenspoint; 30.04.2014