使用Barnes-Hut进行图放置的优化问题 [英] Optimization issues using Barnes-Hut for graph placing

问题描述

我一直在试图解决Force-Directed图形/ Barnes-Hut在我的图形可视化应用程序的问题。我检查到目前为止octree创建，它看起来正确（树由框和圆圈表示我的图节点）：

我的<$ c中的字段$ c> Quadtree 如下：

  class Quadtree 
 {
 public ：
 int level; 
 Quadtree * trees [2] [2] [2]; 
 glm :: vec3 vBoundriesBox [8]; 
 glm :: vec3 center; 
 bool leaf; 
 float combined_weight = 0; 
 std :: vector< Element *>对象; 
 //添加方法/字段
 private：
 //其他方法/字段
 protected：
} 
  pre> 
 
 
这是我如何向四叉树递归添加元素：
  #define MAX_LEVELS 5 
 
 void Quadtree :: AddObject（Element * object）
 {
 this-> objects.push_back（object）; 
} 
 
 void Quadtree :: Update（）
 {
 if（this-> objects.size（）< = 1 || level> MAX_LEVELS ）
 {
 for（Element * Element：this-> objects）
 {
 Element-> parent_group = this; 
 this-> combined_weight + = Element-> weight; 
} 
 return; 
} 
 
 if（leaf）
 {
 GenerateChildren（）; 
 leaf = false; 
} 
 
 while（！this-> objects.empty（））
 {
 Element * obj = this-> objects.back 
 this-> objects.pop_back（）; 
 if（contains（trees [0] [0] [0]，obj））
 {
 trees [0] [0] [0] 
 trees [0] [0] [0]  - > combined_weight + = obj-> weight; 
} else if（contains（trees [0] [0] [1]，obj））
 {
 trees [0] [0] [1]  - & ; 
 trees [0] [0] [1]  - > combined_weight + = obj-> weight; 
} else if（contains（trees [0] [1] [0]，obj））
 {
 trees [0] [1] [0]  - & ; 
 trees [0] [1] [0]  - > combined_weight + = obj-> weight; 
} else if（contains（trees [0] [1] [1]，obj））
 {
 trees [0] [1] [1] ; 
 trees [0] [1] [1]  - > combined_weight + = obj-> weight; 
} else if（contains（trees [1] [0] [0]，obj））
 {
 trees [1] [0] [0]  - & ; 
 trees [1] [0] [0]  - > combined_weight + = obj-> weight; 
} else if（contains（trees [1] [0] [1]，obj））
 {
 trees [1] [0] [1] ; 
 trees [1] [0] [1]  - > combined_weight + = obj-> weight; 
} else if（contains（trees [1] [1] [0]，obj））
 {
 trees [1] [1] [0]  - & ; 
 trees [1] [1] [0]  - > combined_weight + = obj-> weight; 
} else if（contains（trees [1] [1] [1]，obj））
 {
 trees [1] [1] [1] ; 
 trees [1] [1] [1]  - > combined_weight + = obj-> weight; 
} 
} 
 
 for（int i = 0; i <2; i ++）
 {
 for（int j = 0; j < ; j ++）
 {
 for（int k = 0; k <2; k ++）
 {
 trees [i] [j] ; 
} 
} 
} 
} 
 
 bool Quadtree :: contains（Quadtree * child，Element * object）
 {
 if（object-> pos [0]> = child-> vBoundriesBox [0] [0]&& object-> pos [0]< = child-> vBoundriesBox [1] [0 ]&& 
 object-> pos [1]> = child-> vBoundriesBox [4] [1]&& object-> pos [1]< = child-> vBoundriesBox [0] [1]&& 
 object-> pos [2]> = child-> vBoundriesBox [3] [2]& ; = child-> vBoundriesBox [0] [2]）
 return true; 
返回false; 
} 
  
正如你在图片上看到的，节点是非常集群的。我一直在想办法解决我的排斥力计算，但它仍然不工作，结果仍然是这样的。
 
 
 
