September 2, 2004
Detecting of cycles in graphs using XSLT and XQuery
Interesting post by Michael Kay on detecting cycles in graphs using XSLT and XQuery:
> I have XML data in the form of a graph (nodes, edges) and ITake a look at the stylesheet here. And now even more intriguing:
> need to check if
> any cycles exist in the data before I join the data together
> in one XML file.
>
> Can anyone point me to any resources to do this? Has anyone
> already done this in XQuery?
>
There is an example of how to do this in my book XSLT 2.0 Programmer's Reference, and the example translates directly into XQuery.
If you don't want to buy the book, the code (together with a "main program" that invokes it to look for cycles among the attribute sets in a stylesheet) is here:
The book also shows how to generalize this so the code that looks for cycles is independent of the way that the nodes and arcs are implemented. Unfortunately this generalization relies on Dimitre Novatchev's technique for simulating higher-order functions, which is dependent on XSLT and won't work in XQuery.Wow, I can't wait for the book to arrive. That's going to be my next one in reading queue, out of all priorities.
del.ico.us
digg it
redditThe link to Harry Robinson's article is:
http://www.geocities.com/harry_robinson_testing/graph_theory.htm
Posted by: Dimitre Novatchev at September 2, 2004 12:54 PMI provided an XSLT 1.0 solution to this problem in January, 2004 -- see it here:
http://lists.xml.org/archives/xml-dev/200401/msg00444.html
In Feb. - March this was generalised for a multigraph and, as one may expect, was more complicated. It was part of my XSLT implementation of the "Street Sweeper" algorithm.
The idea is to perform Eulerisation -- to duplicate certain arcs in the graph, so that it becomes traversable in a way, in which every arc is traversed exactly once. First the idea for the solution was proposed by the Chinese mathematician Kwan in 1962, but for not-directed graph. In his honour, the problem was named "the Chinese Postman Problem". A modification for directed graphs bears the name "the New York Street Sweeper Problem". Needless to say, in the beginning it was Euler with his famous proof that the Koenigsberg Bridges problem does not have a solution.
For a very nice description of this problem area see the article of Harry Robinson "Graph Theory Techniques in Model-Based Testing".
Cheers,
Dimitre Novatchev.
Posted by: Dimitre Novatchev at September 2, 2004 12:53 PM|
|
