Opened 2 years ago
Closed 2 years ago
#26679 closed enhancement (fixed)
clean generic_graph.py (part 13) - searches and constructors
Reported by: | dcoudert | Owned by: | |
---|---|---|---|
Priority: | major | Milestone: | sage-8.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, GitHub, GitLab) | 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 2 years 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 2 years 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 2 years 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 2 years ago by
- Commit changed from 08be872ea36a216092a94eea499e3343f7c91bea to 2eb311625e1298e9a00d553d1a29b933674dbc5c
comment:5 Changed 2 years ago by
I have reverted modifications of method union
and created a dedicated ticket (#26851).
comment:6 Changed 2 years ago by
- Description modified (diff)
comment:7 Changed 2 years 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 2 years ago by
- Milestone changed from sage-8.5 to sage-8.7
comment:9 Changed 2 years ago by
no merge conflict with 8.7.beta3.
comment:10 follow-up: ↓ 12 Changed 2 years 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 2 years ago by
- Commit changed from 2f1e2c0fcfe8dd79337e52c26351bcdbca970f4b to 5e97618a98e7e2deca5eedae0633dc0739e67c1a
comment:12 in reply to: ↑ 10 Changed 2 years ago by
Right, the test is much better like that. Thank you.
comment:13 Changed 2 years 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 2 years 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