Graph.cpp

Go to the documentation of this file.

// MIT License
//
// Copyright (c) 2019 Ian Parberry
//
// Permission is hereby granted, free of charge, to any person obtaining a copy
// of this software and associated documentation files (the "Software"), to
// deal in the Software without restriction, including without limitation the
// rights to use, copy, modify, merge, publish, distribute, sublicense, and/or
// sell copies of the Software, and to permit persons to whom the Software is
// furnished to do so, subject to the following conditions:
//
// The above copyright notice and this permission notice shall be included in
// all copies or substantial portions of the Software.
//
// THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND, EXPRESS OR
// IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF MERCHANTABILITY,
// FITNESS FOR A PARTICULAR PURPOSE AND NONINFRINGEMENT. IN NO EVENT SHALL THE
// AUTHORS OR COPYRIGHT HOLDERS BE LIABLE FOR ANY CLAIM, DAMAGES OR OTHER
// LIABILITY, WHETHER IN AN ACTION OF CONTRACT, TORT OR OTHERWISE, ARISING
// FROM, OUT OF OR IN CONNECTION WITH THE SOFTWARE OR THE USE OR OTHER DEALINGS
// IN THE SOFTWARE.

#include "Graph.h"
#include "Random.h"
#include "Helpers.h"

// CEdge functions.


CEdge::CEdge(CVertex* p0, CVertex* p1, UINT index):
  m_pVertex0(p0), m_pVertex1(p1), m_nIndex(index){
} //constructor


CVertex* CEdge::GetNextVertex(CVertex* p){
  if(m_pVertex0 == p)return m_pVertex1;
  else if(m_pVertex1 == p)return m_pVertex0;
  else return nullptr;
} //GetNextVertex


UINT CEdge::GetIndex(){
  return m_nIndex;
} //GetIndex


void CEdge::Mark(bool b){
  m_bMarked = b;
} //Mark


bool CEdge::Marked(){
  return m_bMarked;
} //Marked


void CEdge::GetVertexIndices(UINT& i0, UINT& i1){
  i0 = m_pVertex0->GetIndex();
  i1 = m_pVertex1->GetIndex();
} //GetVertexIndices

// CVertex functions.

CVertex::CVertex(){
} //constructor


void CVertex::InsertAdjacency(CEdge* pEdge){
  if(pEdge == nullptr)return;
  m_vAdjacencyList.push_back(pEdge);
} //InsertAdjacency


void CVertex::SetIndex(const UINT n){
  m_nIndex = n;
} //SetIndex


UINT CVertex::GetIndex(){
  return m_nIndex;
} //GetIndex


void CVertex::Mark(bool b){
  m_bMarked = b;
} //Mark


bool CVertex::Marked(){
  return m_bMarked;
} //Marked


std::vector<CEdge*>* CVertex::GetAdjacencyList(){
  return &m_vAdjacencyList;
} //GetAdjacencyList


size_t CVertex::GetDegree(){
  return m_vAdjacencyList.size();
} //GetDegree

// CGraph functions.


CGraph::CGraph(const UINT n):
  m_nNumVerts(n)
{
  m_pVertexList = new CVertex[n];

  for(UINT i=0; i<n; i++)
    m_pVertexList[i].SetIndex(i);

  m_cRandom.srand();
} //constructor


CGraph::~CGraph(){
  delete [] m_pVertexList;

  for(auto p: m_vEdgeList)
    delete p;
} //destructor


void CGraph::InsertEdge(const UINT i, const UINT j){
  if(i >= m_nNumVerts || j >= m_nNumVerts || i == j)return; //bail out

  CVertex* p0 = &m_pVertexList[i];
  CVertex* p1 = &m_pVertexList[j];

  CEdge* pEdge = new CEdge(p0, p1, m_nNumEdges++);

  m_vEdgeList.push_back(pEdge); //append edge to edge list
  p0->InsertAdjacency(pEdge); //append edge to adjacency list of first vertex
  p1->InsertAdjacency(pEdge); //append edge to adjacency list of second vertex
} //InsertEdge


UINT CGraph::BFSF(std::vector<UINT>& result){
  UINT numtrees = 0; //number of trees in spanning forest

  for(UINT i=0; i<m_nNumVerts; i++){
    if(!m_pVertexList[i].Marked()){
      m_qBFSQueue.push(&m_pVertexList[i]);
      m_pVertexList[i].Mark();

      while(!m_qBFSQueue.empty()){
        CVertex* current = m_qBFSQueue.front(); //get next queue element
        m_qBFSQueue.pop(); //remove from queue

        std::vector<CEdge*>* pAdjList = current->GetAdjacencyList(); //shorthand

        //random permutation of adjacency list

        const int n = (int)pAdjList->size();
        auto& adjacencylist = *pAdjList;

        for(int i=0; i<n-1; i++)
          std::swap(adjacencylist[i], adjacencylist[m_cRandom.randn(i, n-1)]);
    
        for(CEdge* pEdge: *pAdjList){ //for edges incident with current vertex
          CVertex* next = pEdge->GetNextVertex(current); //vertex at other end

          if(next != nullptr && !next->Marked()){ //if next vertex is unvisited
            result.push_back(pEdge->GetIndex()); //append edge index to  result
            m_qBFSQueue.push(next); //recurse on next vertex 
            next->Mark();
          } //if
        } //for
      } //while
    } //if

    numtrees++; //one more tree in the forest
  } //for

  //PrintGraph();

  return numtrees;
} //BFSF


void CGraph::PrintGraph(){
  FILE* output = nullptr;
  fopen_s(&output, "graph.txt", "wt");

  if(output != 0){
    fprintf_s(output, "%d vertices, %d edges\n", m_nNumVerts, m_nNumEdges);

    for(CEdge* p: m_vEdgeList){
      UINT i, j;
      p->GetVertexIndices(i, j);
      fprintf(output, "(%u, %u)\n", i, j);
    } //for

    fclose(output);
  } //if
} //PrintGraph