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:  sage8.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: 
Description (last modified by )
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
Branch:  → public/26274_avoid_comparison_of_vertices 

Cc:  Jori Mäntysalo Frédéric Chapoton Travis Scrimshaw added 
Commit:  → fb629490cfbe8fc36379cc7f4ba129ee37137a32 
Description:  modified (diff) 
comment:2 Changed 4 years ago by
Status:  new → needs_review 

comment:3 Changed 4 years ago by
Commit:  fb629490cfbe8fc36379cc7f4ba129ee37137a32 → 91b12ac17c4b0ac455a2a9ff992269a3d586ba56 

Branch pushed to git repo; I updated commit sha1. New commits:
91b12ac  trac #26274: rebase on 8.4.beta5 and fix merge conflict

comment:4 followup: 6 Changed 4 years ago by
 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
Commit:  91b12ac17c4b0ac455a2a9ff992269a3d586ba56 → 9d80cfb2b274b9ab242701e22ec81f540e859ff5 

Branch pushed to git repo; I updated commit sha1. New commits:
9d80cfb  trac #26274: implement reviewer's comments

comment:6 followup: 7 Changed 4 years ago by
Thank you for the comments.
 about
list(range(...))
: Ifrange
becomes an iterator, then we can iterate only once onclasses
. Right ? I changed the code to use explicitlyrange(k)
.
 I moved the import of
MIPSolverException
andMixedIntegerLinearProgram
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 Changed 4 years ago by
comment:8 Changed 4 years ago by
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
Commit:  9d80cfb2b274b9ab242701e22ec81f540e859ff5 → c074efc7a886fa1945c245aa1159578794b3adfa 

Branch pushed to git repo; I updated commit sha1. New commits:
c074efc  trac #26274: reviewer comment

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

Status:  needs_review → positive_review 
ok, let it be
comment:11 Changed 4 years ago by
Branch:  public/26274_avoid_comparison_of_vertices → c074efc7a886fa1945c245aa1159578794b3adfa 

Resolution:  → fixed 
Status:  positive_review → closed 
On the way, I also did some minor improvements.
New commits:
trac #26274: improve graph_coloring