Opened 7 months ago
Closed 4 months ago
#26679 closed enhancement (fixed)
clean generic_graph.py (part 13)  searches and constructors
Reported by:  dcoudert  Owned by:  

Priority:  major  Milestone:  sage8.7 
Component:  graph theory  Keywords:  
Cc:  tscrim, chapoton  Merged in:  
Authors:  David Coudert  Reviewers:  Vincent Klein 
Report Upstream:  N/A  Work issues:  
Branch:  5e97618 (Commits)  Commit:  5e97618a98e7e2deca5eedae0633dc0739e67c1a 
Dependencies:  Stopgaps: 
Description (last modified by )
Here, we clean (PEP8 and avoid .vertices
/ .edges
) methods:
 searches:
breadth_first_search
,depth_first_search
(lex_BFS
is done in #26630)  constructors:
add_clique
,add_cycle
,add_path
,complement
,to_simple
,disjoint_union
,cartesian_product
,tensor_product
,lexicographic_product
,strong_product
,disjunctive_product
(methodstransitive_...
are done in #26634)
Change History (14)
comment:1 Changed 7 months ago by
 Branch set to public/26679_generic_graph_part_13
 Cc tscrim chapoton added
 Commit set to 08be872ea36a216092a94eea499e3343f7c91bea
 Description modified (diff)
 Status changed from new to needs_review
comment:2 Changed 7 months ago by
The changes are breaking the construction of graphs.EllinghamHorton54Graph()
, but so far I don't understand what's going on.
In method union
, if, instead of
 G.add_vertices(self.vertices())  G.add_vertices(other.vertices())  G.add_edges(self.edges())  G.add_edges(other.edges()) + G.add_vertices(self) + G.add_vertices(other) + G.add_edges(self.edge_iterator()) + G.add_edges(other.edge_iterator())
I let the line G.add_vertices(other.vertices())
, I don't have errors anymore O_o
Any suggestion on possible cause of this issue?
comment:3 Changed 7 months ago by
My understanding is the following.
graphs.EllinghamHorton54Graph()
uses twicedisjoint_union
, and makes assumption on the name of vertices after each operationdisjoint_union
relabels the vertices of the graphs according the orderinglist(G)
, and then callsunion
. When adding vertices in the graph
G
resulting from the union ofself
andother
, the order in which vertices are added toG
fixes the orderinglist(G)
. So, a later call todisjoint_union
, that relabels the graphs using the orderinglist(G)
might result in a different result.
So, either we decide that the proposed changes, avoiding to use .vertices()
, is ok and then I have to update method EllinghamHorton54Graph
according the new ordering, or it is not ok and we must let G.add_vertices(self.vertices())
and G.add_vertices(other.vertices())
in union
.
In my opinion, the current situation in which disjoint_union
relies on the ordering list(G)
and union
relies on the ordering G.vertices()
is not good.
I can open a specific ticket if needed.
comment:4 Changed 6 months ago by
 Commit changed from 08be872ea36a216092a94eea499e3343f7c91bea to 2eb311625e1298e9a00d553d1a29b933674dbc5c
comment:5 Changed 6 months ago by
I have reverted modifications of method union
and created a dedicated ticket (#26851).
comment:6 Changed 6 months ago by
 Description modified (diff)
comment:7 Changed 5 months ago by
 Commit changed from 2eb311625e1298e9a00d553d1a29b933674dbc5c to 2f1e2c0fcfe8dd79337e52c26351bcdbca970f4b
Branch pushed to git repo; I updated commit sha1. New commits:
2f1e2c0  trac #26679: Merged with 8.7.beta0

comment:8 Changed 5 months ago by
 Milestone changed from sage8.5 to sage8.7
comment:9 Changed 4 months ago by
no merge conflict with 8.7.beta3.
comment:10 followup: ↓ 12 Changed 4 months ago by
sage: if product_size != expected:  ....: print("Something is really wrong here...", product_size, "!=", expected) + ....: raise ValueError("something is really wrong here... {} != {}".format(product_size, expected))
I am not sure why raising a ValueError? would be better here ?
And to begin with the message has little value.
In similar cases i think we usually do something like:
sage: product_size == expected True
This comment is more a question and not a blocking point.
Some pep8 comments :
 1. Multiple space after keyword :
line 17058 if (neighbors is None and not isinstance(start, list) and distance is None
 2. Blank line contains whitespace: l 17465.
 3. Missing whitespace after ',' :
l 17890 G.add_vertices((u,v) for u in self for v in other)
l 17972 G.add_vertices((u,v) ...
l 18043 G.add_vertices((u,v) ...
comment:11 Changed 4 months ago by
 Commit changed from 2f1e2c0fcfe8dd79337e52c26351bcdbca970f4b to 5e97618a98e7e2deca5eedae0633dc0739e67c1a
comment:12 in reply to: ↑ 10 Changed 4 months ago by
Right, the test is much better like that. Thank you.
comment:13 Changed 4 months ago by
 Reviewers set to Vincent Klein
 Status changed from needs_review to positive_review
You're welcome.
Looks good to me.
comment:14 Changed 4 months ago by
 Branch changed from public/26679_generic_graph_part_13 to 5e97618a98e7e2deca5eedae0633dc0739e67c1a
 Resolution set to fixed
 Status changed from positive_review to closed
New commits:
trac #26679: searches and constructors