Java Library with subgraph isomorphism problem support?

Question

I'm trying to analyze the usage of "#include" in C files (what is included first, dependencies...).

To do so, I extract from a C file the "#include" and I'm building a graph. I would like to identify common patterns in this graph...

So far, I'm using JGraphT as the graph engine (not sure this is the correct expression) and JGraph for the rendering (however using jgraph is a bit problematic since the Layouts are no longer included in the free release).

I've been unable to find any isomorphism support in jgrapht. Do you know any solution providing this kind of support (something like igraph but for java)..?

I'm using java 1.5 and the proposed solution must be free...

Answer 1

Have you looked at Parsemis?

It's a Java graph mining library, and (sub)graph isomorphism is fundamental to this process, so my guess is that they're solving this issue somehow.

Not sure about the license though, but I believe it's open source as it was developed for academic reasons.

Answer 2

Not sure one of them can do isomorphism but I've collected a couple of links to graph layout engines in my blog: http://blog.pdark.de/2009/02/11/graph-layout-in-java/

You might want to look at graphviz, too. It's not Java but has a very powerful layout engine.

As for isomorphism: You probably only need to check for patterns at level 0 (i.e. the direct includes) because anything below that must be isomorphic by definition (all files included by some include file will always be the same unless someone used a lot of #if magic in the includes section).

Answer 3

I've been pondering this problem myself lately (looking for common markup structures to factor out of JSPs into tags, in my case).

A library for this would be great. I haven't found one yet. In the meantime, here are a couple of problems that may be related to yours (isomorphically?).

• I was planning to research the technique mathematical software uses to analytically evaluate integrals in calculus problems. In this case, there are a bunch of known structural patterns, and the problem in question has to be matched to one of the known patterns. The best way to do this is not always obvious because it depends on what terms are grouped together, etc.

• Algorithms used in biology to find corresponding structures in two complex molecules might also be adapted to this problem.

Answer 4

I sure don't know of a particular graph library with subgraph isomorphism code — since it's known NP-complete, you can't do a lot other than search anyway. It shows up a lot in graph rewriting schemes, so AGG might help.

Answer 5

Looks like there was a mention of isomorphism in the "experimental" package of JGraphT a few months back, but apparently no documentation.

Isomorphism comparison is a fundamental requirement in cheminformatics software (technically it's monomorphism that's used). Atoms are "nodes" and bonds are "edges". Molecular graphs are undirected and can be cyclic. A few open source cheminformatics libraries written in Java are available. You might be able to find some clues for solving your problem by looking at these libraries.

For example, I've written a BSD-licensed cheminformatics library called MX that implements a monomorphism algorithm based on VF. I wrote a high-level overview of how the algorithm was implemented, and you can browse the source for the mapping package in my GitHub repository. Most of the work is done in the DefaultState class.

MX also includes a fast exhaustive ring detector and other graph manipulations that might be applicable to your problem.