Итеративное создание графа без циклов из другого графа путем удаления ребер

Question

У меня есть ненаправленный граф с некоторыми ребрами, и он гарантированно будет иметь несколько циклов.Назовем этот граф G1.Я должен создать еще один график, скажем, G2 из этого графика итеративным способом.Я беру одно ребро из первого графа G1 и добавляю его ко второму графу G2 тогда и только тогда, когда добавление этого ребра не создает циклов в G2.Если это создает цикл, я не добавляю это ребро.Способ, которым мне нужно вынуть ребра, определяется в моей программной логике.(У каждого ребра есть тип, и мы используем ребра первого типа, а затем второго типа и т. Д.)

Поэтому я использовал алгоритм поиска нормального цикла, например https://www.geeksforgeeks.org/detect-cycle-undirected-graph/ каждый раз после добавления ребра.Если он создал цикл, я удалил ребро из второго графа G2.К сожалению, это чертовски медленно на графике 5000 узлов.Каковы лучшие подходы для решения этой проблемы?

Информация на графике: Ребра на графиках представляют сложную топологию сети.Каждое ребро является структурой данных

struct edge
{
  int weight ;
  int type ;
  int verter1;
  int vertex2;
};

Тип является целым числом enum

enum type
{
  wired , wifi , 4g , 3g , 2g ;
} ;

Данные не являются произвольными, но назначаются на основе некоторых сетевых данных.Затем логика обработки требует создания второго графа на основе типов.Мы хотим сначала использовать проводные линии без создания циклов.Затем обрабатывать линии Wi-Fi и так далее.

Answer 1

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

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

Чтобы быстро найти, к какому компоненту принадлежит вершина, создайте карту, снабженную вершинами. Для данной вершины карта содержит в качестве значения компонент, членом которого является вершина.

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

Answer 2

Похоже, вы можете адаптировать Алгоритм Крускала для минимального связующего дерева . Вы действительно строите лес - множество деревьев - как G2. Это именно то, что делает алгоритм Крускала. Разница лишь в том, что у Крускала гарантированно заканчивается связное дерево. Ваш может или не может в зависимости от характера краев, которые вы пытаетесь добавить.

Изначально G2 - это лес, в котором каждый узел сам по себе является «деревом». Новое ребро образует цикл тогда и только тогда, когда оно соединяет два узла, которые уже находятся в одном дереве. Когда нет цикла, добавьте край. Это соединяет два дерева в одно, поэтому вычисляем объединение соответствующих наборов узлов.

Используйте хорошо известную UNION-FIND непересекающуюся структуру данных набора , чтобы очень эффективно отслеживать узлы каждого дерева, обнаруживать циклы и выполнять обновления. Каждая из этих операций предназначена для всех практических целей O (1), если UNION-FIND реализован правильно. (В действительном временном ограничении есть обратный термин Аккермана, но для числа атомов во вселенной это меньше 5 ...)

Следовательно, последний алгоритм будет запущен за время O (m), где m - количество ребер, которые вы пытаетесь вставить в G2.

Я действительно не могу улучшить презентацию в Википедии Крукалса или непересекающегося множества UNION-FIND . Круто то, что оба алгоритма очень компактны и просты в реализации. 5000 узлов не должно быть проблемой вообще. Я был бы удивлен, если бы 50 миллионов не были простыми для среднего современного ноутбука.

Добавлена ​​реализация Quick Hack Вот некоторый очень, очень слегка протестированный код. Кажется, работает, но не доверяйте ему для производства:

#include <stdio.h>
#include <stdlib.h>

struct vertex {
  int parent;
  int size;
};

struct edge {
  int a;
  int b;
  int is_g2_edge;
};

struct vertex vertices[40];
struct edge edges[100];
#define ARRAY_SIZE(A) (sizeof A / sizeof A[0])

void init_sets(void) {
  for (int x = 0; x < ARRAY_SIZE(vertices); ++x)
    vertices[x] = (struct vertex) {.parent = x, .size = 1};
}

int find(int x) {
  if (vertices[x].parent != x)
    vertices[x].parent = find(vertices[x].parent);
  return vertices[x].parent;
}

void merge(int x, int y) {
  x = find(x);
  y = find(y);
  if (x == y) return;
  if (vertices[x].size < vertices[y].size) {
   vertices[x].parent = y;
   vertices[y].size += vertices[x].size;
  } else {
   vertices[y].parent = x;
   vertices[x].size += vertices[y].size;
  }
}

void maybe_add_edge(int x) {
  int a_set = find(edges[x].a);
  int b_set = find(edges[x].b);
  if (a_set == b_set) {
    edges[x].is_g2_edge = 0;
    return;
  }
  edges[x].is_g2_edge = 1;
  merge(a_set, b_set);
}

int main(int argc, char *argv[]) {
  srand(argc > 1 ? atoi(argv[1]) : 42);
  // Build a random graph for fun.
  for (int x = 0; x < ARRAY_SIZE(edges); ++x) 
    edges[x] = (struct edge){
      .a = rand() % ARRAY_SIZE(vertices),
      .b = rand() % ARRAY_SIZE(vertices)
    };
  // Put all vertices in sets by themselves.
  init_sets();
  // Try adding all the edges to G2 in no special order.
  for (int x = 0; x < ARRAY_SIZE(edges); ++x) maybe_add_edge(x);
  // Print edges in DOT: G2 edges solid and not G2 dotted.
  printf("graph G {\n");
  for (int x = 0; x < ARRAY_SIZE(edges); ++x)
    printf(" %d -- %d%s\n", edges[x].a, edges[x].b,
           edges[x].is_g2_edge ? "" : " [style=dotted]");
  printf("}\n");
  return 0;
}

