Re: Counting items related by a linked list

This is a graph problem.

Recently I did some work on graphs and am able to help.

The template isPath returns 1 if there is a path from at least one of the
"From" vertices to the "To" vertex.

 <xsl:stylesheet version="1.0"
 xmlns:xsl="http://www.w3.org/1999/XSL/Transform">

   <xsl:key name="kEdgeBySource" match="edge"
            use="@source"/>



<!--
    The following template checks if there is a path
    from at least one of the "From" vertices
    to the "To" vertex
-->
  <xsl:template name="isPath">
    <xsl:param name="pNodes" select="/.."/>
    <xsl:param name="pEdges" select="/.."/>
    <xsl:param name="pFromNodes" select="''"/>
    <xsl:param name="pidTo" select="''"/>
    <xsl:param name="pExcluded" select="/.."/>

    <xsl:if test="$pFromNodes">
      <xsl:choose>
        <xsl:when test="$pFromNodes[2]">
          <xsl:variable name="vFound">
            <xsl:call-template name="isPath">
              <xsl:with-param name="pNodes" select="$pNodes"/>
              <xsl:with-param name="pEdges" select="$pEdges"/>
              <xsl:with-param name="pidTo" select="$pidTo"/>
              <xsl:with-param name="pFromNodes"
                              select="$pFromNodes[1]"/>
              <xsl:with-param name="pExcluded"
                              select="$pExcluded"/>
            </xsl:call-template>
          </xsl:variable>

          <xsl:choose>
            <xsl:when test="string($vFound)">1</xsl:when>

            <xsl:otherwise>
              <xsl:call-template name="isPath">
                <xsl:with-param name="pNodes"
                                select="$pNodes"/>
                <xsl:with-param name="pEdges"
                     select="$pEdges"/>
                <xsl:with-param name="pidTo"
                     select="$pidTo"/>
                <xsl:with-param name="pFromNodes"
                     select="$pFromNodes[position() > 1]"/>
                <xsl:with-param name="pExcluded"
                     select="$pExcluded | $pFromNodes[1]"/>

              </xsl:call-template>
            </xsl:otherwise>
          </xsl:choose>
        </xsl:when>
        <!-- pFromNodes is just one vertex -->
        <xsl:otherwise>
          <xsl:for-each select="$pEdges/..">
            <xsl:variable name="vOutEdges"
             select="key('kEdgeBySource',
                          $pFromNodes[1]/@id)"/>
            <xsl:choose>
              <xsl:when test="$vOutEdges[@target = $pidTo]">1</xsl:when>
              <xsl:otherwise>
                <xsl:call-template name="isPath">
                  <xsl:with-param name="pNodes"
                                  select="$pNodes"/>
                  <xsl:with-param name="pEdges"
                                  select="$pEdges"/>
                  <xsl:with-param name="pFromNodes"
                 select="$pNodes[@id = $vOutEdges/@target
                                and
                                 not(@id = $pExcluded/@id)
                                 ]"/>
                  <xsl:with-param name="pidTo" select="$pidTo"/>
                  <xsl:with-param name="pExcluded"
                   select="$pExcluded | $pFromNodes[1]"/>
                </xsl:call-template>
              </xsl:otherwise>
            </xsl:choose>
          </xsl:for-each>
        </xsl:otherwise>
      </xsl:choose>

    </xsl:if>

  </xsl:template>

</xsl:stylesheet>


Here's a test for the isPath template. It tests if there's a path between
v7
and v6 and produces the correct result 1.

<xsl:stylesheet version="1.0"
 xmlns:xsl="http://www.w3.org/1999/XSL/Transform"
 xmlns:vendor="urn:schemas-microsoft-com:xslt"
 xmlns:msxsl="http://exslt.org/common"
 exclude-result-prefixes="vendor msxsl"
 >
 <xsl:import href="isPath.xsl"/>

 <xsl:variable name="vVertices">
   <node id ="v1"/>
   <node id ="v2"/>
   <node id ="v3"/>
   <node id ="v4"/>
   <node id ="v5"/>
   <node id ="v6"/>
   <node id ="v7"/>
 </xsl:variable>

 <xsl:variable name="vEdges">
   <edge id="e1" source="v1" target="v2" />
   <edge id="e2" source="v2" target="v3" />
   <edge id="e3" source="v3" target="v4" />
   <edge id="e4" source="v4" target="v5" />
   <edge id="e5" source="v5" target="v2" />
   <edge id="e6" source="v5" target="v6" />
   <edge id="e7" source="v6" target="v1" />
   <edge id="e8" source="v7" target="v5" />
   <edge id="e9" source="v7" target="v2" />
 </xsl:variable>

 <xsl:output omit-xml-declaration="yes" indent="yes"/>

  <xsl:template match="/">
    <xsl:call-template name="isPath">
     <xsl:with-param name="pNodes"
          select="vendor:node-set($vVertices)/*"/>
     <xsl:with-param name="pEdges"
          select="vendor:node-set($vEdges)/*"/>
     <xsl:with-param name="pFromNodes"
          select="vendor:node-set($vVertices)/*[@id = 'v7']"/>
     <xsl:with-param name="pidTo" select="'v6'"/>
    </xsl:call-template>
  </xsl:template>
