Распространять значения внутри подключенного компонента с помощью BFSVisitor? (Ускорение, С++)?

Я строю график повышения. Для каждого подключенного компонента в графе я хотел бы распространить уникальное значение идентификатора для каждой вершины в этом подключенном компоненте. Мне интересно, есть ли способ сделать это, используя концепцию Boost BFSVisitor?

Я предполагаю, что это можно сделать с помощью функции examine_edge (http://www.boost.org/doc/libs/1_55_0/libs/graph/doc/BFSVisitor.html), но мне трудно понять, как реализовать такой класс. Любые идеи/ссылки на примеры очень помогут!


c++ boost boost-graph
person mskb    schedule 02.08.2014    source источник
comment
Если вас не интересуют конкретные значения ID, а только тот факт, что они должны быть уникальными для каждого компонента, вы можете использовать connected_components(). Его второй аргумент — карта свойств с возможностью записи, где будут записаны целочисленные метки.   -  person taketwo    schedule 02.08.2014
comment
распространять уникальное значение идентификатора для каждой вершины в этом связанном компоненте. Пожалуйста, опишите, что подразумевается под этим - простой пример того, что вы ожидаете, будет хорошо.   -  person ravenspoint    schedule 02.08.2014
comment
Интерпретация @ravenspoint taketwo - это в основном то, к чему я стремился. Каждый подключенный компонент должен иметь уникальное значение идентификатора. Каждая вершина в каждом компоненте должна иметь сохраненное значение идентификатора. Спасибо!   -  person mskb    schedule 02.08.2014
comment
@taketwo, спасибо! Причина, по которой я задавался вопросом о классе BFSVisitor, заключается в следующем: я мог добавлять и удалять ребра, и мне было бы интересно посмотреть, появляются ли новые компоненты; наивным следствием этого было бы обнаружение новых компонентов посредством поиска BFS из исходных/целевых вершин ребра, которое я добавил/убрал. Итак, я подумал, что BFSVisitor, вероятно, будет более эффективным, чем поиск подключенных_компонентов по всему графу?   -  person mskb    schedule 02.08.2014
comment
Если вы используете BFS, вы должны использовать discovery_vertex. Если вы используете exam_edge, вы должны использовать цель ребра, чтобы получить вершину. Также обратите внимание на точки сочленения. По определению их удаление увеличивает количество компонентов.   -  person pbible    schedule 03.08.2014

Ответы (1)


arrow_upward
1
arrow_downward

Похоже, вы просто хотите реализовать пользовательского посетителя BFS. На это был дан ответ здесь.

В частности, в вашем методе discovery_vertex. Вы можете просто использовать:

void discover_vertex(const graph_t::vertex_descriptor &s, const graph_t &g) const {
  std::cout << "Discover: " << g[s] << std::endl;
  g[s].component_id = myNewId;
}

Или вы можете использовать карту недвижимости.

put(component_id,s,myNewId);

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

Вот пример пользовательской DFS передача переменной в конструктор. Это тот же принцип, что и BFS.

person pbible    schedule 04.08.2014
comment
Эй, 1. как передать функцию myNewId в функцию discover_vertex? и 2. с идеей карты свойств, вы хотели сказать put(s, component_id, myNewId) (может быть много вершин с одним и тем же идентификатором). - person mskb; 05.08.2014
comment
1) Как и любой класс, создайте конструктор с частной переменной. Всем посещенным вершинам потребуется один и тот же идентификатор компонента, верно? 2) Я смотрю здесь . У них есть первый аргумент карта свойств. Поэтому он вставляет myNewId в карту component_id, используя s в качестве ключа. - person pbible; 05.08.2014