So far, I am trying to use sage using sage's all_simple_paths to list all simple paths between two fixed vertices of certain (embeddings of) graphs, but with these two additional conditions: 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:
only paths of maximal length the longest paths in the output of all_simple_paths are output, kept, and
of the maximal length longest paths from 1., only the paths without self-intersections are kept.
By self-intersection, I mean Here, a path P has a self-intersection if one edge of the path crossing P crosses over another (which edge of P (note that this definition depends on the embedding of the underlying graph).
I can use all_simple_paths to output all simple paths from one vertex to the other by creating a dictionary d={} (specifying vertices, and the outgoing edges), then forming a digraph, then using all_simple_paths. But I'm not sure how to restrict the output list so that only simple paths both of maximal length and without self-crossings are given.
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. The I think the ability to set the minimum length of a path would be sufficient for my application. application (but, being able to say "from the output of all_simple_paths, only keep the lists of length k" would also be useful to me).
Rough idea for 2: For excluding self-crossing After restricting the output of all_simple_paths the first time, which leaves only longest paths, my idea I'd like to do the following:
-Make a set, L, where the elements of this set are the longest paths just mentioned
-Write a function:
Domain: L
Range: {YES, NO} (would tell you if the path has a self-intersection).
The function would work as follows. Take the path l from L. This path is to somehow tell sage "if you cross edge j while forming a path, do not use list of 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 j while creating the remainder of the path". Since the edge crossings in the underlying graph depends e_2. 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 how we draw it, I would think we have to manually tell sage which edges not to cross and when.
I am new to sage (and have no programming background), so I'm not sure how to do this, or if this would even work. Any help is really appreciated. each possible input in L, throws out all the "bad" paths, and returns only the "good" 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 maximal length longest paths are given:given (which forms the set "L"):
[[1, 2, 4, 5, 3, 6],
[1, 4, 2, 5, 3, 6],
[1, 5, 4, 2, 3, 6]]
Finally, note that the last maximal longest path [1, 5, 4, 2, 3, 6] is a "bad" path, since it has a 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 maximal longest paths listed above do not have any self-intersections, they are "good" paths, and the final output of the program should be:
[[1, 2, 4, 5, 3, 6],
[1, 4, 2, 5, 3, 6]]
