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)