Opened 7 years ago

Closed 7 years ago

#18876 closed enhancement (fixed)

Boost Cuthill-McKee, King Ordering

Reported by: borassi Owned by:
Priority: major Milestone: sage-6.8
Component: graph theory Keywords: Cuthill-McKee ordering, King ordering, bandwidth
Cc: ncohen, dcoudert Merged in:
Authors: Michele Borassi Reviewers: David Coudert
Report Upstream: N/A Work issues:
Branch: ecda30f (Commits, GitHub, GitLab) Commit: ecda30fc9954a53b8104d9cf14edd1f73a7a4cad
Dependencies: #18811, #18564, #18839 Stopgaps:

Status badges

Description (last modified by borassi)

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

Change History (28)

comment:1 Changed 7 years ago by borassi

  • Authors set to Michele Borassi
  • Cc ncohen dcoudert added
  • Component changed from PLEASE CHANGE to graph theory
  • Dependencies set to #18811, #18564, #18839
  • Description modified (diff)
  • Keywords Cuthill-McKee ordering King ordering bandwidth added
  • Type changed from PLEASE CHANGE to enhancement

comment:2 Changed 7 years ago by borassi

  • Branch set to u/borassi/boost_cuthill_mckee__king_ordering

comment:3 Changed 7 years ago by borassi

  • Commit set to 6a5c9d02abb93f12313b039a61ba0a62b6f88788
  • Status changed from new to needs_review

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.

comment:4 follow-up: Changed 7 years ago by dcoudert

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
    

comment:5 Changed 7 years ago by git

  • Commit changed from 6a5c9d02abb93f12313b039a61ba0a62b6f88788 to 124cf8a6d7c27100479f7f17289040b8ea805c43

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

124cf8aReviewer's comments

comment:6 in reply to: ↑ 4 Changed 7 years ago by borassi

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!

comment:7 Changed 7 years ago by dcoudert

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.

comment:8 follow-up: Changed 7 years ago by dcoudert

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.

comment:9 Changed 7 years ago by git

  • Commit changed from 124cf8a6d7c27100479f7f17289040b8ea805c43 to b1b1612dbbf59bedfc97282f49c0e79932a40ef6

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

b1b1612Added link from bandwidth module to bandwidth_heuristics

comment:10 in reply to: ↑ 8 Changed 7 years ago by borassi

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

comment:11 Changed 7 years ago by dcoudert

Exactly ;)

comment:12 Changed 7 years ago by dcoudert

  • Reviewers set to David Coudert
  • Status changed from needs_review to positive_review

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

comment:13 Changed 7 years ago by vbraun

  • Status changed from positive_review to needs_work

Merge conflict

comment:14 Changed 7 years ago by git

  • Commit changed from b1b1612dbbf59bedfc97282f49c0e79932a40ef6 to 6c084ecd07a17b4ca7c63c6cb7f244fe0dde0545

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

6c084ecMerge branch 'develop' into t/18876/boost_cuthill_mckee__king_ordering

comment:15 Changed 7 years ago by borassi

  • Status changed from needs_work to needs_review

I have merged the new version of the develop branch into this new branch. Is it sufficient?

comment:16 Changed 7 years ago by dcoudert

  • Status changed from needs_review to positive_review

OK for me with last develop branch.

comment:17 Changed 7 years ago by vbraun

  • Status changed from positive_review to needs_work

Still conflicts, probably #18868

comment:18 Changed 7 years ago by dcoudert

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$

comment:19 Changed 7 years ago by vbraun

Just wait for beta0 (tonight, probably)

comment:20 Changed 7 years ago by git

  • Commit changed from 6c084ecd07a17b4ca7c63c6cb7f244fe0dde0545 to 3847037e70388b86146c5f9e97e25bb92ec6e949

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

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

comment:21 Changed 7 years ago by borassi

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

comment:22 Changed 7 years ago by borassi

  • Status changed from needs_work to needs_review

comment:23 Changed 7 years ago by dcoudert

  • Status changed from needs_review to positive_review

Also working for me.

comment:24 follow-up: Changed 7 years ago by ncohen

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`

comment:25 Changed 7 years ago by git

  • Commit changed from 3847037e70388b86146c5f9e97e25bb92ec6e949 to ecda30fc9954a53b8104d9cf14edd1f73a7a4cad
  • Status changed from positive_review to needs_review

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

ecda30fApplied Nathann's suggestion

comment:26 in reply to: ↑ 24 Changed 7 years ago by borassi

Done!

Replying to ncohen:

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`

comment:27 Changed 7 years ago by dcoudert

  • Status changed from needs_review to positive_review

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

comment:28 Changed 7 years ago by vbraun

  • Branch changed from u/borassi/boost_cuthill_mckee__king_ordering to ecda30fc9954a53b8104d9cf14edd1f73a7a4cad
  • Resolution set to fixed
  • Status changed from positive_review to closed
Note: See TracTickets for help on using tickets.