igraph in R：接続を維持しながら、非分岐点の頂点を削除するにはどうしたらいいですか？

Question

私はいくつかの木のような構造の画像からグラフを抽出しました。グラフは、たとえその点が分岐または端ではない（すなわち、ノード順序が2である）場合でも、各関節点の頂点を有する。これらの2次頂点を削除したいが、これらの中間体を介して接続されていた分岐点または終了頂点が1つのエッジで接続されるように接続性を維持したい。小さなグラフでは、頂点を削除してエッジを1つずつ接続することでこれを行うことができますが、10,000+エッジで作業する場合はこれが遅いです。

これは開始グラフの例です。 I 9と同様に4を接続するエッジを挿入している間、私はエッジを挿入しながら、頂点5を削除したい、8および6頂点（例えば）削除したい7〜4

edge_matrix = cbind(
    c(1,2,3,4,4,5,6,8,9,9,10,11), 
    c(2,3,4,5,6,7,8,9,10,11,12,13)) 
example_graph = graph.data.frame(edge_matrix, directed=F) 

structure(list(13, FALSE, c(1, 2, 3, 4, 5, 10, 6, 7, 8, 9, 11, 
12), c(0, 1, 2, 3, 3, 4, 5, 6, 7, 7, 8, 9), c(0, 1, 2, 3, 4, 
6, 7, 8, 9, 5, 10, 11), c(0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11 
), c(0, 0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12), c(0, 1, 2, 
3, 5, 6, 7, 8, 10, 11, 12, 12, 12, 12), list(c(1, 0, 1), structure(list(), .Names = character(0)), 
    structure(list(name = c("1", "2", "3", "4", "5", "6", "8", 
    "9", "10", "11", "7", "12", "13")), .Names = "name"), list()), 
    <environment>), class = "igraph") 

Answer 1

私はこれを間違ったやり方でやっていると確信していますが、基本的に度数が2のノードを探してグラフを歩き回り、それらをすべて新しいグラフに再接続する関数です。

walk_thin <- function(g, v=V(g)[[1]]) { 
    dd <- degree(g) 
    keep <- V(g)[names(dd[dd!=2])] 
    edges <- c() 
    find_next <- function(v, from, past = c()) { 
    v2 <- adjacent_vertices(g, v)[[1]] 
    v2 <- v2[!v2 %in% past] 
    for(i in seq_along(v2)) { 
     nv <- v2[i] 
     if (nv %in% keep) { 
     edges <<- c(c(from, nv)$name, edges) 
     find_next(nv, nv, past=c(nv, past)) 
     } else { 
     find_next(nv, from, past=c(nv, past)) 
     } 
    } 
    } 
    find_next(v, v, v) 
    make_graph(edges,directed = FALSE) 
} 

実際に、それだけではなく、再構築しようとするよりも、グラフの次数2のノードを削除する方が良いかもしれあなたのサンプルデータ

g <- walk_thin(example_graph) 
plot(g) 

Answer 2

で動作するようです最小限の情報を持つグラフ。この関数は再帰を気にしないし、おそらくより効率的

trim_deg2 <- function(g) { 
    get_deg2 <- function(x) { 
    dd <- degree(x) 
    trim <- V(x)[names(dd[dd==2])]  
    } 
    ng <- g 
    trim <- get_deg2(ng) 
    while(length(trim)) { 
    tv <- trim[1] 
    touch <- adjacent_vertices(ng, tv)[[1]] 
    ng <- delete_edges(ng, E(ng)[tv %--% touch]) 
    ng <- add_edges(ng, touch$name) 
    ng <- delete_vertices(ng, V(ng)[tv]) 
    trim <- get_deg2(ng) 
    } 
    ng 
} 

それはあなたのサンプルデータ

g <- trim_deg2(example_graph) 
plot(g)