[XSL-LIST Mailing List Archive Home] [By Thread] [By Date]

Re: [xsl] graph-traversal query

---

---

Has been done a year ago and is not difficult to do in XSLT, See for example:

     http://lists.xml.org/archives/xml-dev/200401/msg00444.html


Since then I have successfully developed other, more complex
graph-theory algorithms like Eulerisation used in a "Chinese
Postman"-like (The New York Street Sweeeper) algorithm.



Cheers,
Dimitre,


On Fri, 28 Jan 2005 12:15:33 -0500, Wendell Piez
<wapiez@xxxxxxxxxxxxxxxx> wrote:
> I've never solved the graph-traversal problem myself (that I can recall
> ;-), though I know others on this list have.
> 
> I'd be interested in hints that would suggest how:
> 
>   This could be implemented recursively, traversing (either 'up' or 'down')
>   until terminal nodes are found;
> 
>   Circular references would be detected (passing a set of 'already hit'
> nodes as a
>   parameter?).
> 
> Cheers,
> Wendell
> 
> At 10:25 AM 1/28/2005, Mike wrote:
> >Ignoring the stuff about case-independence, define a key on the identifier
> >
> ><xsl:key name="k" match="DEFCONCEPT" use="@name"/>
> >
> >Find the logical parent using the key function:
> >
> >key("k", PARENT/CONCEPT/@name)
> >
> >or the grandparent by doing it twice:
> >
> >key("k", PARENT/CONCEPT/@name) / key("k", PARENT/CONCEPT/@name)
> >
> >That's XPath 2.0, in 1.0 you write
> >
> >key("k", key("k", PARENT/CONCEPT/@name)/PARENT/CONCEPT/@name)
> >
> >Since your data (unusually) represents relationships in both directions, you
> >can also use the key to find the children
> >
> >key("k", CHILD/CONCEPT/@name)
> >
> >or grandchildren:
> >
> >key("k", CHILD/CONCEPT/@name) / key("k", CHILD/CONCEPT/@name)
> >
> >Michael Kay
> >http://www.saxonica.com/
> >
> >
> > > -----Original Message-----
> > > From: RQamar [mailto:qamar_rahil@xxxxxxxxxxx]
> > > Sent: 28 January 2005 14:27
> > > To: xsl-list@xxxxxxxxxxxxxxxxxxxxxx
> > > Subject: [xsl] graph-traversal query
> > >
> > > Hi
> > >
> > > This is a question I asked earlier on the forum and was advised by
> > > Wendell to send it as a seperate query so I could get feedback from a
> > > wider audience.
> > >
> > > I'm educating myself on XSLT and XPath but until the two books Ive
> > > recently ordered arrive, I'd need some help from the experts
> > > to help me
> > > proceed.
> > >
> > > My query is thus:
> > >
> > > > Im finding the dynamic assigning and traversing process in
> > > XSL quite
> > > > confusing. Is there a logical way of  traversing through a tree to
> > > > determine the grandchild of an element albeit indirectly. So I know
> > > > that my XML file is as below
> > > >
> > > > -----------------------
> > > > <DEFCONCEPT id="10180" name="Car">
> > > >        <PARENT>
> > > >            <CONCEPT name="Automobile" ref="10181"/>
> > > >        </PARENT>
> > > >        <CHILD>
> > > >            <CONCEPT name="Toyota" ref="10235"/>
> > > >        </CHILD>
> > > > </DEFCONCEPT >
> > > > <DEFCONCEPT id="10235" name="Toyota">
> > > >        <PARENT>
> > > >            <CONCEPT name="Car" ref="10180"/>
> > > >        </PARENT>
> > > >        <CHILD>
> > > >            <CONCEPT name="Corolla" ref="10279"/>
> > > >        </CHILD>
> > > > </DEFCONCEPT >
> > > > <DEFCONCEPT id="10279" name="Corolla">
> > > >        <PARENT>
> > > >            <CONCEPT name="Toyota" ref="10235"/>
> > > >        </PARENT>
> > > > </DEFCONCEPT >
> > > > -----------------------
> > > > and I want to reach the <DEFCONCEPT name="Corolla"> from the node
> > > > <DEFCONCEPT name="Car"> because I have a query to determine the
> > > > existence of a kind_of  Car 'Corolla' irrespective of the
> > > case (upper
> > > > or lower) in which it has been written and where in the
> > > hierarchy it
> > > > exists. How will it be possible using XSLT?
> > >
> > >
> > > Thanks
> > > Rahil
> 
> 
> ======================================================================
> Wendell Piez                            mailto:wapiez@xxxxxxxxxxxxxxxx
> Mulberry Technologies, Inc.                http://www.mulberrytech.com
> 17 West Jefferson Street                    Direct Phone: 301/315-9635
> Suite 207                                          Phone: 301/315-9631
> Rockville, MD  20850                                 Fax: 301/315-8285
> ----------------------------------------------------------------------
>   Mulberry Technologies: A Consultancy Specializing in SGML and XML
> ======================================================================

---