Opened 4 months ago

Closed 5 weeks 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) Commit: 5e97618a98e7e2deca5eedae0633dc0739e67c1a
Dependencies: Stopgaps:

Description (last modified by dcoudert)

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 (methods transitive_... are done in #26634)

Change History (14)

comment:1 Changed 4 months ago by dcoudert

  • 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

New commits:

08be872trac #26679: searches and constructors

comment:2 Changed 4 months ago by dcoudert

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 4 months ago by dcoudert

My understanding is the following.

  • graphs.EllinghamHorton54Graph() uses twice disjoint_union, and makes assumption on the name of vertices after each operation
  • disjoint_union relabels the vertices of the graphs according the ordering list(G), and then calls union.
  • When adding vertices in the graph G resulting from the union of self and other, the order in which vertices are added to G fixes the ordering list(G). So, a later call to disjoint_union, that relabels the graphs using the ordering list(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 4 months ago by git

  • Commit changed from 08be872ea36a216092a94eea499e3343f7c91bea to 2eb311625e1298e9a00d553d1a29b933674dbc5c

Branch pushed to git repo; I updated commit sha1. New commits:

4b12167trac #26679: Merged with 8.5.beta6
2eb3116trac #26679: revert modifications of union

comment:5 Changed 4 months ago by dcoudert

I have reverted modifications of method union and created a dedicated ticket (#26851).

comment:6 Changed 4 months ago by dcoudert

  • Description modified (diff)

comment:7 Changed 8 weeks ago by git

  • Commit changed from 2eb311625e1298e9a00d553d1a29b933674dbc5c to 2f1e2c0fcfe8dd79337e52c26351bcdbca970f4b

Branch pushed to git repo; I updated commit sha1. New commits:

2f1e2c0trac #26679: Merged with 8.7.beta0

comment:8 Changed 8 weeks ago by dcoudert

  • Milestone changed from sage-8.5 to sage-8.7

comment:9 Changed 6 weeks ago by dcoudert

no merge conflict with 8.7.beta3.

comment:10 follow-up: Changed 5 weeks ago by vklein

             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 5 weeks ago by git

  • Commit changed from 2f1e2c0fcfe8dd79337e52c26351bcdbca970f4b to 5e97618a98e7e2deca5eedae0633dc0739e67c1a

Branch pushed to git repo; I updated commit sha1. New commits:

e2784a3trac #26679: Merged with 8.7.beta3
5e97618trac #26679: reviewer's comments

comment:12 in reply to: ↑ 10 Changed 5 weeks ago by dcoudert

Right, the test is much better like that. Thank you.

comment:13 Changed 5 weeks ago by vklein

  • Reviewers set to Vincent Klein
  • Status changed from needs_review to positive_review

You're welcome.

Looks good to me.

comment:14 Changed 5 weeks ago by vbraun

  • Branch changed from public/26679_generic_graph_part_13 to 5e97618a98e7e2deca5eedae0633dc0739e67c1a
  • Resolution set to fixed
  • Status changed from positive_review to closed
Note: See TracTickets for help on using tickets.