</xsl:stylesheet>

You can directly use the isPath template, calling it for every "AItem"
element and then summing the result. The successful work of isPath doesn't
require your conditions 3. and 4.


Cheers,

Dimitre Novatchev,
FXSL developer,

http://fxsl.sourceforge.net/ -- the home of FXSL
Resume: http://fxsl.sf.net/DNovatchev/Resume/Res.html


"Joe K" <anotherquestion@xxxxxxxxxxx> wrote in message
news:BAY8-F106SV2bltjl6D00017564@xxxxxxxxxxxxxx
> I have the following type of xml document:
> Note:
> 1) All IDs are unique and can be any positive number
> 2) The link pairs below can link any item to any different Item.
> 3) CItems are always in the "Target" portion of the link table.
> 4) No item can be linked more than once to another item.
>
> The question:  I would like to define a variable such that given the
CItem
> ID, say 1003, I can get a count of all the AItems linked to it.
>
> <TopLevel>
>
> <AItem>
>    <ID=1/>
>    <Name=./>
> </AItem>
> <AItem>
>    <ID=2/>
>    <Name=./>
> </AItem>
> <AItem>
>    <ID=3/>
>    <Name=./>
> </AItem>
> <AItem>
>    <ID=4/>
>    <Name=./>
> </AItem>
> <AItem>
>    <ID=5/>
>    <Name=./>
> </AItem>
>
> <BItem>
>    <ID=101/>
>    <Name=./>
> </BItem>
> <BItem>
>    <ID=102/>
>    <Name=./>
> </BItem>
> <BItem>
>    <ID=103/>
>    <Name=./>
> </BItem>
> <BItem>
>    <ID=104/>
>    <Name=./>
> </BItem>
> <BItem>
>    <ID=105/>
>    <Name=./>
> </BItem>
> <BItem>
>    <ID=106/>
>    <Name=./>
> </BItem>
>
> <CItem>
>    <ID=1001/>
>    <Name=./>
> </CItem>
> <CItem>
>    <ID=1002/>
>    <Name=./>
> </CItem>
> <CItem>
>    <ID=1003/>
>    <Name=./>
> </CItem>
> <CItem>
>    <ID=1004/>
>    <Name=./>
> </CItem>
> <CItem>
>    <ID=1005/>
>    <Name=./>
> </CItem>
> <CItem>
>    <ID=1006/>
>    <Name=./>
> </CItem>
> <CItem>
>    <ID=1007/>
>    <Name=./>
> </CItem>
>
>
> <LinkItem>
>    <SourceID>4</SourceID>
>    <TargetID>1003</TargetID>
> </LinkItem>
> <LinkItem>
>    <SourceID>6</SourceID>
>    <TargetID>1003</TargetID>
> </LinkItem>
> <LinkItem>
>    <SourceID>105</SourceID>
>    <TargetID>1002</TargetID>
> </LinkItem>
> <LinkItem>
>    <SourceID>3</SourceID>
>    <TargetID>101</TargetID>
> </LinkItem>
> <LinkItem>
>    <SourceID>4</SourceID>
>    <TargetID>1003</TargetID>
> </LinkItem>
> <LinkItem>
>    <SourceID>102</SourceID>
>    <TargetID>1</TargetID>
> </LinkItem>
> <LinkItem>
>    <SourceID>101</SourceID>
>    <TargetID>1003</TargetID>
> </LinkItem>
>
> </TopLevel>
>
> _________________________________________________________________
> Get rid of annoying pop-up ads with the new MSN Toolbar - FREE!
> http://clk.atdmt.com/AVE/go/onm00200414ave/direct/01/
>
>



__________________________________
Do you Yahoo!?
Yahoo! Finance Tax Center - File online. File on time.
http://taxes.yahoo.com/filing.html