所以我如何计算它：
 
 
 
首先在我的主文件中，我正在通过所有图形节点运行循环：
 code> for（auto& n_el：graph-> node_vector）
 {
 tree-> CheckNode（& n_el）; 
} 
  
下一页 Qyadtree  class，（ tree 是这个类对象），我有这个递归方法：
  void Quadtree :: CheckNode（Node * node）
 {
 glm :: vec3 diff = this-> center  -  node-> pos; 
 
 double distance_sqr =（diff.x * diff.x）+（diff.y * diff.y）+（diff.z * diff.z）; 
 double width_sqr =（vBoundriesBox [1] [0]  -  vBoundriesBox [0] [0]）*（vBoundriesBox [1] [0]  -  vBoundriesBox [0] [0] 
 if（width_sqr / distance_sqr <10.0f || leaf）
 {
 if（leaf）
 {
 for（auto& n：objects）
 {
 n-> Repulse（& objects）; 
} 
} 
 else 
 {
 node-> RepulseWithGroup（this）; 
} 
} 
 else 
 {
 for（int i = 0; i <2; i ++）
 {
 for = 0; j <2; j ++）
 {
 for（int k = 0; k <2; k ++）
 {
 trees [i] [j] - > CheckNode（node）; 
} 
} 
} 
} 
} 
  
 
 $ b b 
最后，我有两个方法计算斥力，取决于它是在组和节点之间还是在两个节点之间的事实：
  double Node :: Repulse（std :: vector< Node *> * nodes）
 {
 double dx; 
 double dy; 
 double dz; 
 double force = 0.0; 
 double distance_between; 
 double delta_weights; 
 double temp; 
（auto& element_node：* nodes）
 {
 if（this-> name == element_node-> name）
 {
 continue; 
} 
 if（！element_node-> use）continue; 
 delta_weights = 0.5 + abs（this-> weight-element_node-> weight）; 
 dx = this-> pos [0]  -  element_node-> pos [0]; 
 dy = this-> pos [1]  -  element_node-> pos [1]; 
 dz = this-> pos [2]  -  element_node-> pos [2]; 
 distance_between = dx * dx + dy * dy + dz * dz; 
 force = 0.19998 * delta_weights /（distance_between * distance_between）; 
 temp = std :: min（1.0，force）; 
 if（temp< 0.0001）
 {
 temp = 0; 
} 
 double mx = temp * dx; 
 double my = temp * dy; 
 double mz = temp * dz; 
 this-> pos [0] + = mx; 
 this-> pos [1] + = my; 
 this-> pos [2] + = mz; 
 element_node-> pos [0]  -  = mx; 
 element_node-> pos [1]  -  = my; 
 element_node-> pos [2]  -  = mz; 
} 
} 
 
 void Node :: RepulseWithGroup（Quadtree * tree）
 {
 double dx; 
 double dy; 
 double dz; 
 double force = 0.0; 
 double distance_between; 
 double delta_weights; 
 double temp; 
 
 delta_weights = 0.5 + abs（this-> weight-tree-> combined_weight）; 
 dx = this-> pos [0]  -  tree-> center.x; 
 dy = this-> pos [1]  -  tree-> center.y; 
 dz = this-> pos [2]  -  tree-> center.z; 
 distance_between = dx * dx + dy * dy + dz * dz; 
 force = 0.19998 * delta_weights /（distance_between * distance_between）; 
 temp = std :: min（1.0，force）; 
 if（temp< 0.0001）
 {
 temp = 0; 
} 
 double mx = temp * dx; 
 double my = temp * dy; 
 double mz = temp * dz; 
 this-> pos [0] + = mx + this-> parent_group-> repulsion_force.x; 
 this-> pos [1] + = my + this-> parent_group-> repulsion_force.y; 
 this-> pos [2] + = mz + this-> parent_group-> repulsion_force.z; 
} 
  
