Opened 6 months ago

Closed 5 months ago

#26284 closed enhancement (fixed)

Avoid comparison of vertex labels in MIP (Step 3)

Reported by: dcoudert Owned by:
Priority: major Milestone: sage-8.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 6 months ago by dcoudert

  • Branch set to public/26284_cleaning_in_some_MIPs
  • Commit set to 5bd8e80a1dd2f1d2a3aa512f979401945dd26830
  • Status changed from new to needs_review

New commits:

5bd8e80trac #26284: cleaning in various MIPs

comment:2 Changed 6 months ago by git

  • Commit changed from 5bd8e80a1dd2f1d2a3aa512f979401945dd26830 to 921a353b5e4e9daea3fbf321bf80116577fc245a

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

921a353trac #: Merged with 8.4.beta5

comment:3 Changed 6 months ago by git

  • Commit changed from 921a353b5e4e9daea3fbf321bf80116577fc245a to a938f9c286d99752388c61a3315a92aaf4ec7c14

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

a938f9ctrac #26284: change a lambda wrapper to a def

comment:4 Changed 6 months ago by dcoudert

  • Cc tscrim chapoton added

comment:5 Changed 6 months ago by tscrim

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 6 months ago by git

  • Commit changed from a938f9c286d99752388c61a3315a92aaf4ec7c14 to 4194063683449e51a11573dbcf3071597870d288

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

83fa55etrac #26284: Merged with 8.4.beta7
4194063trac #26284: implement reviewer's comments

comment:7 Changed 6 months ago by dcoudert

Right, reorder_edge was not needed here.

comment:8 Changed 6 months ago by tscrim

  • Reviewers set to Travis Scrimshaw
  • Status changed from needs_review to positive_review

Thanks. LGTM.

comment:9 Changed 5 months ago by vbraun

  • Branch changed from public/26284_cleaning_in_some_MIPs to 4194063683449e51a11573dbcf3071597870d288
  • Resolution set to fixed
  • Status changed from positive_review to closed
Note: See TracTickets for help on using tickets.