prim algorithm for some Graph structure

primtMST.cpp

// iPair ==>  Integer Pair
typedef std::pair<int, int> iPair;
std::vector<int> Graph::primtMST(int src)			// Taking vertex 0 as source
{
  // Create a priority queue to store vertices that
  // are being preinMST. This is weird syntax in C++.
  // Refer below link for details of this syntax
  // http://geeksquiz.com/implement-min-heap-using-stl/
  std::priority_queue< iPair, std::vector <iPair>, std::greater<iPair> > pq;


  // Create a vector for keys and initialize all
  // keys as infinite (INF)
  std::vector<int> key(m_vGraphVertexes.size(), INF);

  // To store parent array  which in turn store MST
  std::vector<int> parent(m_vGraphVertexes.size(), -1);

  // To keep track of vertices included in MST
  std::vector<bool> inMST(m_vGraphVertexes.size(), false);

  // Insert source itself in priority queue and initialize
  // its key as 0.
  pq.push(std::make_pair(0, src));
  key[src] = 0;

  /* Looping till priority queue becomes empty */
  while (!pq.empty())
  {
    // The first vertex in pair is the minimum key
    // vertex, extract it from priority queue.
    // vertex label is stored in second of pair (it
    // has to be done this way to keep the vertices
    // sorted key (key must be first item
    // in pair)
    int u = pq.top().second;
    pq.pop();

    inMST[u] = true;  // Include vertex in MST

                      // 'i' is used to get all adjacent vertices of a vertex
    for (auto i = m_vGraphVertexes[u].getNeighbours().begin(); i != m_vGraphVertexes[u].getNeighbours().end(); ++i)
    {
      // Get vertex label and weight of current adjacent
      // of u.
      int v = (*i).first;
      int weight = (*i).second;
      //  If v is not in MST and weight of (u,v) is smaller
      // than current key of v
      if (!inMST[v] && key[v] > weight)
      {
        // Updating key of v
        key[v] = weight;
        pq.push(std::make_pair(key[v], v));
        parent[v] = u;
      }
    }
  }

  //reserve the space
  m_vGraphMST.reserve(m_vGraphVertexes.size());
  // Copy vertexes (IT IS NOT THE BEST WAY, IS JUST TESTING)
  std::for_each(m_vGraphVertexes.begin(), m_vGraphVertexes.end(), [&](CGraphVertex & v)
  {
    CGraphVertex newVertex(v.getIndex(), v.getPtr());
    m_vGraphMST.push_back(newVertex);
  });

  //Copy edges of MST using parent array 
  for (int i = 1; i < m_vGraphMST.size(); ++i)
  {
    if (parent[i] != -1)
    {
      double d = vtkMath::Distance2BetweenPoints(m_vGraphVertexes[i].getPtr(), m_vGraphVertexes[parent[i]].getPtr());
      m_vGraphMST[i].link(m_vGraphMST[parent[i]].getIndex(), d);
      m_vGraphMST[parent[i]].link(m_vGraphMST[i].getIndex(), d);
    }
  }
  return parent;
}

//std::vector<Vertex>::iterator findVertexIndex(double* val, bool& res)
//{
//	std::vector<Vertex>::iterator it;
//	Vertex v(val);
//	it = std::find(m_vVertexes.begin(), m_vVertexes.end(), v);
//	if (it != m_vVertexes.end()) {
//		res = true;
//		return it;
//	}
//	else {
//		res = false;
//		return m_vVertexes.end();
//	}
//}

//void addEdge(int n1, int n2)
//{
//	bool foundNet1 = false, foundNet2 = false;
//	auto vit1 = findVertexIndex(n1, foundNet1);
//	int node1Index = -1, node2Index = -1;
//	if (!foundNet1)
//	{
//		Vertex v1(n1);
//		m_vVertexes.push_back(v1);
//		node1Index = m_vVertexes.size() - 1;
//	}
//	else
//	{
//		node1Index = vit1 - m_vVertexes.begin();
//	}
//	Vertices::iterator vit2 = findVertexIndex(n2, foundNet2);
//	if (!foundNet2)
//	{
//		Vertex v2(n2);
//		m_vVertexes.push_back(v2);
//		node2Index = m_vVertexes.size() - 1;
//	}
//	else
//	{
//		node2Index = vit2 - vertices.begin();
//	}

//	assert((node1Index > -1) && (node1Index <  vertices.size()));
//	assert((node2Index > -1) && (node2Index <  vertices.size()));

//	addEdgeIndices(node1Index, node2Index);
//}