Le mardi 29 janvier 2019 23:19:12 UTC+1, Thierry (sage-googlesucks@xxx) a
écrit :
>
> Hi,
>
> On Sun, Jan 27, 2019 at 11:21:21AM -0800, David Coudert wrote:
> [...]
> > The most complicated issue is certainly edges of Graph: we sort the
> > vertices of an edge before returning it... I have no solution for this
> > issue. We can decide to stop ordering the vertices, but then we will
> have
> > to update a very large number of algorithms. We could also design a
> method
> > to compare object of different types.
> > In fact, the main issue is that we use and compare vertices by id
> instead
> > of mapping vertices to integer and work only with these integers. That
> > would ease our life, but it's not easy to change that.
>
> We discussed the difference between mathematical and algorithmic level
> various times (for equality, comparison, etc).
>
> Here, at the "algorithmic" level, the vertices are of course comparable,
> and most algorithms in graph theory rely on this (starting by the most
> fundamental such as DFS, BFS, etc). Trying to avoid comparison of
> vertices would be suicidary, and trying to do that with Sage will just
> lead to unreadable artificially complicated code.
>
> If you want an integer label for each vertex, why not just ask to the
> backend:
>
> sage: G = graphs.WorldMap()
> sage: G
> World Map: Graph on 251 vertices
> sage: G.vertices()[0]
> 'Afghanistan'
>
> sage: GG = G._backend.c_graph()[0]
> sage: GG
> <sage.graphs.base.sparse_graph.SparseGraph object at 0x7ff500875768>
> sage: GG.verts()[0]
> 0
>
> So, somehow, you do not have to map Sage objects back to integers, since
> we already have a map from integers to Sage objects.
>
> I did not check the implementations, but though it is kind of too late
> given the size of Sage, i would advocate to have two explicit layers for
> combinatorial objects such as words, graphs, permutations, etc, one
> "algorithmic" where the atoms are integers, with all the good
> properties, and a "label" dictionary, where we could attach any Sage
> object to them for "mathematical" questions. And it would be amazing if
> they were an specified way to do that uniformly.
>
In fact we already have methods to do that, but changing the code to use
these methods is not an easy task...
sage: G = graphs.PetersenGraph()
sage: G.set_vertex(0, 'abc')
sage: G.set_vertex(1, graphs.CycleGraph(3))
sage: print(G.get_vertices())
{0: 'abc', 1: Cycle graph: Graph on 3 vertices, 2: None, 3: None, 4: None,
5: None, 6: None, 7: None, 8: None, 9: None}
That said, regarding the .edges() method, i think that returning a list
> of pairs is a very wrong approach (though this is what is done for
> years). Indeed, a list is not only an iterator, but also a container. In
> particular:
>
> (a,b) in G.edges()
>
> is a syntaxially correct statement, but it is far from equivalent to:
>
> G.has_edge(a,b)
>
> Which is extremely misleading and can lead to silent mistakes
> (personally, i used lot of hand-made reorderings in my pyograms before i
> discovered has_edge).
>
> Here i would advocate that G.edges() returns a *view* on G, with a
> dedicated __iter__ method corresponding to the edge_iterator method and
> a __contains__ method corresponding to the has_edge method. By having a
> view, you will save a lot of time and memory, and have the benefit that
> it will follow the graph's mutations.
>
>
This is an interesting idea, although I'm not sure how to implement that
efficiently.
David.
PS: when all currently in "needs review" tickets will be closed, the number
of py3 failing doctests in the graph module will be small (HELP welcome
here to review tickets and fix remaining doctests). It will then become
easier to see the effect of changes like not sorting end vertices of edges
(we could try that), implement a *view* on G, etc.
--
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.
