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

edit

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.

Example:

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