python - 按边缘属性进行深度优先搜索

Question

我正在使用 graph-tool for python，这是一个实现 boost 的库。我需要仅使用具有 edge_property 的边进行深度优先搜索:

rel_need = True

所以，我正在使用

gt.dfs_search(g, g.vertex(0), NeedFinder(rel_need, pred, time))

使用这个 DFSVisitor:

class NeedFinder(gt.DFSVisitor):

    def __init__(self, rel_need, pred, time):
        self.rel_need = rel_need
        self.pred = pred
        self.time = time
        self.last_time = 0

    def discover_vertex(self, u):
        self.time[u] = self.last_time
        self.last_time += 1

    def examine_edge(self, e):
        pass

    def tree_edge(self, e):
        if self.rel_need[e]:
            self.pred[e.target()] = int(e.source())

似乎我应该在 examine_edge def 中做一些检查，但我没能找到解释它的文档。我在 tree_edge def 中进行了检查，它成功过滤了所有 rel_need=true 边，但它不会改变遍历。如何制作仅遍历某些边而不是所有边的 DFSVisitor？

Answer 1

您应该先创建一个过滤图。你可以这样做:

u = GraphView(g, efilt=rel_need)

其中rel_need是一个 bool 属性映射，其中rel_need[e] == True表示没有过滤掉边缘。

然后您可以继续使用图 u 进行 DFS 搜索，rel_need[e] == False 的边将被忽略。