Opened 5 years ago

Closed 5 years ago

# Cutwidth of a graph

Reported by: Owned by: dcoudert minor sage-6.8 graph theory ncohen David Coudert Nathann Cohen N/A 551d0f0 (Commits) 551d0f0ab9c7942e4d8d61bc2f18808011698dfb

This ticket implements a first method for computing the cutwidth of (small) graphs. In an other ticket, I will add a MILP formulation for comparison purpose.

### comment:1 Changed 5 years ago by dcoudert

• Branch set to public/18746

### comment:2 Changed 5 years ago by git

• Commit set to 165c0b64eeb569161e862603535e2ef2592c2229

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

 ​0a0cfa1 trac #18746: preparation ​bf5d9fa trac #18746: add int_to_vertices to fast digraph ​06007fc trac #18746: creation of the module and doc ​507a3bc trac #18746: add method for measuring the width of a layout ​cbad95a trac #18746: Dynamic programming algorithm ​542e347 trac #18746: front end method ​189bde8 trac #18746: typo ​165c0b6 trac #18746: various minor issues

### comment:3 Changed 5 years ago by dcoudert

• Description modified (diff)
• Status changed from new to needs_review

We could certainly share more code with the vertex_separation_exp methods. To do so, we should change the type int8_t used in vertex_separation_exp to uint8_t which is needed for cutwidth since the numbers are larger than for vertex separation. Let me know if I should do such change (and certainly add a .pxd file).

### comment:4 Changed 5 years ago by ncohen

Helloooooooo,

Several remarks:

