Boost Cuthill-McKee, King Ordering #18876

sagetrac-borassi · 2015-07-10T08:33:33Z

Uses Boost to compute Cuthill-McKee and King ordering of vertices: heuristically, these orderings are used to minimize the bandwidth of the graph.

The bandwidth bw(M) of a matrix M is the smallest integer k such that all non-zero entries of M are at distance k from the diagonal. The bandwidth bw(G) of an undirected graph G is the minimum bandwidth of the adjacency matrix of G, over all possible relabellings of its vertices.

Since computing the bandwidth of a graph is NP-hard, two heuristics were developed, in order to find a good ordering: Cuthill-McKee and King ordering. This ticket will include in Sage the implementation of these two heuristics (closing also ticket #16583, which asks for an implementation of Cuthill-McKee).

Depends on #18811
Depends on #18564
Depends on #18839

CC: @nathanncohen @dcoudert

Component: graph theory

Keywords: Cuthill-McKee ordering, King ordering, bandwidth

Author: Michele Borassi

Branch/Commit: ecda30f

Reviewer: David Coudert

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

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

sagetrac-borassi · 2015-07-10T08:44:08Z

Dependencies: #18811, #18564, #18839

sagetrac-borassi · 2015-07-10T08:44:08Z

Changed keywords from none to Cuthill-McKee ordering, King ordering, bandwidth

sagetrac-borassi · 2015-07-10T08:44:08Z

Author: Michele Borassi

sagetrac-borassi · 2015-07-13T08:15:57Z

Branch: u/borassi/boost_cuthill_mckee__king_ordering

sagetrac-borassi · 2015-07-13T08:41:34Z

Commit: 6a5c9d0

sagetrac-borassi · 2015-07-13T08:41:34Z

comment:3

This is the first draft for the inclusion of the Boost Cuthill-McKee and King orderings. I just wrote a post on sage-devel forum to ask if this algorithm could be useful for matrix analysis, and, in case, how to include it.

dcoudert · 2015-07-13T14:00:41Z

comment:4

Some issues:

You should return a tuple instead of a list, so (6, [9, 5, 8, 4, 6, 0, 7, 3, 1, 2]) instead of [6, [9, 5, 8, 4, 6, 0, 7, 3, 1, 2]].
I don't know how to do, but it would be nice to see bandwidth_heuristics in the html output of the bandwidth module.
Not working with trivial graphs

from sage.graphs.graph_decompositions import bandwidth as BW
sage: BW.bandwidth_heuristics(Graph())
---------------------------------------------------------------------------
ValueError                                Traceback (most recent call last)
<ipython-input-10-88d2a8f9e7cb> in <module>()
----> 1 BW.bandwidth_heuristics(Graph())

/Users/dcoudert/sage/src/sage/graphs/base/boost_graph.pyx in sage.graphs.base.boost_graph.bandwidth_heuristics (/Users/dcoudert/sage/src/build/cythonized/sage/graphs/base/boost_graph.cpp:4970)()
    366 
    367 
--> 368 cpdef bandwidth_heuristics(g, algorithm = 'cuthill_mckee'):
    369     r"""
    370     Uses Boost heuristics to approximate the bandwidth of the input graph.

/Users/dcoudert/sage/src/sage/graphs/base/boost_graph.pyx in sage.graphs.base.boost_graph.bandwidth_heuristics (/Users/dcoudert/sage/src/build/cythonized/sage/graphs/base/boost_graph.cpp:4815)()
    453     cdef int n = g.num_verts()
    454     cdef dict pos = {int_to_vertex[result[i]]:i for i in range(n)}
--> 455     cdef int bandwidth = max([abs(pos[u]-pos[v]) for u,v in g.edges(labels=False)])
    456 
    457     sig_off()

ValueError: max() arg is an empty sequence

sage: BW.bandwidth_heuristics(graphs.PathGraph(1))
---------------------------------------------------------------------------
ValueError                                Traceback (most recent call last)
<ipython-input-11-bf860ec1a3e2> in <module>()
----> 1 BW.bandwidth_heuristics(graphs.PathGraph(Integer(1)))

/Users/dcoudert/sage/src/sage/graphs/base/boost_graph.pyx in sage.graphs.base.boost_graph.bandwidth_heuristics (/Users/dcoudert/sage/src/build/cythonized/sage/graphs/base/boost_graph.cpp:4970)()
    366 
    367 
--> 368 cpdef bandwidth_heuristics(g, algorithm = 'cuthill_mckee'):
    369     r"""
    370     Uses Boost heuristics to approximate the bandwidth of the input graph.

/Users/dcoudert/sage/src/sage/graphs/base/boost_graph.pyx in sage.graphs.base.boost_graph.bandwidth_heuristics (/Users/dcoudert/sage/src/build/cythonized/sage/graphs/base/boost_graph.cpp:4815)()
    453     cdef int n = g.num_verts()
    454     cdef dict pos = {int_to_vertex[result[i]]:i for i in range(n)}
--> 455     cdef int bandwidth = max([abs(pos[u]-pos[v]) for u,v in g.edges(labels=False)])
    456 
    457     sig_off()

ValueError: max() arg is an empty sequence

sagetrac-git · 2015-07-13T15:29:45Z

Changed commit from 6a5c9d0 to 124cf8a

sagetrac-git · 2015-07-13T15:29:45Z

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

`124cf8a`	`Reviewer's comments`

sagetrac-borassi · 2015-07-13T15:32:15Z

comment:6

Hello!

You should return a tuple instead of a list, so (6, [9, 5, 8, 4, 6, 0, 7, 3, 1, 2]) instead of [6, [9, 5, 8, 4, 6, 0, 7, 3, 1, 2]].

Done!

I don't know how to do, but it would be nice to see bandwidth_heuristics in the html output of the bandwidth module.

Probably we need to use types.FunctionType, as we used types.MethodType when we were working with the dominator tree. However, I have troubles finding the right command (and I have very little experience with these routines). Nathann, can you help us?

Not working with trivial graphs

Done, and added a doctest!

dcoudert · 2015-07-13T15:48:28Z

comment:7

Note that you can simple write return bandwidth, [int_to_vertex[result[i]] for i in range(n)] and it will return a tuple.

I did the following test and it's working ;)

sage: G = Graph(loops=True, multiedges=True)
sage: G.add_edge(0,0,'a')
sage: G.add_edge(0,0,'b')
sage: G.edges()
[(0, 0, 'a'), (0, 0, 'b')]
sage: bandwidth_heuristics(G)
(0, [0])
sage: bandwidth_heuristics(G, algorithm='king')
(0, [0])

Let see if Nathann has a good trick for adding the algorithm to the documentation of the bandwidth module.

dcoudert · 2015-07-15T11:25:02Z

comment:8

Hello Michele,

It seems that the easiest solution is to add an index of the methods as done for vertex_separation and to point directly to the description of the method in the boost_graph module.

David.

sagetrac-git · 2015-07-15T17:41:45Z

Changed commit from 124cf8a to b1b1612

sagetrac-git · 2015-07-15T17:41:45Z

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

`b1b1612`	`Added link from bandwidth module to bandwidth_heuristics`

sagetrac-borassi · 2015-07-15T17:42:45Z

comment:10

I'm not sure I understood well your comment: is this what you mean?

dcoudert · 2015-07-15T20:32:54Z

comment:11

Exactly ;)

