title: Fast algorithm for generating Directed Acyclic Graph
body: <p>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 &lt; 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:</p>
  
  <pre><code>#include &lt;iostream&gt;
  #include &lt;vector&gt;
  #include &lt;math.h&gt;
  typedef unsigned int unint;
  using namespace std;
  class Node
  {
      friend class DAG;
  private:
      unint value;
      vector&lt;Node* &gt; neighbourTo;
      vector&lt;Node* &gt; neighbors;
  public:
      Node(unint );
  };
  Node::Node(unint _value)
      : value(_value) {}
  class DAG
  {
  private:
      int noNodes;
      vector&lt;Node* &gt; nodes;
  public:
      DAG(int );
      void initializeNodes(int ,int );
      int isPowerOf2(unsigned int );
      int getMaxNaighbourTo(int );
      int getMinNeighbor(int );
      int numberOfPathsLengthK(int );
      int recursion(Node&amp; , int );
      void print();
  };
  DAG::DAG(int size)
  {
      noNodes = size;
  
      nodes.resize(noNodes);
      int i, j;
  
      initializeNodes(0, noNodes-1);
      for(i = 0; i &lt; noNodes-1; i++)
      {
          for(j = i+1; j &lt; noNodes; j++)
          {
              if(isPowerOf2(i ^ j))
              {
                  nodes[i]-&gt;neighbors.push_back(nodes[j]);
                  nodes[j]-&gt;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) &amp;&amp; !(value &amp; (value - 1)));
  }
  int DAG::getMaxNaighbourTo(int index)
  {
      if(index &gt; 0 &amp;&amp; index &lt;= (noNodes-1))
      {
          int size = nodes[index]-&gt;neighbourTo.size();
          return nodes[index]-&gt;neighbourTo[size-1]-&gt;value;
      }
      return -1;
  }
  int DAG::getMinNeighbor(int index)
  {
      if(index &gt;= 0 &amp;&amp; index &lt; (noNodes-1))
          return nodes[index]-&gt;neighbors[0]-&gt;value;
      return -1;
  }
  int DAG::numberOfPathsLengthK(int K)
  {
      if(K &lt;= 0)
          return 0;
      long int paths = 0;
      for(int i = 0; i &lt; nodes.size(); i++)
      {
          paths += recursion(*nodes[i], K - 1);
      }
      return (paths % 100003);
  }
  int DAG::recursion(Node&amp; node, int K)
  {
      if( K &lt;= 0 )
          return node.neighbors.size();
      else
      {
          long int paths = 0;
          for(int i = 0; i &lt; node.neighbors.size(); i++)
          {
              paths += recursion(*node.neighbors[i], K - 1);
          }
          return paths;
      }
  }
  void DAG::print()
  {
      for(int i = 0; i &lt; nodes.size(); i++)
      {
          cout &lt;&lt; "Node: " &lt;&lt; nodes[i]-&gt;value &lt;&lt; "\tNeighbors: ";
          for(int j = 0; j &lt; nodes[i]-&gt;neighbors.size(); j++)
          {
              cout &lt;&lt; nodes[i]-&gt;neighbors[j]-&gt;value &lt;&lt; " ";
          }
          cout &lt;&lt; endl;
      }
  }
  int main()
  {
      int
      N, M, K,
      i, j;
      cin &gt;&gt; N &gt;&gt; M &gt;&gt; K;
      DAG graf(pow(2, N));
      graf.print();
      cout &lt;&lt; "==1==" &lt;&lt; endl;
      cout &lt;&lt; graf.getMaxNaighbourTo(M) &lt;&lt; endl;
      cout &lt;&lt; "==2==" &lt;&lt; endl;
      cout &lt;&lt; graf.getMinNeighbor(M) &lt;&lt; endl;
      cout &lt;&lt; "==3==" &lt;&lt; endl;
      cout &lt;&lt; graf.numberOfPathsLengthK(K) &lt;&lt; endl;
      return 0;
  }
  </code></pre>
  
  <p>Here is a simple output:</p>
  
  <pre><code>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
  </code></pre>
  
  <p>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.</p>