r - Using igraph/network packages, how do I determine if network is fully connected (each vertex can reach each other vertex somehow)

Question

I have a table of Inbound/Outbound flights and travel times. I need to determine if the flight network is "fully connected", meaning that you can get from every city to every other city somehow. It doesn't matter how many flights it takes (whether a direct flight, or multiple flights).

There are ~58 flight locations in total, and ~438 different combinations (not sure if it matters or not). This is a sample of the data:

╔═════════╦══════════╦═════════╗
║ Inbound ║ Outbound ║ Minutes ║
╠═════════╬══════════╬═════════╣
║ ACY     ║ ATL      ║     102 ║
╠═════════╬══════════╬═════════╣
║ ACY     ║ FLL      ║     136 ║
╠═════════╬══════════╬═════════╣
║ ACY     ║ MCO      ║     122 ║
╠═════════╬══════════╬═════════╣
║ ACY     ║ MYR      ║      90 ║
╠═════════╬══════════╬═════════╣
║ ACY     ║ RSW      ║     137 ║
╠═════════╬══════════╬═════════╣
║ ACY     ║ TPA      ║     129 ║
╠═════════╬══════════╬═════════╣
║ ATL     ║ ACY      ║     102 ║
╠═════════╬══════════╬═════════╣
║ ATL     ║ BOS      ║     132 ║
╚═════════╩══════════╩═════════╝

---

This is what I have set up so far:

data <- read.table(file="filename.txt", header=TRUE, sep = "\t")
colnames(data) <- c("Inbound", "Outbound", "Minutes")

# Make a directed igraph object from inbound/outbound columns
graph <- graph_from_data_frame(data[, c("Inbound", "Outbound")], directed=TRUE,vertices=NULL)

# Make an edgelist from the igraph object
edgelist <- as_edgelist(graph, names=T)

# Make network object from edgelist
network <- as.network(edgelist)

# Use Minutes as weight for edges
E(graph)$weight <- data$Minutes

---

Then (I THINK) I have code that properly gets the shortest path from each city to every other city:

shortestPaths <- do.call(c, lapply(V(graph), function(v) get.shortest.paths(graph,v,V(graph), weights=weights, output='epath')$epath))

But how do I find the pairs of airports that can't reach each other using only flights? (As in, no direct/layover flights to connect them)

---

EDIT So I have made some progress, but it isn't 100% what I need.

Using this code, I get the total time for each path (from one city to another):

shortestPathsTimes <- do.call(c, lapply(V(graph),
  function(v) shortest.paths(graph,v,V(graph),
  weights=weights)))

I added a couple of fake lines that don't have any shared inbound/outbound. I discovered that the code above returns "inf" any time a path isn't connected. So using this:

noPath <- shortestPathsTimes[which(is.infinite(shortestPathsTimes))]

Returns output like this (basically each location has 2 Inf, one for each of the 2 fake locations I created).

+===============================================================================+
| ACY59 ACY60  ATL59 ATL60  AUA59 AUA60  AXM59 AXM60  BDL59 BDL60  BOG59 BOG60  |
+===============================================================================+
| Inf  Inf  Inf  Inf  Inf  Inf  Inf  Inf  Inf  Inf  Inf  Inf                    |
+-------------------------------------------------------------------------------+

---

HOWEVER, what I need is the actual text path shown, like how get.shortest.paths outputs. So for example, I need it to just return something like ACY=>TESTIN, ACY=>TESTOUT, ATL=>TESTIN, ATL=>TESTOUT, and so on.

标签： rigraph