dcoudert · 2015-07-15T20:58:41Z

Reviewer: David Coudert

dcoudert · 2015-07-15T20:58:41Z

comment:12

For me the patch is now good to go (install, tests, doc, etc.).

vbraun · 2015-07-26T14:30:16Z

comment:13

Merge conflict

sagetrac-git · 2015-07-27T09:30:21Z

Changed commit from b1b1612 to 6c084ec

dcoudert · 2015-07-27T18:14:05Z

comment:16

OK for me with last develop branch.

vbraun · 2015-07-28T22:49:29Z

comment:17

Still conflicts, probably #18868

dcoudert · 2015-07-29T11:54:13Z

comment:18

Volker,

The develop branch we use is 6.8, and ticket #18868 is not in it. Consequently, and unless we are doing something wrong with git, we don't have any merge conflict (see below [1]).

However, I'm not able to merge ticket #18868 on top of the current develop branch (see below [2])!

So, can I set this ticket to positive review ?

Best,
David.

[1] Trying this ticket on top of current develop branch, 6.8:

confetti:sage dcoudert$ git trac checkout develop
Local branch already exists. Use "git trac pull" to get updates.
confetti:sage dcoudert$ git trac pull
confetti:sage dcoudert$ make
...
Sage build/upgrade complete!

To install small scripts to directly run Sage's versions of GAP,
the PARI/GP interpreter, Maxima, or Singular etc. (by typing e.g.
just 'gap' or 'gp') into a standard 'bin' directory, start Sage
by typing 'sage' (or './sage') and enter something like

    install_scripts('/usr/local/bin')

