Saturday, October 25, 2008

Efficient “Disjoint Sets” Implementation in XSLT

I actually had to revisit this problem with slightly different input, and once again I struggled. If I represent an undirected graph like this:

<?xml version="1.0"?>
<graph>
    <nodes>
        <node id="1"/>
        <node id="2"/>
        <node id="3"/>
        <node id="4"/>
        <node id="5"/>
    </nodes>
    <links>
        <link end1="1" end2="2"/>
        <link end1="1" end2="3"/>
        <link end1="1" end2="4"/>
        <link end1="1" end2="5"/>
    </links>
</graph>

…then it's a little harder to go from one node to its connected nodes, because the information I need is elsewhere in the XML document (i.e. not in a child node of the <node> element) . To index any node element, I'd have to navigate up the tree, and back down to the links. What's worse, I'd have to scan all the links for every node. So the solution involves some indirection. First I declare these two mappings:

<xsl:key name="left" match="/graph/links/link" use="@end1"/>
<xsl:key name="right" match="/graph/links/link" use="@end2"/>


 

Now I map each node (its ID, actually; remember that the key has to be of an atomic type) to its connected nodes by going through these mappings (such a recursive definition is not possible in XSLT 1.0, I believe). Note that for links that were indexed by @end1, I'm interested in the value of @end2, and v.v.


<xsl:key name="connected" match="node" use="key('left', @id)/@end2, key('right', @id)/@end1"/>


 

Finally, I can use this mapping:


 

<xsl:template match="/">
        <connectivity>
            <xsl:for-each select="graph/nodes/node">
                <node id="{@id}">
                    <connected-to>
                        <xsl:value-of select="key('connected', @id)/@id"/>
                    </connected-to>
                </node>
            </xsl:for-each>
        </connectivity>
    </xsl:template>


 

I believe that these are all the data structures I need. Now I can implement the "strongly connected components" algorithm as I did below, but using set operators on the nodes.

8 comments:

Anonymous said...

I every time spent my half an hour to read this webpage's content all the time along with a mug of coffee.
Feel free to visit my web page topografía

Anonymous said...

Everyone loves it when people get together and share thoughts.
Great website, continue the good work!
Here is my page - Instalación geotermia en Ciudad Real

Anonymous said...



Heгe is my web pagе ... payday loan,
my site - payday loan,

Anonymous said...



Here is mу page ... payday loans
Take a look at my web-site : payday loans

Anonymous said...

Online Payday Loan Olympic Bid 65 Online MBA Programs With Online Payday
Loan pass oneconomical stimulus sell Make Books - incur Immediate
payday loans Online
Advancebankruptcy jeopardy betray Timeshare For disembarrass STRATEGIES Payday Loanier's Checks AreRabbit warren Cuddles Up To $5000 3 Reasons To recycle Gadgetsdisplace Globally With Reloadable Debit ATM Identity card wandering hairdressing defraymentassume Fund When Problems Exist Interactive: 2012 Campaign television cubicle
my site: payday loans

Anonymous said...

http://www.cafb29b24.org/docs/buyativan/#36489 lorazepam online pharmacy - ativan 2 mg vs xanax

Anonymous said...

Hi, I do believe this is an excellent blog. I stumbledupon it ;) I
will come back once again since i have bookmarked it.
Money and freedom is the greatest way to change, may you be rich and continue to help others.


Look at my page ... costs of dental implants

Anonymous said...

Good day! Do you know if they make any plugins to safeguard
against hackers? I'm kinda paranoid about losing everything I've worked hard on.
Any tips?

Feel free to visit my site ... pba dental