Beefy Boxes and Bandwidth Generously Provided by pair Networks
We don't bite newbies here... much

Comment on

( #3333=superdoc: print w/replies, xml ) Need Help??

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.

Through your help on the wikipedia page, I was able to find this paper:

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?

In reply to Re^2: How to compare two undirected graphs? by Anonymous Monk
in thread How to compare two undirected graphs? by Anonymous Monk

Use:  <p> text here (a paragraph) </p>
and:  <code> code here </code>
to format your post; it's "PerlMonks-approved HTML":

  • Posts are HTML formatted. Put <p> </p> tags around your paragraphs. Put <code> </code> tags around your code and data!
  • Titles consisting of a single word are discouraged, and in most cases are disallowed outright.
  • Read Where should I post X? if you're not absolutely sure you're posting in the right place.
  • Please read these before you post! —
  • Posts may use any of the Perl Monks Approved HTML tags:
    a, abbr, b, big, blockquote, br, caption, center, col, colgroup, dd, del, div, dl, dt, em, font, h1, h2, h3, h4, h5, h6, hr, i, ins, li, ol, p, pre, readmore, small, span, spoiler, strike, strong, sub, sup, table, tbody, td, tfoot, th, thead, tr, tt, u, ul, wbr
  • You may need to use entities for some characters, as follows. (Exception: Within code tags, you can put the characters literally.)
            For:     Use:
    & &amp;
    < &lt;
    > &gt;
    [ &#91;
    ] &#93;
  • Link using PerlMonks shortcuts! What shortcuts can I use for linking?
  • See Writeup Formatting Tips and other pages linked from there for more info.
  • Log In?

    What's my password?
    Create A New User
    and all is quiet...

    How do I use this? | Other CB clients
    Other Users?
    Others scrutinizing the Monastery: (5)
    As of 2018-08-20 02:37 GMT
    Find Nodes?
      Voting Booth?
      Asked to put a square peg in a round hole, I would:

      Results (190 votes). Check out past polls.