• You can rewrite dict( (u,i) for i,u in enumerate(L) ) as  {u:i for i,v in enumerate(L)
• In  cpt += popcount32( (Sbar&g.graph[i]) * ((S>>i)&1) )  Instead of multiplying by ((S>>i)&1), which is 0 or 1, you can do  cpt += popcount32( (Sbar&g.graph[i]) & (-((S>>i)&1)) )  given that 0 in binary is '0...0' and that -1 is '1.....1'.

This being said, there may be time to save by not re-computing the cost from scratch (considering all n vertices) but by computing only the difference from the previous cost, caused by the addition of the last vertex in the ordering.

+    This method differs from method
+    sage.graphs.graph_decompositions.vertex_separation.exists by a single
+    line. We can certainly combine codes.

Something with templates, like it is done in #18395?
+
+    This is a copy/paste of method
+    sage.graphs.graph_decompositions.vertex_separation.find_order and so we
+    can certainly directly import it.

If all you need is to change int8_t into uint8_t vertex_separation_exp then yes of course!

Have fuuuuuuun,

Nathann

### comment:5 Changed 5 years ago by git

• Commit changed from 165c0b64eeb569161e862603535e2ef2592c2229 to d92f30f684949592f36e53e4c03c3bf73c583299

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

 ​5a08116 trac #18746: Merged with 6.8.beta6 ​27d7342 trac #18746: simple corrections ​4ae616a trac #18746: change int8_t to uint8_t in vertex_separation ​9aa0943 trac #18746: add missing sig_off to solve test errors -- weird ​d92f30f trac #18746: use method find_order from vertex_separation

### comment:6 follow-up: ↓ 7 Changed 5 years ago by dcoudert

Hello,

I have performed several modifications and I'm now using the find_order method of vertex_separation.

I don't know how to use the templates (and I'm unable to find this in #18395).

I agree that we can certainly speed-up method compute_edge_cut. The best operation to compute the number of edges from S+i to V\(S+i) is count_S + degree[i] - 2*popcount32(S&g.graph[i]), where count_S is the number of edges from S to V\S. However, we don't store the number of edges from S to V\S, so I don't know how to do this incremental process.

David.

Last edited 5 years ago by dcoudert (previous) (diff)

### comment:7 in reply to: ↑ 6 Changed 5 years ago by ncohen

I have performed several modifications and I'm now using the find_order method of vertex_separation.

Okay ! Note that replacing the import 'fily.pyx' with a cimport is not totally free. If you cimport functions, those functions will not be inlined (in particular popcount32).

I don't know how to use the templates (and I'm unable to find this in #18395).

I just added a merge commit (that branch was in conflict with the latest beta). The trick that is used in that ticket is the following: the function run_spring takes an argument of type dimension_t (a fused type). We do not care what the value of this parameter is, only its type matters (D_TWO or D_THREE), for the function will be compiled twice, once for each type.

Inside the function, depending on the *type* of this variable, the value of dim is determined. As it never changes throughout the function, all tests 'if dim == 2' are resolved at compile-time. You could use the same trick to be able to pick different cost functions for free (at runtime), but admittedly the trick is more a 'hack'.

I agree that we can certainly speed-up method compute_edge_cut. The best operation to compute the number of edges from S+i to V\(S+i) is count_S + degree[i] - 2*popcount32(S&g.graph[i]), where count_S is the number of edges from S to V\S. However, we don't store the number of edges from S to V\S, so I don't know how to do this incremental process.

Well, it is the 'current cost' that is computed in 'exists', isn't it? We can just add an argument 'previous_cost' to 'exists', and then whenever 'exists' (which computed 'current_cost') calls 'exists', it can pass its 'current_cost' as a 'previous_cost'?.. This way 'exists' only has to compute the difference.

Nathann

### comment:8 Changed 5 years ago by git

• Commit changed from d92f30f684949592f36e53e4c03c3bf73c583299 to d1e49ecf1085fc3c407cef28b0457713b349ad9c

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

 ​ba946f8 trac #18746: incremental cost computation ​d1e49ec trac #18746: resolve test error

### comment:9 Changed 5 years ago by dcoudert

Hello,

I have improved the cost computation. It is now incremental and so faster.

I don't see how I can avoid the cimport of popcount32. If I want to reuse the find_order method from vertex_separation, I need a .pxd file. Since FastDigraph is an input parameter of the method, it should appear in that .pxd file, right? Do you have a better solution in mind? The only alternative I see is to not share the code.

For the fuse type / template stuff, since now the methods have different inputs, it is may be too complicated for the possible benefit. You agree?

David.

### comment:10 follow-up: ↓ 13 Changed 5 years ago by ncohen

Hello David,

I added a commit on top on top of your public branch (hoping that you will nto mind). It does the following things:

• Unimportant things
• remove a 'verbose' flag that you do not use
• Simplify the test for connectivity (rather unimportant too)
• use cw in the recursive call to cutwidth
• use cut_off in the call to cutwidth_dyn
• You could not guess how much time I spent over your "fake simple loop", only to figure out that you wanted to be able to use 'break'. It really takes a lot of time. I swear. When you use tricks like that, *please* say it explicitly in a comment.

More technically: I first added a comment above the loop to make it clearer, then thought that it was making things very very complicated to avoid a copy/paste of the three lines needed before the 'return'. Besides, your code did not free the memory when it was interrupted with a CTRL+C.

I rewrote it with a try/except and with two nested loops. Three lines are copy/pasted, but I find this a much better deal in terms of readability than a fake nested loop. Plus it frees the memory.

• In 'exists', I renamed count_S to cost_S. Same here. You have no idea how many questions can be raised in the head of somebody reading the code and not understanding what you do with this variable called 'count_S' which, which turns out to not count S at all. My interpretation of this variable is that it stores the cost of S. Please check.
• When you want to multiply something by two, please use *2 and not <<1. It makes your meaning much clearer. Gcc generates the same code anyway.
-    cdef int mini = (1<<g.n)-1
+    cdef int mini = (<uint8_t> -1)

I also wondered for a moment why you defined this specific value for mini. I ended up convincing myself that you just wanted "a big constant".
• I made a slightly unrelated modification to a distant 'doctest' file. Here is why: this code 'injects' in any Sage file, when you run the tests, a check that there are as many sig_on as sig_off. You will see it if you run the tests on cutwidth.pyx after removing one of the sig_off (for instance the one that appears inside of the return, in the nested loop).

It indicates that a doctest is broken, at some line in cutwidth.pyx. Of course, this doctest is not really there so you are looking for a line that does not really exists. I added a comment to it, so that its meaning is clearer when you get an error in a sage -t.

Could you also document the parameters of the 'exists' function, and the expected behavior? I was surprised that a variable named 'cost' was actually used as "max_admissible_cost".

Thanks,

Nathann

### comment:11 Changed 5 years ago by git

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

 ​7c70b55 trac #18746: Reviewer's commit

### comment:12 Changed 5 years ago by git

• Commit changed from 7c70b555f824ad9a6876f394cd79a65cce0022c7 to b536ed4dbb5e44f705ddd12c429b9473ec24cc58

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

 ​b536ed4 trac #18746: documentation improvements

### comment:13 in reply to: ↑ 10 ; follow-up: ↓ 14 Changed 5 years ago by dcoudert

I'm so sorry that you spend so much time understanding this code. In fact the exists method is almost a copy/paste of the method you did for vertex separation/pathwidth, and I have omitted to extend the documentation. Sorry.

More technically: I first added a comment above the loop to make it clearer, then thought that it was making things very very complicated to avoid a copy/paste of the three lines needed before the 'return'. Besides, your code did not free the memory when it was interrupted with a CTRL+C.

I rewrote it with a try/except and with two nested loops. Three lines are copy/pasted, but I find this a much better deal in terms of readability than a fake nested loop. Plus it frees the memory.

Are you sure that the finally part is executed even after the return instruction in the try ? Shouldn't I add a sage_free before that return ?

• In 'exists', I renamed count_S to cost_S. Same here. You have no idea how many questions can be raised in the head of somebody reading the code and not understanding what you do with this variable called 'count_S' which, which turns out to not count S at all. My interpretation of this variable is that it stores the cost of S. Please check.

I have renamed cost -> k to be consistent with the cutwidth_dyn method. It should be easier to follow.

• When you want to multiply something by two, please use *2 and not <<1. It makes your meaning much clearer. Gcc generates the same code anyway.

OK. I wasn't sure of that.

-    cdef int mini = (1<<g.n)-1
+    cdef int mini = (<uint8_t> -1)

I also wondered for a moment why you defined this specific value for mini. I ended up convincing myself that you just wanted "a big constant".

Right. For vertex separation it was sufficient to initialize it with g.n, but here the maximum value can reach n^2/2 (luckily, since n\leq 31, the maximum possible value, 15*16=240, can be stored in an uint8_t.

• I made a slightly unrelated modification to a distant 'doctest' file. Here is why: this code 'injects' in any Sage file, when you run the tests, a check that there are as many sig_on as sig_off. You will see it if you run the tests on cutwidth.pyx after removing one of the sig_off (for instance the one that appears inside of the return, in the nested loop).

It indicates that a doctest is broken, at some line in cutwidth.pyx. Of course, this doctest is not really there so you are looking for a line that does not really exists. I added a comment to it, so that its meaning is clearer when you get an error in a sage -t.

ok. This is admittedly easier that to create a one line ticket.

Could you also document the parameters of the 'exists' function, and the expected behavior? I was surprised that a variable named 'cost' was actually used as "max_admissible_cost".

I tried to improve both the module documentation and the computation steps.

Thanks,

Thanks to you.

David.

New commits:

 ​b536ed4 trac #18746: documentation improvements

### comment:14 in reply to: ↑ 13 Changed 5 years ago by ncohen

Hellooooooo,

Are you sure that the finally part is executed even after the return instruction in the try ?

Yepyep, 'unfortunately'. I needed it recently, and... Well, it works :-P

sage: def a():
....:     try:
....:         return 1
....:     finally:
....:         print "Hey"
sage: a()
Hey
1


Nathann

### comment:15 Changed 5 years ago by ncohen

• Reviewers set to Nathann Cohen
• Status changed from needs_review to positive_review

OKayyyyyyyyyyyyy ! I looked at it again and it looks good. Thanks for the update!

Assuming that you have no problem with my commit, I switch this to positive_review. THaaaaaanks,

Nathann

### comment:16 Changed 5 years ago by dcoudert

• Status changed from positive_review to needs_work

Hello,

Thanks for the review and the commit ! Unfortunately, I see from the patchbot that we have many errors due to the counting of sig_on/ sig_off. So I assume we have no choice but opening a specific ticket, right?

D.

sage -t --long src/sage/doctest/sources.py
**********************************************************************
File "src/sage/doctest/sources.py", line 694, in sage.doctest.sources.FileDocTestSource._test_enough_doctests
Failed example:
for path, dirs, files in itertools.chain(os.walk('sage'), os.walk('doc')): # long time
path = os.path.relpath(path)
dirs.sort(); files.sort()
for F in files:
_, ext = os.path.splitext(F)
if ext in ('.py', '.pyx', '.pxd', '.pxi', '.sage', '.spyx', '.rst'):
filename = os.path.join(path, F)
FDS = FileDocTestSource(filename, DocTestDefaults(long=True,optional=True))
FDS._test_enough_doctests(verbose=False)
Expected:
There are 7 tests in sage/combinat/dyck_word.py that are not being run
There are 4 tests in sage/combinat/finite_state_machine.py that are not being run
There are 6 tests in sage/combinat/interval_posets.py that are not being run
There are 18 tests in sage/combinat/partition.py that are not being run
There are 15 tests in sage/combinat/permutation.py that are not being run
There are 14 tests in sage/combinat/skew_partition.py that are not being run
There are 18 tests in sage/combinat/tableau.py that are not being run
There are 8 tests in sage/combinat/crystals/tensor_product.py that are not being run
There are 11 tests in sage/combinat/rigged_configurations/rigged_configurations.py that are not being run
There are 15 tests in sage/combinat/root_system/cartan_type.py that are not being run
There are 8 tests in sage/combinat/root_system/type_A.py that are not being run
There are 8 tests in sage/combinat/root_system/type_G.py that are not being run
There are 3 unexpected tests being run in sage/doctest/parsing.py
There are 1 unexpected tests being run in sage/doctest/reporting.py
There are 3 tests in sage/rings/invariant_theory.py that are not being run
Got:
There are 7 tests in sage/combinat/dyck_word.py that are not being run
There are 4 tests in sage/combinat/finite_state_machine.py that are not being run
There are 6 tests in sage/combinat/interval_posets.py that are not being run
There are 18 tests in sage/combinat/partition.py that are not being run
There are 15 tests in sage/combinat/permutation.py that are not being run
There are 14 tests in sage/combinat/skew_partition.py that are not being run
There are 18 tests in sage/combinat/tableau.py that are not being run
There are 8 tests in sage/combinat/crystals/tensor_product.py that are not being run
There are 11 tests in sage/combinat/rigged_configurations/rigged_configurations.py that are not being run
There are 15 tests in sage/combinat/root_system/cartan_type.py that are not being run
There are 8 tests in sage/combinat/root_system/type_A.py that are not being run
There are 8 tests in sage/combinat/root_system/type_G.py that are not being run
There are 3 unexpected tests being run in sage/doctest/parsing.py
There are 1 unexpected tests being run in sage/doctest/reporting.py
There are 3 tests in sage/rings/invariant_theory.py that are not being run
There are 1 unexpected tests being run in doc/en/developer/coding_in_cython.rst
There are 3 unexpected tests being run in doc/en/developer/coding_in_other.rst
There are 1 unexpected tests being run in doc/en/developer/coding_in_python.rst
There are 1 unexpected tests being run in doc/en/thematic_tutorials/coding_theory.rst
**********************************************************************
File "src/sage/doctest/sources.py", line 1456, in sage.doctest.sources.RestSource.parse_docstring
Failed example:
for ex in tests[1].examples:
print ex.sage_source,
Expected:
test1()
test2()
sig_on_count()
Got:
test1()
test2()
sig_on_count() # check sig_on/off pairings
**********************************************************************
1 of   9 in sage.doctest.sources.FileDocTestSource._test_enough_doctests
1 of  14 in sage.doctest.sources.RestSource.parse_docstring
[339 tests, 2 failures, 100.78 s]
sage -t --long src/sage/doctest/test.py
**********************************************************************
File "src/sage/doctest/test.py", line 273, in sage.doctest.test
Failed example:
subprocess.call(["sage", "-t",  "--warn-long", "0", "sig_on.rst"], **kwds)  # long time
Expected:
Running doctests...
Doctesting 1 file.
sage -t --warn-long 0.0 sig_on.rst
**********************************************************************
File "sig_on.rst", line 5, in sage.doctest.tests.sig_on
Failed example:
sig_on_count()
Expected:
0
Got:
1
**********************************************************************
1 of   4 in sage.doctest.tests.sig_on
[2 tests, 1 failure, ...]
----------------------------------------------------------------------
sage -t --warn-long 0.0 sig_on.rst  # 1 doctest failed
----------------------------------------------------------------------
...
1
Got:
Running doctests with ID 2015-06-29-23-32-47-2a7e60db.
Git branch: patchbot/ticket_merged
Using --optional=ccache,gcc,mpir,python2,sage,scons
Doctesting 1 file.
sage -t --warn-long 0.0 sig_on.rst
**********************************************************************
File "sig_on.rst", line 5, in sage.doctest.tests.sig_on
Failed example:
sig_on_count() # check sig_on/off pairings
Expected:
0
Got:
1
**********************************************************************
1 of   4 in sage.doctest.tests.sig_on
[2 tests, 1 failure, 1.61 s]
----------------------------------------------------------------------
sage -t --warn-long 0.0 sig_on.rst  # 1 doctest failed
----------------------------------------------------------------------
Total time for all tests: 1.7 seconds
cpu time: 0.1 seconds
cumulative wall time: 1.6 seconds
1
**********************************************************************
1 of  45 in sage.doctest.test
[44 tests, 1 failure, 71.79 s]
sage -t --long src/sage/doctest/forker.py
**********************************************************************
File "src/sage/doctest/forker.py", line 2035, in sage.doctest.forker.DocTestTask
Failed example:
ntests, results = DTT(options=DD)
Expected nothing
Got:
**********************************************************************
File "/home/sage/sage-devel/src/sage/doctest/sources.py", line 1456, in sage.doctest.sources.RestSource.parse_docstring
Failed example:
for ex in tests[1].examples:
print ex.sage_source,
Expected:
test1()
test2()
sig_on_count()
Got:
test1()
test2()
sig_on_count() # check sig_on/off pairings
**********************************************************************
1 of  14 in sage.doctest.sources.RestSource.parse_docstring
**********************************************************************
[439 tests, 1 failure, 13.16 s]
----------------------------------------------------------------------
sage -t --long src/sage/doctest/sources.py  # 2 doctests failed
sage -t --long src/sage/doctest/test.py  # 1 doctest failed
sage -t --long src/sage/doctest/forker.py  # 1 doctest failed
----------------------------------------------------------------------


### comment:17 Changed 5 years ago by ncohen

Arggggggggggg.... Okay T_T

### comment:18 Changed 5 years ago by git

• Commit changed from b536ed4dbb5e44f705ddd12c429b9473ec24cc58 to 551d0f0ab9c7942e4d8d61bc2f18808011698dfb

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

 ​551d0f0 trac #18746: Remove modifications to doctest.py`

### comment:19 Changed 5 years ago by ncohen

• Status changed from needs_work to positive_review

Thank you.

### comment:21 Changed 5 years ago by vbraun

• Branch changed from public/18746 to 551d0f0ab9c7942e4d8d61bc2f18808011698dfb
• Resolution set to fixed
• Status changed from positive_review to closed
Note: See TracTickets for help on using tickets.