FindPath with required Edges

Question

Suppose I have a graph g with some edges reqEdges (in the example code here, just one edge). I would like to use FindPath to find all of the paths from some point s to some point t, but on the condition that all paths should traverse the edges in reqEdges.

While the question is quite general, here is some code that produces an extremely stripped-down version of the real problem:

(*Setting the parameters for the graph:*)
verts = Range@4;
vertsPart = Partition[verts, 2];
horiCon = 
  Flatten[UndirectedEdge @@@ Partition[#, 2, 1, 1] & /@ vertsPart];
vertiCon = 
  Flatten[
   UndirectedEdge @@@ Partition[#, 2, 1] & /@ Transpose[vertsPart]];
reqEdges = {1 \[UndirectedEdge] 2};
vertCoords = (First@Position[Reverse /@ Transpose[vertsPart], #] & /@ 
    verts);
(*Generating the graph and highlighting the required edge:*)
g = Graph[verts, Join[horiCon, vertiCon], 
   GraphLayout -> "GravityEmbedding", VertexCoordinates -> vertCoords,
    VertexLabels -> Automatic];
HighlightGraph[g, 
 Style[PathGraph[reqEdges], Directive[Darker@Red, Thickness[.015]]], 
 Background -> White]

This produces a Graph like this:

If one uses, e.g., FindPath[g,3,2,Infinity,All], they get two paths: {{3, 4, 2}, {3, 1, 2}}. I would only like to generate (not take) {3,1,2}, since it has contains the required 1 \[UndirectedEdge] 2 edge.

It's easy enough to simply check through the resultant paths and extract those which contain the Sequence 1,2 or 2,1 (or to rewrite the list of vertices as a list of edges traversed), but that's not computationally feasible in the real problem.

I did think to try EdgeWeights, but I couldn't devise anything the seemed to work. (I don't know much about graphs, so tried setting the required edge to 0 and the others to Infinity and vice-versa, but no luck there, as you'd probably expected.)

It feels as if there should be some way to do this, but neither the documentation nor searching here has provided anything that I can understand as a solution. Any tips?

EDIT: I'm adding a graph with 9 vertices rather than the 4 in the OP, as I originally simplified the graph enough that it was no longer representative of the actual problem and was—in addition to that—misleading.

Answer 1

I don't think you'll be able to use FindPath to directly generate and not take the paths. For example, how will FindPath know that {3,4,2} doesn't contain reqEdges until after it finds {3,4,2} in the first place?

One thing you could do is used FindPath to go from the starting node to each node in the subgraph made by reqEdges. Then use something like FindEularianCycle to hit every required edge, then use FindPath again from the exit of the reqEdges subgraph to the destination node.

So, your algorithm might look like:

1. Find all inPaths from startNode to each vertex in the subgraph of reqEdges.
2. Find all paths in the reqEdges subgraph that hit all edges from the entryVertex. This will give a list of exitVertices.
3. Use FindPath to find all outPaths from each exitVertex in exitVertices to endNode.
4. Join correctly the inPaths, subgraph paths, and outPaths

EDIT: You say in a comment

A path cannot go through the same vertex multiple times, nor can it traverse the same edge multiple times

Restricting the path to crossing an edge only once can present some problems depending on the structure of the graph and on the required edges. For example, in the following it's not possible to go from 4 to 5 and hit all the red edges only once.

However, if that's ok, or if you can find a good way to traverse each edges of the required edges subgraph, then... If you have say the following graph and want to go from 3 to 7 through the red edge:

verts = Range@9;
vertsPart = Partition[verts, 3];
horiCon = 
  Flatten[UndirectedEdge @@@ Partition[#, 2, 1, 1] & /@ vertsPart];
vertiCon = 
  Flatten[UndirectedEdge @@@ Partition[#, 2, 1] & /@ 
    Transpose[vertsPart]];
reqEdges = {{1 \[UndirectedEdge] 2}};
vertCoords = (First@Position[Reverse /@ Transpose[vertsPart], #] & /@ 
    verts);
(*Generating the graph and highlighting the required edge:*)
g = Graph[verts, Join[horiCon, vertiCon], 
   GraphLayout -> "GravityEmbedding", VertexCoordinates -> vertCoords,
    VertexLabels -> Automatic];
HighlightGraph[g, 
 Style[PathGraph[#], Directive[Darker@Red, Thickness[.015]]] & /@ 
  reqEdges, Background -> White]

Pick where to start and where to end, and what the required vertices are

startNode = 7
endNode = 3
reqVerts = Flatten[VertexList[#] & /@ reqEdges]

Make a subgraph of the required edges

h = Subgraph[g, reqVerts]

Remove required edges from inPath search so it won't find paths that use these edges

(* Limited to 5 paths for here *)
gg = EdgeDelete[g, EdgeList[h]]
inPaths = FindPath[gg, startNode, #, Infinity, 5] & /@ reqVerts
Table[HighlightGraph[gg, PathGraph[#]] & /@ inPaths[[i, All]], {i, 1, 
  2}]

This gives a list of lists paths to each required vertex. I.e. inPaths[[1]] is a list of all the paths from startNode to the first required vertex.

Find the PostmanTour Cycle for each in node (or use some other method to traverse the required edges)

pt = FindPostmanTour[h, 1]
perms = Permutations[Range@Length[pt[[1]]]]

Can use the permutations to cycle the tour depending on which reqVertices is the end of the current inPaths list.

For each list in inPaths (i.e. in node) get the outPaths

outPaths = FindPath[gg, #, endNode, Infinity, 5] & /@ reqVerts

(* Join these for all the paths from start to end that enter the required edges subgraph at the first required vertex *)
inPaths[[1, All]]
pt
outPaths[[1, All]]

All of that assumes that the path structure goes to the required edges, around the required edges, and then from the required edges to the end vertex. It has the potential for paths repeating edges during the postman tour, and also that an inPath and outPath path might overlap. You could remove the inPath edges from the outPath FindPath graph search. All of this removing edges and subgraph stuff might not scale very well or be any faster than doing what your original question is trying to avoid (take). I think things would be easier if you wanted the shortest path instead of all paths.

If for example you had

the following path from 9 to 5 traverses each required edge only once but enters and leaves the required edge subgraph.

{9, 10, 11, 12, 8, 7, 11, 15, 14, 13, 9, 5} or

{9 \[UndirectedEdge] 10, 10 \[UndirectedEdge] 11, 
 11 \[UndirectedEdge] 12, 12 \[UndirectedEdge] 8, 
 8 \[UndirectedEdge] 7, 7 \[UndirectedEdge] 11, 
 11 \[UndirectedEdge] 15, 15 \[UndirectedEdge] 14, 
 14 \[UndirectedEdge] 13, 13 \[UndirectedEdge] 9, 
 9 \[UndirectedEdge] 5}

It looks like what you're trying to do is pretty hard without maybe more defined structure on what the required edges are, and how the paths can cross them.