Wie finden ‚ersten‘ und ‚letzten‘ Vertex

Question

nach Knoten verbunden ich eine Adjazenzmatrix Angenommen, haben wie folgt:

library(igraph) 
df <- data.frame(id = 1:8, parent = c(NA, NA, 1, 1, 3, 4, NA, 7)) 
g <- graph_from_data_frame(na.omit(df)) 

Für jede Ecke, wie mache ich das erste und letzte Vertices im gerichteten Pfad? Zum Beispiel beginnt der Vertex '4' bei 6 und endet bei 1. (Alternativ würde das Erlangen einer Liste aller Vertices in diesem Pfad funktionieren).

Answer 1

Betrachten Sie eine topologische Sortierung. Topologisches Sortieren eines gerichteten Graphen gibt Ihnen den ersten und letzten Eckpunkt.

Für R können Sie die topologische Sortiermethode im igraph-Paket verwenden. http://igraph.org/r/doc/topo_sort.html

Answer 2

Nach this answer endete I auf dem Wald dabei eine Graph Zersetzung, dann finden, die Scheitelpunkte gleich 0 einen Ausgangsgrad hatte, wodurch den Wurzelknoten für jeden Baumbestimmungs (für das gleiche zu tun in Grad Ausbeuten welche Scheitelpunkte sind terminal, obwohl ich erkannte, dass ich diese Information nicht brauchte - als Ergebnis schreibe ich das nicht als Antwort.

library(igraph) 
library(dplyr) 

df <- data.frame(id = 1:8, parent = c(NA, NA, 1, 1, 3, 4, NA, 7)) 
edgelist_df <- na.omit(df) 
g <- graph_from_data_frame(edgelist_df) 

tree_to_df <- function(graph, forest_edgelist){ 
    # for a directed tree, find its root and assign that root to every 
    # node in the tree's edgelist 

    # `dplyr::filter` fails on the subset below, so we use base R 
    tree_dat <- forest_edgelist[forest_edgelist$id %in% V(graph)$name,] 

    root <- which(degree(graph, v = V(graph), mode = 'out') == 0, useNames = T) 
    tree_dat$root <- names(root) 
    return(tree_dat) 
} 

root_dat <- 
    decompose.graph %>% # find connected subgraphs 
    lapply(tree_to_df, forest_edgelist = edgelist_df) %>% 
    bind_rows