Logo Questions Linux Laravel Mysql Ubuntu Git Menu
 

How to split an igraph into connected subgraphs?

Tags:

r

igraph

I have an igraph with several disconnected components. For example:

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

a plot of an igraph with several disconnected components

In this example, node 9 is its own graph, as are nodes 7 and 8, and the rest form a third graph.

I'd like to treat these separately, so I want to convert the single igraph into a list of 3 igraphs (split by connectedness).

I hacked some code to achieve this, but it's inefficient and fairly awful.

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) 

Is there a cleaner way of splitting the graph?

like image 703
Richie Cotton Avatar asked Apr 19 '15 13:04

Richie Cotton


People also ask

Are Subgraphs connected?

A graph is connected if and only if it has exactly one connected component. The strong components are the maximal strongly connected subgraphs of a directed graph. A vertex cut or separating set of a connected graph G is a set of vertices whose removal renders G disconnected.

What is the difference between subgraph and induced subgraph?

What's the Difference? , whereas an ordinary subgraph may miss some. So, an induced subgraph keeps both adjacency and non-adjacency of the inducing vertices, in contrast to an ordinary subgraph that preserves only non-adjacency.

What is a subgraph in R?

subgraph creates a subgraph of a graph, containing only the specified vertices and all the edges among them.


1 Answers

You could calculate the connected components of your graph by using:

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

Or you could create a separate graph for each component of your graph by using:

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

enter image description here

like image 177
lukeA Avatar answered Sep 22 '22 18:09

lukeA