at the Sage command prompt ('sage:').

confetti:sage dcoudert$ ./sage --version
SageMath Version 6.8, Release Date: 2015-07-26
confetti:sage dcoudert$ git trac checkout 18876
Loading ticket #18876...
Checking out Trac #18876 remote branch u/borassi/boost_cuthill_mckee__king_ordering -> local branch t/18876/boost_cuthill_mckee__king_ordering...
confetti:sage dcoudert$ git branch
  develop
  master
* t/18876/boost_cuthill_mckee__king_ordering
  tmp
confetti:sage dcoudert$ make
...
Sage build/upgrade complete!

To install small scripts to directly run Sage's versions of GAP,
the PARI/GP interpreter, Maxima, or Singular etc. (by typing e.g.
just 'gap' or 'gp') into a standard 'bin' directory, start Sage
by typing 'sage' (or './sage') and enter something like

    install_scripts('/usr/local/bin')

at the Sage command prompt ('sage:').

confetti:sage dcoudert$ ./sage --version
SageMath Version 6.8, Release Date: 2015-07-26
confetti:sage dcoudert$

[2] Trying to merge ticket #18868 on top of current develop branch, 6.8:

confetti:sage dcoudert$ git branch
  basic
* develop
  master
  t/18876/boost_cuthill_mckee__king_ordering
  tmp
confetti:sage dcoudert$ git trac checkout 18868
Loading ticket #18868...
Checking out Trac #18868 remote branch 0304d9f21aa483f8b37bc6959e1a7490cd23ddb5 -> local branch t/18868/0304d9f21aa483f8b37bc6959e1a7490cd23ddb5...
Traceback (most recent call last):
  File "/Users/dcoudert/sage/git-trac-command/bin/git-trac", line 18, in <module>
    cmdline.launch()
  File "/Users/dcoudert/sage/git-trac-command/git_trac/cmdline.py", line 204, in launch
    app.checkout(args.ticket_or_branch, args.branch_name)
  File "/Users/dcoudert/sage/git-trac-command/git_trac/app.py", line 98, in checkout
    self._checkout_ticket(int(ticket_or_branch), branch_name)
  File "/Users/dcoudert/sage/git-trac-command/git_trac/app.py", line 122, in _checkout_ticket
    self.repo.checkout_new_branch(ticket.branch, branch)
  File "/Users/dcoudert/sage/git-trac-command/git_trac/git_repository.py", line 123, in checkout_new_branch
    self.git.fetch('trac', remote)
  File "/Users/dcoudert/sage/git-trac-command/git_trac/git_interface.py", line 341, in meth
    return self.execute(git_cmd, *args, **kwds)
  File "/Users/dcoudert/sage/git-trac-command/git_trac/git_interface.py", line 328, in execute
    popen_stderr=subprocess.PIPE)
  File "/Users/dcoudert/sage/git-trac-command/git_trac/git_interface.py", line 263, in _run
    raise GitError(result)
git_trac.git_error.GitError: git returned with non-zero exit code (1) when executing "git fetch trac 0304d9f21aa483f8b37bc6959e1a7490cd23ddb5"
confetti:sage dcoudert$

vbraun · 2015-07-29T13:36:58Z

comment:19

Just wait for beta0 (tonight, probably)

sagetrac-git · 2015-07-30T09:36:03Z

Changed commit from 6c084ec to 3847037

sagetrac-git · 2015-07-30T09:36:03Z

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

`3847037`	`Merge branch 'develop' into t/18876/boost_cuthill_mckee__king_ordering`

sagetrac-borassi · 2015-07-30T09:37:25Z

comment:21

Hello!

I have merged with beta0, and I solved a conflict in bandwidth file. I have tested the whole graph part of the library, and all tests were passed.

Hope now the conflict is solved!

Thank you,

Michele

dcoudert · 2015-07-30T09:41:59Z

comment:23

Also working for me.

nathanncohen · 2015-07-30T09:45:22Z

comment:24

