построение двусвязного графа

3,4,5 - чтобы граф стал односвязным, затем

1,2,3,4,5 - чтобы двухсвязным

Блин, не факт - что односвязный будет входит в минимальный двухсвязный. Надо как-то еще поплясать.

братишка, я тебе покушать принёс я и сам бы рад так сразу всё сконденсировать да связать, но вот biconnected_components работает на основе информации о рёбрах - то есть, если у нас существуют вершины, ни с чем не связанные - ничего мы и не получим. беда, в общем. второй день думаю над этим.

Э... я в ентих ваших грфафх-князьях-баронах не силен, унивеситетов не заканчивал, поэтому наверное и проблем не вижу.

А что сделать то надо, можно как то попроще объяснить? Что значит «обеспечить двусвязность» - вот есть граф, местами односвязный (связь A->B есть, связи B->A нету), и надо добавить недостающие связи, так?

граф неориентированный, то есть A->B == B->A

A connected graph is biconnected if the removal of any single vertex (and all edges incident on that vertex) can not disconnect the graph.

но вот biconnected_components работает на основе информации о рёбрах - то есть, если у нас существуют вершины, ни с чем не связанные - ничего мы и не получим

Ну это-то не принципиально: никто не мешает разбить на связные компоненты и каждую из них разбивать на двусвязные.

// Возможно в качестве «пляски» подойдет: после 1,2,3,4,5 (на этапе двусвязности) проверить ребра, добавленные на 3,4,5 - и удалить те, которые перестали быть нужными для двусвязности.

то есть, если у нас существуют вершины, ни с чем не связанные

Ну для этого собственно и было предложено сначала провести: 3,4,5 - дабы обеспечить односвязность (biconnected_components на этом этапе еще не нужен).

Ну для этого собственно и было предложено сначала провести: 3,4,5 - дабы обеспечить односвязность (biconnected_components на этом этапе еще не нужен).

3) Сжимаем каждую связную компоненту в вершину

как не нужен? информацию о связных компонентах я получаю как раз из результатов алгоритма biconnected_components, он для этого и предназначен :)

Эм... разбитие на компоненты - это одно из применений поиска в глубину.

biconnected_components - относится к пунктам 1-2

он для этого и предназначен :)

Прув?

Прув?

http://www.boost.org/doc/libs/1_49_0/libs/graph/example/biconnected_component...

  for (boost::tie(ei, ei_end) = edges(g); ei != ei_end; ++ei)
    std::cout << (char)(source(*ei, g) + 'A') << " -- " 
              << (char)(target(*ei, g) + 'A')
              << "[label=\"" << component[*ei] << "\"]\n";

Где написано, что он предназначен для разбиение на односвязные компоненты?

http://www.boost.org/doc/libs/1_49_0/libs/graph/doc/connected_components.html - чем не подходит для первой части 3,4,5

приношу извинения, похоже, неправильно понял вашу мысль. прошу ещё раз изложить конечный алгоритм.

Сначала достроить до односвязного: разбить на компоненты -> сжать в вершины -> минимальное остовное дерево  — получим набор дополнительных ребер (*).

Теперь изначальных алгоритм нормально отработает. Получится двусвязный граф. Но некоторые ребра из (*) теперь могут оказаться лишними: нужно проверять каждое (*)-ребро на необходимость его для двухсвязности.

Но некоторые ребра из (*) теперь могут оказаться лишними: нужно проверять каждое (*)-ребро на необходимость его для двухсвязности.

но как? неужели перебирать все рёбра тем же biconnected_components?

но как? неужели перебирать все рёбра тем же biconnected_components?

Пока не вижу эффективный способ, а ожидаемое число компонент связности может быть большим?

ну, как сказать. граф со 150-200 вершинами и всевозможными способами соединения, это много или мало? мне почему-то кажется, больно жирно получится

Есть такая статья: http://www.cs.utexas.edu/~vlr/papers/bi_aug.pdf

Another version of the problem is to augment a graph, with a weight assigned to each edge, to meet a connectivity requirement using a set of edges with a minimum total cost. Several related problems have been proved to be NP-complete. These results can be found in Eswaran & Tarjan 4 , Frank 5 , Frederickson & Ja'Ja' 7 , Watanabe & Nakamura 26 and Watanabe, Narita & Nakamura 29

Посмотрите, вдруг задача действительно в общем случае NP-полная.

150-200 вершинами и всевозможными способами соединения, это много или мало?

Конечно, мало).