如果这个想法：
  if（width_sqr / distance_sqr <10.0f || leaf）
 {
 if（leaf）
 {
 for auto& n：objects）
 {
 n-> Repulse（& objects）; 
} 
} 
 else 
 {
 node-> RepulseWithGroup（this）; 
} 
} 
  
不清楚是因为我想出，在一个树叶中实际上可能有多个元素。如果最大级别可能已经达到并且元素仍在一个框中，则可能发生这种情况。然后我还需要计算框内的力对节点内部。
 
 
 
更烦恼的是这种方法的速度（这表明octree不能正常工作）是速度。这是代表时间/节点数量的简单图：
  
据我所知，原始的力导向图算法具有复杂性 O（n ^ 2），但是对于Barnes-Hut，它应该是 O（nlogn）。然而，情节甚至不接近nlogn。
 
 
 
有人能告诉我我在这里做错了什么吗？我一直在看这段代码相当长一段时间，我没有看到我缺少的东西。
 
 
 
 编辑： 
 
 
 
基于@Ilmari Karonen答案我已经运行测试 MAX_LEVELS  5，20，50，100都在下面。因为它看起来没有有意义的差异，我会说（不幸的是）
  
解决方案
刚刚离开我的头顶，
  #define MAX_LEVELS 5 
  
似乎很低。你可能只是在你的八叉树中跑得太深，导致你的算法退化成O（ n ²）直接求和。您可以尝试将 MAX_LEVELS 增加到一个明显更高的值（至少是10或20），然后看看是否能提高性能。
 
 
 
我没有测试你的代码，所以我不能确定这是真正的问题，还是唯一的。 
 
 
 
 
 
 
看一下你的代码，我看到了一个夫妇的其他潜在问题，太。严格来说，这些可能不会影响效果，但可能会影响结果的正确性。
 
 
 
首先，您有一个中心向量在 Quadtree 类中，可能代表子树内节点的质心，但是你从来没有更新向量添加节点到树中。因为你在计算中使用这个向量，你可能会得到假的结果。
 
 
 
（事实上， 're使用中心向量计算节点和子树之间的距离，因此决定是否更深入到子树，这也可能搞乱你的性能。）
 
 
 
此外，您似乎在遍历树时直接更新位置，这意味着您的算法生成的轨迹将取决于节点被遍历并且树被扩展。为了获得更一致和可重现的结果，您可能需要首先在算法的当前迭代中计算每个节点的位移，将其存储在单独的向量中，然后在节点上运行第二遍，以将位移添加到它们的位置并重置它的下一次迭代）。
 
 
 
此外，我肯定不能是唯一一个发现你有一个名为 Quadtree 实现了一个 oc 树烦人，我可以吗？ :) 
 
I've been trying to work out the problem of Force-Directed graph/Barnes-Hut in my graph visualization app. I've checked so far octree creation, and it looks correctly (tree is represented by boxes and circles are my graph nodes):

Fields in my Quadtree are following:
class Quadtree
{
    public:
        int level;
        Quadtree* trees[2][2][2];
        glm::vec3 vBoundriesBox[8];
        glm::vec3 center;
        bool leaf;
        float combined_weight = 0;
        std::vector<Element*> objects;
        //Addition methods/fields
    private:
    //Additional methods/fields
    protected:
}
This is how I am adding elements recursively to my quadtree:
#define MAX_LEVELS 5

void Quadtree::AddObject(Element* object)
{
    this->objects.push_back(object);
}

