OGDF PQTree: How to add leaves?

Question

Using OGDF I've created and initialized a PQTree. Initialization was done with 3 edges, where node a is root, b, c and d are Leaves of a. Now, after calculation, I need to add the leaves e, d and f to b as leaves. But problem is, b is a leaf, so accepts neither children, nor leaves. Code is here. As std::cout, I've got, that, they were added, but if I write it to the GML file using writeGML, there is no difference between before and after adding the nodes, they are not in the tree. I think, it is because of the PQLeafKey, where for non leaf edges/nodes it should be PQNodeKey. According to the documentation, ablk->nodePointer() should return PQLeaf, which derived from PQNode and is not "compatible" with PQInternelNode, which also derived PQNode. But I don't know, how to add the in different way. Code:

G = new Graph();
GA = new GraphAttributes(*G, GraphAttributes::nodeGraphics |
                         GraphAttributes::edgeGraphics |
                         GraphAttributes::nodeStyle |
                         GraphAttributes::nodeId |
                         GraphAttributes::edgeType |
                         GraphAttributes::edgeArrow |
                         GraphAttributes::edgeStyle);
node a = G->newNode();
node b = G->newNode();
node c = G->newNode();
node d = G->newNode();
edge ab = G->newEdge(a, b);
edge ac = G->newEdge(a, c);
edge ad = G->newEdge(a, d);

PQLeafKey<edge, IndInfo *, bool> *ablk = new PQLeafKey<edge, IndInfo *, bool>(ab);
PQLeafKey<edge, IndInfo *, bool> *aclk = new PQLeafKey<edge, IndInfo *, bool>(ac);
PQLeafKey<edge, IndInfo *, bool> *adlk = new PQLeafKey<edge, IndInfo *, bool>(ad);

SListPure<PQLeafKey<edge, IndInfo *, bool> *> *lkl = new SListPure<PQLeafKey<edge, IndInfo *, bool> *>();
lkl->pushBack(ablk);
lkl->pushBack(aclk);
lkl->pushBack(adlk);

pqtree = new PQTree<edge, IndInfo *, bool>();
pqtree->Initialize(*lkl);
pqtree->writeGML("/home/LPT/graph_qtree_MOC_after_initialization.gml");

node e = G->newNode();
node f = G->newNode();
node g = G->newNode();
edge be = G->newEdge(b, e);
edge bf = G->newEdge(b, f);
edge bg = G->newEdge(b, g);
PQLeafKey<edge, IndInfo *, bool> *belk = new PQLeafKey<edge, IndInfo *, bool>(be);
PQLeafKey<edge, IndInfo *, bool> *bflk = new PQLeafKey<edge, IndInfo *, bool>(bf);
PQLeafKey<edge, IndInfo *, bool> *bglk = new PQLeafKey<edge, IndInfo *, bool>(bg);
SListPure<PQLeafKey<edge, IndInfo *, bool> *> *lkl4 = new SListPure<PQLeafKey<edge, IndInfo *, bool> *>();
lkl4->pushBack(belk);
lkl4->pushBack(bflk);
lkl4->pushBack(bglk);

PQInternalNode<edge, IndInfo *, bool> *father = (PQInternalNode<edge, IndInfo *, bool> *) (ablk->nodePointer());
father->type(PQNodeRoot::PNode);
bool r = pqtree->addNewLeavesToTree(father, *lkl4);
QString res = r ? "done." : "failed.";
std::cout << "Adding leaves to the tree for MOC has " << res.toStdString() << std::endl;
pqtree->writeGML("/home/LPT/graph_qtree_MOC_after_addition_be_bf_bg.gml");

score 0 · Answer 1 · answered Dec 03 '16 at 12:47

oki, doki,

I got it and have done, works perfectly. Sorry for the late answer. Directly adding the leaves to an existing leaf will no work. The method I've used is the protected exchangeNodes(PQNode *oldNode, PQNode *newNode) in class PQTree. First, I extract the ID of the leaf, then create a new PQInternalNode *newNode, which in its turn is EMPTY and P-Node with the extracted ID. Extracting and using the same ID is not a MUST, but it looks this way more readable. Exchanging the node of the leaf to the *newNode affects the node type in the leaf and cheats the pqtree to handle the leaf like a p-node starting after the exchange, which in its turn allows me to add the new leaves to the *newNode, which is not a leaf anymore.

OGDF PQTree: How to add leaves?

1 Answers1