On 2019-02-11 11:12, David Coudert wrote:
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.
I don't see why it should be inefficient (assuming you implement it in
Cython of course).
--
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.
