Opened 4 years ago

Closed 4 years ago

#26274 closed enhancement (fixed)

Avoid comparison of vertex labels (Step 1)

Reported by: David Coudert Owned by:
Priority: major Milestone: sage-8.4
Component: graph theory Keywords: py3, graph
Cc: Jori Mäntysalo, Frédéric Chapoton, Travis Scrimshaw Merged in:
Authors: David Coudert Reviewers: Frédéric Chapoton
Report Upstream: N/A Work issues:
Branch: c074efc (Commits, GitHub, GitLab) Commit: c074efc7a886fa1945c245aa1159578794b3adfa
Dependencies: Stopgaps:

Status badges

Description (last modified by David Coudert)

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 4 years ago by David Coudert

Branch: public/26274_avoid_comparison_of_vertices
Cc: Jori Mäntysalo Frédéric Chapoton Travis Scrimshaw added
Commit: fb629490cfbe8fc36379cc7f4ba129ee37137a32
Description: modified (diff)

On the way, I also did some minor improvements.


New commits:

fb62949trac #26274: improve graph_coloring

comment:2 Changed 4 years ago by David Coudert

Status: newneeds_review

comment:3 Changed 4 years ago by git

Commit: fb629490cfbe8fc36379cc7f4ba129ee37137a3291b12ac17c4b0ac455a2a9ff992269a3d586ba56

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

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

comment:4 Changed 4 years ago by Frédéric 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 4 years ago by git

Commit: 91b12ac17c4b0ac455a2a9ff992269a3d586ba569d80cfb2b274b9ab242701e22ec81f540e859ff5

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

9d80cfbtrac #26274: implement reviewer's comments

comment:6 in reply to:  4 ; Changed 4 years ago by David Coudert

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 4 years ago by Frédéric 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 4 years ago by Frédéric 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 4 years ago by git

Commit: 9d80cfb2b274b9ab242701e22ec81f540e859ff5c074efc7a886fa1945c245aa1159578794b3adfa

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

c074efctrac #26274: reviewer comment

comment:10 Changed 4 years ago by Frédéric Chapoton

Reviewers: Frédéric Chapoton
Status: needs_reviewpositive_review

ok, let it be

comment:11 Changed 4 years ago by Volker Braun

Branch: public/26274_avoid_comparison_of_verticesc074efc7a886fa1945c245aa1159578794b3adfa
Resolution: fixed
Status: positive_reviewclosed
Note: See TracTickets for help on using tickets.