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

Priority:  major  Milestone:  sage8.4 
Component:  graph theory  Keywords:  
Cc:  tscrim, chapoton  Merged in:  
Authors:  David Coudert  Reviewers:  Travis Scrimshaw 
Report Upstream:  N/A  Work issues:  
Branch:  4194063 (Commits)  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 2 years ago by
 Branch set to public/26284_cleaning_in_some_MIPs
 Commit set to 5bd8e80a1dd2f1d2a3aa512f979401945dd26830
 Status changed from new to needs_review
comment:2 Changed 2 years ago by
 Commit changed from 5bd8e80a1dd2f1d2a3aa512f979401945dd26830 to 921a353b5e4e9daea3fbf321bf80116577fc245a
Branch pushed to git repo; I updated commit sha1. New commits:
921a353  trac #: Merged with 8.4.beta5

comment:3 Changed 2 years ago by
 Commit changed from 921a353b5e4e9daea3fbf321bf80116577fc245a to 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 2 years ago by
 Cc tscrim chapoton added
comment:5 Changed 2 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 2 years ago by
 Commit changed from a938f9c286d99752388c61a3315a92aaf4ec7c14 to 4194063683449e51a11573dbcf3071597870d288
comment:7 Changed 2 years ago by
Right, reorder_edge
was not needed here.
comment:8 Changed 2 years ago by
 Reviewers set to Travis Scrimshaw
 Status changed from needs_review to positive_review
Thanks. LGTM.
comment:9 Changed 2 years ago by
 Branch changed from public/26284_cleaning_in_some_MIPs to 4194063683449e51a11573dbcf3071597870d288
 Resolution set to fixed
 Status changed from positive_review to closed
New commits:
trac #26284: cleaning in various MIPs