void Quadtree::Update()
{
    if(this->objects.size()<=1 || level > MAX_LEVELS)
    {
        for(Element* Element:this->objects)
        {
            Element->parent_group = this;
            this->combined_weight += Element->weight;
        }
        return;
    }

    if(leaf)
    {
        GenerateChildren();
        leaf = false;
    }

    while (!this->objects.empty())
    {
        Element* obj = this->objects.back();
        this->objects.pop_back();
        if(contains(trees[0][0][0],obj))
        {
            trees[0][0][0]->AddObject(obj);
            trees[0][0][0]->combined_weight += obj->weight;
        } else if(contains(trees[0][0][1],obj))
        {
            trees[0][0][1]->AddObject(obj);
            trees[0][0][1]->combined_weight += obj->weight;
        } else if(contains(trees[0][1][0],obj))
        {
            trees[0][1][0]->AddObject(obj);
            trees[0][1][0]->combined_weight += obj->weight;
        } else if(contains(trees[0][1][1],obj))
        {
            trees[0][1][1]->AddObject(obj);
            trees[0][1][1]->combined_weight += obj->weight;
        } else if(contains(trees[1][0][0],obj))
        {
            trees[1][0][0]->AddObject(obj);
            trees[1][0][0]->combined_weight += obj->weight;
        } else if(contains(trees[1][0][1],obj))
        {
            trees[1][0][1]->AddObject(obj);
            trees[1][0][1]->combined_weight += obj->weight;
        } else if(contains(trees[1][1][0],obj))
        {
            trees[1][1][0]->AddObject(obj);
            trees[1][1][0]->combined_weight += obj->weight;
        } else if(contains(trees[1][1][1],obj))
        {
            trees[1][1][1]->AddObject(obj);
            trees[1][1][1]->combined_weight += obj->weight;
        }
    }

    for(int i=0;i<2;i++)
    {
        for(int j=0;j<2;j++)
        {
            for(int k=0;k<2;k++)
            {
                trees[i][j][k]->Update();
            }
        }
    }
}

bool Quadtree::contains(Quadtree* child, Element* object)
{
    if(object->pos[0] >= child->vBoundriesBox[0][0] && object->pos[0] <= child->vBoundriesBox[1][0] &&
       object->pos[1] >= child->vBoundriesBox[4][1] && object->pos[1] <= child->vBoundriesBox[0][1] &&
       object->pos[2] >= child->vBoundriesBox[3][2] && object->pos[2] <= child->vBoundriesBox[0][2])
        return true;
    return false;
}
As you can see on the picture nodes are very clustered. I've been trying to figure out the way to fix my repulsion force calculations, but it still not working and result is still this same.

So how I'm calculating it:

First in my main file I am running loop through all graph nodes:
for(auto& n_el:graph->node_vector)
{
    tree->CheckNode(&n_el);
}
Next in my Qyadtree class, (tree is this class object), I have this recursive method:
void Quadtree::CheckNode(Node* node)
{
    glm::vec3 diff = this->center - node->pos;

    double distance_sqr = (diff.x * diff.x) + (diff.y*diff.y) + (diff.z*diff.z);
    double width_sqr = (vBoundriesBox[1][0] - vBoundriesBox[0][0]) * (vBoundriesBox[1][0] - vBoundriesBox[0][0]);
    if(width_sqr/distance_sqr < 10.0f || leaf)
    {
        if(leaf)
        {
            for(auto& n: objects)
            {
                n->Repulse(&objects);
            }
        }
        else
        {
            node->RepulseWithGroup(this);
        }
    }
    else
    {
        for(int i=0; i<2; i++)
        {
            for(int j=0; j<2; j++)
            {
                for(int k=0; k<2; k++)
                {
                    trees[i][j][k]->CheckNode(node);
                }
            }
        }
    }
}
Finally I have two methods calculate repulse force depending on the fact if it's between group and node or between two nodes:
double Node::Repulse(std::vector<Node*>* nodes)
{
    double dx;
    double dy;
    double dz;
    double force = 0.0;
    double distance_between;
    double delta_weights;
    double temp;
    for(auto& element_node:*nodes)
    {
        if(this->name == element_node->name)
        {
            continue;
        }
        if(!element_node->use) continue;
        delta_weights = 0.5 + abs(this->weight - element_node->weight);
        dx = this->pos[0] - element_node->pos[0];
        dy = this->pos[1] - element_node->pos[1];
        dz = this->pos[2] - element_node->pos[2];
        distance_between = dx * dx + dy * dy + dz * dz;
        force = 0.19998 * delta_weights/(distance_between * distance_between);
        temp = std::min(1.0, force);
        if(temp<0.0001)
        {
            temp = 0;
        }
        double mx = temp * dx;
        double my = temp * dy;
        double mz = temp * dz;
        this->pos[0] += mx;
        this->pos[1] += my;
        this->pos[2] += mz;
        element_node->pos[0] -= mx;
        element_node->pos[1] -= my;
        element_node->pos[2] -= mz;
    }
}

