Unblogging

Google Reader is more than just a feed reader. It's a cache and an archive: http://www.google.com/reader/atom/feed/FEED_URL?r=n&n=X displays the last X posts from FEED_URL even if FEED_URL itself does not contain all of its last X posts. If the author of FEED_URL deletes an old post it will not be removed from the cache. This is nothing strange, caching and archiving are part and parcel of the Internet.

However, there are a number of issues with this type of caching. Firstly, many authors try a number of "test" posts after creating a blog. If they check the posts in Google Reader, they become difficult to delete. Secondly, there is no indication when browsing Google Reader that a post may have been deleted and that the author no longer wishes the post to be public. Thirdly, there is no robots.txt mechanism to restrict caching. Fourthly, Google does not delete posts from the cache by request.

In Google's own words: "Reader caches all entries in your feed as your feed most likely only contains your most recent entries. Unfortunately, there isn't a way for Reader to tell which items have been deliberately removed from your site as opposed to having just fallen off the end of your feed. You can create a blank item with the same GUID tag as the original item to at least remove the content from Reader and other feed readers. Contact your blogging software provider for more help with this issue."

So, how do you find the GUIDs of your deleted posts? Assuming you have a Google Account and an account with Blogger, the following Ruby script will output the GUIDs of your deleted posts:



Next, you need to edit the contents of each post using http://www.blogger.com/post-edit.g?blogID=12345&postID=67890. You may also have to bring the post dates forward so that Google Reader will notice the changes.

Irish Discussion Trends

Inspired by an analysis of computer science research trends, I wrote a simple application using Adobe Flex and Apache Lucene to analyze trends on the Irish discussion website boards.ie from 1998 to mid-2008. For example, computing only term frequencies within posts, one can observe the rise and fall of Ireland's mobile phone networks:





Please note that the 2008 dataset is incomplete, and so the results trail off for this year.

It's Not a Feature, It's a Bug

The Flex compiler (mxmlc) has the following feature: It will only include classes in the output swf that are explicitly referenced either within the .mxml files or any explicitly referenced .as files. There is a request for a compiler option to support the inclusion of all classes, but it's still in the works.

The following is one such example where this feature causes difficulties. Suppose I have a Flex client that uses BlazeDS to make an RPC. The RPC returns a Java object that is explicitly mapped to an ActionScript object using [RemoteClass(alias="...")] above the definition of the ActionScript class. This ActionScript class may never be referenced within the Flex code yet is needed to de-serialize the response! The end result is an "Server.Acknowledge.Failed" fault code:

