Поддерживает ли boost :: topological_sort () ТОЛЬКО подключенный DiGraph? - PullRequest
Новая
       42

Поддерживает ли boost :: topological_sort () ТОЛЬКО подключенный DiGraph?

0 голосов
/ 27 мая 2019

Я сейчас пытаюсь использовать функцию boost :: topological_sort () и столкнулся с проблемой.

Сначала я проверил пример кода, заданного

https://boostjp.github.io/tips/graph.html#topological-sort

, и он отлично работает в моей среде (Win10 x64 Pro / Visual Studio 2017 с Boost 1.6.9).Но когда я изменяю определение графика на 

const std::vector<Edge> edges = {
    { 0,  1},
    { 1, 14},
    { 3,  4},
    { 4, 15},
    { 5,  6},
    { 6, 16},
    { 7,  2},
    { 8,  9},
    { 9, 17},
    {10, 11},
    {11, 18},
    {12, 13},
    {13, 19},
    {22, 23},
    {23, 20},
    {24, 25},
    {25, 21},
};

, он возвращает неправильный ответ

24 25 22 23 21 20 12 13 19 10 1118 8 9 17 7 5 6 16 3 4 15 2 0 1 14.

Правильный

24 25 21 22 23 20 12 13 19 10 11 18 8 9 17 7 2 5 6 16 3 4 15 0 1 14.

Хотя график DAG, он сильно отсоединенкак

https://dreampuf.github.io/GraphvizOnline/#digraph%20G%7B%0A%090-%3E1%0A%091-%3E14%0A%093-%3E4%0A%094-%3E15%0A%095-%3E6%0A%096-%3E16%0A%097-%3E2%0A%098-%3E9%0A%099-%3E17%0A%0910-%3E11%0A%0911-%3E18%0A%0912-%3E13%0A%0913-%3E19%0A%0922-%3E23%0A%0923-%3E20%0A%0924-%3E25%0A%0925-%3E21%0A%7D

Не поддерживает ли boost :: topological_sort () НЕ отключенный ориентированный граф в целом?Когда я изменил определение графика 

const std::vector<Edge> edges_ok = {
    { 0,  1},
    { 1, 14},
    {14,  3},       //add
    { 3,  4},
    { 4, 15},
    {15,  5},       //add
    { 5,  6},
    { 6, 16},
    {16,  7},       //add
    { 7,  2},
    { 2,  8},       //add
    { 8,  9},
    { 9, 17},
    {17, 10},       //add
    {10, 11},
    {11, 18},
    {18, 12},       //add
    {12, 13},
    {13, 19},
    {19, 22},       //add
    {22, 23},
    {23, 20},
    {20, 24},       //add
    {24, 25},
    {25, 21},
};

https://dreampuf.github.io/GraphvizOnline/#digraph%20G%7B%0A%200-%3E%201%0A%201-%3E14%0A14-%3E%203%0A%203-%3E%204%0A%204-%3E15%0A15-%3E%205%0A%205-%3E%206%0A%206-%3E16%0A16-%3E%207%0A%207-%3E%202%0A%202-%3E%208%0A%208-%3E%209%0A%209-%3E17%0A17-%3E10%0A10-%3E11%0A11-%3E18%0A18-%3E12%0A12-%3E13%0A13-%3E19%0A19-%3E22%0A22-%3E23%0A23-%3E20%0A20-%3E24%0A24-%3E25%0A25-%3E21%0A%0A%7D

Работает нормально.

Заранее спасибо.

Такеши

...