Когда я запускаю это с 5000 узлами и 30000 ребрами, время выполнения незаметно. Намного меньше секунды.

Вывод на языке DOT со сплошными ребрами G2 и пунктирными неиспользованными ребрами G1:

Answer 3

Краткий ответ

Действительно, проверка того, создается ли цикл каждый раз, когда вы добавляете вершину к графу G2, стоит дорого. Более эффективный метод может заключаться в с использованием поиска в ширину (BFS) на вашем графике G1 и в сообщать о ребрах, которые вы используете для перемещения от узла к другому, когда вы путешествуете по G1 в вашем G2 по ходу дела . Я рекомендую вторую часть этого видео для демонстрации BFS.

Регулярный BFS-обход G1 для построения G2

Сначала я опишу, как стандартный обход BFS может помочь вам устранить петли в исходном графике. Ваши предпочтения по удалению одних типов ребер перед другими см. Ниже.

Я собираюсь предположить, что каждая вершина знает, каковы ее соседи (то есть каждая вершина имеет некоторый список соседей, с которыми они имеют общее ребро). Рассмотрим следующий график:

Graph1:
A------B------C
|      |
D------E

При запуске алгоритма BFS мы добавим обнаруженные вершины в Graph2 с ребром, которое использовалось для их обнаружения.

Мы собираемся начать обход BFS графа в вершине A. Мы окрашиваем A как посещенный (я представляю его на графике как строчный символ) и помещаем его в нашу очередь узлов для проверки. Поскольку мы посетили A, и это наш первый узел, я поместил его в Graph2:

Graph1:                        Graph2:
a------B------C                A
|      |
D------E

Queue: A

Теперь мы выбираем первую вершину в очереди и проверяем ее соседей. Мы выбираем А из очереди. Узел A имеет "B" в качестве соседа, который еще не посещен. Мы окрашиваем B как «посещенные», добавляем его в очередь и добавляем во второй график с ребром, которое связывает его с A.

Graph1:                        Graph2:
a------b------C                A------B
|      |
D------E

Queue: A B

Следующим соседом узла A является D. D еще не посещался. Мы окрашиваем его как посещенный, добавляем в очередь и помещаем в Graph2 с краем, обозначенным буквой A. Мы исследовали всех соседей A, поэтому удалили его из нашей очереди.

Graph1:                        Graph2:
a------b------C                A------B
|      |                       |
d------E                       D

Queue: B D

Мы берем следующий узел в очереди: Узел B. Узел B имеет соседа A, который уже посещен -> здесь ничего не нужно делать. Следующий сосед - это узел C, который еще не посещен. Мы раскрасим его, добавим в очередь и добавим в graph2 с ребром в B.

Graph1:                        Graph2:
a------b------c                A------B------C                
|      |                       |
d------E                       D

Queue: B D C

Последним соседом B является узел E, который еще не посещен. Мы окрашиваем его, добавляем в очередь и добавляем его ребром в узел B в graph2. Наконец, мы удаляем B из очереди, как мы закончили с этим.

Graph1:                        Graph2:
a------b------c                A------B------C                
|      |                       |      |
d------e                       D      E

Queue: D C E

Затем мы берем следующий узел в очереди, D не имеет соседей, которые еще не посещены, поэтому он удаляется из очереди. То же самое касается узлов C и E. Когда очередь пуста, алгоритм завершается.

Теперь посмотрите на график 2: у него нет циклов.

Чтобы действительно решить вашу проблему, этот обычный обход BFS потребует некоторых адаптаций, которые я опишу ниже.

Постановка проблемы (пере) формулировка / желаемое поведение BFS для вашей конкретной потребности

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

Модификация состоит в том, чтобы начать исследование BFS для графа 1, но использовать только «проволочные» ребра. Когда этот первый обход прекращается (больше нет узлов в очереди), все равно останутся части графика, которые вы не смогли бы посетить, потому что вы не могли использовать ребра типа "wifi". В этом случае вы захотите перепроверить узлы, которые вы посетили, но используя ребра следующего типа. Если по Wi-Fi-ссылке вы можете получить доступ к узлу, который раньше у вас не было, вы захотите возобновить исследование с этого узла, используя «проводное» соединение.

Адаптация алгоритма BFS

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

В вашей ситуации, я думаю, вы можете использовать приоритетную очередь для хранения ваших узлов. В этой приоритетной очереди есть 5 отдельных очередей: по одной для каждого типа ребер (проводной, Wi-Fi, ...). В начале исследования узел помещается в проводную очередь. Алгоритм DFS исследует этот узел и добавит соседей, к которым можно получить доступ по проводам, в «проводную» очередь. Затем, вместо того, чтобы отбрасывать этот первый узел, вы помещаете его в следующую очередь, а именно в очередь "wifi".

Алгоритм BFS всегда должен выбирать узлы в очереди предпочитаемых ребер. Только когда нет узлов в «проводной очереди», он выбирает в очереди «Wifi».

Еще одна тонкость: когда вы выбираете узел из очереди "wifi", если есть невидимый сосед этого узла по wifi, вы помещаете этого соседа в очередь "проводной" и перезапускаете BFS, используя этот узел. В этой конкретной ситуации, когда вы получаете доступ к невидимому узлу с фронта с «более низким приоритетом», вы должны прекратить проверять соседей вашего текущего узла, так как эти соседи могут быть доступны по проводам от первого найденного вами соседа. Поэтому вы оставите текущий узел в своей очереди, чтобы вернуться к нему позже.

Надеюсь, мои объяснения понятны, я с нетерпением жду ваших комментариев.