Boost:Graph recursive traverse and graph-copy

Question

I had some first experience with creating and traversing graphs. But now I have a problem, of which I don't now, if boost::graph has some algorithms to solve it.

Here is my graph-definition:

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;

So BGraph contains items and logical relations between them. Now I would like to transform this graph into multiple graphs, each of which should contains NO or-relations, but represent all by the OR-vertices defind combinatorial alternates of items and their AND-relations.

An example: if there are three items A, B, C related so: A AND ( B OR C) then the result of the traversal should be two graphs, containing the following combinations: (1) A AND B (2) A AND C

My (simple) idea now is to traverse the graph, and each time the traversal finds an OR-vertex, to copy the whole graph and follow from there on each part of the OR-node recursive:

if graph[vertex] == OR {
for (... // each child vertex of vertex BGraph newGraph = copy(Graph); traverse(newGraph,childVertex); } }

This won't work correctly, because my recursive call of each child would miss the stack structure (the information, how to come back upwards in the graph). This means: the traversal would climb down correct, but not upwards again.

I have no idea, if there is a more (or at all) efficient way to solve such a problem with boost::graph and its embedded algorithms.

But to me it seems to be an interesting problem, so I would like to discuss it here, maybe it leads to a deeper insight of boost::graph.

Thank you!

Answer 1

My overall approach would be to do a depth-first walk of the input graph, and construct the output graphs bottom-up. Because you want to construct an arbitrary number of graphs, the traversal function has to return a list of graphs.

So here's an algorithm in pseudo-code

-- syntax: [xxx,xxx,...] is a list, and (xxx AND yyy) is a node.

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

For example: pass in ((A OR B) AND (C OR D))

The individual terms compile to simple lists:

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

The OR conditions simply become parallel queries:

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

The AND condition must be combined in all possible permutations:

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

Hope this helps. If you cast it into C++, you'll have to take care of housekeeping, i.e., destroying intermediate list objects after they are no longer needed.