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-отношений.

В качестве примера: если есть три элемента А, В, С , связанные так: А и (В или С) то результат обхода должно быть два графика, , содержащие следующие комбинации: (1) а и в (2) а и с

Моими (простая) идея теперь должны пересекать график, и каждый раз, когда обхода находит OR-вершину, чтобы скопировать весь график и следовать оттуда на каждом часть рекурсивного OR-узла:

if graph [vertex] == OR {
для (... // каждая дочерняя вершина вершины BGraph newGraph = копия (график); traverse (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] 

The OR условия просто становятся параллельные запросы:

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

И-условие должны быть объединены во всех возможных перестановках:

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

Надеюсь, что это поможет. Если вы добавите его на C++, вам придется позаботиться о домашнем хозяйстве, то есть уничтожить объекты промежуточного списка после того, как они больше не нужны.

Answer 2

Здесь принятие на питон как дополнение (Еще раз спасибо, это работает отлично !!!):

_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)