I have a problem and would appreciate your help. I have to generate a DAG with 2^N nodes which are valued form 0 to 2^(N-1), with this property: There is directed edge between nodes x and y (x and y being their values) if x < y and there is non-negative integer p such as x ⊕ y = 2^p. So far I've tried two nested for loops but this solution is too slow when it comes to number of nodes as high as 2^15. Here is a code snippet:
#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;
}
Here is a simple output:
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 is a vector of Node pointers, and Node a is a class which holds the node value and two vectors, one Node pointers to the neighbors of the current node, and another is a Node pointers to the nodes that the current node is neighbor to. The above code is in C++. I apologize for any grammatical errors. English is not my mother tongue.
