Алгоритмы для идентификации всех баз циклов в неориентированном графе

StackOverflow https://stackoverflow.com/questions/1607124

  •  05-07-2019
  •  | 
  •  

Вопрос

У меня есть неориентированный граф с Вершиной V и Край E.Я ищу алгоритм для идентификации всех баз циклов на этом графике.

Я думаю , что Алгоритм Тарджанса это хорошее начало.Но ссылка У меня есть идея найти все циклы, не основа цикла (который по определению является циклом, который не может быть построен путем объединения других циклов).

Например, взгляните на приведенный ниже график:

Итак, алгоритм был бы полезен.Если есть существующая реализация (желательно на C #), это еще лучше!

Это было полезно?

Решение

Из того, что я могу сказать, верно не только предчувствие Брайана, но и еще более веское предположение:каждое ребро, которого нет в минимальном связующем дереве, добавляет ровно один новый "базовый цикл".

Чтобы убедиться в этом, давайте посмотрим, что происходит, когда вы добавляете ребро E, которого нет в MST.Давайте применим любимый математический способ усложнения и добавим некоторые обозначения ;) Вызовем исходный график G, график перед добавлением Eg' и график после добавления Eg ".Итак, нам нужно выяснить, как изменяется "количество базовых циклов" от G' к G".

Добавление E должно закрыть по крайней мере один цикл (в противном случае E было бы на первом месте в G в первую очередь).Поэтому очевидно, что он должен добавить по крайней мере один "базовый цикл" к уже существующим в G'.Но добавляет ли это больше одного?

Он не может добавить более двух, поскольку ни одно ребро не может быть членом более чем двух базовых циклов.Но если E является членом двух базовых циклов, то "объединение" этих двух базовых циклов должно было быть базовым циклом в G', так что снова мы получаем, что изменение числа циклов по-прежнему равно единице.

Следовательно, для каждого ребра, не входящего в MST, вы получаете новый базовый цикл.Итак, часть "подсчета" проста.Найти все ребра для каждого базового цикла немного сложнее, но, следуя приведенным выше рассуждениям, я думаю, что это могло бы сделать это (в псевдопитоне):

for v in vertices[G]:
    cycles[v] = []

for e in (edges[G] \ mst[G]):
    cycle_to_split = intersect(cycles[e.node1], cycles[e.node2])
    if cycle_to_split == None:
        # we're adding a completely new cycle
        path = find_path(e.node1, e.node2, mst[G])
        for vertex on path:
            cycles[vertex].append(path + [e]) 
        cycles
    else:
        # we're splitting an existing base cycle
        cycle1, cycle2 = split(cycle_to_split, e)
        for vertex on cycle_to_split:
            cycles[vertex].remove(cycle_to_split)
            if vertex on cycle1:
                cycles[vertex].append(cycle1)
            if vertex on cycle2:
                cycles[vertex].append(cycle2)

base_cycles = set(cycles)

Редактировать:код должен найти все базовые циклы на графике (base_cycles задан внизу).Предполагается, что вы знаете, как:

  • найти минимальное остовное дерево графа (mst[G])
  • найдите разницу между двумя списками (ребра \ mst[G])
  • найдите пересечение двух списков
  • найдите путь между двумя вершинами на MST
  • разделите цикл на две части, добавив к нему дополнительное ребро (функция разделения)

И это в основном следует из приведенного выше обсуждения.Для каждого ребра, не входящего в MST, у вас есть два случая:либо это приводит к совершенно новому базовому циклу, либо разделяет существующий на две части.Чтобы отследить, какой из двух имеет место, мы отслеживаем все базовые циклы, частью которых является вершина (используя словарь циклов).

Другие советы

Вдобавок ко всему, я бы начал с изучения любого алгоритма минимального связующего дерева (Prim, Kruskal и т. д.). Не может быть больше базовых циклов (если я правильно понимаю), чем ребер, которых нет в MST ....

Ниже приведен мой непроверенный код C #, чтобы найти все эти "базовые циклы": 

