Saxon

I have for many years found it frustrating that XML is confined to hierarchic relationships (things like IDREF and XLink are clumsy workarounds); also the fact that the arbitrary division of data into "documents" plays such a decisive role: documents should only exist in the serialized representation of the model, not in the model itself.

I started my career working with the Codasyl-defined network data model. It's a fine and very flexible data model; its downfall was the (DOM-like) procedural navigation language. So I've often wondered what one could do trying to re-invent the Codasyl model in a more modern idiom, coupling it with an XPath-like declarative access language extended to handle networks (graphs) rather than hierarchies.

I've no idea how close a reinventiion of Codasyl would be to some of the modern graph data models; it would be interesting to see. The other interesting aspect of this is whether you can make it work for schema-less data.

But I don't think that would be an incremental evolution of XSLT; I think it would be something completely new.

I was not so radical in my thoughts. :-)

Even C++ API is not so radical, as they do not impose hard requirements on internal graph representation but rather define template API that will work both with third party representations (they even mention Fortran) or several built-in implementations that uses standard vectors.

Their strong point is in algorithms provided as part of library and not graph internal structure (I think authors of that paper have structured it not the best way). E.g. in the second part they list graph algorithms: Depth First Search (DFS); Breadth First Search (BFS); Topological Sort (TopoSort); Shortest Paths Algorithms; Dijkstra Algorithms; and so on.

If we shall try to map it to xpath world them graph on API level might be represented as a user function or as a map of user functions.

On a storage level user may implement graph using a sequence of maps or map of maps, or even using xdm elements.

So, my approach is evolutional. In fact I suggest pure API that could even be implemented now.

Yes, there's certainly scope for graph-oriented functions such as closure($origin, $function) and is-reachable($origin, $function) and find-path($origin, $destination, $function) where we use the existing data model, treating any item as a node in a graph, and representing the arcs using functions. There are a few complications, e.g. what's the identity comparison between arbitrary items, but it can probably be done.

There are a few complications, e.g. what's the identity comparison between arbitrary items, but it can probably be done.

One approach to address this is through definition of graph API. E.g. to define graph as a map (interface analogy) of functions, with equality functions, if required:

map
{
  vertices: function(),
  edges: function(),
  value: function(vertex),
  in-vertex: function(edge),
  out-vertex: function(edge),
  edges: function(vertex),
  is-in-vertex: function(edge, vertex),
  is-out-vertex: function(edge, vertex)
  ...
}

I've decided to go with sample to prove myself it's doable and created a github repository (xslt-graph)[https://github.com/nesterovsky-bros/xslt-graph].

There we can see:

• graph API in graph.xslt;
• depth-first-search algorithm in depth-first-search.xslt; and
• test tests/routes.xslt;

I'll try to add more algorithms later, but what we can see now is that graph API fits very much to xslt.

While implementing graph API I have found another xslt 4 candidate.

Graph algorithms are often expressed with while cycles, e.g "Dijkstra's algorithm" has:

12      while Q is not empty:
13          u ← vertex in Q with min dist[u]  

body is executed when condition is satisfied, but condition is impacted by body itself.

In xslt 3.0 I did this with simple recursion:

  <!--
    A while cycle:
      If $condition($state) is true() then
        $action($state) is called to produce a subset of result;
        f:while template is called with state parameter as 
        $next($state, $action($state)).
        
    $condition as function($state as item()) as xs:boolean - 
      a while condition function.
    $action as function($state as item()) as item()* - 
      a while action function.
    $next as function($state as item(), $items as item()*) as item()* - 
      a while next function.
    Returns combined result produced by $action($state) calls.  
  -->
  <xsl:template name="f:while" as="item()*">
    <xsl:param name="condition" as="function(item()*) as xs:boolean"/>
    <xsl:param name="action" as="function(item()*) as item()*"/>
    <xsl:param name="next" as="function(item()*, item()*) as item()*"/>
    <xsl:param name="state" as="item()*"/>

    <xsl:if test="$condition($state)">
      <xsl:variable name="items" as="item()*" select="$action($state)"/>

      <xsl:sequence select="$items"/>

      <xsl:call-template name="f:while">
        <xsl:with-param name="condition" select="$condition"/>
        <xsl:with-param name="action" select="$action"/>
        <xsl:with-param name="next" select="$next"/>
        <xsl:with-param name="state" select="$next($state, $items)"/>
      </xsl:call-template>
    </xsl:if>
  </xsl:template>

But here is the point. It could be done in more comprehended way. E.g. if xsl:iterate instruction could be specified without select attribute, and that would mean cycling until xsl:break is reached.

<xsl:iterate>
  <xsl:param name="name" as="..." value="..."/>
  
  <xsl:if test="...">
    <xsl:break/>
  </xsl:if>

  ...
</xsl:iterate>