Opened 4 years ago

Closed 4 years ago

# Avoid comparison of vertex labels (Step 1)

Reported by: Owned by: David Coudert major sage-8.4 graph theory py3, graph Jori Mäntysalo, Frédéric Chapoton, Travis Scrimshaw David Coudert Frédéric Chapoton N/A c074efc c074efc7a886fa1945c245aa1159578794b3adfa

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.

### comment:1 Changed 4 years ago by David Coudert

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

On the way, I also did some minor improvements.

New commits:

 ​fb62949 `trac #26274: improve graph_coloring`

### comment:2 Changed 4 years ago by David Coudert

Status: new → needs_review

### comment:3 Changed 4 years ago by git

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 follow-up:  6 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: 91b12ac17c4b0ac455a2a9ff992269a3d586ba56 → 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 ; follow-up:  7 Changed 4 years ago by David Coudert

• 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

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

 ​c074efc `trac #26274: reviewer comment`

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

Reviewers: → Frédéric Chapoton needs_review → positive_review

ok, let it be

### comment:11 Changed 4 years ago by Volker Braun

Branch: public/26274_avoid_comparison_of_vertices → c074efc7a886fa1945c245aa1159578794b3adfa → fixed positive_review → closed
Note: See TracTickets for help on using tickets.