# XSL-T to map a D(A)G

 Subject: XSL-T to map a D(A)G From: Mark Nahabedian Date: Tue, 2 Oct 2001 09:31:42 -0400
```Goetz Bock writes:
[...]
> I know that such a mapping is not easy and  due to the scructur of the
> XML it is possible to created the strangest graphs :-(
> But I'd be happy just do map a DAG, ignorring all the backward
> references.
>
> I don't need this immediatly, because this functionality will only be
> the suggar for my current project.
> Anyway, has anyone ever written a D(A)G mapper in XSL-T?
> Or should I just forget XSL-T for this and use a "real" programming
> language.

The hardest part of your problem is an algorithmic one, not a
programming one.  How does one decide where to place the nodes of the
graph.

If your graph is directed and acyclic, you can put the root node in
the top row and sucessive generations of descendcents in suceeding
rows: nodes that have in-links directly from the root would be in the
second row, nodes with in links from those nodes in the third row,
etc.  A node might have in-links from several different "genereations"
of nodes.  Its row should be determined based on (one more than) the
lowest row of any of the nodes which have links directed to it.

The previous paragraph descives a way to place the nodes along one
axis.  To determine their locations on the other axis, you would
ideally want to minimize the lengths of the arrows which represent the
links.  You might decide that this is too much work for the first
attempt and just place the nodes of a given row in the order they
appear in the input.

This will get out a graph but it may not be pretty.  It might look
cluttered.  Some rows might appear too wide for convenient display.
Anything better is probably much hardser though.

I think that in XSLT I'd approach this with a two pass solution. The
first pass would read the graph description input XML file and output
the same XML tree but with additional attributes that assign locations
to the nodes.  The second pass would just generate SVG from that
modified tree.

I've not tried this but I have worked oin a similar problem: drawing a
picture of a knot given an XML description.  I did this using two
transformations.  The first transformation extracts a specified know
from a "knot library file" (in XML) and outputs the description of
that knot along with additional elements and attributes which serve as
placeholders in which the user is to edit the placement information
(locations where the crossings of cords should be placed).  The second
transformation generates SVG from the output of the first, after th3e
used has filled in the placement information.

I hope these suggestions are helpful.

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

```

### PURCHASE STYLUS STUDIO ONLINE TODAY!

Purchasing Stylus Studio from our online shop is Easy, Secure and Value Priced!