Re: Network diagram - node set intersection

<cknell@xxxxxxxxxx> wrote in message
news:B0018919762@xxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxx
> ==========> Direction of graph
> ______
>             |        |
>           / |__B__|
> ______/           \_____
> |        |           |        |
> |__A__|           |__D__|
>           \            /
>            \ ______/
>            |        |
>            |__C__|
>
> I'm working on producing a network diagram in SVG by processing an XML
document with XSLT. Above is a symbolic representation of the output. The
relationship between nodes in the graph can't be represented directly in XML
because it isn't a tree (Node D has two parents which isn't allowed in XML).
>
> Here is a simplified sample of the XML document:
> <network>
>   <node>
>     <node-id>A</node-id>
>     <predecessor-id></predecessor-id>
>     <successor-id>B</successor-id>
>   </node>
>   <node>
>     <node-id>B</node-id>
>     <predecessor-id>A</predecessor-id>
>     <successor-id>D</successor-id>
>   </node>
>   <node>
>     <node-id>C</node-id>
>     <predecessor-id>A</predecessor-id>
>     <successor-id>D</successor-id>
>   </node>
>   <node>
>     <node-id>D</node-id>
>     <predecessor-id>B</predecessor-id>
>     <predecessor-id>C</predecessor-id>
>     <successor-id></successor-id>
>   </node>
> </network>
>
> In my stylesheet I have a template that matches <node>. For the purpose of
positioning the SVG elements I want to determine how many other nodes have a
<predecessor-id> that matches one of the <predecessor-id> children of the
context <node>. In addition to determining how many "siblings" a <node> has,
I also want to know where the context node is in document order relation to
these "siblings".
>
> The <node> elements with common <predecessor-id> values would be, in the
context of the network diagram, "siblings". Of course in the XML document
all the <node> elements are siblings in the XPath sense.
>
> To determine the number of siblings a <node> element has, I thought I
would count the elements in the intersection of the set of <predecessor-id>
children of the context node with the set of <predecessor-id> children of
all the other <node> elements. I modelled the expression on the example
shown on page 425 of the XSLT Programmer's Reference 2nd Edition.
>
> Here is a simplfied stylesheet:
>
> <?xml version="1.0" encoding="UTF-8" ?>
> <xsl:stylesheet version="1.0"
xmlns:xsl="http://www.w3.org/1999/XSL/Transform">
>   <xsl:output method="xml" indent="yes" encoding="UTF-8" />
>
>   <xsl:template match="/">
>     <xsl:apply-templates />
>   </xsl:template>
>
>   <xsl:template match="network">
>     <xsl:apply-templates />
>   </xsl:template>
>
>   <xsl:template match="node">
>     <xsl:variable name="this-node-id" select="node-id" />
>     <xsl:variable name="this-predecessor-nodes" select="predecessor-id" />
>     <xsl:variable name="other-predecessor-nodes"
select="/network/node[node-id != $this-node-id]" />
>     <xsl:variable name="sibling-cnt"
select="count($this-predecessor-nodes[count(. | $other-predecessor-nodes) !=
count($other-predecessor-nodes)])" />
>
>     This node id = <xsl:value-of select="$this-node-id" />
>     Sibling count = <xsl:value-of select="$sibling-cnt" />
>   </xsl:template>
>
> </xsl:stylesheet>
>
> This yielded the following output:
>
> <?xml version="1.0" encoding="UTF-8"?>
>
>
>     This node id = A
>     Sibling count = 1
>
>
>     This node id = B
>     Sibling count = 1
>
>
>     This node id = C
>     Sibling count = 1
>
>
>     This node id = D
>     Sibling count = 2
>
> It the intersection operation didn't do what I expected. I expected that
nodes A and D would have a Sibling count of 0 and that nodes B and C would
each have a sibling count of 1.
>
> Could anyone tell me where I'm going wrong and point me in the right
direction?
> Thanks.

The reason is you're mixing node-identity with value-identity. The XPath
expression for intersection of two node-sets selects the *identical* nodes
from the two node-sets. In your case you want to find all nodes with the
same *value*.

Here's a transformation, which produces what you want:

<xsl:stylesheet version="1.0"
xmlns:xsl="http://www.w3.org/1999/XSL/Transform">
  <xsl:output method="xml" indent="yes" encoding="UTF-8" />

  <xsl:template match="/">
    <xsl:apply-templates />
  </xsl:template>

  <xsl:template match="network">
    <xsl:apply-templates />
  </xsl:template>

  <xsl:template match="node">
    <xsl:variable name="this-node-id" select="node-id" />
    <xsl:variable name="this-predecessor-nodes"
         select="/*/node[node-id = current()/node-id]/predecessor-id" />
    <xsl:variable name="other-predecessor-nodes"
         select="/*/node[node-id != $this-node-id]/predecessor-id" />
    <xsl:variable name="sibling-cnt"
    select="count($other-predecessor-nodes
                    [. =$this-predecessor-nodes]
                  )" />

    This node id = <xsl:value-of select="$this-node-id" />
    Sibling count = <xsl:value-of select="$sibling-cnt" />
  </xsl:template>

</xsl:stylesheet>

When this transformation is applied on your source.xml:

<network>
  <node>
    <node-id>A</node-id>
    <predecessor-id></predecessor-id>
    <successor-id>B</successor-id>
  </node>
  <node>
    <node-id>B</node-id>
    <predecessor-id>A</predecessor-id>
    <successor-id>D</successor-id>
  </node>
  <node>
    <node-id>C</node-id>
    <predecessor-id>A</predecessor-id>
    <successor-id>D</successor-id>
  </node>
  <node>
    <node-id>D</node-id>
    <predecessor-id>B</predecessor-id>
    <predecessor-id>C</predecessor-id>
    <successor-id></successor-id>
  </node>
</network>

the wanted result is produced:

    This node id = A
    Sibling count = 0


    This node id = B
    Sibling count = 1


    This node id = C
    Sibling count = 1


    This node id = D
    Sibling count = 0

One final remark: the chosen representation of the graph is not good at all.
 I'd recommend a better one, e.g. the standard for graph representation -- 
graphML.


Hope this helped.

Cheers,

Dimitre Novatchev ,
FXSL developer,

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




 XSL-List info and archive:  http://www.mulberrytech.com/xsl/xsl-list