Modified graph traversal

Question

This question is most easy to describe as a modification of that my question.

Suppose that question is solved as the following Python class:

class Traversal(object):
 # ...
 def next(self): # next node of the graph
 # ...

Now I want to modify the algorithm: Sometimes I want to traverse to the next non-preferred node.

class Traversal(object):
 # ...
 def next(self): # next node of the graph
 # ...
 def next2(self): # next non-preferred node of the graph
 # ...

How to modify the algorithm to implement next2()?

Note that both next() and next2() return a graph node and this node should be recorded not to be traversed again.

Sorry I cannot describe the real example where this problem appears, it would be too verbose. You can see https://en.wikiversity.org/wiki/Automatic_transformation_of_XML_namespaces for the big problem I am solving.

• dagnelies: Regarding your question, I find it unclear. Regarding your goal of "transformation of XML namespaces", isn't that already doable with XSLT?
• porton: @dagnelies XSLT is one of many engines my transformations use

Answer 1

It seems I've found a good solution of my problem:

Because we have only two priorities: "preferred" and "non-preferred", the priority queue can be easily implemented as two queues: "preferred" and "non-preferred". In the usual (next()) traversal order, we will look first into preferred and then if it is empty non-preferred queue. If we need next2() traversal order, then instead look into non-preferred queue only.