Алгоритмы для идентификации всех циклических баз в неориентированном графе
У меня есть ненаправленный граф с вершины V и край E, Я ищу алгоритм для идентификации всех основ цикла в этом графе.
Я думаю, что алгоритм Таржана - хорошее начало. Но у меня есть ссылка на поиск всех циклов, а не базы циклов (которая по определению является циклом, который не может быть построен путем объединения других циклов).
Например, взгляните на график ниже:
Таким образом, алгоритм будет полезен. Если есть существующая реализация (желательно в C#), это даже лучше!
4 ответа
Из того, что я могу сказать, Брайан не только находится в догадке, но еще более сильное предложение: каждое ребро, которое не входит в минимальное связующее дерево, добавляет ровно один новый "базовый цикл".
Чтобы увидеть это, давайте посмотрим, что произойдет, когда вы добавите ребро E, которого нет в MST. Давайте сделаем любимый математический способ усложнить вещи и добавить некоторые обозначения;) Назовите исходный граф G, график перед добавлением E G'и график после добавления E G''. Итак, нам нужно выяснить, как меняется "счет базового цикла" с G на G.
Добавление E должно завершить хотя бы один цикл (в противном случае E было бы в MST G). Очевидно, он должен добавить хотя бы один "базовый цикл" к уже существующим в G'. Но это добавляет больше чем один?
Он не может добавить больше двух, поскольку ни одно ребро не может быть членом более двух базовых циклов. Но если E является членом двух базовых циклов, то "объединение" этих двух базовых циклов, должно быть, было базовым циклом в G', поэтому мы снова получаем, что изменение количества циклов по-прежнему равно единице.
Ergo, для каждого ребра не в MST вы получаете новый базовый цикл. Таким образом, часть "считать" проста. Найти все ребра для каждого базового цикла немного сложнее, но, следуя рассуждениям выше, я думаю, что это можно сделать (в псевдо-Python):
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, у вас есть два случая: либо он приносит совершенно новый базовый цикл, либо разбивает существующий один на два. Чтобы отследить, какой из двух случаев имеет место, мы отслеживаем все базовые циклы, частью которых является вершина (используя словарь циклов).
Вдобавок ко всему, я бы начал с рассмотрения любого алгоритма Minimum Spanning Tree (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;
}
Код Огги был очень хорош и ясен, но я уверен, что он содержит ошибку, или я не понимаю ваш код псевдо-питона:)
cycles[v] = []
не может быть индексированным по вершинам словарем списков ребер. На мой взгляд, это должен быть индексированный по вершинам словарь наборов списков ребер.
И, чтобы добавить уточнение:
for vertex on cycle_to_split:
цикл-к-разделению, вероятно, является упорядоченным списком ребер, поэтому для его итерации по вершинам вы должны преобразовать его в набор вершин. Порядок здесь ничтожен, поэтому это очень простой алгоритм.
Повторяю, это непроверенный и неполный код, но это шаг вперед. Это все еще требует правильной структуры графа (я использую список инцидентности) и многих алгоритмов графа, которые вы можете найти в учебниках, таких как Кормен. Я не смог найти FindPath() и SplitCycle() в учебниках, и мне очень трудно их кодировать за линейное время числа ребер + вершин в графе. Сообщу о них здесь, когда я их опробую.
Большое спасибо, Огги!
Стандартный способ обнаружения цикла состоит в использовании двух итераторов - для каждой итерации один движется вперед на один шаг, а два других - вперед. Если будет цикл, они в какой-то момент будут указывать друг на друга.
Этот подход может быть расширен, чтобы записывать найденные циклы и двигаться дальше.