How to extract certain types of paths in igraph?

Question

TL; DR: I would like to extract the border types of each path between two vertices in the graph. Is there a relatively reasonable way to do this?

---

The clinic in which I work recently conducted a fairly large (1,400 people) study of tuberculosis in high school. I have class schedules for all students and teachers (!) And are placed on the network (using igraph in R), with each student and each room-room combination being the top (for example, the class in Room 123 in Period 1 is the top with directed edge to the class that is in Room 123 for Period 2). I also know which rooms share the ventilation system - a plausible but unlikely infection mechanism. The graph is sent from a single source, so each path in the network has only two people - the source and the contact, separated by a variable number of vertices of space-time. Conceptually, there are four kinds of paths:

• personal contact (source → contact only)
• division of the general class (source → period-number → contact)
• next period exposure (source-> Room 123 Period 1 → Room 123 Period 2 → contact)
• Ventilation (source → Room 123 Period 1 → Room 125 Period 1 → contact)

Each edge has an attribute indicating whether it is an individual exposure, the same different period or ventilation boundary.

As an intermediate step in modeling the infection in this network, I would just like to get a simple count of the number of exhibits of each type that the student had. For example, a student could share a class with a source, and then was in the room in which the source was located, but after a while, and perhaps the next day was in the room associated with ventilation. These student indicators would be the following:

personal.contact: 0 shared.class: 1 next.period: 1 vent: 1 

I'm not sure how best to get such information, although I see functions for getting the shortest paths, which makes it easier to identify personal contact links, but I think I need to evaluate all the paths (which seem crazy to ask for on a typical social network , but not so crazy when only the initial and indoor periods have extremes). If I could get to the point where each path from the source to the contact was represented by an ordered vector of edge types, I think I could easily match them to my criteria. I just don’t know how to get there. If igraph is not the right basis for this, and I just need to write some big horrible cycles according to the schedule of the students, so be it! But I would appreciate some advice before plunging into this hole.

---

Here is an example contact schedule for each of the three indirect paths:

 # Strings ain't factors options(stringsAsFactors = FALSE) library(igraph) # Create a sample case edgelist <- data.frame(out.id = c("source", "source", "source", "Rm 123 Period 1", "Rm 125 Period 2", "Rm 125 Period 3", "Rm 127 Period 4", "Rm 129 Period 4"), in.id = c("Rm 123 Period 1", "Rm 125 Period 2", "Rm 127 Period 4", "contact", "Rm 125 Period 3", "contact", "Rm 129 Period 4", "contact"), edge.type = c("Source in class", "Source in class", "Source in class", "Student in class", "Class-to-class", "Student in class", "Vent link", "Student in class" ) ) samp.graph <- graph.data.frame(edgelist, directed = TRUE) # Label the vertices with meaningful names V(samp.graph)$label <- V(samp.graph)$name plot(samp.graph, layout = layout.fruchterman.reingold) 

Answer 1

I'm not quite sure I understand your graph model, but if the question is:

 I have two vertices and I wish to extract every path between them, then extract the edge attributes of those edges. 

maybe it might work.

Go with a breadth-first search. An Igraph contains one, but it’s easy enough to roll on its own, and this will give you more flexibility regarding what information you want to receive. I assume that there are no cycles on your chart, otherwise you will get an infinite number of paths. I don't know much Python (although I use igraph in R), so here is some pseudo code.

 list <- empty allSimplePaths(u, v, thisPath) if (u == v) return for (n in neighborhood(u)) if (n in thisPath) next if (u == v) list <- list + (thisPath + v) for (n in neighborhood(u)) thisPath <- thisPath + n allSimplePaths(n, v, thisPath) thisPath <- thisPath - thisPath.end 

Basically it says "from every vertex, try all possible extension paths to get to the end." Just add another thisPathEdges and insert the edges, pass it through the function, as well as the vertices. Of course, it would be better if it were not recursive. Be careful, as this algorithm can knock down your stack with enough nodes.

You can still go with the @PaulG model and just have multiple edges between student nodes. You could do cool things, for example, do a first breadth-first search to find out how the disease spreads or find a minimal spanning tree to get an estimate of the time, or find a minimal incision for quarantining the current infection or something else.