Just a tip: what is done here with

:meth:`bandwidth_heuristics()<sage.graphs.base.boost_graph.bandwidth_heuristics>`

is more easily achieved with

:meth:`~sage.graphs.base.boost_graph.bandwidth_heuristics`

sagetrac-git · 2015-07-30T10:42:04Z

Branch pushed to git repo; I updated commit sha1 and set ticket back to needs_review. New commits:

`ecda30f`	`Applied Nathann's suggestion`

sagetrac-git · 2015-07-30T10:42:04Z

Changed commit from 3847037 to ecda30f

sagetrac-borassi · 2015-07-30T10:42:35Z

comment:26

Done!

Replying to @nathanncohen:

Just a tip: what is done here with

:meth:`bandwidth_heuristics()<sage.graphs.base.boost_graph.bandwidth_heuristics>`

is more easily achieved with

:meth:`~sage.graphs.base.boost_graph.bandwidth_heuristics`

dcoudert · 2015-07-30T11:22:27Z

comment:27

unless another merge problem arrives, this ticket is good to go.

vbraun · 2015-07-31T17:52:22Z

Changed branch from u/borassi/boost_cuthill_mckee__king_ordering to ecda30f

sagetrac-borassi mannequin added this to the sage-6.8 milestone Jul 10, 2015

sagetrac-borassi mannequin added the p: major / 3 label Jul 10, 2015

This comment has been minimized.

Sign in to view

sagetrac-borassi mannequin added c: graph theory labels Jul 10, 2015

sagetrac-borassi mannequin added the s: needs review label Jul 13, 2015

dcoudert added s: positive review and removed s: needs review labels Jul 15, 2015

vbraun added s: needs work and removed s: positive review labels Jul 26, 2015

dcoudert added s: positive review and removed s: needs review labels Jul 27, 2015

vbraun added s: needs work and removed s: positive review labels Jul 28, 2015

sagetrac-borassi mannequin added s: needs review and removed s: needs work labels Jul 30, 2015

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

sagetrac-git mannequin added s: needs review and removed s: positive review labels Jul 30, 2015

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

vbraun removed the s: positive review label Jul 31, 2015

vbraun closed this as completed in c33a40b Jul 31, 2015

This was referenced Jul 31, 2015

Boost minimum spanning tree #18910

Closed

Refactor Closeness Centrality #19007

Closed

Boost Cuthill-McKee, King Ordering #18876

Boost Cuthill-McKee, King Ordering #18876

Comments

sagetrac-borassi mannequin commented Jul 10, 2015

sagetrac-borassi mannequin commented Jul 10, 2015

This comment has been minimized.

sagetrac-borassi mannequin commented Jul 10, 2015

sagetrac-borassi mannequin commented Jul 10, 2015

sagetrac-borassi mannequin commented Jul 13, 2015

sagetrac-borassi mannequin commented Jul 13, 2015

sagetrac-borassi mannequin commented Jul 13, 2015

dcoudert commented Jul 13, 2015

sagetrac-git mannequin commented Jul 13, 2015

sagetrac-git mannequin commented Jul 13, 2015

sagetrac-borassi mannequin commented Jul 13, 2015

dcoudert commented Jul 13, 2015

dcoudert commented Jul 15, 2015

sagetrac-git mannequin commented Jul 15, 2015

sagetrac-git mannequin commented Jul 15, 2015

sagetrac-borassi mannequin commented Jul 15, 2015

dcoudert commented Jul 15, 2015

dcoudert commented Jul 15, 2015

dcoudert commented Jul 15, 2015

vbraun commented Jul 26, 2015

sagetrac-git mannequin commented Jul 27, 2015

dcoudert commented Jul 27, 2015

vbraun commented Jul 28, 2015

dcoudert commented Jul 29, 2015

vbraun commented Jul 29, 2015

sagetrac-git mannequin commented Jul 30, 2015

sagetrac-git mannequin commented Jul 30, 2015

sagetrac-borassi mannequin commented Jul 30, 2015

dcoudert commented Jul 30, 2015

nathanncohen mannequin commented Jul 30, 2015

sagetrac-git mannequin commented Jul 30, 2015

sagetrac-git mannequin commented Jul 30, 2015

sagetrac-borassi mannequin commented Jul 30, 2015

dcoudert commented Jul 30, 2015

vbraun commented Jul 31, 2015