4
$\begingroup$

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: simple graph

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.

graphUpdate

$\endgroup$
12
  • $\begingroup$ The postprocessing method is not an option because FindPath[g,s,d,Infinity,All] is too expensive? $\endgroup$
    – Jason B.
    Aug 6 at 20:48
  • $\begingroup$ Hi Jason—I think that it may be possible for the case of a larger graph, but not the full case. The full-sized graph here has about 36 million possible paths, which I suspect are searchable. The full case, however, requires finding two non-intersecting paths (each with its own starting and ending points), and then the "required edges" must all be traversed in the union of these paths' traversed edges. I figured that if I could cut down on the number of possible combinations first, it would be possible to select a solution, but looking for a pairing between two lists of 36 million paths... $\endgroup$ Aug 7 at 21:11
  • $\begingroup$ How many connected components is the subgraph of required edges? $\endgroup$
    – Derek H
    Aug 10 at 20:23
  • $\begingroup$ Does your graph have multiple edges between vertices as in your example? Also, can a path go through the same vertex multiple times? $\endgroup$
    – Carl Woll
    Aug 10 at 22:49
  • $\begingroup$ Hi Derek—if I understand you correctly, then it's pretty arbitrary. I would like some list of edges that must be traversed, and the number and connectedness of the edges could really be anything. $\endgroup$ Aug 11 at 6:22
5
+50
$\begingroup$

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.

enter image description here

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]

enter image description here

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}]

enter image description here

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

enter image description here

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}

enter image description here

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.

$\endgroup$
4
  • $\begingroup$ Hi Derek—I don't know the details of how FindPath is working internally, but it doesn't seem completely unreasonable (caveat: I know very little about graphs) that it could have a way eliminate paths which don't traverse the required edges (e.g., there are paths you could take which, before getting to the end, would "lock you out" of being able to traverse the requested edge). Even at worse, simply discarding the paths as they're searched/collected would reduce memory usage very significantly, right? It would be double important for combinatoric cases like this. I'll try out your suggestion. $\endgroup$ Aug 11 at 22:42
  • $\begingroup$ Maybe FindHamiltonianPath[] could help? $\endgroup$
    – Teabelly
    Aug 12 at 11:40
  • 1
    $\begingroup$ @BenKalziqi - I believe you are right that FindPath could be written to filter out the paths while finding them, rather than returning them all and letting you filter them. But I do not think it is written that way currently. $\endgroup$
    – Jason B.
    Aug 12 at 17:59
  • 1
    $\begingroup$ @JasonB. a guy can dream, right? 😅 Derek — thanks for the thought process outlined in your answer here. I think that it's likely the best we can do here, given that (as you correctly diagnose) this is a really nontrivial problem. $\endgroup$ Aug 13 at 22:35

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.