Opened 6 months ago
Closed 6 months ago
#26274 closed enhancement (fixed)
Avoid comparison of vertex labels (Step 1)
Reported by:  dcoudert  Owned by:  

Priority:  major  Milestone:  sage8.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 )
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 6 months ago by
 Branch set to public/26274_avoid_comparison_of_vertices
 Cc jmantysalo chapoton tscrim added
 Commit set to fb629490cfbe8fc36379cc7f4ba129ee37137a32
 Description modified (diff)
comment:2 Changed 6 months ago by
 Status changed from new to needs_review
comment:3 Changed 6 months ago by
 Commit changed from fb629490cfbe8fc36379cc7f4ba129ee37137a32 to 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 6 months 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 6 months ago by
 Commit changed from 91b12ac17c4b0ac455a2a9ff992269a3d586ba56 to 9d80cfb2b274b9ab242701e22ec81f540e859ff5
Branch pushed to git repo; I updated commit sha1. New commits:
9d80cfb  trac #26274: implement reviewer's comments

comment:6 in reply to: ↑ 4 ; followup: ↓ 7 Changed 6 months 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 in reply to: ↑ 6 Changed 6 months ago by
comment:8 Changed 6 months 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 6 months ago by
 Commit changed from 9d80cfb2b274b9ab242701e22ec81f540e859ff5 to c074efc7a886fa1945c245aa1159578794b3adfa
Branch pushed to git repo; I updated commit sha1. New commits:
c074efc  trac #26274: reviewer comment

comment:10 Changed 6 months ago by
 Reviewers set to Frédéric Chapoton
 Status changed from needs_review to positive_review
ok, let it be
comment:11 Changed 6 months ago by
 Branch changed from public/26274_avoid_comparison_of_vertices to c074efc7a886fa1945c245aa1159578794b3adfa
 Resolution set to fixed
 Status changed from positive_review to closed
On the way, I also did some minor improvements.
New commits:
trac #26274: improve graph_coloring