Opened 5 years ago
Closed 5 years ago
#18746 closed enhancement (fixed)
Cutwidth of a graph
Reported by:  dcoudert  Owned by:  

Priority:  minor  Milestone:  sage6.8 
Component:  graph theory  Keywords:  
Cc:  ncohen  Merged in:  
Authors:  David Coudert  Reviewers:  Nathann Cohen 
Report Upstream:  N/A  Work issues:  
Branch:  551d0f0 (Commits)  Commit:  551d0f0ab9c7942e4d8d61bc2f18808011698dfb 
Dependencies:  Stopgaps: 
Description (last modified by )
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.
Change History (21)
comment:1 Changed 5 years ago by
 Branch set to public/18746
comment:2 Changed 5 years ago by
 Commit set to 165c0b64eeb569161e862603535e2ef2592c2229
comment:3 Changed 5 years ago by
 Cc ncohen added
 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
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 docpt += 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 recomputing 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.
 About
+ 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?
 About
+ + 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 changeint8_t
intouint8_t
vertex_separation_exp
then yes of course!
Have fuuuuuuun,
Nathann
comment:5 Changed 5 years ago by
 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 followup: ↓ 7 Changed 5 years ago by
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 speedup 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.
comment:7 in reply to: ↑ 6 Changed 5 years ago by
I have performed several modifications and I'm now using the
find_order
method ofvertex_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 compiletime. 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 speedup method
compute_edge_cut
. The best operation to compute the number of edges fromS+i
toV\(S+i)
iscount_S + degree[i]  2*popcount32(S&g.graph[i])
, wherecount_S
is the number of edges fromS
toV\S
. However, we don't store the number of edges fromS
toV\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
 Commit changed from d92f30f684949592f36e53e4c03c3bf73c583299 to d1e49ecf1085fc3c407cef28b0457713b349ad9c
comment:9 Changed 5 years ago by
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 followup: ↓ 13 Changed 5 years ago by
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 tocutwidth
 use
cut_off
in the call tocutwidth_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
tocost_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 ofS
. 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.
 About:
 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 formini
. 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
assig_off
. You will see it if you run the tests oncutwidth.pyx
after removing one of thesig_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 asage 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
 Commit changed from d1e49ecf1085fc3c407cef28b0457713b349ad9c to 7c70b555f824ad9a6876f394cd79a65cce0022c7
Branch pushed to git repo; I updated commit sha1. New commits:
7c70b55  trac #18746: Reviewer's commit

comment:12 Changed 5 years ago by
 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 ; followup: ↓ 14 Changed 5 years ago by
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
tocost_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 ofS
. 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.
 About:
 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 formini
. 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
assig_off
. You will see it if you run the tests oncutwidth.pyx
after removing one of thesig_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 asage 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
Hellooooooo,
Are you sure that the
finally
part is executed even after thereturn
instruction in thetry
?
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
 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
 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 ********************************************************************** 2 items had failures: 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", "warnlong", "0", "sig_on.rst"], **kwds) # long time Expected: Running doctests... Doctesting 1 file. sage t warnlong 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 item had failures: 1 of 4 in sage.doctest.tests.sig_on [2 tests, 1 failure, ...]  sage t warnlong 0.0 sig_on.rst # 1 doctest failed  ... 1 Got: Running doctests with ID 201506292332472a7e60db. Git branch: patchbot/ticket_merged Using optional=ccache,gcc,mpir,python2,sage,scons Doctesting 1 file. sage t warnlong 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 item had failures: 1 of 4 in sage.doctest.tests.sig_on [2 tests, 1 failure, 1.61 s]  sage t warnlong 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 item had failures: 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/sagedevel/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 item had failures: 1 of 14 in sage.doctest.sources.RestSource.parse_docstring ********************************************************************** 1 item had failures: 1 of 14 in sage.doctest.forker.DocTestTask [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
Arggggggggggg.... Okay T_T
comment:18 Changed 5 years ago by
 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
 Status changed from needs_work to positive_review
comment:20 Changed 5 years ago by
Thank you.
comment:21 Changed 5 years ago by
 Branch changed from public/18746 to 551d0f0ab9c7942e4d8d61bc2f18808011698dfb
 Resolution set to fixed
 Status changed from positive_review to closed
Branch pushed to git repo; I updated commit sha1. New commits:
trac #18746: preparation
trac #18746: add int_to_vertices to fast digraph
trac #18746: creation of the module and doc
trac #18746: add method for measuring the width of a layout
trac #18746: Dynamic programming algorithm
trac #18746: front end method
trac #18746: typo
trac #18746: various minor issues