Opened 9 months ago

Closed 9 months ago

#26274 closed enhancement (fixed)

Avoid comparison of vertex labels (Step 1)

Reported by: dcoudert Owned by:
Priority: major Milestone: sage-8.4
Component: graph theory Keywords: py3, graph
Cc: jmantysalo, chapoton, tscrim Merged in:
Authors: David Coudert Reviewers: Frédéric Chapoton
Report Upstream: N/A Work issues:
Branch: c074efc (Commits) Commit: c074efc7a886fa1945c245aa1159578794b3adfa
Dependencies: Stopgaps:

Description (last modified by dcoudert)

Avoid comparison of vertex labels in graph_coloring.py.

Comparison of vertex labels is often used in linear programs to avoid having one variable for u,v and another for v,u. Most of the time, we can simply use a frozenset.

Change History (11)

comment:1 Changed 9 months ago by dcoudert

  • Branch set to public/26274_avoid_comparison_of_vertices
  • Cc jmantysalo chapoton tscrim added
  • Commit set to fb629490cfbe8fc36379cc7f4ba129ee37137a32
  • Description modified (diff)

On the way, I also did some minor improvements.


New commits:

fb62949trac #26274: improve graph_coloring

comment:2 Changed 9 months ago by dcoudert

  • Status changed from new to needs_review

comment:3 Changed 9 months ago by git

  • Commit changed from fb629490cfbe8fc36379cc7f4ba129ee37137a32 to 91b12ac17c4b0ac455a2a9ff992269a3d586ba56

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

91b12actrac #26274: rebase on 8.4.beta5 and fix merge conflict

comment:4 follow-up: Changed 9 months ago by chapoton

  • are you sure you need wrapping by list here:
    +    N = list(range(n))
    

and there

+    classes = list(range(k))

and again later

  • you should not remove this import
    -from sage.numerical.mip import MIPSolverException
    

as it makes pyflakes unhappy

  • This can be further simplified using if not ... :
    +                    if len(list(set(classe) & set(g.neighbor_iterator(deg[-1])))) == 0:
    
  • do not use lambda declarations, but functions:
    E = lambda x,y : frozenset((x,y))
    

and the same in other frozen wrappers.

comment:5 Changed 9 months ago by git

  • Commit changed from 91b12ac17c4b0ac455a2a9ff992269a3d586ba56 to 9d80cfb2b274b9ab242701e22ec81f540e859ff5

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

9d80cfbtrac #26274: implement reviewer's comments

comment:6 in reply to: ↑ 4 ; follow-up: Changed 9 months ago by dcoudert

Thank you for the comments.

  • about list(range(...)): If range becomes an iterator, then we can iterate only once on classes. Right ? I changed the code to use explicitly range(k).
  • I moved the import of MIPSolverException and MixedIntegerLinearProgram at the top of the file, and removed other imports.
  • This can be further simplified using if not ... :
  • actually, we can do even better with
    if set(classe).isdisjoint(g.neighbor_iterator(deg[-1])):
    

  • do not use lambda declarations, but functions:

I did the modification (and will do in #26282, #26284, #26285), but what's the reason for that ?

comment:7 in reply to: ↑ 6 Changed 9 months ago by chapoton

  • do not use lambda declarations, but functions:

I did the modification (and will do in #26282, #26284, #26285), but what's the reason for that ?

Well, this a pep8 recommendation, so not anything important. No need to change it everywhere in other tickets.

comment:8 Changed 9 months ago by chapoton

You should not do the following, for keeping the coherence with other lines before and after it (this is not the first line of a docstring)

-    :meth:`all_graph_colorings` | Computes all `n`-colorings a graph
+    :meth:`all_graph_colorings` | Compute all `n`-colorings a graph

comment:9 Changed 9 months ago by git

  • Commit changed from 9d80cfb2b274b9ab242701e22ec81f540e859ff5 to c074efc7a886fa1945c245aa1159578794b3adfa

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

c074efctrac #26274: reviewer comment

comment:10 Changed 9 months ago by chapoton

  • Reviewers set to Frédéric Chapoton
  • Status changed from needs_review to positive_review

ok, let it be

comment:11 Changed 9 months ago by vbraun

  • Branch changed from public/26274_avoid_comparison_of_vertices to c074efc7a886fa1945c245aa1159578794b3adfa
  • Resolution set to fixed
  • Status changed from positive_review to closed
Note: See TracTickets for help on using tickets.