Как разбить граф на связанные подграфы?

У меня есть график с несколькими отключенными компонентами. Например:

library(igraph)
g <- simplify(
  graph.compose(
    graph.ring(10), 
    graph.star(5, mode = "undirected")
  )
) + edge("7", "8")

сюжет графика с несколькими отключенными компонентами

В этом примере узел 9 является собственным графом, как узлы 7 и 8, а остальные образуют третий граф.

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

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

split_graph_into_connected_subgraphs <- function(g)
{
  adjacency_list <- get.adjlist(g)

  connected_nodes <- lapply(
    adjacency_list,
    function(adjacent_nodes)
    {
      new_nodes <- out <- adjacent_nodes
      # Keep finding nodes that are adjacent to ones we already know about,
      # until we find no more
      repeat
      {
        doubly_adjacent_nodes <- Reduce(union, adjacency_list[new_nodes])
        new_nodes <- setdiff(doubly_adjacent_nodes, out)
        if(length(new_nodes) == 0)
        {
          break
        }
        out <- union(out, new_nodes)      
      }
      sort(out)
    }
  )

  # Single value nodes should contain themselves, not be empty
  connected_nodes <- ifelse(
    vapply(adjacency_list, length, integer(1)) == 0,
    seq_along(connected_nodes),
    connected_nodes
  )

  # We don't care about repeats, just the unique graphs
  connected_nodes <- unique(connected_nodes)

  # Get the subgraph from each 
  lapply(
    connected_nodes,
    function(nodes) induced.subgraph(g, nodes)
  )
}

list_of_subgraphs <- split_graph_into_connected_subgraphs(g)
lapply(list_of_subgraphs, plot)

Есть ли более чистый способ разбить граф?


r igraph
person Richie Cotton    schedule 19.04.2015    source источник

Ответы (1)


arrow_upward
41
arrow_downward

Вы можете рассчитать связанные компоненты вашего графика, используя:

clusters(g)
# $membership
# [1] 1 1 1 1 1 1 2 2 3 1
# 
# $csize
# [1] 7 2 1
# 
# $no
# [1] 3

Или вы можете создать отдельный график для каждого компонента вашего графика, используя:

dg <- decompose.graph(g) # returns a list of three graphs
plot(dg[[1]]) # plot e.g. the 1st one

введите описание изображения здесь

person lukeA    schedule 19.04.2015
comment
Гарантирует ли это, что первый компонент всегда самый большой? - person Michael Schubert; 25.04.2017
comment
@ user538603 нет. Однако вы можете заказать результат по vcount и получить желаемый результат. - person lukeA; 27.04.2017