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.

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.