void Node::RepulseWithGroup(Quadtree* tree)
{
    double dx;
    double dy;
    double dz;
    double force = 0.0;
    double distance_between;
    double delta_weights;
    double temp;

    delta_weights = 0.5 + abs(this->weight - tree->combined_weight);
    dx = this->pos[0] - tree->center.x;
    dy = this->pos[1] - tree->center.y;
    dz = this->pos[2] - tree->center.z;
    distance_between = dx * dx + dy * dy + dz * dz;
    force = 0.19998 * delta_weights/(distance_between * distance_between);
    temp = std::min(1.0, force);
    if(temp<0.0001)
    {
        temp = 0;
    }
    double mx = temp * dx;
    double my = temp * dy;
    double mz = temp * dz;
    this->pos[0] += mx + this->parent_group->repulsion_force.x;
    this->pos[1] += my + this->parent_group->repulsion_force.y;
    this->pos[2] += mz + this->parent_group->repulsion_force.z;
}
In case this idea:
if(width_sqr/distance_sqr < 10.0f || leaf)
    {
        if(leaf)
        {
            for(auto& n: objects)
            {
                n->Repulse(&objects);
            }
        }
        else
        {
            node->RepulseWithGroup(this);
        }
    }
is not clear it is because I've figured out, that there might be actually multiple elements in one tree leaf. That might happen if the maximum level might be already reached and still elements are in one box. Then I need also to calculate force within box against nodes inside.

What's more is bothering me is the speed of this approach (and it's indicating that octree is not working correctly) is the speed. This is simple plot representing time/number of nodes:

As far as I know the original Force-directed graph algorithm have complexity O(n^2), but with Barnes-Hut it should be O(nlogn). Yet, the plot it's not even close to nlogn.

Can someone tell me what I am doing here wrong? I've been looking at this code for quite a long now, and I don't see where I am missing something.

EDIT:

Based on @Ilmari Karonen answer I've run test for MAX_LEVELS 5, 20, 50, 100. Results are below. As it looks there is no meaningful difference I'd say (unfortunately)
解决方案
Just off the top of my head,
#define MAX_LEVELS 5
seems awfully low.  You may simply be running out of depth in your octree, causing your algorithm to degenerate into O(n²) direct summing.  You may want to try increasing MAX_LEVELS to a significantly higher value (at least, say, 10 or 20) and seeing if that improves the performance.

I haven't tested your code, so I can't be sure if this is the real issue, or the only one.  But it's definitely what I'd check first.



Looking a bit more closely at your code, I'm seeing a couple of other potential issues, too.  These might not, strictly speaking, affect performance, but they might affect the correctness of the results.

First, you have a center vector in your Quadtree class, presumably representing the center of mass of the nodes within the subtree, but you never seem to update that vector when adding nodes into the tree.  Since you do use that vector in your calculations, you might be getting bogus results because of that.

(In fact, since one thing you're using the center vector for is calculating the distance between a node and a subtree, and so deciding whether to descend deeper into the subtree, that might also be messing up your performance.)

Also, you seem to be updating the positions directly while traversing the tree, which means that the trajectories generated by your algorithm will depend on the order in which the nodes are traversed and the tree expanded.  For more consistent and reproducible results, you may want to first calculate the displacement of each node during the current iteration of the algorithm, storing it in a separate vector, and then run a second pass over the nodes to add the displacement to their position (and reset it for the next iterations).

Also, surely I can't be the only one who finds the fact that you have a class named Quadtree that implements an octree annoying, can I? :)  

                        
这篇关于使用Barnes-Hut进行图放置的优化问题的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！