Граф повышения с существующей структурой данных или с использованием ее в качестве структуры данных

Я пишу приложение, которое анализирует структуру данных с чем-то вроде

struct Block
{
  std::string foo;
  /* ... even more local data ... */
};

std::map<std::string, Block> blockContainer; // Each Block will have a name here

struct Signal
{
  // the direct links to the Blocks, no redundant storage of the name so that an
  // simple renaming of a Block would be possible
  std::map<std::string, Block>::iterator from; 
  std::map<std::string, Block>::iterator to;

  std::string bar;
  /* ... even more local data ... */
};

std::vector<Signal> signalContainer;

разобрать и заполнить этот список было довольно легко. Теперь мне нужно сделать топологическую сортировку Блоков в зависимости от Сигналов — тоже довольно просто, когда я использую Boost::Graph.

Но сначала анализировать его в структуре данных STL, а затем копировать их в структуру Boost::Graph, для меня не имеет особого смысла. Тем более, что все, что впоследствии будет сделано с этими данными, — это, возможно, несколько простых модификаций (добавление/удаление блоков и сигналов, некоторое перенаправление сигналов, их повторная сериализация) с последующей новой топологической сортировкой.

Так что я был бы в порядке с любым из этих возможных решений:

  1. Заставить Boost::Graph напрямую работать с моими контейнерами
  2. Анализируйте данные непосредственно в структурах данных Boost::Graph (и, например, используйте граф со связанными свойствами, такими как boost::adjacency_list<boost::mapS, boost::vecS, boost::directedS, Block, Signal>)

Но, похоже, я недостаточно умен, чтобы понять документацию здесь, чтобы сделать то же самое. Кроме того, все примеры, которые я нашел в сети, показывали, как использовать связанные свойства, но не показывали, как построить график с ними на лету. (И, конечно же, не со свойствами узла и вершины одновременно, или как использовать std::map для доступа к узлам по их имени,...)

Кто-нибудь может мне помочь?

Спасибо!


c++ boost-graph
person Chris    schedule 16.12.2012    source источник

Ответы (1)


arrow_upward
4
arrow_downward

Никто не достаточно умен для документации boost::graph ;) Требуется много времени, чтобы научиться ее использовать.

Вы можете создать структуру графа повышения вокруг ваших данных, однако это, вероятно, будет довольно болезненным. Там есть документация: http://www.boost.org/doc/libs/1_52_0/libs/graph/doc/leda_conversion.html

Я бы предложил пойти со вторым подходом, но я не уверен, что понимаю вашу структуру данных.

Вы видели этот вопрос: добавление пользовательских вершин в граф повышения делает это отвечает вашим потребностям?

Вы также можете сделать следующее, чтобы создать узел (или ребро) и сразу определить свойства:

vertex_t u = boost::add_vertex(Block(42, "hi"), g);

Возможно, вам потребуется сохранить карту во время разбора.

person Tristram Gräbener    schedule 16.12.2012
comment
Хорошо, теперь я выбрал решение 2 - и оно работает :) :) :) Помимо (теперь...) прямого добавления параметров ребра и вершины, самым большим оставшимся вопросом для меня была эффективная обработка имен вершин. . Решение состояло в том, чтобы сохранить имя в Block, а также в std::map<std::string,vertex_t> (и сделать так, чтобы оба были синхронизированы). Таким образом, я могу быстро найти сохраненный блок по его имени (через map), а также по имени, когда у меня есть блок (через свойство) - person Chris; 17.12.2012