Использование bfs (igraph, R) для выборки из моего большого графика

У меня есть большой график, и я хотел бы «разбить его на части», используя подход поиска в ширину. То есть я случайным образом выбираю начальную вершину, а затем выполняю BFS, пока у меня не останется граф с (например) 100 вершинами. Это процесс, который я планирую повторять несколько раз, чтобы в конечном итоге у меня было несколько разных подграфов моего большого графа. На данный момент, вот как я кодирую это в R (это просто пример, мой граф не является кольцом).

y <- make_ring(1000)
bfsy <- bfs(y, root=1, "all", order=TRUE)
suby <- bfsy$order[1:100]
newgraph = induced.subgraph(y, suby)

Очевидно, это неэффективно, так как я выполняю всю BFS и мне нужно всего 100 вершин. Любые намеки на то, как кодировать это лучше? И какие-нибудь намеки на то, как я могу еще больше рандомизировать этот процесс, рандомизируя порядок очереди на каждом новом этапе (это моя следующая проблема, которую нужно решить, ха)? Ссылки на область учебников / документов всегда приветствуются.


r graph-traversal igraph breadth-first-search
person EUps    schedule 02.10.2016    source источник
comment
Ошибка: не удалось найти функцию bfs... в какой библиотеке находится эта функция   -  person and-bri    schedule 03.10.2016
comment
он находится в библиотеке (igraph). Извините, я не уточнил это.   -  person EUps    schedule 03.10.2016

Ответы (2)


arrow_upward
1
arrow_downward

Вы можете попробовать использовать параметр функции обратного вызова следующим образом, также вы можете использовать дополнительный параметр:

y <- make_ring(1000)
f <- function(graph, data, extra) {
 data['rank'] == 100
}
bfsy  <- bfs(y, root=1, "all", order=TRUE, callback = f)

bfsy$order # only the first 100 values are not NAs
+ 1000/1000 vertices:
   [1]    1    2 1000    3  999    4  998    5  997    6  996    7  995    8  994    9  993   10  992   11  991   12  990   13  989   14  988
  [28]   15  987   16  986   17  985   18  984   19  983   20  982   21  981   22  980   23  979   24  978   25  977   26  976   27  975   28
  [55]  974   29  973   30  972   31  971   32  970   33  969   34  968   35  967   36  966   37  965   38  964   39  963   40  962   41  961
  [82]   42  960   43  959   44  958   45  957   46  956   47  955   48  954   49  953   50  952   51  951   NA   NA   NA   NA   NA   NA   NA
 [109]   NA   NA   NA   NA   NA   NA   NA   NA   NA   NA   NA   NA   NA   NA   NA   NA   NA   NA   NA   NA   NA   NA   NA   NA   NA   NA   NA
 [136]   NA   NA   NA   NA   NA   NA   NA   NA   NA   NA   NA   NA   NA   NA   NA   NA   NA   NA   NA   NA   NA   NA   NA   NA   NA   NA   NA
 [163]   NA   NA   NA   NA   NA   NA   NA   NA   NA   NA   NA   NA   NA   NA   NA   NA   NA   NA   NA   NA   NA   NA   NA   NA   NA   NA   NA
 [190]   NA   NA   NA   NA   NA   NA   NA   NA   NA   NA   NA   NA   NA   NA   NA   NA   NA   NA   NA   NA   NA   NA   NA   NA   NA   NA   NA
 [217]   NA   NA   NA   NA   NA   NA   NA   NA   NA   NA   NA   NA   NA   NA   NA   NA   NA   NA   NA   NA   NA   NA   NA   NA   NA   NA   NA
 [244]   NA   NA   NA   NA   NA   NA   NA   NA   NA   NA   NA   NA   NA   NA   NA   NA   NA   NA   NA   NA   NA   NA   NA   NA   NA   NA   NA

suby <- bfsy$order[1:100]
newgraph = induced.subgraph(y, suby)
person Sandipan Dey    schedule 03.10.2016

arrow_upward
0
arrow_downward

Я не знаком с R, но думаю, вы можете легко это сделать, используя собственный метод обхода графа. Просто измените BFS или DFS в соответствии с вашими требованиями:

VERTICES = 100
RANDOM_CHANCE = 0.5

Breadth-First-Search(Graph, root):

     create empty queue Q      

     Q.enqueue(root)
     visited.put(root)     
     create empty list Edges        

     # this will stop the BFS after reaching to a certain amount of nodes
     while Q is not empty AND visited.size() <‌ VERTICES:        
         current = Q.dequeue()

         for each node n that is adjacent to current:
             if n in visited:
                 continue
             # This will randomly choose the edges
             if random() < RANDOM_CHANCE:
                 continue
             Q.enqueue(n)
             visited.put(n)
             Edges.put( current->n )

В конце концов, ваш подграф состоит из узлов visited и ребер в Edges. Вы можете настроить значение VERTICES и RANDOM_CHANCE, чтобы получить различные виды графиков. Также вы можете установить ограничение на количество ребер.

Вы можете применить аналогичный метод к DFS. DFS даст вам графики с большей глубиной.

person Saeid    schedule 03.10.2016