Come dividere un igraph in sottografi connessi?

Question

Ho un igraph con diversi componenti disconnessi. Ad esempio:

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

In questo esempio, il nodo 9 è proprio grafico, come lo sono i nodi 7 e 8, e il resto formare un terzo grafico.

Vorrei trattare questi separatamente, quindi voglio convertire la singola igraph in una lista di 3 igraphs (divisi per connessione).

Ho hackerato del codice per ottenere questo risultato, ma è inefficiente e abbastanza orribile.

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) 

C'è un modo più pulito di dividere il grafico?

Answer 1

Si potrebbe calcolare i componenti collegati del vostro grafico utilizzando:

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

Oppure si potrebbe creare un grafico separato per ciascun componente del grafico utilizzando:

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