Finden von linearen Pfadabschnitten in einem Graph in R

Question

Ich muss eine azyklische Grafik in lineare Abschnitte partitionieren. Jeder Abschnitt ist ein linearer Pfad, der aus mindestens einem Knoten besteht. Lineare Abschnitte dürfen keine Verzweigungen enthalten.

Zum Beispiel, hier ist ein Beispiel grafische Darstellung:

library(igraph); 
dor = data.frame(from = c(1, 1, 2, 3, 4, 5, 6), 
    to = c(2, 3, 4, 5, 6, 6, 7)) 
g = graph_from_data_frame(dor) 
plot(g) 

In diesem Diagramm gibt es 4 lineare Abschnitte:

1 
3 -> 5 
2 -> 4 
6 -> 7 

Wie ich eine Grafik in einem linearen partitionieren Wegabschnitte?

Answer 1

Ich denke, dass was Sie tun möchten, ist dies. Wenn ein Knoten mehr als eine eingehende Kante hat, löschen Sie alle eingehenden Kanten. Wenn ein Knoten mehr als eine ausgehende Kante hat, löschen Sie alle ausgehenden Kanten. Also meine vorgeschlagene Lösung ... zählt die einfallenden Kanten und löscht sie, wenn es zu viele gibt.

## Your original data 
library(igraph) 
dor = data.frame(from = c(1, 1, 2, 3, 4, 5, 6), 
    to = c(2, 3, 4, 5, 6, 6, 7)) 
g = graph_from_data_frame(dor) 


g2 = g 
TooManyOut = which(sapply(incident_edges(g2, V(g2), mode="out"), length) > 1) 
for(TMO in TooManyOut) { 
    g2 = delete_edges(g2, attr(incident_edges(g2, V(g2), mode="out")[[TMO]], "vnames")) 
} 
TooManyIn = which(sapply(incident_edges(g2, V(g2), mode="in"), length) > 1) 
for(TMI in TooManyIn) { 
    g2 = delete_edges(g2, attr(incident_edges(g2, V(g2), mode="in")[[TMI]], "vnames")) 
} 
plot(g2) 

Natürlich können Sie bekommen, welche Knoten mit components verbunden sind.