title: Optimize Network Graph creation
body: <p>I have the following code that goes through a matrix of 188k x 188k rows of data and attempts to create a network graph out of it. The problem here is my algorithm is extremely slow (as expected since its quadratic). Is there a better way of doing this that I'm not seeing? I'm already thinking of using openMP to parallelize this but would be great if I don't have to.</p>
  
  <p>Here's whats true about my matrix - its symmetric, its over 188 thousand by 188 thousand, each value in the matrix corresponds to the edge weight So for example, an element aij is the weight of the edge between i and j. Here's my code:</p>
  
  <p>The graph creation:</p>
  
  <pre><code>typedef boost::adjacency_list
  &lt;
  boost::vecS,
  boost::vecS,
  boost::undirectedS,
  boost::property&lt;boost::vertex_name_t, std::string&gt;,
  boost::property&lt;boost::edge_weight_t, float&gt;,
  boost::property&lt;boost::graph_name_t, std::string&gt;
  &gt; UGraph;
  
  typedef UGraph::vertex_descriptor vertex_t;
  typedef UGraph::edge_descriptor edge_t;
  </code></pre>
  
  <p>Now the function creating the network:</p>
  
  <pre><code>    vertex_t u;
      vertex_t v;
      edge_t e;
  
      bool found=0;
      int idx =0;
  
      float cos_similarity;
      for(int p =1;p&lt;=adj_matrix.cols();p++){
  
              //using a previously created vector to track already created nodes
              if(std::find(created_nodes.begin(), created_nodes.end(), nodes[idx]) == created_nodes.end()){
                      u = add_vertex(nodes[idx], ug);
                      created_nodes.push_back(nodes[idx]);
              }else{
                      u = vertex(p,ug);
              }
              int jdx = 0;
  
              for(int q =1;q&lt;=adj_matrix.cols();q++){
  
                      if(p!=q){//NO LOOPS IN THIS GRAPH
                              //using a previously created vector to track already created nodes
                              if(std::find(created_nodes.begin(), created_nodes.end(), nodes[jdx]) == created_nodes.end()){
                              v = add_vertex(nodes[jdx], ug);
                      created_nodes.push_back(nodes[jdx]);
                              }else{
                                      u = vertex(q,ug);
                              }
  
  
                              tie(e, found) = edge(u, v, ug);
  
                              if(!found){//check that edge does not already exist
                                      cos_similarity = adj_matrix(p,q);
                                      fil&lt;&lt;cos_similarity&lt;&lt;endl;
                                      fil.flush();
                                      if(cos_similarity &gt;= 0.2609){ //only add edge if value of cell is greater than this threshold
                                              boost::add_edge(u,v,cos_similarity, ug);
                                              edge_out&lt;&lt;p&lt;&lt;" "&lt;&lt;q&lt;&lt;" "&lt;&lt;cos_similarity&lt;&lt;endl; //creating an edge-weight list for later use
                                      }
                              }
                      }
                      jdx++;
              }
              idx++;
      }
  </code></pre>