ASKSAGE: Sage Q&A Forum - RSS feedhttps://ask.sagemath.org/questions/Q&A Forum for SageenCopyright Sage, 2010. Some rights reserved under creative commons license.Mon, 04 Jul 2022 09:35:01 +0200Restrict output of all_simple_paths, to obtain only longest simple paths that do not have edge self-intersections?https://ask.sagemath.org/question/63021/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]]Mon, 27 Jun 2022 01:12:02 +0200https://ask.sagemath.org/question/63021/restrict-output-of-all_simple_paths-to-obtain-only-longest-simple-paths-that-do-not-have-edge-self-intersections/Comment by SageIdiot for <p>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:</p>
<ol>
<li><p>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 </p></li>
<li><p>of the longest paths from 1., only the paths without edge self-intersections are kept. </p></li>
</ol>
<p>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). </p>
<hr>
<p>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). </p>
<hr>
<p>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:</p>
<p>-Make a set, L, where the elements of this set are the longest simple paths just mentioned</p>
<p>-Write a function:
Domain: L
Range: {YES, NO} (would tell you if the path has a self-intersection). </p>
<p>The following is the rule defining the function. Take the path l from L. This path is a series of directed edges </p>
<p>i_1 --> i_2 --> ... i_m. </p>
<p>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. </p>
<p>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. </p>
<p>-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. </p>
<hr>
<p>Example:</p>
<pre><code>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])
</code></pre>
<p>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). </p>
<p>This gives the following output:</p>
<pre><code>[[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]]
</code></pre>
<p>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:</p>
<pre><code>[[1, 2, 4, 5, 3, 6],
[1, 4, 2, 5, 3, 6],
[1, 5, 4, 2, 3, 6]]
</code></pre>
<p>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:</p>
<pre><code>[[1, 2, 4, 5, 3, 6],
[1, 4, 2, 5, 3, 6]]
</code></pre>
https://ask.sagemath.org/question/63021/restrict-output-of-all_simple_paths-to-obtain-only-longest-simple-paths-that-do-not-have-edge-self-intersections/?comment=63109#post-id-63109I see, thanks.Mon, 04 Jul 2022 09:35:01 +0200https://ask.sagemath.org/question/63021/restrict-output-of-all_simple_paths-to-obtain-only-longest-simple-paths-that-do-not-have-edge-self-intersections/?comment=63109#post-id-63109Comment by David Coudert for <p>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:</p>
<ol>
<li><p>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 </p></li>
<li><p>of the longest paths from 1., only the paths without edge self-intersections are kept. </p></li>
</ol>
<p>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). </p>
<hr>
<p>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). </p>
<hr>
<p>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:</p>
<p>-Make a set, L, where the elements of this set are the longest simple paths just mentioned</p>
<p>-Write a function:
Domain: L
Range: {YES, NO} (would tell you if the path has a self-intersection). </p>
<p>The following is the rule defining the function. Take the path l from L. This path is a series of directed edges </p>
<p>i_1 --> i_2 --> ... i_m. </p>
<p>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. </p>
<p>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. </p>
<p>-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. </p>
<hr>
<p>Example:</p>
<pre><code>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])
</code></pre>
<p>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). </p>
<p>This gives the following output:</p>
<pre><code>[[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]]
</code></pre>
<p>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:</p>
<pre><code>[[1, 2, 4, 5, 3, 6],
[1, 4, 2, 5, 3, 6],
[1, 5, 4, 2, 3, 6]]
</code></pre>
<p>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:</p>
<pre><code>[[1, 2, 4, 5, 3, 6],
[1, 4, 2, 5, 3, 6]]
</code></pre>
https://ask.sagemath.org/question/63021/restrict-output-of-all_simple_paths-to-obtain-only-longest-simple-paths-that-do-not-have-edge-self-intersections/?comment=63107#post-id-63107If you consider only small graphs, you can filter the output by length and then remove paths containing crossing edges. However, this solution will not scale. The number of paths returned by `all_simple_paths` is exponential in the size of the graph.Mon, 04 Jul 2022 09:08:27 +0200https://ask.sagemath.org/question/63021/restrict-output-of-all_simple_paths-to-obtain-only-longest-simple-paths-that-do-not-have-edge-self-intersections/?comment=63107#post-id-63107Comment by SageIdiot for <p>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:</p>
<ol>
<li><p>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 </p></li>
<li><p>of the longest paths from 1., only the paths without edge self-intersections are kept. </p></li>
</ol>
<p>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). </p>
<hr>
<p>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). </p>
<hr>
<p>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:</p>
<p>-Make a set, L, where the elements of this set are the longest simple paths just mentioned</p>
<p>-Write a function:
Domain: L
Range: {YES, NO} (would tell you if the path has a self-intersection). </p>
<p>The following is the rule defining the function. Take the path l from L. This path is a series of directed edges </p>
<p>i_1 --> i_2 --> ... i_m. </p>
<p>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. </p>
<p>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. </p>
<p>-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. </p>
<hr>
<p>Example:</p>
<pre><code>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])
</code></pre>
<p>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). </p>
<p>This gives the following output:</p>
<pre><code>[[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]]
</code></pre>
<p>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:</p>
<pre><code>[[1, 2, 4, 5, 3, 6],
[1, 4, 2, 5, 3, 6],
[1, 5, 4, 2, 3, 6]]
</code></pre>
<p>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:</p>
<pre><code>[[1, 2, 4, 5, 3, 6],
[1, 4, 2, 5, 3, 6]]
</code></pre>
https://ask.sagemath.org/question/63021/restrict-output-of-all_simple_paths-to-obtain-only-longest-simple-paths-that-do-not-have-edge-self-intersections/?comment=63096#post-id-63096I can now use list comprehension for the first output filter described above.
For example, 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.Sun, 03 Jul 2022 23:14:19 +0200https://ask.sagemath.org/question/63021/restrict-output-of-all_simple_paths-to-obtain-only-longest-simple-paths-that-do-not-have-edge-self-intersections/?comment=63096#post-id-63096Comment by David Coudert for <p>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:</p>
<ol>
<li><p>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 </p></li>
<li><p>of the longest paths from 1., only the paths without edge self-intersections are kept. </p></li>
</ol>
<p>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). </p>
<hr>
<p>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). </p>
<hr>
<p>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:</p>
<p>-Make a set, L, where the elements of this set are the longest simple paths just mentioned</p>
<p>-Write a function:
Domain: L
Range: {YES, NO} (would tell you if the path has a self-intersection). </p>
<p>The following is the rule defining the function. Take the path l from L. This path is a series of directed edges </p>
<p>i_1 --> i_2 --> ... i_m. </p>
<p>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. </p>
<p>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. </p>
<p>-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. </p>
<hr>
<p>Example:</p>
<pre><code>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])
</code></pre>
<p>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). </p>
<p>This gives the following output:</p>
<pre><code>[[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]]
</code></pre>
<p>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:</p>
<pre><code>[[1, 2, 4, 5, 3, 6],
[1, 4, 2, 5, 3, 6],
[1, 5, 4, 2, 3, 6]]
</code></pre>
<p>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:</p>
<pre><code>[[1, 2, 4, 5, 3, 6],
[1, 4, 2, 5, 3, 6]]
</code></pre>
https://ask.sagemath.org/question/63021/restrict-output-of-all_simple_paths-to-obtain-only-longest-simple-paths-that-do-not-have-edge-self-intersections/?comment=63072#post-id-63072A path is *simple* if it has no repeated vertices. However, it may have crossing edges, i.e., the drawing of 2 edges may cross (it depends on an embedding). A specific method is needed here, taking as input conflicts between edges.Thu, 30 Jun 2022 19:42:07 +0200https://ask.sagemath.org/question/63021/restrict-output-of-all_simple_paths-to-obtain-only-longest-simple-paths-that-do-not-have-edge-self-intersections/?comment=63072#post-id-63072Comment by Max Alekseyev for <p>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:</p>
<ol>
<li><p>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 </p></li>
<li><p>of the longest paths from 1., only the paths without edge self-intersections are kept. </p></li>
</ol>
<p>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). </p>
<hr>
<p>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). </p>
<hr>
<p>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:</p>
<p>-Make a set, L, where the elements of this set are the longest simple paths just mentioned</p>
<p>-Write a function:
Domain: L
Range: {YES, NO} (would tell you if the path has a self-intersection). </p>
<p>The following is the rule defining the function. Take the path l from L. This path is a series of directed edges </p>
<p>i_1 --> i_2 --> ... i_m. </p>
<p>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. </p>
<p>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. </p>
<p>-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. </p>
<hr>
<p>Example:</p>
<pre><code>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])
</code></pre>
<p>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). </p>
<p>This gives the following output:</p>
<pre><code>[[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]]
</code></pre>
<p>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:</p>
<pre><code>[[1, 2, 4, 5, 3, 6],
[1, 4, 2, 5, 3, 6],
[1, 5, 4, 2, 3, 6]]
</code></pre>
<p>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:</p>
<pre><code>[[1, 2, 4, 5, 3, 6],
[1, 4, 2, 5, 3, 6]]
</code></pre>
https://ask.sagemath.org/question/63021/restrict-output-of-all_simple_paths-to-obtain-only-longest-simple-paths-that-do-not-have-edge-self-intersections/?comment=63070#post-id-63070Isn't *simple* path non-selfintersecting by [definition](https://en.wikipedia.org/wiki/Simple_path)?Thu, 30 Jun 2022 17:50:19 +0200https://ask.sagemath.org/question/63021/restrict-output-of-all_simple_paths-to-obtain-only-longest-simple-paths-that-do-not-have-edge-self-intersections/?comment=63070#post-id-63070Comment by David Coudert for <p>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:</p>
<ol>
<li><p>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 </p></li>
<li><p>of the longest paths from 1., only the paths without edge self-intersections are kept. </p></li>
</ol>
<p>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). </p>
<hr>
<p>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). </p>
<hr>
<p>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:</p>
<p>-Make a set, L, where the elements of this set are the longest simple paths just mentioned</p>
<p>-Write a function:
Domain: L
Range: {YES, NO} (would tell you if the path has a self-intersection). </p>
<p>The following is the rule defining the function. Take the path l from L. This path is a series of directed edges </p>
<p>i_1 --> i_2 --> ... i_m. </p>
<p>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. </p>
<p>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. </p>
<p>-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. </p>
<hr>
<p>Example:</p>
<pre><code>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])
</code></pre>
<p>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). </p>
<p>This gives the following output:</p>
<pre><code>[[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]]
</code></pre>
<p>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:</p>
<pre><code>[[1, 2, 4, 5, 3, 6],
[1, 4, 2, 5, 3, 6],
[1, 5, 4, 2, 3, 6]]
</code></pre>
<p>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:</p>
<pre><code>[[1, 2, 4, 5, 3, 6],
[1, 4, 2, 5, 3, 6]]
</code></pre>
https://ask.sagemath.org/question/63021/restrict-output-of-all_simple_paths-to-obtain-only-longest-simple-paths-that-do-not-have-edge-self-intersections/?comment=63067#post-id-63067I get it. So it is possible to modify the algorithms used in `longest_path` to find the longest non-crossing path. With the `MILP` algorithm, you need to add constraints to forbid selecting crossing edges. If you also add a constraint to prevent finding a given path, you can get an iterator over the longest non-crossing paths.Thu, 30 Jun 2022 12:13:21 +0200https://ask.sagemath.org/question/63021/restrict-output-of-all_simple_paths-to-obtain-only-longest-simple-paths-that-do-not-have-edge-self-intersections/?comment=63067#post-id-63067Comment by SageIdiot for <p>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:</p>
<ol>
<li><p>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 </p></li>
<li><p>of the longest paths from 1., only the paths without edge self-intersections are kept. </p></li>
</ol>
<p>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). </p>
<hr>
<p>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). </p>
<hr>
<p>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:</p>
<p>-Make a set, L, where the elements of this set are the longest simple paths just mentioned</p>
<p>-Write a function:
Domain: L
Range: {YES, NO} (would tell you if the path has a self-intersection). </p>
<p>The following is the rule defining the function. Take the path l from L. This path is a series of directed edges </p>
<p>i_1 --> i_2 --> ... i_m. </p>
<p>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. </p>
<p>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. </p>
<p>-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. </p>
<hr>
<p>Example:</p>
<pre><code>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])
</code></pre>
<p>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). </p>
<p>This gives the following output:</p>
<pre><code>[[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]]
</code></pre>
<p>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:</p>
<pre><code>[[1, 2, 4, 5, 3, 6],
[1, 4, 2, 5, 3, 6],
[1, 5, 4, 2, 3, 6]]
</code></pre>
<p>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:</p>
<pre><code>[[1, 2, 4, 5, 3, 6],
[1, 4, 2, 5, 3, 6]]
</code></pre>
https://ask.sagemath.org/question/63021/restrict-output-of-all_simple_paths-to-obtain-only-longest-simple-paths-that-do-not-have-edge-self-intersections/?comment=63065#post-id-63065I edited the question again, and tried to be much more specific.Thu, 30 Jun 2022 00:00:25 +0200https://ask.sagemath.org/question/63021/restrict-output-of-all_simple_paths-to-obtain-only-longest-simple-paths-that-do-not-have-edge-self-intersections/?comment=63065#post-id-63065Comment by SageIdiot for <p>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:</p>
<ol>
<li><p>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 </p></li>
<li><p>of the longest paths from 1., only the paths without edge self-intersections are kept. </p></li>
</ol>
<p>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). </p>
<hr>
<p>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). </p>
<hr>
<p>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:</p>
<p>-Make a set, L, where the elements of this set are the longest simple paths just mentioned</p>
<p>-Write a function:
Domain: L
Range: {YES, NO} (would tell you if the path has a self-intersection). </p>
<p>The following is the rule defining the function. Take the path l from L. This path is a series of directed edges </p>
<p>i_1 --> i_2 --> ... i_m. </p>
<p>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. </p>
<p>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. </p>
<p>-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. </p>
<hr>
<p>Example:</p>
<pre><code>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])
</code></pre>
<p>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). </p>
<p>This gives the following output:</p>
<pre><code>[[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]]
</code></pre>
<p>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:</p>
<pre><code>[[1, 2, 4, 5, 3, 6],
[1, 4, 2, 5, 3, 6],
[1, 5, 4, 2, 3, 6]]
</code></pre>
<p>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:</p>
<pre><code>[[1, 2, 4, 5, 3, 6],
[1, 4, 2, 5, 3, 6]]
</code></pre>
https://ask.sagemath.org/question/63021/restrict-output-of-all_simple_paths-to-obtain-only-longest-simple-paths-that-do-not-have-edge-self-intersections/?comment=63063#post-id-63063"*fixing a path and searching for other non crossing paths is not a good solution.*"
This is not what I was proposing. Instead, what I wrote about excluding edges as you cross them was for building a **single** path - draw the first edge of the path, and if that edge crosses any other edges in the underlying graph, declare that you can't use these edges in the remainder of the path. Next draw, the second edge in the path, etc.
My apologies if I'm misunderstanding anything. Thank you again for your help.Wed, 29 Jun 2022 21:39:21 +0200https://ask.sagemath.org/question/63021/restrict-output-of-all_simple_paths-to-obtain-only-longest-simple-paths-that-do-not-have-edge-self-intersections/?comment=63063#post-id-63063Comment by SageIdiot for <p>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:</p>
<ol>
<li><p>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 </p></li>
<li><p>of the longest paths from 1., only the paths without edge self-intersections are kept. </p></li>
</ol>
<p>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). </p>
<hr>
<p>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). </p>
<hr>
<p>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:</p>
<p>-Make a set, L, where the elements of this set are the longest simple paths just mentioned</p>
<p>-Write a function:
Domain: L
Range: {YES, NO} (would tell you if the path has a self-intersection). </p>
<p>The following is the rule defining the function. Take the path l from L. This path is a series of directed edges </p>
<p>i_1 --> i_2 --> ... i_m. </p>
<p>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. </p>
<p>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. </p>
<p>-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. </p>
<hr>
<p>Example:</p>
<pre><code>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])
</code></pre>
<p>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). </p>
<p>This gives the following output:</p>
<pre><code>[[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]]
</code></pre>
<p>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:</p>
<pre><code>[[1, 2, 4, 5, 3, 6],
[1, 4, 2, 5, 3, 6],
[1, 5, 4, 2, 3, 6]]
</code></pre>
<p>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:</p>
<pre><code>[[1, 2, 4, 5, 3, 6],
[1, 4, 2, 5, 3, 6]]
</code></pre>
https://ask.sagemath.org/question/63021/restrict-output-of-all_simple_paths-to-obtain-only-longest-simple-paths-that-do-not-have-edge-self-intersections/?comment=63062#post-id-63062"*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.Wed, 29 Jun 2022 21:37:41 +0200https://ask.sagemath.org/question/63021/restrict-output-of-all_simple_paths-to-obtain-only-longest-simple-paths-that-do-not-have-edge-self-intersections/?comment=63062#post-id-63062Comment by David Coudert for <p>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:</p>
<ol>
<li><p>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 </p></li>
<li><p>of the longest paths from 1., only the paths without edge self-intersections are kept. </p></li>
</ol>
<p>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). </p>
<hr>
<p>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). </p>
<hr>
<p>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:</p>
<p>-Make a set, L, where the elements of this set are the longest simple paths just mentioned</p>
<p>-Write a function:
Domain: L
Range: {YES, NO} (would tell you if the path has a self-intersection). </p>
<p>The following is the rule defining the function. Take the path l from L. This path is a series of directed edges </p>
<p>i_1 --> i_2 --> ... i_m. </p>
<p>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. </p>
<p>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. </p>
<p>-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. </p>
<hr>
<p>Example:</p>
<pre><code>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])
</code></pre>
<p>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). </p>
<p>This gives the following output:</p>
<pre><code>[[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]]
</code></pre>
<p>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:</p>
<pre><code>[[1, 2, 4, 5, 3, 6],
[1, 4, 2, 5, 3, 6],
[1, 5, 4, 2, 3, 6]]
</code></pre>
<p>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:</p>
<pre><code>[[1, 2, 4, 5, 3, 6],
[1, 4, 2, 5, 3, 6]]
</code></pre>
https://ask.sagemath.org/question/63021/restrict-output-of-all_simple_paths-to-obtain-only-longest-simple-paths-that-do-not-have-edge-self-intersections/?comment=63055#post-id-63055The 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.Wed, 29 Jun 2022 11:15:41 +0200https://ask.sagemath.org/question/63021/restrict-output-of-all_simple_paths-to-obtain-only-longest-simple-paths-that-do-not-have-edge-self-intersections/?comment=63055#post-id-63055Comment by SageIdiot for <p>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:</p>
<ol>
<li><p>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 </p></li>
<li><p>of the longest paths from 1., only the paths without edge self-intersections are kept. </p></li>
</ol>
<p>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). </p>
<hr>
<p>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). </p>
<hr>
<p>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:</p>
<p>-Make a set, L, where the elements of this set are the longest simple paths just mentioned</p>
<p>-Write a function:
Domain: L
Range: {YES, NO} (would tell you if the path has a self-intersection). </p>
<p>The following is the rule defining the function. Take the path l from L. This path is a series of directed edges </p>
<p>i_1 --> i_2 --> ... i_m. </p>
<p>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. </p>
<p>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. </p>
<p>-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. </p>
<hr>
<p>Example:</p>
<pre><code>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])
</code></pre>
<p>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). </p>
<p>This gives the following output:</p>
<pre><code>[[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]]
</code></pre>
<p>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:</p>
<pre><code>[[1, 2, 4, 5, 3, 6],
[1, 4, 2, 5, 3, 6],
[1, 5, 4, 2, 3, 6]]
</code></pre>
<p>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:</p>
<pre><code>[[1, 2, 4, 5, 3, 6],
[1, 4, 2, 5, 3, 6]]
</code></pre>
https://ask.sagemath.org/question/63021/restrict-output-of-all_simple_paths-to-obtain-only-longest-simple-paths-that-do-not-have-edge-self-intersections/?comment=63051#post-id-63051Thanks for your comment David, I edited the post. Hopefully what I am looking for is more clear now.Wed, 29 Jun 2022 01:03:28 +0200https://ask.sagemath.org/question/63021/restrict-output-of-all_simple_paths-to-obtain-only-longest-simple-paths-that-do-not-have-edge-self-intersections/?comment=63051#post-id-63051Comment by David Coudert for <p>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:</p>
<ol>
<li><p>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 </p></li>
<li><p>of the longest paths from 1., only the paths without edge self-intersections are kept. </p></li>
</ol>
<p>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). </p>
<hr>
<p>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). </p>
<hr>
<p>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:</p>
<p>-Make a set, L, where the elements of this set are the longest simple paths just mentioned</p>
<p>-Write a function:
Domain: L
Range: {YES, NO} (would tell you if the path has a self-intersection). </p>
<p>The following is the rule defining the function. Take the path l from L. This path is a series of directed edges </p>
<p>i_1 --> i_2 --> ... i_m. </p>
<p>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. </p>
<p>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. </p>
<p>-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. </p>
<hr>
<p>Example:</p>
<pre><code>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])
</code></pre>
<p>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). </p>
<p>This gives the following output:</p>
<pre><code>[[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]]
</code></pre>
<p>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:</p>
<pre><code>[[1, 2, 4, 5, 3, 6],
[1, 4, 2, 5, 3, 6],
[1, 5, 4, 2, 3, 6]]
</code></pre>
<p>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:</p>
<pre><code>[[1, 2, 4, 5, 3, 6],
[1, 4, 2, 5, 3, 6]]
</code></pre>
https://ask.sagemath.org/question/63021/restrict-output-of-all_simple_paths-to-obtain-only-longest-simple-paths-that-do-not-have-edge-self-intersections/?comment=63045#post-id-63045Can 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.Tue, 28 Jun 2022 18:02:30 +0200https://ask.sagemath.org/question/63021/restrict-output-of-all_simple_paths-to-obtain-only-longest-simple-paths-that-do-not-have-edge-self-intersections/?comment=63045#post-id-63045Comment by slelievre for <p>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:</p>
<ol>
<li><p>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 </p></li>
<li><p>of the longest paths from 1., only the paths without edge self-intersections are kept. </p></li>
</ol>
<p>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). </p>
<hr>
<p>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). </p>
<hr>
<p>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:</p>
<p>-Make a set, L, where the elements of this set are the longest simple paths just mentioned</p>
<p>-Write a function:
Domain: L
Range: {YES, NO} (would tell you if the path has a self-intersection). </p>
<p>The following is the rule defining the function. Take the path l from L. This path is a series of directed edges </p>
<p>i_1 --> i_2 --> ... i_m. </p>
<p>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. </p>
<p>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. </p>
<p>-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. </p>
<hr>
<p>Example:</p>
<pre><code>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])
</code></pre>
<p>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). </p>
<p>This gives the following output:</p>
<pre><code>[[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]]
</code></pre>
<p>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:</p>
<pre><code>[[1, 2, 4, 5, 3, 6],
[1, 4, 2, 5, 3, 6],
[1, 5, 4, 2, 3, 6]]
</code></pre>
<p>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:</p>
<pre><code>[[1, 2, 4, 5, 3, 6],
[1, 4, 2, 5, 3, 6]]
</code></pre>
https://ask.sagemath.org/question/63021/restrict-output-of-all_simple_paths-to-obtain-only-longest-simple-paths-that-do-not-have-edge-self-intersections/?comment=63037#post-id-63037Welcome to Ask Sage! Thank you for your question.Tue, 28 Jun 2022 06:08:30 +0200https://ask.sagemath.org/question/63021/restrict-output-of-all_simple_paths-to-obtain-only-longest-simple-paths-that-do-not-have-edge-self-intersections/?comment=63037#post-id-63037