Риграф найти все циклы - PullRequest
Новая
       18

Риграф найти все циклы

0 голосов
/ 10 марта 2019

Я направил игру и хочу получить все циклы. Функция обхвата работает, но возвращает только самый маленький цикл. Есть ли способ в R выбрать все циклы в графе длины больше 3 (без вершин, указывающих на себя и циклов)

1 Ответ

3 голосов
/ 11 марта 2019

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

Пример данных 

## Sample graph
library(igraph)
set.seed(1234)
g = erdos.renyi.game(7, 0.29, directed=TRUE)
plot(g, edge.arrow.size=0.5)

Sample Graph

Поиск циклов

Позвольте мне начать с одного узла и одного соседа. Узел 2 соединяется с Узлом 4. Таким образом, некоторые циклы могут выглядеть как 2 -> 4 -> (Узлы, отличные от 2 или 4) -> 2. Давайте получим все пути, подобные этому. 

v1 = 2
v2 = 4
lapply(all_simple_paths(g, v2,v1, mode="out"), function(p) c(v1,p))
[[1]]
[1] 2 4 2
[[2]]
[1] 2 4 3 5 7 6 2
[[3]]
[1] 2 4 7 6 2

Мы видим, что есть три цикла, начинающиеся с 2 с 4 в качестве второго узла. (Я знаю, что вы сказали, что длина больше 3. Я вернусь к этому.)

Теперь нам просто нужно сделать это для каждого узла v1 и каждого соседа v2 из v1. 

Cycles = NULL
for(v1 in V(g)) {
    for(v2 in neighbors(g, v1, mode="out")) {
        Cycles = c(Cycles, 
            lapply(all_simple_paths(g, v2,v1, mode="out"), function(p) c(v1,p)))
    }
}

Это дает 17 циклов во всем графике. Есть две проблемы, которые вам, возможно, придется рассмотреть в зависимости от того, как вы хотите это использовать. Во-первых, вы сказали, что хотите иметь циклы длиной больше 3, поэтому я предполагаю, что вы не хотите, чтобы циклы выглядели как 2 -> 4 -> 2. От них легко избавиться. 

LongCycles = Cycles[which(sapply(Cycles, length) > 3)]

LongCycles имеет 13 циклов, исключив 4 коротких цикла 

2 -> 4 -> 2
4 -> 2 -> 4
6 -> 7 -> 6
7 -> 6 -> 7

Но этот список указывает на другую проблему. Есть некоторые циклы, которые вы можете рассматривать как дубликаты. Например: 

2 -> 7 -> 6 -> 2
7 -> 6 -> 2 -> 7
6 -> 2 -> 7 -> 6

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

LongCycles[sapply(LongCycles, min) == sapply(LongCycles, `[`, 1)]
[[1]]
[1] 2 4 3 5 7 6 2
[[2]]
[1] 2 4 7 6 2
[[3]]
[1] 2 7 6 2

Это дает только отдельные циклы.

Дополнение относительно эффективности и масштабируемости

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

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

## More efficient version
FindCycles = function(g) {
    Cycles = NULL
    for(v1 in V(g)) {
        if(degree(g, v1, mode="in") == 0) { next }
        GoodNeighbors = neighbors(g, v1, mode="out")
        GoodNeighbors = GoodNeighbors[GoodNeighbors > v1]
        for(v2 in GoodNeighbors) {
            TempCyc = lapply(all_simple_paths(g, v2,v1, mode="out"), function(p) c(v1,p))
            TempCyc = TempCyc[which(sapply(TempCyc, length) > 3)]
          TempCyc = TempCyc[sapply(TempCyc, min) == sapply(TempCyc, `[`, 1)]
          Cycles  = c(Cycles, TempCyc)
        }
    }
    Cycles
}

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

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

## ecount ~ 2 * vcount
Nodes   Edges   Cycles
10   21    15
20   41    18
30   65    34
40   87   424
50  108  3433
55  117 22956

Но вы сообщаете, что ваши данные имеют примерно в 5 раз много ребер как вершины. Давайте посмотрим на некоторые примеры, подобные этому. 

## ecount ~ 5 * vcount
Nodes  Edges    Cycles
10      48        3511
12      61       10513
14      71      145745

С учетом роста числа циклов, используя 10К узлов с краями 50K, кажется, не может быть и речи. Кстати, это заняло несколько минут для вычисления примера с 14 вершинами и 71 ребром.

Для воспроизводимости, вот как я генерировал вышеупомянутые данные. 

set.seed(1234)
g10 = erdos.renyi.game(10, 0.2, directed=TRUE)
ecount(g10)
length(FindCycles(g10))

set.seed(1234)
g20 = erdos.renyi.game(20, 0.095 , directed=TRUE)
ecount(g20)
length(FindCycles(g20))

set.seed(1234)
g30 = erdos.renyi.game(30, 0.056 , directed=TRUE)
ecount(g30)
length(FindCycles(g30))

set.seed(1234)
g40 = erdos.renyi.game(40, 0.042 , directed=TRUE)
ecount(g40)
length(FindCycles(g40))

set.seed(1234)
g50 = erdos.renyi.game(50, 0.038 , directed=TRUE)
ecount(g50)
length(FindCycles(g50))

set.seed(1234)
g55 = erdos.renyi.game(55, 0.035 , directed=TRUE)
ecount(g55)
length(FindCycles(g55))

##########
set.seed(1234)
h10 = erdos.renyi.game(10, 0.55, directed=TRUE)
ecount(h10)
length(FindCycles(h10))

set.seed(1234)
h12 = erdos.renyi.game(12, 0.46, directed=TRUE)
ecount(h12)
length(FindCycles(h12))

set.seed(1234)
h14 = erdos.renyi.game(14, 0.39, directed=TRUE)
ecount(h14)
length(FindCycles(h14))
...