Re: [sage-devel] [Graph Theory Project] Reverse Cuthill-McKee

[Minh Nguyen]

Hi Raniere,

Sorry for the very late reply.

On Wed, Sep 19, 2012 at 10:30 AM, Raniere Gaia Silva
<r.ga...@gmail.com> wrote:
> I will implement the Reverse Cuthill-McKee algorithm in the next months and think do it as a new Sage feature.

It's awesome that you are thinking about contributing.


> I send a previous email to Robert Miller asking for some tips because a haven't much experience and he suggest ask in this list too.

The (reverse) Cuthill-McKee algorithms (RCM or CM) are special cases
of breadth-first search, so I don't expect to see any major difference
between breadth-first search and implementations of RCM and CM. I
think a good start to learn about how to implement RCM is to look
through how breadth-first search is implemented in Sage. See this
function for details:

* sage.graphs.generic_graph.GenericGraph.breadth_first_search

The full documentation is at

http://www.sagemath.org/doc/reference/sage/graphs/generic_graph.html#sage.graphs.generic_graph.GenericGraph.breadth_first_search

It might be worthwhile to think about how to speed up RCM. The GPS
algorithm comes to mind:

http://www.jstor.org/discover/10.2307/2156090

--
Regards,
Minh Van Nguyen
http://bit.ly/mvngu