Re: [sage-devel] Re: Py3, sorting vertices of graph
Two more: - #26284 : deals with comparability.pyx, digraph.py, vertex_separation.pyx, cutwidth.pyx and connectivity.pyx - #26285: avoid comparison of vertex labels in MIPs of generic_graph. Le vendredi 14 septembre 2018 13:43:37 UTC+2, David Coudert a écrit : > > I'm working on reducing the number of places where we explicitly compare > vertex labels. > So far I'm focusing on MIPs. > >- #26274 : avoid comparison of vertex labels in MIP for file >`graph_coloring.py` >- #26282 : avoid comparison of vertex labels in MIP for file `graph.py` > > More to come, and help for reviewing is more than welcome. > -- You received this message because you are subscribed to the Google Groups "sage-devel" group. To unsubscribe from this group and stop receiving emails from it, send an email to sage-devel+unsubscr...@googlegroups.com. To post to this group, send email to sage-devel@googlegroups.com. Visit this group at https://groups.google.com/group/sage-devel. For more options, visit https://groups.google.com/d/optout.
Re: [sage-devel] Re: Py3, sorting vertices of graph
I'm working on reducing the number of places where we explicitly compare vertex labels. So far I'm focusing on MIPs. - #26274 : avoid comparison of vertex labels in MIP for file `graph_coloring.py` - #26282 : avoid comparison of vertex labels in MIP for file `graph.py` More to come, and help for reviewing is more than welcome. -- You received this message because you are subscribed to the Google Groups "sage-devel" group. To unsubscribe from this group and stop receiving emails from it, send an email to sage-devel+unsubscr...@googlegroups.com. To post to this group, send email to sage-devel@googlegroups.com. Visit this group at https://groups.google.com/group/sage-devel. For more options, visit https://groups.google.com/d/optout.
Re: [sage-devel] Re: Py3, sorting vertices of graph
On Thu, Sep 6, 2018 at 11:40 AM David Coudert wrote: > > Comparisons like u < v are used in many places in the code of graphs. > We can try to use hash(u) < hash(v) instead, but this is certainly not the > smartest solution. I have a long-outstanding proposal for a SafeSortable utility that would help with these cases. I would prefer a solution like this (with the exact details negotiable): https://trac.sagemath.org/ticket/25981 -- You received this message because you are subscribed to the Google Groups "sage-devel" group. To unsubscribe from this group and stop receiving emails from it, send an email to sage-devel+unsubscr...@googlegroups.com. To post to this group, send email to sage-devel@googlegroups.com. Visit this group at https://groups.google.com/group/sage-devel. For more options, visit https://groups.google.com/d/optout.
Re: [sage-devel] Re: Py3, sorting vertices of graph
On Thu, 6 Sep 2018, John H Palmieri wrote:
Also not ideal, but you could first try u < v, and if that fails, catch the
error and use str(u) < str(v).
But we can have Graph({'1': [1]}) and so not total order for str() of
vertices.
--
Jori Mäntysalo
[sage-devel] Re: Py3, sorting vertices of graph
On Thursday, September 6, 2018 at 6:23:26 AM UTC-7, David Coudert wrote: > > Le jeudi 6 septembre 2018 14:16:33 UTC+2, Martin R a écrit : >> >> Would it be hard to separate vertex labels and vertices? In other words, >> vertices would always be 0,...,n-1, and there would be an additional array >> containing the vertex labels. >> > > Some graph backends do that, like `c_graph`. I'm not sure it's true for > all backends. > But, there might be situation in which it is useful to compare vertex > labels. > > > Also not ideal, but you could first try u < v, and if that fails, catch the error and use str(u) < str(v). -- You received this message because you are subscribed to the Google Groups "sage-devel" group. To unsubscribe from this group and stop receiving emails from it, send an email to sage-devel+unsubscr...@googlegroups.com. To post to this group, send email to sage-devel@googlegroups.com. Visit this group at https://groups.google.com/group/sage-devel. For more options, visit https://groups.google.com/d/optout.
[sage-devel] Re: Py3, sorting vertices of graph
Le jeudi 6 septembre 2018 14:16:33 UTC+2, Martin R a écrit : > > Would it be hard to separate vertex labels and vertices? In other words, > vertices would always be 0,...,n-1, and there would be an additional array > containing the vertex labels. > Some graph backends do that, like `c_graph`. I'm not sure it's true for all backends. But, there might be situation in which it is useful to compare vertex labels. -- You received this message because you are subscribed to the Google Groups "sage-devel" group. To unsubscribe from this group and stop receiving emails from it, send an email to sage-devel+unsubscr...@googlegroups.com. To post to this group, send email to sage-devel@googlegroups.com. Visit this group at https://groups.google.com/group/sage-devel. For more options, visit https://groups.google.com/d/optout.
[sage-devel] Re: Py3, sorting vertices of graph
Would it be hard to separate vertex labels and vertices? In other words, vertices would always be 0,...,n-1, and there would be an additional array containing the vertex labels. (I would prefer to have this for many "labelled" combinatorial objects, such as set partitions, permutations, posets, etc., but I realise that it would be a lot of work.) Martin -- You received this message because you are subscribed to the Google Groups "sage-devel" group. To unsubscribe from this group and stop receiving emails from it, send an email to sage-devel+unsubscr...@googlegroups.com. To post to this group, send email to sage-devel@googlegroups.com. Visit this group at https://groups.google.com/group/sage-devel. For more options, visit https://groups.google.com/d/optout.
[sage-devel] Re: Py3, sorting vertices of graph
Comparisons like u < v are used in many places in the code of graphs. We can try to use hash(u) < hash(v) instead, but this is certainly not the smartest solution. -- You received this message because you are subscribed to the Google Groups "sage-devel" group. To unsubscribe from this group and stop receiving emails from it, send an email to sage-devel+unsubscr...@googlegroups.com. To post to this group, send email to sage-devel@googlegroups.com. Visit this group at https://groups.google.com/group/sage-devel. For more options, visit https://groups.google.com/d/optout.
[sage-devel] Re: Py3, sorting vertices of graph
This also affects various computations in the `homology` directory, since a common practice is to take a simplicial complex and discard everything above dimension 1, and then look at the resulting graph. If the vertices in the original simplicial complex have labels which are not sortable in Python 3, these computations fail. So I would very much appreciate it if someone who knows the graph theory parts of Sage could investigate this. -- John On Thursday, August 30, 2018 at 7:04:12 AM UTC-7, Jori Mäntysalo wrote: > > What is the situation with sorting of graph vertices in Python 3? > > Currently one can not, for example, create a poset with Py3. This comes > down to 42 < 'xyz', which raises exception in Py3, but returns either True > or False in Py2. Comparison is used in sorted(), which is used in > .vertices() for (di)graphs. > > It is trivial to try sort vertices, and when failed, return them in an > arbitrary order, but I don't know what would be broken then. > > -- > Jori Mäntysalo > -- You received this message because you are subscribed to the Google Groups "sage-devel" group. To unsubscribe from this group and stop receiving emails from it, send an email to sage-devel+unsubscr...@googlegroups.com. To post to this group, send email to sage-devel@googlegroups.com. Visit this group at https://groups.google.com/group/sage-devel. For more options, visit https://groups.google.com/d/optout.
