more useful options PerlMonks

How to compare two undirected graphs?

 on Oct 18, 2010 at 07:03 UTC Need Help??

Anonymous Monk has asked for the wisdom of the Perl Monks concerning the following question:

Sort of a meta-question here.

I'm trying to come up with a simple algorithm for comparing the shape of two undirected graphs. Each node in the graph has a "name" (which is meaningless for this comparison), a property (called the "width and length ratio" but here has nothing to do with the structure of the graph, just that the nominally same node in the two compared graphs should have the same w/l ratio), and zero or more unordered child-nodes that the graph is connected to. There are well-defined "top" and "bottom" nodes, but the middle is a bit messier, as multiple nodes may connect to the same node.

Does anyone have an idea of what I could use as a ranking criterion here? Or better yet, if there were a module that could do this sort of calculation for me I would just be absolutely elated.

Replies are listed 'Best First'.
Re: How to compare two undirected graphs?
by LanX (Cardinal) on Oct 18, 2010 at 12:56 UTC

Comparing the "shape" sound like a isomorphism test. In this case be aware that the "graph isomorphism problem" is NP-complete.

Then you say your nodes are already named and have "children". General graphs have no children they have neighbours. So maybe you are speaking of trees or lattices (which have a bottom and a top element).

But names and other properties should simplify the comparison it can be easier to normalize both graph according those weights and consequently ordering the nodes.

This depends on the memory representation, e.g. when taking an incidence matrix of both graphs you can order rows and columns according to the associated weights (e.g. first row/column representing the "top node" and so on). Graphs with the same incidence matrix after permutation are isomorphic.

Of course this becomes more complicated when having a nontrivial automorphism group in large graphs which is the reason for the mentioned NP-completeness.

In short there is no general fast solution for arbitrary graphs when they get big, but "a number of important special cases of the graph isomorphism problem have efficient, polynomial-time solutions"

Cheers Rolf

Thank you, I didn't even know how to really properly describe the algorithm trouble I was having, but yes, I am trying to find the isomorphism between two undirected graphs. Apologies about my poor description of the data structure; let me try to give a little more information.

Essentially, what I'm trying to do is to see if two transistor schematics are identical. I have a large, several thousand device netlist that I'm trying to simplify by identifying structures (the majority of which are called "static gates", which are like NAND gates, XOR gates, etc) and then abstracting those away into a sub-component. I guess a conceptually similar way to think of the problem is if you were working on a several-thousand line procedural Perl script, and say you had some incredible code to identify bits of code that, say, "this bit reads in data from a file" or "this bit encodes a string", and you were able to pull out those chunks of code and replace them with a call to a function.

Now, I have code that can identify a group of devices as a static gate, but now I'd like now is to make sure that I don't have a dozen instantiations of, say, a dozen different 2-input NAND gates that are only separate because their outputs are named N1, N2, N3, etc. What I'd like is to be able to say, "Oh, these two static gates are both NAND gates, so I'm gonna throw out the second one and make sure they're both instantiations of the same gate."

I can separate each static gate into two halves, so that, say in a really easy case, the top half of one might look like this:

``` VDD
|
|------|
|      |
M1|      |
|    M3|
X      |
|      |
M2|      |
|      |
|------|
|
OUT

That is to say, the edges are the transistors themselves, and the vertices are the source/drain of the transistor. Unfortunately, although this looks like a tree shape, it actually isn't because two paths may be in parallel, e.g. that they would have the same parent and child nodes. The actual names of the edges and vertices don't actually matter to me, as they could be anything and arbitrary and certainly won't be the same - what does matter though is that the properties of all the edges (the W/L ratio) between two different gates match, and that the structure of two different gates match.

http://portal.acm.org/citation.cfm?id=803896

Although I'm not really sure if my structure qualifies as a planar graph. It still *feels* like there should be a simpler solution here... maybe if I treated my structure as directed rather than undirected it would help cut down on complexity?

Don't know much about transistor schematics.

So your talking about identifying isomorphic subgraphs which are only connected via two nodes (IN and OUT) to the rest of the graph?

As long as those subgraphs are not too big you can simply use a brute force normalization of the incidence matrix, i.e. trying all permutations until certain criterias are optimized.

Sorry anything else is IMHO far too complicated for perlmonks, this doesn't only fill bookshelves it fills international conferences.

Cheers Rolf

If your structures can be etched in a single layer onto the surface of a silicon wafer, it is almost certainly planer.

David.
Re: How to compare two undirected graphs?
by juampatronics (Initiate) on Oct 18, 2010 at 08:58 UTC

Your question is far too vague.

Go have a look at the Graph module. You can just define your own comparison by overloading the eq member of that class.

As for ranking nodes: you need to define a criteria first. Most likely you'll find what you need in that module.

Re: How to compare two undirected graphs?
by snape (Pilgrim) on Oct 18, 2010 at 08:22 UTC

I don't understand what do you mean by comparison here. DO you want to know how the nodes are connected then you may look into a module called Graph::Undirected.

It will let you know how the graphs are linked and accordingly you may use the something like hash of arrays where the vertex between 2 nodes as a key and array will the weights. I think then you may compare the graphs.

Re: How to compare two undirected graphs?
by ambrus (Abbot) on Oct 18, 2010 at 07:52 UTC

Can you define what exactly you mean by top and bottom nodes? For example, is it the case that there's a unique shortest path from the top node to any node? That, for example, would be a managable case.

Re: How to compare two undirected graphs?
by Herkum (Parson) on Oct 18, 2010 at 08:01 UTC

How do you define, "Compare"? Which nodes are there, which nodes are not? What about the order of nodes? Perhaps you should figure out what you need before you try to compare two graphs.

Re: How to compare two undirected graphs?
by zentara (Archbishop) on Oct 18, 2010 at 12:40 UTC
The first thing that comes to mind is do a "least squares fit" analysis of the data points. Google for "perl least square fits". A pattern may emerge in the least square data. A decent example is at cpan example of least squares

I'm not really a human, but I play one on earth.
Old Perl Programmer Haiku ................... flash japh
Re: How to compare two undirected graphs?
by sundialsvc4 (Abbot) on Oct 18, 2010 at 14:16 UTC

As others have said, you need to ponder what “shape” means to you.   Then, I suggest that you consider generating a simple list of (start_node, end_node) tuples.   Sort this list, thus placing the identical node-names conveniently next to one another, and count them.   Or, stuff the data into an SQLite database (file...) and let it do the dirty work for you.   (They are fast, they are “just files,” and yet you can query them.)

You might decide, for instance, that the “shape” of a node is defined by the number of nodes that connect to or from it.   You might calculate the “depth” of each node and then count the number of connections at the same depth.   Or, whatever you decide is right for you.

Create A New User
Node Status?
node history
Node Type: perlquestion [id://865880]
Approved by Corion
Front-paged by Corion
help
Chatterbox?
and the web crawler heard nothing...

How do I use this? | Other CB clients
Other Users?
Others taking refuge in the Monastery: (7)
As of 2021-01-18 12:57 GMT
Sections?
Information?
Find Nodes?
Leftovers?
Voting Booth?
The STEM quote I most wish I'd made is:

Results (179 votes). Check out past polls.

Notices?