топологическую сортировку с поддержкой циклических зависимостей

Question

Рассмотрим следующие зависимости (где A --> B означает В зависит от А, так эффективно, А является «родитель»)

A --> B 
A --> C 
C --> D 
C --> E 

Более графически:

A 
    | 
---------- 
|  | 
B  C 
     | 
    ----------- 
    |   | 
    D   E 

Алгоритм топологической сортировки возвращал бы что-то вроде:

ABCDE 

У меня есть fou nd код для этого (exhibit A и exhibit B), но не поддерживают зависимости цикличности. Я в situtation, что это может произойти:

A --> B 
B --> C 
B --> D 
C --> B 
C --> E 

Графически:

A 
| 
B <--> C 
|  | 
D  E 

Это может вернуть ABCDE или ACBDE. Так как B и C находятся на одном уровне, порядок между ними не важен (аналогично для D и E).

Как я мог выполнить такую ​​вещь. Я понимаю, что это не точно топологическая сортировка, но я не эксперт-математик, поэтому я не знаю, с чего начать, не говоря уже о том, как это реализовать.

Лично я работаю на C#, но если вы знаете, как это сделать на любом другом языке, я был бы рад изучить ваш код и перевести его на C#.

обновление

Я также могу иметь следующую ситуацию:

A <-------- 
|   | 
--> B --> C 
    |  | 
    D  E 

Так, важно, это не должно быть деревом. Я могу иметь любой произвольный граф. На самом деле не все узлы должны быть связаны друг с другом.

Answer 1

Прежде всего, это концептуально проще, если у вас есть график, чтобы вы могли спросить «на что вы зависите»? Я собираюсь предположить, что у нас есть график, где направленное ребро от A до B означает «A зависит от B», что противоположно вашему утверждению.

Я немного смущен вашим вопросом, так как сортировка topo, которая игнорирует циклы, практически такая же, как обычная сортировка topo. Я разработаю алгоритм так, чтобы вы могли обрабатывать циклы по своему усмотрению; возможно, это поможет.

Идея сортировки:

• Граф представляет собой набор узлов, таким образом, что каждый узел имеет набор соседей. Как я уже сказал, если узел A имеет соседний B, то A зависит от B, поэтому B должен произойти до A.

• Сортировка принимает граф и производит отсортированный список узлов.

• Во время операции сортировки поддерживается словарь, который отображает каждый узел на одно из трех значений: живое, мертвое и неживое. Живой узел еще не обработан. Мертвый узел уже обработан. Узел нежити обрабатывается; он уже не жив, но еще не мертв.

• Если вы столкнулись с мертвым узлом, вы можете пропустить его; он уже находится в списке вывода.

• Если вы столкнулись с живым узлом, вы обрабатываете его рекурсивно.

• Если вы столкнулись с узлом нежити, то это часть цикла. Делай, что хочешь. (Производят ошибку, если циклы являются незаконными, относиться к нему как мертвые, если циклы являются законными, и т.д.) смысл

---

function topoSort(graph) 
    state = [] 
    list = [] 
    for each node in graph 
    state[node] = alive 
    for each node in graph 
    visit(graph, node, list, state) 
    return list 

function visit(graph, node, list, state) 
    if state[node] == dead 
    return // We've done this one already. 
    if state[node] == undead 
    return // We have a cycle; if you have special cycle handling code do it here. 
    // It's alive. Mark it as undead. 
    state[node] = undead 
    for each neighbour in getNeighbours(graph, node) 
    visit(graph, neighbour, list, state) 
    state[node] = dead 
    append(list, node); 

Make?

Answer 2

В самом деле, вы хотите breadth-first распечатки вашего графа

Связанного список википедии страницы алгоритм для выполнения этого.

Там также this question на SO

Answer 3

начать думать о проблеме права. У вас нет дерева. У вас есть произвольный граф.

Имея это в виду, то, что вам, вероятно, нужно сделать в первую очередь, это find cycles и разбить их, удалив край в цикле (ОК, отмечая край как «игнорируйте это при выполнении топологической сортировки»).

При удалении всех циклов вы можете применить формуляр toplogical к остальным узлам и дугам.

Answer 4

Редактировать 3 года спустя: Я иногда возвращаюсь к этому, так как я впервые реализовал это в 2014 году. Я не очень хорошо понимал это в то время, когда я впервые разместил этот ответ, так что ответ был слишком сложный. Сортировка на самом деле довольно проста для реализации:

public class Node 
{ 
    public int Data { get; set; } 
    public List<Node> Children { get; set; } 

    public Node() 
    { 
     Children = new List<Node>(); 
    } 
} 

public class Graph 
{ 
    public List<Node> Nodes { get; set; } 

    public Graph() 
    { 
     Nodes = new List<Node>(); 
    } 

    public List<Node> TopologicSort() 
    { 
     var results = new List<Node>(); 
     var seen = new List<Node>(); 
     var pending = new List<Node>(); 

     Visit(Nodes, results, seen, pending); 

     return results; 
    } 

    private void Visit(List<Node> graph, List<Node> results, List<Node> dead, List<Node> pending) 
    { 
     // Foreach node in the graph 
     foreach (var n in graph) 
     { 
      // Skip if node has been visited 
      if (!dead.Contains(n)) 
      { 
       if (!pending.Contains(n)) 
       { 
        pending.Add(n); 
       } 
       else 
       { 
        Console.WriteLine(String.Format("Cycle detected (node Data={0})", n.Data)); 
        return; 
       } 

       // recursively call this function for every child of the current node 
       Visit(n.Children, results, dead, pending); 

       if (pending.Contains(n)) 
       { 
        pending.Remove(n); 
       } 

       dead.Add(n); 

       // Made it past the recusion part, so there are no more dependents. 
       // Therefore, append node to the output list. 
       results.Add(n); 
      } 
     } 
    } 
}