Boost：图递归遍历和图副本

Question

我有一些第一次创建和穿越 图的经验。但现在我有一个问题，其中我现在不是， 如果boost :: graph有一些算法来解决它。

这里是我的图形清晰度：

const int _AND = 1001; 
const int _OR = 1002; 
const int _ITEM = 1003; 

struct gEdgeProperties 
{ 
    string label; 
}; 

struct gVertexProperties 
{ 
    string label; 
    int typ; // _AND, _OR, ITEM 
}; 

typedef adjacency_list< vecS, vecS, undirectedS, gVertexProperties, gEdgeProperties>  
BGraph; 

所以BGraph包含的项目以及它们之间的逻辑关系。 现在我想将这个图转换成多个图，其中每个图都应该包含NO或者关系，但是全部由OR顶点定义组合替代项 和它们的AND关系代表 。

一个例子：如果存在三个项A，B，C 相关，以便：a和（B OR C） 然后遍历的结果应该是两个曲线图， 含有下列组合： （1） A和B （2）A和C

我的（简单）的想法，现在是遍历图形，每一次 遍历找到一个OR-顶点，复制整个 图表，并按照从那里在每个部分OR节点递归：

if graph [vertex] == OR {
for（... //顶点的每个子顶点 BGraph newGraph = copy（Graph）;遍历（newGraph，childVertex）; }}

这将无法正常工作，因为我的每个孩子 的递归调用会怀念这里的堆叠结构（信息，怎么回来向上 中图）。这意味着：遍历将向下爬升正确，但是不会再向上爬升。

我不知道，如果有更多（或根本）有效的方法来解决这样一个与boost :: graph及其嵌入式算法有关的问题 。

但是对我来说这似乎是一个有趣的问题，所以我想 在这里讨论它，也许它会导致boost :: graph更深入的洞察力。

谢谢！

Answer 1

我的整体做法是先对输入图进行深度优先遍历，然后从下往上构建输出图。因为要构建任意数量的图，遍历函数必须返回图的列表列表。

因此，这里是伪代码的算法

- 语法：[xxx,xxx,...]是一个列表，(xxx AND yyy)是一个节点。

traverse (node): 
    if typeof(node) == term 
     return [ node ] 
    else 
     leftlist = traverse(node.left) 
     rightlist = traverse(node.right) 
     if node.condition == OR 
      result = leftlist .appendAll(rightlist) 
     else if node.condition == AND 
      result = [ ] 
      foreach left in leftlist 
       foreach right in rightlist 
        result .append((left AND right)) 
     else 
      panic("unknown condition") 
    return result 

例如：通过在((A OR B) AND (C OR D))

各个项编译为简单列表：

A -> [A] 
B -> [B] 
C -> [C] 
D -> [D] 

的OR条件简单地成为并行查询：

(A OR B) -> [A] OR [B] -> [A, B] 
(C OR D) -> [C] OR [D] -> [C, D] 

AND条件必须组合成所有可能的排列组合：

(... AND ...) -> [A, B] AND [C, D] -> 
    [(A AND C), (A AND D), (B AND C), (B AND D)] 

希望这会有所帮助。如果将它转换为C++，则必须处理内务管理，即在中间列表对象不再需要后将其销毁。

Answer 2

这里通过以Python作为加法（再次感谢，它的伟大工程！）：

_AND  = 1 
    _OR   = 2 
    _ITEM  = 3 

    class Node: 
     def __init__(self, name): 
      self.name = name 
      self.condition = _ITEM 
      self.left = None 
      self.right = None 

    def showList(aList): 
     for node in aList: 
      print " elem cond: " , node.condition, " left: ", node.left.name, " right: ", node.right.name 

    def traverse (node): 
     leftlist = None 
     if node.condition == _ITEM: 
      return [ node ] 
     else: 
      leftlist = traverse(node.left) 
      rightlist = traverse(node.right) 
      found = 0 
      if node.condition == _OR: 
       found = 1 
       result = leftlist 
       for right in rightlist: 
        result.append(right) 
      else: 
       if node.condition == _AND: 
        found = 1 
        result = [ ] 
        for left in leftlist: 
         for right in rightlist: 
          newNode = Node(left.name + "_AND_" + right.name) 
          newNode.left = left 
          newNode.right = right 
          result.append(newNode)      
      if (found != 1): 
       print "unknown condition" 
       raise Exception("unknown condition") 
     return result 

    #EXAMPLE ((A OR B) AND (C OR D)): 

    node1 = Node("A") 
    node2 = Node("B") 
    node3 = Node("C") 
    node4 = Node("D") 

    node12 = Node("A_or_B") 
    node12.condition = _OR; 
    node12.left = node1 
    node12.right = node2 

    node34 = Node("C_or_D") 
    node34.condition = _OR; 
    node34.left = node3 
    node34.right = node4 

    root = Node("root") 
    root.condition = _AND; 
    root.left = node12 
    root.right = node34 

    aList = traverse(root) 

    showList(aList)