[RPC Fault faultString="Didn't receive an acknowledge message"
faultCode="Server.Acknowledge.Failed" faultDetail="Was expecting
mx.messaging.messages.AcknowledgeMessage, but received null"]

Duplex Printing with the Lexmark T640 and Mac OS X 10.4 (Tiger)

Mac OS X 10.4 includes a driver for the Lexmark T640. However, even with the duplex option installed (System Preferences > Print & Fax > [printer name] > Printer Setup > Installable Options) and either "long-edged binding" or "short-edged binding" selected (Print > Layout), pages come out one-sided! The "Generic PostScript Printer" driver doesn't appear to support duplex printing either.

As a work around, you can install Gutenprint and Gimp-Print for Mac OS X and use, for example, the "Generic PCL 6/PCL XL Printer - CUPS+Gutenprint v5.2.3" driver.

Is One More Powerful Than We Think?

The Power of One is an initiative by the Department of Communications, Energy and Natural Resources to promote energy efficiency in Ireland. One of their TV ads, centered around the Heffernan Family, appears to have the following logic:

• The Heffernans reduce their energy consumption by, for example, switching their thermostat setting from 23 to 21 degrees.
  
• Through these efforts they save €320 annually on their heating costs.
  
• They save this money in their "holiday fund" allowing the five of them, in the closing scene, to head off into the sun with their surfboards and bags packed.
  

Any problem here? Does saving €320 on annual heating costs, only to spend it on a foreign holiday (I presume that's what the sun represents), make sense? Suppose they travel by air? Technically, it promotes energy efficiency in Ireland, but does it increase energy use somewhere else?



Did I mention Jevons Paradox? As we increase the efficiency with which we use a resource (through technological progress), we increase (rather than decrease) the rate of consumption of that resource. We are dealing with something similar here. If the Heffernans improve the efficiency with which they can heat their home, they may actually use the savings to consume more energy elsewhere. What's worse, the ad appears to promote this.

I will say that the paradox is not universally accepted. The general argument against it is that, in a mature market, the savings made will be greater than the amount used due to the rebound effect. However, I think the ad's advice is counter to this argument.

The 'Branches/Tags/Trunk' Convention

Q. I have several projects under Subversion which do not adhere to the branches/tags/trunk convention. How do I move to this convention?

A. Check out each project and 'cd' to the local copy. Then:

mkdir branches tags trunk; svn add branches tags trunk
ls -A | egrep -v '\.svn|branches|tags|trunk' | xargs -I X svn move X trunk
svn commit -m "Moved to the 'branches/tags/trunk' convention."

Europa to Ganymede

I recently upgraded my version of Eclipse from Europa (v3.3) to Ganymede (v3.4) on Mac OS X. I wanted to install the following plug-ins: Subclipse (for Subversion), M2Eclipse (for Maven), WTP (for various editors, e.g. XML, XSD, etc.), and PDT (for PHP).

First up, Subclipse. I added the update site and installed it without a hitch. Eclipse required a restart; an annoyance I was hoping Ganymede would have fixed.

On to M2Eclipse. I added the update site, tried an install and got the following cryptic error messages:

Unsatisfied dependency: [org.maven.ide.eclipse.ajdt.feature.feature.group
0.9.5.20080717-1821] requiredCapability:
org.eclipse.equinox.p2.iu/org.eclipse.ajdt.core/0.0.0
Unsatisfied dependency: [org.eclipse.jst.common.frameworks 1.1.102.v200709122200]
requiredCapability: osgi.bundle/org.eclipse.emf.ecore.xmi/[2.2.0,2.4.0)
... snip (many more lines of similar error messages) ...

After some Googling, I found out that M2Eclipse requires that the AspectJ Development Tools (AJDT) and the Web Tools Platform (WTP) are installed first. I added the AJDT update site and installed it with one peculiarity. Prior to the install, Eclipse complained that the http://md.pp.ru/~eu/12 website was unavailable. This website belongs to a Eugene Kuleshov, a developer who is interested in, amongst other things, AspectJ. Perhaps he is an AJDT developer. Anyhow, the warning did not prevent the install from completing successfully. I added the WTP update site and it (eventually) installed. I returned to M2Eclipse and it installed correctly.

Finally, the PDT. I added the update site, tried an install, and got another error message:

Cannot find a solution satisfying the following requirements Match[requiredCapability:
org.eclipse.equinox.p2.iu/org.eclipse.wst.web_ui.feature.feature.group
/[3.0.1.v200807220139-7R0ELZE8Ks-y8HYiQrw5ftEC3UBF,3.0.1.v200807220139-7R0ELZE8Ks-
y8HYiQrw5ftEC3UBF]].

I have had problems with this plug-in before when using Europa. I followed the instructions on the PDT website, but to no avail. Three out of four plug-ins will have to suffice for now :-( Maybe Eclipse v3.5 will have an smoother plug-in system.

MIT's Simile Timeline

MIT's Simile Timeline is a DHTML-based AJAX widget for visualizing temporal information. Here it is trying to visualize my travel.xml data (where I've been):

Unfortunately, this won't display correctly in an RSS reader. The file timeline-api.js must (annoyingly) be included within the 'head' tags of a HTML page. So, I modified Blogger's template and my own mirror. However, you will also notice that Blogger fails to load travel.xml (the timeline is empty), whereas my mirror, which is on the same server as travel.xml and simply gets its feed from Blogger, loads it correctly. Ugh!

CiteSeer's Dataset

I am exploring the citation and co-authorship graphs of the documents (and contexts) indexed by CiteSeer. However, parsing their index has proved tricky. The good news is that CiteSeer provides an OAI-PMH compliant dump of their index. I downloaded and unzipped the index as follows:

$ wget http://cs1.ist.psu.edu/public/oai/oai_citeseer.tar.gz
$ tar -zxf oai_citeseer.tar.gz

The file is based on the Dublin Core standard with additional metadata fields, including citation relationships (References and IsReferencedBy), author affiliations, and author addresses. The index is split into many 'dump' files with no root XML tag. So:

$ echo "<records>" `cat oai_citeseer/*` "</records>" > cs.xml

The file is quite big: approximately 1.9GB with over 36 million lines. The bad news is that:

$ xmllint --stream cs.xml

cs.xml:92025: parser error : attributes construct error
 <oai_citeseer:author name="L. "j. Svensson">

The XML is not well-formed. I tried some quick repairs with sed:

$ sed -e 's/L\.\ \"j\.\ Svensson/L\.\ J\.\ Svensson/g' cs.xml > csX.xml; mv csX.xml cs.xml
$ xmllint --stream cs.xml

cs.xml:168403: parser error : internal error
 <dc:title>Imagining CLP(^,= alpheta )</dc:title>

There also appears to be unprintable characters in the file. A post from the Xalan mailing list provides a solution:

$ java XMLFix cs.xml > csX.xml; mv csX.xml cs.xml
$ xmllint --stream cs.xml

cs.xml:418791: parser error : attributes construct error
 <oai_citeseer:author name="Nitin "nick Sawhney">

A recurring problem concerns people who parenthesize some part of their name, e.g. Nitin "Nick" Sawhney's. To fix these errors in the name attribute of the oai_citeseer:author tag:

$ sed -e 's/\(name\=\"[^\"]*\)\"\([^\"]*\"\>\)/\1\2/g' cs.xml > csX.xml; mv csX.xml cs.xml
$ sed -e 's/\(name\=\"[^\"]*\)\"\([^\"]*\)\"\([^\"]*\"\>\)/\1\2\3/g' cs.xml > csX.xml; mv csX.xml cs.xml
$ xmllint --stream cs.xml

cs.xml:25857443: parser error : attributes construct error
 <oai_citeseer:author name="Kai Voy"""zy Massachusettsiassachu">

I manually edit this line with vim, and I'm done! I have a well-formed XML file.

JavaScript: 1997 vs 2008

After buying a very early issue of .net Magazine (1997?) that included the latest versions of both Internet Explorer (4.0?) and Netscape Navigator (4.0?) on a bonus CD, I wrote my very first lines of JavaScript. As far as I can remember, my script allowed a hyperlink to show/hide a block of text within the same page. The CD included many other DHTML examples, some of which needed separate code for the two browsers.

Recently, I've been using JavaScript to write something a little more complicated and I've been watching Douglas Crockford et al.'s JavaScript videos (JavaScript, The Theory of the DOM, Advanced JavaScript, Browser Wars, Quality, The Good Parts, The State of Ajax) to bring me up-to-date. JavaScript has changed alot: first-class functions, prototype-based inheritance, closures, variadic functions, etc. I have some catching up to do :-(

More hyperref woes

Following on from my last post on hyperref and algorithm2e, I have ran into difficulties with hyperref links and page breaks. Suppose I process the following with pdflatex:

\documentclass[11pt,english]{article}
\usepackage{hyperref}

\begin{document}
This is the top of the page!

\vspace{18cm}

This is the bottom of the page! Blah blah blah blah \url{http://www.martinharrigan.ie}?
\end{document}

Then I get:



It looks like the header has become a link as well! With natbib links, the page number is also active. My quick fix is to avoid page breaks in the middle of links altogether by using \clubpenalty:

\documentclass[11pt,english]{article}
\usepackage{hyperref}

\begin{document}
This is the top of the page!!

\vspace{17cm}

This is the bottom of the page! Blah blah blah blah blah blah blah blah blah blah
blah blah blah blah blah blah blah blah blah blah blah blah blah blah blah blah
blah blah blah blah blah blah blah blah blah blah blah blah blah blah blah blah
blah blah blah blah blah blah blah blah blah blah \clubpenalty10000\url{http://www.martinharrigan.ie}?
\end{document}

And then all is well in the world again:



By the way, the hopeful-sounding 'breaklinks' option of the hyperref package doesn't fix the problem.

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