Opened 4 years ago
Closed 4 years ago
#26284 closed enhancement (fixed)
Avoid comparison of vertex labels in MIP (Step 3)
Reported by:  David Coudert  Owned by:  

Priority:  major  Milestone:  sage8.4 
Component:  graph theory  Keywords:  
Cc:  Travis Scrimshaw, Frédéric Chapoton  Merged in:  
Authors:  David Coudert  Reviewers:  Travis Scrimshaw 
Report Upstream:  N/A  Work issues:  
Branch:  4194063 (Commits, GitHub, GitLab)  Commit:  4194063683449e51a11573dbcf3071597870d288 
Dependencies:  Stopgaps: 
Description
Avoid comparison of vertex labels in connectivity.pyx
.
This ticket also do some cleaning in the methods involving MIP in comparability.pyx
, digraph.py
, vertex_separation.pyx
, cutwidth.pyx
.
Change History (9)
comment:1 Changed 4 years ago by
Branch:  → public/26284_cleaning_in_some_MIPs 

Commit:  → 5bd8e80a1dd2f1d2a3aa512f979401945dd26830 
Status:  new → needs_review 
comment:2 Changed 4 years ago by
Commit:  5bd8e80a1dd2f1d2a3aa512f979401945dd26830 → 921a353b5e4e9daea3fbf321bf80116577fc245a 

Branch pushed to git repo; I updated commit sha1. New commits:
921a353  trac #: Merged with 8.4.beta5

comment:3 Changed 4 years ago by
Commit:  921a353b5e4e9daea3fbf321bf80116577fc245a → a938f9c286d99752388c61a3315a92aaf4ec7c14 

Branch pushed to git repo; I updated commit sha1. New commits:
a938f9c  trac #26284: change a lambda wrapper to a def

comment:4 Changed 4 years ago by
Cc:  Travis Scrimshaw Frédéric Chapoton added 

comment:5 Changed 4 years ago by
This change will be a slowdown:
 if g.is_directed():  reorder_edge = lambda x,y : (x,y)  else:  reorder_edge = lambda x,y : (x,y) if x<= y else (y,x) + def reorder_edge(x, y): + if g.is_directed(): + return (x,y) + else: + return frozenset((x,y))
as everytime reorder_edge
is called, it has to check g.is_directed
, whereas before it only checked it once. Actually, it is probably better just to do these changes:
 p.add_constraint(in_set[0,u] + in_set[1,v]  in_cut[reorder_edge(u,v)], max=1)  p.add_constraint(in_set[1,u] + in_set[0,v]  in_cut[reorder_edge(u,v)], max=1) + p.add_constraint(in_set[0,u] + in_set[1,v]  in_cut[frozenset([u,v])], max=1) + p.add_constraint(in_set[1,u] + in_set[0,v]  in_cut[frozenset([u,v])], max=1)
(We already know that g
is not directed here.)
Move this line into each of the two branches above:
p.set_objective(p.sum(weight(l) * in_cut[reorder_edge(u,v)] for u,v,l in g.edge_iterator()))
 for u,v,l in g.edge_iterator():  if in_cut[reorder_edge(u,v)] == 1:  edges.append((u,v,l)) + if g.is_directed(): + for u,v,l in g.edge_iterator(): + if in_cut[u,v] == 1: + edges.append((u,v,l)) + else: + for u,v,l in g.edge_iterator(): + if in_cut[frozenset(u,v)] == 1: + edges.append((u,v,l))
Also PEP8 says remove the whitespace before the closing parenthesis:
 p = MixedIntegerLinearProgram( maximization = False, solver = solver ) + p = MixedIntegerLinearProgram(maximization=False, solver=solver )
comment:6 Changed 4 years ago by
Commit:  a938f9c286d99752388c61a3315a92aaf4ec7c14 → 4194063683449e51a11573dbcf3071597870d288 

comment:8 Changed 4 years ago by
Reviewers:  → Travis Scrimshaw 

Status:  needs_review → positive_review 
Thanks. LGTM.
comment:9 Changed 4 years ago by
Branch:  public/26284_cleaning_in_some_MIPs → 4194063683449e51a11573dbcf3071597870d288 

Resolution:  → fixed 
Status:  positive_review → closed 
New commits:
trac #26284: cleaning in various MIPs