public HashSet<List<EdgeT>> FindBaseCycles(ICollection<VertexT> connectedComponent)
{
   Dictionary<VertexT, HashSet<List<EdgeT>>> cycles =
       new Dictionary<VertexT, HashSet<List<EdgeT>>>();

   // For each vertex, initialize the dictionary with empty sets of lists of
   // edges
   foreach (VertexT vertex in connectedComponent)
       cycles.Add(vertex, new HashSet<List<EdgeT>>());

   HashSet<EdgeT> spanningTree = FindSpanningTree(connectedComponent);

   foreach (EdgeT edgeNotInMST in
           GetIncidentEdges(connectedComponent).Except(spanningTree)) {
       // Find one cycle to split, the HashSet resulted from the intersection
       // operation will contain just one cycle
       HashSet<List<EdgeT>> cycleToSplitSet =
           cycles[(VertexT)edgeNotInMST.StartPoint]
               .Intersect(cycles[(VertexT)edgeNotInMST.EndPoint]);

       if (cycleToSplitSet.Count == 0) {
           // Find the path between the current edge not in ST enpoints using
           // the spanning tree itself
           List<EdgeT> path =
               FindPath(
                   (VertexT)edgeNotInMST.StartPoint,
                   (VertexT)edgeNotInMST.EndPoint,
                   spanningTree);

           // The found path plus the current edge becomes a cycle
           path.Add(edgeNotInMST);

           foreach (VertexT vertexInCycle in VerticesInPathSet(path))
               cycles[vertexInCycle].Add(path);
       } else {
            // Get the cycle to split from the set produced before
            List<EdgeT> cycleToSplit = cycleToSplitSet.GetEnumerator().Current;
            List<EdgeT> cycle1 = new List<EdgeT>();
            List<EdgeT> cycle2 = new List<EdgeT>();
            SplitCycle(cycleToSplit, edgeNotInMST, cycle1, cycle2);

            // Remove the cycle that has been splitted from the vertices in the
            // same cicle and add the results from the split operation to them 
            foreach (VertexT vertex in VerticesInPathSet(cycleToSplit)) {
                cycles[vertex].Remove(cycleToSplit);
                if (VerticesInPathSet(cycle1).Contains(vertex))
                     cycles[vertex].Add(cycle1);
                     if (VerticesInPathSet(cycle2).Contains(vertex))
                         cycles[vertex].Add(cycle2); ;
            }
       }
   }
   HashSet<List<EdgeT>> ret = new HashSet<List<EdgeT>>();
   // Create the set of cycles, in each vertex should be remained only one
   // incident cycle
       foreach (HashSet<List<EdgeT>> remainingCycle in cycles.Values)
           ret.AddAll(remainingCycle);

       return ret;
}

Oggy's код был очень хорошим и понятным , но я уверен, что в нем есть ошибка, или я не понимаю ваш псевдопифонный код:) 

cycles[v] = []

не может быть индексированным по вершинам словарем списков ребер. По моему мнению, это должен быть словарь с индексами вершин наборов списков ребер.

И, чтобы добавить уточнение: 

for vertex on cycle_to_split:

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

Повторюсь, это непроверенный и незавершенный код, но это шаг вперед. Это все еще требует правильной структуры графа (я использую список инцидентности) и многих алгоритмов графа, которые вы можете найти в учебниках, таких как Кормен. Я не смог найти FindPath () и SplitCycle () в учебниках, и очень трудно их кодировать за линейное время числа ребер + вершин в графе. Я сообщу о них здесь, когда я проверю их.

Огромное спасибо, Огги!

Стандартный способ обнаружения цикла - использовать два итератора - для каждой итерации один перемещается на один шаг вперед, а два других - вперед. Если будет цикл, они в какой-то момент будут указывать друг на друга.

Этот подход можно расширить, чтобы записывать найденные циклы и двигаться дальше.

Лицензировано под: CC-BY-SA с атрибуция
Не связан с StackOverflow
scroll top