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

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

edit retag close merge delete

1

( 2022-06-28 06:08:30 +0100 )edit
1

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.

( 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.

( 2022-06-29 01:03:28 +0100 )edit
1

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.

( 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.

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