OGDF PQTree:如何添加叶子？

Question

使用OGDF，我已经创建并初始化了一个PQTree。初始化是用3条边完成的，其中节点a是根，b，c和d是a的叶子。现在，经过计算，我需要将叶子e，d和f添加到b作为叶子。但问题是，b是叶子，所以既不接受孩子，也不接受叶子。代码在这里。作为std::cout，我得到了，它们是被添加的，但是如果我使用writeGML将它写到GML文件中，添加节点之前和之后没有区别，它们不在树中。我认为，这是因为PQLeafKey，对于非叶边缘/节点，它应该是PQNodeKey。根据文档，ablk->nodePointer()应该返回PQLeaf，它派生自PQNode，与同样派生PQNode的PQInternelNode不“兼容”。但我不知道，如何以不同的方式添加。代码：

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");

Answer 1

好的，多奇，

我得到了它，并且已经完成了，工作得很完美。很抱歉回答得太晚了。直接将树叶添加到现有的树叶中将不起作用。我使用的方法是类PQTree中的受保护exchangeNodes(PQNode *oldNode，PQNode *newNode)。首先，我提取叶子的ID，然后创建一个新的PQInternalNode *newNode，它又是空的，P-Node.提取并使用相同的ID并不是必须的，但这样看起来更具可读性。将叶子的节点交换为*newNode会影响叶子中的节点类型，并欺骗pqtree像处理交换后开始的p节点一样处理叶子，这反过来又允许我将新叶子添加到不再是叶子的*newNode中。