c++ - 生成有向无环图的快速算法

Question

我有一个问题，非常感谢你的帮助。我必须生成一个具有 2^N 个节点的 DAG，这些节点的值从 0 到 2^(N-1)，具有以下属性:如果 x < y 并且存在非负整数 p，例如 x ⊕ y = 2^p，则节点 x 和 y 之间存在有向边(x 和 y 是它们的值)。到目前为止，我已经尝试了两个嵌套的 for 循环，但是当涉及到高达 2^15 的节点数时，这个解决方案太慢了。这是一个代码片段:

#include <iostream>
#include <vector>
#include <math.h>
typedef unsigned int unint;
using namespace std;
class Node
{
    friend class DAG;
private:
    unint value;
    vector<Node* > neighbourTo;
    vector<Node* > neighbors;
public:
    Node(unint );
};
Node::Node(unint _value)
    : value(_value) {}
class DAG
{
private:
    int noNodes;
    vector<Node* > nodes;
public:
    DAG(int );
    void initializeNodes(int ,int );
    int isPowerOf2(unsigned int );
    int getMaxNaighbourTo(int );
    int getMinNeighbor(int );
    int numberOfPathsLengthK(int );
    int recursion(Node& , int );
    void print();
};
DAG::DAG(int size)
{
    noNodes = size;

    nodes.resize(noNodes);
    int i, j;

    initializeNodes(0, noNodes-1);
    for(i = 0; i < noNodes-1; i++)
    {
        for(j = i+1; j < noNodes; j++)
        {
            if(isPowerOf2(i ^ j))
            {
                nodes[i]->neighbors.push_back(nodes[j]);
                nodes[j]->neighbourTo.push_back(nodes[i]);
            }
        }
    }
}
void DAG::initializeNodes(int min, int max)
{
    if(max == min)
        nodes[max] = new Node(max);
    else
    {
        int s = (max + min)/2;
        initializeNodes(min, s);
        initializeNodes(s+1, max);
    }
}
int DAG::isPowerOf2(unsigned int value)
{
    return ((value != 0) && !(value & (value - 1)));
}
int DAG::getMaxNaighbourTo(int index)
{
    if(index > 0 && index <= (noNodes-1))
    {
        int size = nodes[index]->neighbourTo.size();
        return nodes[index]->neighbourTo[size-1]->value;
    }
    return -1;
}
int DAG::getMinNeighbor(int index)
{
    if(index >= 0 && index < (noNodes-1))
        return nodes[index]->neighbors[0]->value;
    return -1;
}
int DAG::numberOfPathsLengthK(int K)
{
    if(K <= 0)
        return 0;
    long int paths = 0;
    for(int i = 0; i < nodes.size(); i++)
    {
        paths += recursion(*nodes[i], K - 1);
    }
    return (paths % 100003);
}
int DAG::recursion(Node& node, int K)
{
    if( K <= 0 )
        return node.neighbors.size();
    else
    {
        long int paths = 0;
        for(int i = 0; i < node.neighbors.size(); i++)
        {
            paths += recursion(*node.neighbors[i], K - 1);
        }
        return paths;
    }
}
void DAG::print()
{
    for(int i = 0; i < nodes.size(); i++)
    {
        cout << "Node: " << nodes[i]->value << "\tNeighbors: ";
        for(int j = 0; j < nodes[i]->neighbors.size(); j++)
        {
            cout << nodes[i]->neighbors[j]->value << " ";
        }
        cout << endl;
    }
}
int main()
{
    int
    N, M, K,
    i, j;
    cin >> N >> M >> K;
    DAG graf(pow(2, N));
    graf.print();
    cout << "==1==" << endl;
    cout << graf.getMaxNaighbourTo(M) << endl;
    cout << "==2==" << endl;
    cout << graf.getMinNeighbor(M) << endl;
    cout << "==3==" << endl;
    cout << graf.numberOfPathsLengthK(K) << endl;
    return 0;
}

这是一个简单的输出:

4 3 2
Node: 0     Neighbors: 1 2 4 8
Node: 1     Neighbors: 3 5 9
Node: 2     Neighbors: 3 6 10
Node: 3     Neighbors: 7 11
Node: 4     Neighbors: 5 6 12
Node: 5     Neighbors: 7 13
Node: 6     Neighbors: 7 14
Node: 7     Neighbors: 15
Node: 8     Neighbors: 9 10 12
Node: 9     Neighbors: 11 13
Node: 10    Neighbors: 11 14
Node: 11    Neighbors: 15
Node: 12    Neighbors: 13 14
Node: 13    Neighbors: 15
Node: 14    Neighbors: 15
Node: 15    Neighbors:
2
7
48

nodes是一个Node指针 vector ，Node a是一个类，里面保存了节点值和两个 vector ，一个Node指向当前节点的邻居，另一个是Node指向当前节点所在的节点是邻居。上面的代码是在 C++ 中。对于任何语法错误，我深表歉意。英语不是我的母语。

Answer 1

第一个明显的非算法性能提升是不构建图形，如果您只需要打印邻居，则无需创建数据结构即可。这里的第二个改进是避免用每条输出线刷新流...

对于算法改进，给定一个数字N=0011010(例如，任何数字都有效)，您需要找出哪个数字满足两个要求，N xor M 是 2 的幂，并且 N > M。第一个要求意味着两个数字在一位上完全不同，第二个要求意味着该位必须在 M 中点亮并且在 N 中不点亮，所以答案看起来就在上面的位是:M = { 1011010, 0111010, 0011110, 0011011 } 。现在你可以通过扫描 N 中的每一位来获取所有这些，如果它是 0 则设置它并打印值。

// assert that 'bits < CHAR_BITS * sizeof(unsigned)'
const unsigned int max = 1u << bits;
for (unsigned int n = 1; n < max; ++n) {
   std::cout << "Node: " << n << " Neighbors: ";
   for (unsigned int bit = 0; i < bits; ++i) {
      unsigned int mask = 1 << bit;
      if (!(n & mask)) {
         std::cout << (n | mask);
      }
   }
   std::cout << '\n';
}

对于给定节点的最小和最大邻居，您可以应用相同的推理，给定数字 N 的最大可达邻居将为 M，使得 N 中的最高 0 位点亮。对于最小可达邻居，您需要 M，以便将最低的 0 位设置为 1。