Restrict output of all_simple_paths, to obtain only longest simple paths that do not have edge self-intersections?

asked 2022-06-27 01:12:02 +0100

SageIdiot gravatar image

updated 2022-07-03 23:28:18 +0100

So far, I am using sage's all_simple_paths to list all simple paths between two fixed vertices of certain (embeddings of) graphs. I would like to go further, and restrict the output of all_simple_paths twice, to obtain the paths I'm interested in for the class of graphs I'm considering. Here are the successive restrictions I would like to implement:

  1. only the longest paths in the output of all_simple_paths are kept (EDIT: this can be done with list comprehension, see example below), and

  2. of the longest paths from 1., only the paths without edge self-intersections are kept.

Here, a path P has an edge self-intersection if one edge of P crosses over another edge of P (note that this definition depends on the embedding of the underlying graph).

Rough idea for 1: I think you can set the maximum length of the paths all_simple_paths outputs, but I didn't see any way to set the minimum length. I think the ability to discard all paths less than or equal to a certain length from the output of all_simple_paths would be sufficient for my application (EDIT: this can be done with list comprehension, see example below).

Rough idea for 2: After restricting the output of all_simple_paths the first time, which leaves only the longest simple paths, I'd like to do the following:

-Make a set, L, where the elements of this set are the longest simple paths just mentioned

-Write a function: Domain: L Range: {YES, NO} (would tell you if the path has a self-intersection).

The following is the rule defining the function. Take the path l from L. This path is a series of directed edges

i_1 --> i_2 --> ... i_m.

Now, we will consider each directed edge of the path l one-by-one, in order. So first, consider i_1 --> i_2. Call this edge e_1. Create a set C_{e_1} of all edges from the underlying graph that e_1 crosses, and remember this set until the function outputs YES or NO.

Now, move to the next edge in l, call it e_2. Check if e_2 is in C_{e_1}. If yes, halt and print NO. Else, create the set C_{e_2} of edges from the underlying graph that cross e_2, and remember this set until the function outputs YES or NO. Next, consider e_3. If e_3 is in the union of C_{e_1} and C_{e_2}, then halt and print NO. Else, create C_{e_3}, etc.

-Write a program which runs the function just described on each possible input in L, then throws out all the NO paths, and returns only the YES paths.


d = {1:[2,4,5], 2:[3,4,5,6], 3:[6], 4:[2,5], 5:[3,4,6]}
D = DiGraph(d)
D.all_simple_paths(starting_vertices=[1], ending_vertices=[6])

I'm drawing this graph as two squares, glued together along the edge 2--5, with an "X" inside each square (which is what sage output when I tried G=Graph(d), then show(G), and this is the embedding I had in mind).

This gives the following output:

[[1, 2, 6],
 [1, 5, 6],
 [1, 2, 3, 6],
 [1, 2, 5, 6],
 [1, 4, 2, 6],
 [1, 4, 5, 6],
 [1, 5, 3, 6],
 [1, 2, 4, 5, 6],
 [1, 2, 5, 3, 6],
 [1, 4, 2, 3, 6],
 [1, 4, 2, 5, 6],
 [1, 4, 5, 3, 6],
 [1, 5, 4, 2, 6],
 [1, 2, 4, 5, 3, 6],
 [1, 4, 2, 5, 3, 6],
 [1, 5, 4, 2, 3, 6]]

First, I would like to filter this output so that only the longest simple paths are given (which forms the set "L"). EDIT: This can be done with list comprehension as follows. Let F_1 = D.all_simple_paths(starting_vertices=[1], ending_vertices=[6]). Then using [x for x in F_1 if len(x) > 5] leaves only longest simple paths:

[[1, 2, 4, 5, 3, 6],
 [1, 4, 2, 5, 3, 6],
 [1, 5, 4, 2, 3, 6]]

Finally, note that the last longest path [1, 5, 4, 2, 3, 6] is a NO path, since it has an edge self-intersection (according to how we are drawing the underlying graph): the first edge 1-->5 will be crossed by the edge 4-->2 later in the path. As the first two longest simple paths listed above do not have any edge self-intersections, they are YES paths, and the final output of the program should be:

[[1, 2, 4, 5, 3, 6],
 [1, 4, 2, 5, 3, 6]]
edit retag flag offensive close merge delete



Welcome to Ask Sage! Thank you for your question.

slelievre gravatar imageslelievre ( 2022-06-28 06:08:30 +0100 )edit

Can you clarify what you are looking for. Depending on the constraints, it might be sufficient to filter the paths returned by method all_simple_paths to keep only what you need, or you need a different method.

David Coudert gravatar imageDavid Coudert ( 2022-06-28 18:02:30 +0100 )edit

Thanks for your comment David, I edited the post. Hopefully what I am looking for is more clear now.

SageIdiot gravatar imageSageIdiot ( 2022-06-29 01:03:28 +0100 )edit

The problem you want to solve is difficult. The problem of finding the longest path is already NP-complete. Furthermore, I assume you want the maximum number of non-crossing longest paths, so fixing a path and searching for other non crossing paths is not a good solution. You may obtain a solution with a single path while there is a solution with many non-crossing paths (avoiding the first one).

This problem can certainly be solved using integer linear programming since you can express the crossings from your embedding as constraints.

David Coudert gravatar imageDavid Coudert ( 2022-06-29 11:15:41 +0100 )edit

"Furthermore, I assume you want the maximum number of non-crossing longest paths"

You seem to be implying that I am looking for the largest set of longest paths, such that all paths in this largest set have no edge crossings between them. This is not the case.

Instead, I want the number of all non-self-crossing longest paths - I do not care if any edge from path 1 crosses any edge from path 2, where path 1 and path 2 are any two longest paths without self-crossings. I only care that, for each individual path, say path A for example, that no edge from path A crosses any other edge from path A.

SageIdiot gravatar imageSageIdiot ( 2022-06-29 21:37:41 +0100 )edit