Быстрый алгоритм генерации направленного ациклического графа

У меня есть проблема и буду признателен за вашу помощь.
Я должен сгенерировать DAG с 2 ^ N узлами, которые оцениваются от 0 до 2 ^ (N-1), с этим свойством:
Направленный край между узлами x и y (x и y являются их значениями), если x < y и есть неотрицательное целое число p, такое как x ⊕ y = 2 ^ p.
До сих пор я пробовал два вложенных цикла 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

node — это вектор указателей Node, а Node a — это класс, который содержит значение узла и два вектора, один Node-указатель на соседние узлы текущего узла, а другой — Node-указатель на узлы, соседние с которыми текущий узел , Приведенный выше код на C ++.
Я прошу прощения за любые грамматические ошибки. Английский не мой родной язык.

1

Решение

Первый очевидный выигрыш в производительности без алгоритма не чтобы построить график, если вам нужно только напечатать соседей, вы можете сделать это без создания структуры данных. Второе улучшение здесь должно было бы избежать очистки потока с каждой выходной линией …

Для алгоритмических улучшений, дан ряд N=0011010 (например, любое число является действительным), вам нужно выяснить, какое число соответствует двум требованиям, N xor M является степенью двойки, и 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 будет равен М так, что высший 0 бит в N будет гореть. Для минимально достижимого соседа вам нужен M такой, что младший 0 бит установлен в 1.

2

Другие решения

У меня было немного свободного времени, чтобы написать набросок, посмотрите:

struct node
{
std::vector<std::shared_ptr<node> > link;
};

int main()
{
int N = 4;

int M = 1<<N;
std::vector<std::shared_ptr<node> > tree(M, std::make_shared<node>());

for(int i=0;i<M;++i)
{
std::cout<<"node: "<<i<<" is connected to:\n";

for(int p=0;p<N;++p)
{
int j= (1<<p) ^ i;    //this is the evaluation you asked for
//it's the inverse of i ^ j = 2^p

if(j<=i) continue;
tree[i]->link.push_back(tree[j]);

std::cout<<j<<"  ";
}
std::cout<<std::endl;
}
}

DEMO

За N=4т.е. 2^4=16 узлы, программа печатает

node: 0 is connected to:
1  2  4  8
node: 1 is connected to:
3  5  9
node: 2 is connected to:
3  6  10
node: 3 is connected to:
7  11
node: 4 is connected to:
5  6  12
node: 5 is connected to:
7  13
node: 6 is connected to:
7  14
node: 7 is connected to:
15
node: 8 is connected to:
9  10  12
node: 9 is connected to:
11  13
node: 10 is connected to:
11  14
node: 11 is connected to:
15
node: 12 is connected to:
13  14
node: 13 is connected to:
15
node: 14 is connected to:
15
node: 15 is connected to:

Я надеюсь, что это то, что вы искали. Повеселись.

0

По вопросам рекламы ammmcru@yandex.ru
Adblock
detector