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, 27 Jun 2022 01:12:02 +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]]SageIdiotMon, 27 Jun 2022 01:12:02 +0200https://ask.sagemath.org/question/63021/Path rendering on a Surfacehttps://ask.sagemath.org/question/54279/path-rendering-on-a-surface/I am having a discrepancy with the z-coordinates of a path on a surface.
The blue path shown below is correctly embedded in the red surface.
The z-coordinates for the green path are "almost" correct. I have gone over the math dozens of times. I need to compute rational powers of cosine and sine. Wondering if it could be a rounding issue?
The surface is parametrized in polar coordinates.
The path is parametrized in rectangular coordinates. (This is because on the full surface this portion is shifted along the x-axis. I reparametrized it polar and it seems less accurate).
What I've done is:
1. Specify the path as $(x(u), y(u))$
2. Compute the radial distance to the point $r(u) = \sqrt{x^2 + y^2}$
3. The path is then given by $(x(u), y(u), z(r(u))$
(I've used the parameter $v$ to give the paths some "thickness")
This works fine for blue, not for green.
The surface height grows linearly with the radius.
The blue path's radius decays linearly.
The green path's radius decays non-linearly. But, I don't think that should matter, as I'm simply getting a list of points and plugging them into the height function.
u, v = var('u, v')
right_curve_u = 8+(14/pi)*(u+pi/2) #8+(14/pi)*(phi+pi/2)
f_x(u, v) = v*cos(u)
f_y(u, v) = v*sin(u)
f_z(u, v) = (((v-16)/12)*(12*cos((pi/11)*(right_curve_u - 17)) + 39.5))/12
T=parametric_plot3d([f_x, f_y, f_z], (u, -pi/2, 0), (v, 16, 28), color="red", opacity=0.5, axes=True, mesh=False)
#c=parametric_plot3d([f_x, f_y, f_z], (u, -pi/2, pi/2), (v, 21.9, 22.1), color="black", mesh=True)
#c is the curve in the first example with constant radius
#Path Equation; Note, "u" is the parameter for the path, "v" is to give it a bit of "thickness"
right_curve_u = 8+(14/pi)*(u+pi/2) #8+(14/pi)*(phi+pi/2)
right_curve_x(u,v) = v*(16*(cos(u))^(5/6))
right_curve_y(u,v) = v*(-28*(sin(-u))^(5/6))
#right_curve_path_radius(u,v) = v*(16*28)/(((28*cos(u))^(2.4)+(16*sin(-u))^2.4)^(5/12))
right_curve_path_radius(u,v) = sqrt((right_curve_x)^2+(right_curve_y)^2)
right_curve_path_radius_2(u,v) = v*sqrt((16^2)*(cos(u))^(5/3)+(28^2)*(sin(-u))^(5/3))
right_curve_z(u,v) = ( ( (right_curve_path_radius - 16)/12 ) * ( 12*cos( (pi/11)*(right_curve_u - 17) ) + 39.5 ) )/12
right_curve_z_2(u,v) = ( ( (right_curve_path_radius_2 - 16)/12 ) * ( 12*cos( (pi/11)*(right_curve_u - 17) ) + 39.5 ) )/12
right_curve = parametric_plot3d([right_curve_x, right_curve_y, right_curve_z], (u, -pi/2, -0.01), (v, 0.99, 1.01), color="black")
right_curve_2 = parametric_plot3d([right_curve_x, right_curve_y, right_curve_z_2], (u, -pi/2, -0.01), (v, 0.99, 1.01), color="green")
g_x(u, v) = v*(16-(12*(u-pi/2)/pi))*cos(u)
g_y(u, v) = v*(16-(12*(u-pi/2)/pi))*sin(u)
h(u) = v*(16 - (12/pi)*(u-pi/2))
g_z(u,v) = ( ( (h - 16)/12 ) * ( 12*cos( (pi/11)*(right_curve_u - 17) ) + 39.5 ) )/12
c_xy=parametric_plot3d([g_x, g_y, g_z], (u, -pi/2, 0), (v, 0.99, 1.01), color="blue")
T+c_xy+right_curve+right_curve_2Abbas JaffaryWed, 18 Nov 2020 19:59:27 +0100https://ask.sagemath.org/question/54279/Flow gives error for disconnected verticeshttps://ask.sagemath.org/question/41419/flow-gives-error-for-disconnected-vertices/ When calculating the flow between to vertices which are not connected in a graph, the method returns a ValueError. I would have assumed that it would just return 0. Here's a minimal example:
G=Graph({0:[],1:[]})
G.flow(0,1) # raises the error ValueError: vertex '0' is not in the (di)graph
If on the other hand one tries the shortest_path method it just returns a empty list, since there is not path between 0 and 1.
G.shortest_path(0,1) #returns []AckslWed, 07 Mar 2018 13:21:06 +0100https://ask.sagemath.org/question/41419/