hyperref and algorithm2e line references

I like to use the hyperref and algorithm2e (Release 3.9) packages when creating documents with LaTeX. Unfortunately, there seems to be a slight incompatibility:

Suppose I process the following with pdflatex:

\documentclass{article}
\usepackage[naturalnames]{hyperref}
\usepackage[linesnumbered,boxed]{algorithm2e}
\begin{document}
\begin{algorithm}
First\label{line_1}\;
Second\label{line_2}\;
Third\label{line_3}\;
\end{algorithm}
First is on Line~\ref{line_1}, second is on Line~\ref{line_2} and third is on Line~\ref{line_3}.
\end{document}

Then I get:


The line references don't work -- even though they were meant to be fixed in Release 3.3 of algorithm2e according to the change log! A quick fix is to use the [naturalnames] option of hyperref package and comment out lines 845, 847, 849 and 850 of algorithm2e.sty to get (lines 844 to 853 shown below):

\newcommand{\nl}{%
%  \@ifundefined{href}{% if not hyperref then do a simple refstepcounter
    \refstepcounter{AlgoLine}%
%  }{% else if hyperref, do the anchor so 2 lines in two differents algorithms cannot have the same href
%    \stepcounter{AlgoLine}\Hy@raisedlink{\hyper@anchorstart{AlgoLine\thealgocfline.\theAlgoLine}\hyper@anchorend}%
%    \stepcounter{AlgoLine}\Hy@raisedlink{\hyper@anchorstart{AlgoLine\thealgocfline.\theAlgoLine}\hyper@anchorend}%
%  }% now we can do the line numbering
  \strut\vadjust{\kern-\dp\strutbox\vtop to \dp\strutbox{%
      \baselineskip\dp\strutbox\vss\llap{\scriptsize{\nlSty{\theAlgoLine}\hskip\skiptotal}}\null}}%
}%

A Graph Layout Algorithm for GEF

Project Proposal for Google's Summer of Code 2006

GEF (Graph Editing Framework) is a library of Java classes for editing diagrams and graphs. It is used by ArgoUML for UML diagrams. For my SoC project I will implement a graph layout algorithm to automatically position the nodes and link bends of a graph in a way that is particularly suited to UML class diagrams.

The algorithm will be a combination of the well-known Sugiyama algorithm with some orthogonal drawing techniques. A UML class diagram has two main types of links - the inheritance relationships and the associations. The inheritance relationships form a hierarchical structure. In computing a layout I will use the Sugiyama algorithm to draw the classes involved in the inheritance relationships. The algorithm has four steps; it temporarily removes any directed cycles by reversing a small number of links, places the nodes on horizontal levels so that all links are directed similarly, permutes the nodes on each level to minimize the number of link crossings, and balances the layout. Then I will add in the remaining classes and the association links while preserving the basic structure. UML class diagrams have additional requirements that are not handled by generic graph layout algorithms, for example, the nodes do not have fixed size and the association links are labelled in a very particular manner. See [1] for a much more detailed description of the entire algorithm.

Contributions
My contributions will be:

• An implementation of the Sugiyama algorithm for drawing general directed graphs.
• A combination of this algorithm with some other additions specifically tailored for UML class diagrams (see [1]).
• A demo application.

An implementation of the Sugiyama algorithm with the additions described in [1] is a first-step to drawing UML class diagrams in ArgoUML. There are more advanced methods for the individual steps which may be looked at in the future. For example, it may be desirable to restrict the width of the drawing so that it 'fits' on a computer screen thus allowing a user to see everything by simply scrolling up and down.

References
[1] J. Seemann, Extending the Sugiyama Algorithm for Drawing UML Class Diagrams: Towards Automatic Layout of Object-Oriented Software Diagrams, Proceedings of Graph Drawing, 5th International Symposium, GD '97, Rome, Italy, September, 1997

Update: This was accepted :-)