CGraph Class Reference

Undirected multi-graph. More...

#include <Graph.h>

Inheritance diagram for CGraph:

Public Member Functions
	CGraph (const UINT n)
	Constructor. More...
	~CGraph ()
	Destructor. More...
void	InsertEdge (const UINT i, const UINT j)
	Insert an edge. More...
UINT	BFSF (std::vector< UINT > &result)
	Breadth-first spanning forest. More...
void	PrintGraph ()
	Print the graph to a text file. More...

Protected Attributes
std::vector< CEdge * >	m_vEdgeList
	Edge list.
UINT	m_nNumEdges = 0
	Number of edges.
CVertex *	m_pVertexList = nullptr
	Vertex list.
UINT	m_nNumVerts = 0
	Number of vertices.
std::queue< CVertex * >	m_qBFSQueue
	Queue for breadth-first search.
CRandom	m_cRandom
	Random number generator.

Detailed Description

A multi-graph stored as a list of edges and an incidence list that consists of a list of indices into the edge list for each vertex consisting of the indices of the edges incident with it. The term multi-graph means that there can be multiple edges between two vertices.

Definition at line 102 of file Graph.h.

Constructor & Destructor Documentation

CGraph()

CGraph::CGraph

(

const UINT

n

)

Allocate space for and initialize the vertex list.

Parameters

n	Number of vertices.

Definition at line 145 of file Graph.cpp.

~CGraph()

CGraph::~CGraph

(

)

Free up space used in incidence list and edge list.

Definition at line 158 of file Graph.cpp.

Member Function Documentation

BFSF()

UINT CGraph::BFSF

(

std::vector< UINT > &

result

)

Find a random breadth-first spanning forest (BFSF).

Parameters

[out]

result

A vector of indices of the edges in a BFSF.

Returns

Number of trees in the spanning forest.

Definition at line 189 of file Graph.cpp.

InsertEdge()

void CGraph::InsertEdge	(	const UINT	i,
		const UINT	j
	)

Insert an edge between two vertices by appending an instance of CEdge at the end of the edge list and appending the index of that edge (which is the size of the edge list before insertion) to the incidence lists of the vertices. Self-edges and vertices out of range are ignored.

Parameters

i	The vertex at one end of the edge to be inserted.
j	The vertex at the other end of the edge to be inserted.

Definition at line 172 of file Graph.cpp.

PrintGraph()

void CGraph::PrintGraph

(

)

Print the graph to graph.txt, used to get the example in the paper.

Definition at line 233 of file Graph.cpp.