Cutwidth of a graph #18746

dcoudert · 2015-06-20T08:18:44Z

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.

CC: @nathanncohen

Component: graph theory

Author: David Coudert

Branch/Commit: 551d0f0

Reviewer: Nathann Cohen

Issue created by migration from https://trac.sagemath.org/ticket/18746

The text was updated successfully, but these errors were encountered:

dcoudert · 2015-06-20T10:04:10Z

Branch: public/18746

sagetrac-git · 2015-06-20T10:25:57Z

Commit: 165c0b6

sagetrac-git · 2015-06-20T10:25:57Z

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`

dcoudert · 2015-06-20T10:32:10Z

comment:3

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).

nathanncohen · 2015-06-26T10:51:44Z

comment:4

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.

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 (moderate) Speedup in layout_spring #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 change int8_t into uint8_t vertex_separation_exp then yes of course!

Have fuuuuuuun,

Nathann

sagetrac-git · 2015-06-27T12:18:06Z

Changed commit from 165c0b6 to d92f30f

sagetrac-git · 2015-06-27T12:18:06Z

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`

dcoudert · 2015-06-27T12:25:12Z

comment:6

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.

nathanncohen · 2015-06-27T16:28:06Z

comment:7

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

sagetrac-git · 2015-06-28T17:17:01Z

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

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

sagetrac-git · 2015-06-28T17:17:01Z

Changed commit from d92f30f to d1e49ec

dcoudert · 2015-06-28T17:23:17Z

comment:9

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.

nathanncohen · 2015-06-29T17:45:25Z

comment:10

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.
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 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

sagetrac-git · 2015-06-29T17:45:59Z

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

`7c70b55`	`trac #18746: Reviewer's commit`

sagetrac-git · 2015-06-29T17:45:59Z

Changed commit from d1e49ec to 7c70b55

sagetrac-git · 2015-06-29T20:59:17Z

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

`b536ed4`	`trac #18746: documentation improvements`

sagetrac-git · 2015-06-29T20:59:17Z

Changed commit from 7c70b55 to b536ed4

dcoudert · 2015-06-29T21:00:39Z

comment:13

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.

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 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`

nathanncohen · 2015-06-30T09:22:51Z

comment:14

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

nathanncohen · 2015-06-30T09:42:03Z

Reviewer: Nathann Cohen

nathanncohen · 2015-06-30T09:42:03Z

comment:15

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

dcoudert · 2015-06-30T10:02:37Z

comment:16

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",  "--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 item had failures:
       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 item had failures:
       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 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/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 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
----------------------------------------------------------------------

nathanncohen · 2015-06-30T10:08:26Z

comment:17

Arggggggggggg.... Okay T_T

sagetrac-git · 2015-06-30T10:10:05Z

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

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

sagetrac-git · 2015-06-30T10:10:05Z

Changed commit from b536ed4 to 551d0f0

dcoudert · 2015-06-30T10:34:09Z

comment:20

Thank you.

vbraun · 2015-06-30T23:12:26Z

Changed branch from public/18746 to 551d0f0

dcoudert added this to the sage-6.8 milestone Jun 20, 2015

dcoudert added c: graph theory labels Jun 20, 2015

This comment has been minimized.

Sign in to view

dcoudert added the s: needs review label Jun 20, 2015

nathanncohen mannequin added s: positive review and removed s: needs review labels Jun 30, 2015

dcoudert added s: needs work and removed s: positive review labels Jun 30, 2015

nathanncohen mannequin added s: positive review and removed s: needs work labels Jun 30, 2015

vbraun removed the s: positive review label Jun 30, 2015

vbraun closed this as completed in 4aab354 Jun 30, 2015

nathanncohen mannequin mentioned this issue Jul 5, 2015

Add a hint in the automatic doctest sig_on_count() #18829

Closed

strogdon mentioned this issue Jul 4, 2015

Really fix cleaning of Sage library #18842

Closed

Provide feedback

Saved searches

Use saved searches to filter your results more quickly

Cutwidth of a graph #18746

Cutwidth of a graph #18746

dcoudert commented Jun 20, 2015

dcoudert commented Jun 20, 2015

sagetrac-git mannequin commented Jun 20, 2015

sagetrac-git mannequin commented Jun 20, 2015

dcoudert commented Jun 20, 2015

This comment has been minimized.

nathanncohen mannequin commented Jun 26, 2015

sagetrac-git mannequin commented Jun 27, 2015

sagetrac-git mannequin commented Jun 27, 2015

dcoudert commented Jun 27, 2015

nathanncohen mannequin commented Jun 27, 2015

sagetrac-git mannequin commented Jun 28, 2015

sagetrac-git mannequin commented Jun 28, 2015

dcoudert commented Jun 28, 2015

nathanncohen mannequin commented Jun 29, 2015

sagetrac-git mannequin commented Jun 29, 2015

sagetrac-git mannequin commented Jun 29, 2015

sagetrac-git mannequin commented Jun 29, 2015

sagetrac-git mannequin commented Jun 29, 2015

dcoudert commented Jun 29, 2015

nathanncohen mannequin commented Jun 30, 2015

nathanncohen mannequin commented Jun 30, 2015

nathanncohen mannequin commented Jun 30, 2015

dcoudert commented Jun 30, 2015

nathanncohen mannequin commented Jun 30, 2015

sagetrac-git mannequin commented Jun 30, 2015

sagetrac-git mannequin commented Jun 30, 2015

dcoudert commented Jun 30, 2015

vbraun commented Jun 30, 2015

Cutwidth of a graph #18746

Cutwidth of a graph #18746

Comments

dcoudert commented Jun 20, 2015

dcoudert commented Jun 20, 2015

sagetrac-git mannequin commented Jun 20, 2015

sagetrac-git mannequin commented Jun 20, 2015

dcoudert commented Jun 20, 2015

This comment has been minimized.

nathanncohen mannequin commented Jun 26, 2015

sagetrac-git mannequin commented Jun 27, 2015

sagetrac-git mannequin commented Jun 27, 2015

dcoudert commented Jun 27, 2015

nathanncohen mannequin commented Jun 27, 2015

sagetrac-git mannequin commented Jun 28, 2015

sagetrac-git mannequin commented Jun 28, 2015

dcoudert commented Jun 28, 2015

nathanncohen mannequin commented Jun 29, 2015

sagetrac-git mannequin commented Jun 29, 2015

sagetrac-git mannequin commented Jun 29, 2015

sagetrac-git mannequin commented Jun 29, 2015

sagetrac-git mannequin commented Jun 29, 2015

dcoudert commented Jun 29, 2015

nathanncohen mannequin commented Jun 30, 2015

nathanncohen mannequin commented Jun 30, 2015

nathanncohen mannequin commented Jun 30, 2015

dcoudert commented Jun 30, 2015

nathanncohen mannequin commented Jun 30, 2015

sagetrac-git mannequin commented Jun 30, 2015

sagetrac-git mannequin commented Jun 30, 2015

dcoudert commented Jun 30, 2015

vbraun commented Jun 30, 2015