C++ Graph Representation Problem

**Peter_APIIT** · December 29th, 2008, 02:55 AM

Hello to all expect programmer, i facing some difficulties to code graph data structure.

My code is use adjacency list to represent graph.

Vertex.h

Code:

template <typename T>
class vertex
{
private:
	// Number of edge
	int degree;
	// Vertex name
	std::string vertexID;
	// Vertex information
	T element;
	std::vector<edge> incidentEdge;
	/* 
		This used to represent/store all edges 
		incident(attach/link) from/to this vertex
	*/	
	
public:
	vertex();
	vertex(T element);
	

	~vertex();
};

edge.h

Code:

class edge
{
private:
	// Path's cost
	float weightage;
	std::string firstVertexID;
	std::string secondVertexID;

	/*	An edge in an undirected graph 
		is a set of two vertices
		
		An edge is placed twice, once for A->B
		B->A
	
	*/
	edge *toVertex;

public:
	edge();
	edge(float);
	edge(const edge&);
	edge& operator=(const edge&);

	void setEdge(float);
	float getEdge();
	~edge();

#endif

graph.h

Code:

template <typename T, class edgeType = edge>
class graph
{
private:
	vertex<T> aVertex;
	edgeType aEdge;
public:
	graph();
	graph(vertex<T>, edgeType);

	graph(const graph&);
	graph& operator=(const graph&)const;

	~graph();
};

Explanation
1. incidentEdge is represent all edge incident from a edge.
2. Class edge contain where from and to, its weightage.
3. template <typename T, class edgeType = edge>
edgeType used to represent directed or undirected graph.

My question is
1. How to represent undirected edge in C++ ? (Simple/Flexible)
I don't understand how a edge is placed twice.
2. Does my implementation correct ?

Thanks for your help.

**Peter_APIIT** · January 10th, 2009, 09:15 AM

Reference does not allow implicit conversion from const char* to string. How to solve this ?

This is my latest code/

Code:

template <typename T, class edgeType = edge>
class graph
{
private:
	std::vector<vertex*> allVertex;
public:
	graph();
	graph(const vertex<T>&);

	void Insert(const T&, const std::string&, 
		 const std::string&);
	void Remove(const std::string&);

	~graph();
};

// =============================================
template <typename T, class edgeType>
graph<T, edgeType>::graph() 
	: allVertex(vector<vertex*>()) 
{
}
// =============================================
template <typename T, class edgeType>
graph<T, edgeType>::graph(const vertex<T>& someVertex) 
			 : allVertex(someVertex),
					
{
}
// =============================================
template <typename T, class edgeType>
graph<T, edgeType>::~graph()
{
}
// =============================================
template <typename T, class edgeType>
void graph<T, edgeType>::Insert(const T& infoVertex, 
			const std::string& vertexName,
			const std::string& linkVertexID)
{
	vertex<T>* userVertex = new vertex<T>(infoVertex);
	userVertex->setVertexID(vertexName);

	
	if (this->allVertex.size() == 0 
		&& linkVertexID == "")
	{
		allVertex.push_back(userVertex);
	}
	else
	{
	}
}


template <typename T>
class vertex
{
private:
	// Number of edge incident from this vertex
	int degree;
	// Vertex name
	std::string vertexID;
	// Vertex information
	T element;
	std::vector<edge> incidentEdge;
	/* 
		This used to represent/store all edges 
		incident(attach/link) from/to this vertex
	*/	
	
public:
	vertex();
	vertex(const T& );

	void setDegree(int);
	void setVertexID(const std::string&);
	void setElement(const T&);
	void setIncidentEdge();
	
	~vertex();
};



class edge
{
private:
	// Path's cost
	float weightage;
	std::string firstVertexID;
	std::string secondVertexID;

	/*	An edge in an undirected graph 
		is a set of two vertices
		
		An edge is placed twice, once for A->B
		B->A
	
	*/

public:
	edge();
	edge(float);
	edge(const edge&);
	edge& operator=(const edge&);

	void setEdge(float);
	float getEdge();

	~edge();
};

error C2664: 'std::vector<_Ty>:

ush_back' : cannot convert parameter 1 from 'vertex<T> *' to 'vertex *const &' d:\c++\data structure\graph\graph\graph.h 56

Error is from this line: allVertex.push_back(userVertex);

Thanks for your help.

**Paul McKenzie** · January 10th, 2009, 11:41 PM

Originally Posted by Peter_APIIT

Reference does not allow implicit conversion from const char* to string.

What made you come up to that conclusion? The error you're showing us has nothing to do with strings or const char*.

How to solve this ?

Do you know why the error occured? What type is allVertex? What type are you trying to push_back() into allVertex? Is that type you're trying to push_back() the same as the type that allVertex() expects? That is exactly what the error message is saying to you -- the types are not the same.

Regards,

Paul McKenzie

**Peter_APIIT** · January 11th, 2009, 02:34 AM

Thanks for your help. Finally, i know why the type is not same.
I declare as this.

Code:

vertex<T>* userVertex = new vertex<T>(infoVertex);

Code:

std::vector<vertex* > allVertex;

Correction to this.

Code:

std::vector<vertex<T>* > allVertex;

Thanks.

This is my latest code.

Code:

#include <boost/shared_ptr.hpp>
#include <vector>

#include <string>
#include "Edge.h"

typedef boost::shared_ptr<edge> edgePtr;

template <typename T>
class vertex
{
private:
	// Number of edge incident from this vertex
	int degree;
	// Vertex name
	std::string vertexID;
	// Vertex information
	T element;
	
	std::vector<edgePtr> incidentEdge;
	
	/* 
		This used to represent/store all edges 
		incident(attach/link) from/to this vertex
	*/	
	
public:
	vertex();
	vertex(const T& );

	void decreaseDegree();

	void setDegree();
	void setDegree(int);
	void setVertexID(const std::string& );
	void setElement(const T&);
	void setIncidentEdge(boost::shared_ptr<edge>& );

	int getDegree();
	const std::string getVertexID();
	const T getElement();
	std::vector<edgePtr>& getIncidentEdge();

	
	~vertex();
};
// =============================================
template <typename T>
vertex<T>::vertex() : degree(0), 
				vertexID(std::string("")), 
				element(T()), 
				incidentEdge(vector<edgePtr>())
{
}
// =============================================
template <typename T>
vertex<T>::vertex(const T& info) : degree(0), 
				vertexID(std::string()), 
				element(info),
				incidentEdge(vector<edgePtr>())
{
}
// =============================================
template <typename T>
vertex<T>::~vertex()
{
}
// =============================================
template <typename T>
void vertex<T>::decreaseDegree()
{
	--degree;
}
// =============================================
template <typename T>
void vertex<T>::setDegree()
{
	++degree;
}
// =============================================
template <typename T>
void vertex<T>::setDegree(int myDegree)
{
	degree = myDegree;
}
// =============================================
template <typename T>
void vertex<T>::setVertexID(const std::string& vertexName)
{
	vertexID = vertexName;
}
// =============================================
template <typename T>
void vertex<T>::setElement(const T& info)
{
	element = info;
}
// =============================================
template <typename T>
void vertex<T>::setIncidentEdge(boost::shared_ptr<edge>& userEdge)
{
	incidentEdge.push_back(userEdge);
}
// =============================================
template <typename T>
int vertex<T>::getDegree()
{
	return this->degree;
}	
// =============================================
template <typename T>
const std::string vertex<T>::getVertexID()
{
	return this->vertexID;
}
// =============================================
template <typename T>
const T vertex<T>::getElement()
{
	return this->element;
}
// =============================================
template <typename T>
std::vector<edgePtr>& vertex<T>::getIncidentEdge()
{
	return this->incidentEdge;
}



#include <vector>


// Forward Declaration minimize file dependecies
class edge;

template <typename T>
class vertex;



template <typename T, class edgeType = edge>
class graph
{
private:

// shared_ptr's template parameter is object 
	typedef boost::shared_ptr<vertex<T> > 
		vertexPtr;
	std::vector<vertexPtr > allVertex;
	
public:
	graph();

	void Insert(const T&, const std::string&, 
		 const std::string&, const float);
	void Remove(const std::string&);

	void display()const;

	~graph();
};

// =============================================
template <typename T, class edgeType>
graph<T, edgeType>::graph() 
	: allVertex(vector<vertexPtr>()) 
{
}
// =============================================
template <typename T, class edgeType>
graph<T, edgeType>::~graph()
{
}
// =============================================
template <typename T, class edgeType>
void graph<T, edgeType>::Insert(const T& infoVertex, 
			const std::string& vertexName,
			const std::string& linkVertexID,
			const float userCost)
{
	vertexPtr userVertex(new vertex<T>(infoVertex));
	userVertex->setVertexID(vertexName);

	if (this->allVertex.size() == 0 
		&& linkVertexID == ""
		&& userCost == 0)
	{
		allVertex.push_back(userVertex);
	}
	else
	{
		for (size_t loop=0;loop<allVertex.size();
			++loop)
		{
			if (allVertex[loop]->getVertexID() 
				== linkVertexID)
			{
				// First set
				shared_ptr<edge> firstEdge(new edge());
				
				firstEdge->setWeightage(userCost);
				firstEdge->setFirstVertexID(allVertex[loop]->getVertexID());
				firstEdge->setSecondVertexID(vertexName);
				
				allVertex[loop]->setIncidentEdge(firstEdge);
				allVertex[loop]->setDegree();


				// Second set
				shared_ptr<edge> secondEdge(new edge());

				secondEdge->setWeightage(userCost);
				secondEdge->setFirstVertexID(vertexName);
				secondEdge->setSecondVertexID(allVertex[loop]->getVertexID());
				
				// here
				allVertex.push_back(userVertex);
				allVertex.at(allVertex.size()-1)->setIncidentEdge(secondEdge);
				allVertex[allVertex.size()-1]->setDegree();
			}
		}
	}
}
// =============================================
template <typename T, class edgeType>
void graph<T, edgeType>::Remove(const std::string& vertexID)
{
	size_t allVertexSize = allVertex.size();
	for (size_t loop=0;loop<allVertexSize;++loop)
	{
		if (allVertex[loop]->getVertexID() 
			== vertexID)
		{
			// Remove
			std::vector<edgePtr> myIncidentEdge;
			myIncidentEdge = 
				allVertex[loop]->getIncidentEdge();
			
			/* 
				Get all vertex incident from 
				target remove vertex	
				
			*/

			vector<string> decreaseVertex;
			for (size_t loop=0;
					loop<myIncidentEdge.size();
					++loop)
			{
				decreaseVertex.push_back
					(myIncidentEdge[loop]->getSecondVertexID());
			}
				
			typedef vector<edgePtr>::iterator vecIte; 
			vecIte	startIte = myIncidentEdge.begin();
			vecIte endtIte = myIncidentEdge.end();
			
			// Error delete in myIncidentEdge but not allVertex
			if (!myIncidentEdge.empty())
			{
				myIncidentEdge.erase(startIte, endtIte);
			}
			else 
			{
				cerr << "Empty Incident Edge Remove\n";
			}

			// To decrease degree
			for (size_t loop=0;
				loop<allVertex.size();++loop)
			{
				for (size_t sentinel=0;
					sentinel<decreaseVertex.size();
					++sentinel)
				{
					if (allVertex[loop]->getVertexID() 
						== decreaseVertex[sentinel])
					{
						allVertex[loop]->decreaseDegree();
					}
				}
			}
		}
	}
}
// =============================================
template <typename T, class edgeType>
void graph<T, edgeType>:: display()const
{
	cout << "\n\n";
	size_t vertexSize = allVertex.size();
	
	for (size_t loop=0;loop<vertexSize;++loop)
	{
		cout << allVertex[loop]->getVertexID()
			<< "["
			<< allVertex[loop]->getDegree()
			<< "]"
			<< " :"; 

		std::vector<edgePtr> myIncidentEdge;
		myIncidentEdge = allVertex[loop]->getIncidentEdge();
		
		size_t incidentEdgeSize = myIncidentEdge.size();
		for (size_t sentinel=0;sentinel<incidentEdgeSize;++sentinel)
		{
			cout << " " ;
			cout << myIncidentEdge[sentinel]->getSecondVertexID(); 	
		}
		cout << std::endl;
	}
}


int main()
{
	graph<string> aGrp;

// Insert(element stored,vertexID,linkVertexID, weightage);
	aGrp.Insert("1", "1", "", 0);
	aGrp.Insert("2", "2", "1", 2);
	aGrp.Insert("3", "3", "1", 2);
	aGrp.Insert("4", "4", "2", 2);

	aGrp.display();
	aGrp.Remove("2");
	aGrp.display();
}

Does my code look correct to you in terms of graph implementation ?

**Peter_APIIT** · January 12th, 2009, 11:37 PM

Beside the above question, i have an another question.

Here is the remove function for a graph.

Code:

template <typename T, class edgeType>
void graph<T, edgeType>::Remove(const std::string& vertexID)
{
	
	typedef vector<vertexPtr>::iterator aVeIte;
	aVeIte removeIte = allVertex.begin();
	aVeIte endIte = allVertex.end();
	
	size_t allVertexSize = allVertex.size();

	size_t loop=0;
	bool IsRemove = false;
	while (loop<allVertexSize && !IsRemove)
	{
		if (allVertex[loop]->getVertexID() 
			== vertexID)
		{
			// Get all incident edge from target remove vertex
			std::vector<edgePtr> myIncidentEdge;
			myIncidentEdge = 
				allVertex[loop]->getIncidentEdge();
			
			/* 
				Get all vertex incident from 
				target remove vertex	
				
			*/
			vector<string> decreaseVertex;
			for (size_t myLoop=0;
					myLoop<myIncidentEdge.size();
					++myLoop)
			{
				decreaseVertex.push_back
					(myIncidentEdge[myLoop]->getSecondVertexID());
			}
				
			typedef vector<edgePtr>::iterator vecIte; 
			vecIte	startIte = myIncidentEdge.begin();
			vecIte endtIte = myIncidentEdge.end();
			
			// Remove incident edge from target vertex
			// Error delete in myIncidentEdge but not allVertex
			if (!myIncidentEdge.empty())
			{
				myIncidentEdge.erase(startIte, endtIte);
				allVertex[loop]->incidentEdge.erase(
					allVertex[loop]->incidentEdge.begin(), 
					allVertex[loop]->incidentEdge.end());
			}
			else 
			{
				cerr << "Empty Incident Edge Remove\n";
			}

			// To decrease degree
			for (size_t outerLoop=0;
				outerLoop<allVertex.size();++outerLoop)
			{
				for (size_t sentinel=0;
					sentinel<decreaseVertex.size();
					++sentinel)
				{
					if (allVertex[outerLoop]->getVertexID() 
						== decreaseVertex[sentinel])
					{
						allVertex[outerLoop]->decreaseDegree();
					}
				}
			}
			// Remove Target vertex
		//	allVertex.erase(allVertex.begin() + loop);
			IsRemove = true;
		}
		++loop;	
	}
}

Assume that the graph contain following value.
1[2]: 2-3
2[2]: 1-4
3[1]: 1
4[1]: 2

[1] = This represent the degree that edges incident from a particular vertex..

And now i want to remove vertex two(2).

As shown in the diagram above, i need to remove incident vertex edge from two which is the edge from two to one and two to four.

I have no problem remove a single particular vertex 2 in this case but i do have a problem remove edge of from two to one and two to four.

I try following code.

Code:

if (!myIncidentEdge.empty())
{
myIncidentEdge.erase(startIte, endtIte);	
}
else 
{
	cerr << "Empty Incident Edge Remove\n";
}

Remove was successful in myIncidentEdge variable but not in the vertex class incidentEdge. In others words, the remove is not reflected in an object that contain all vertex where each vertex contains edge(allVertex).

Remove not successful but the below does remove the target edges.

The incidentEdge has change from private to public in vertex class in this case.

Code:

if (!myIncidentEdge.empty())
{
allVertex[loop]->incidentEdge.erase(
     allVertex[loop]->incidentEdge.begin(), 
     allVertex[loop]->incidentEdge.end());
}
else 
{
	cerr << "Empty Incident Edge Remove\n";
}

Does this related to ownership management of smart pointer since i use boost::shared_ptr from boost?

As an references, the insert() function was attached at below section.

Code:

typedef boost::shared_ptr<vertex<T> > 
		vertexPtr;
	std::vector<vertexPtr > allVertex;

template <typename T, class edgeType>
void graph<T, edgeType>::Insert(const T& infoVertex, 
			const std::string& vertexName,
			const std::string& linkVertexID,
			const float userCost)
{
	vertexPtr userVertex(new vertex<T>(infoVertex));
	userVertex->setVertexID(vertexName);

	if (this->allVertex.size() == 0 
		&& linkVertexID == ""
		&& userCost == 0)
	{
		allVertex.push_back(userVertex);
	}
	else
	{
		for (size_t loop=0;loop<allVertex.size();
			++loop)
		{
			if (allVertex[loop]->getVertexID() 
				== linkVertexID)
			{
				// First set
				shared_ptr<edge> firstEdge(new edge());
				
				firstEdge->setWeightage(userCost);
				firstEdge->setFirstVertexID(allVertex[loop]->getVertexID());
				firstEdge->setSecondVertexID(vertexName);
				
				allVertex[loop]->setIncidentEdge(firstEdge);
				allVertex[loop]->setDegree();


				// Second set
				shared_ptr<edge> secondEdge(new edge());

				secondEdge->setWeightage(userCost);
				secondEdge->setFirstVertexID(vertexName);
				secondEdge->setSecondVertexID(allVertex[loop]->getVertexID());
				
				// here
				allVertex.push_back(userVertex);
				allVertex.at(allVertex.size()-1)->setIncidentEdge(secondEdge);
				allVertex[allVertex.size()-1]->setDegree();
			}
		}
	}
}

This is all my code.

Code:

class edge
{
private:
	// Path's cost
	float weightage;
	std::string firstVertexID;
	std::string secondVertexID;

	/*	An edge in an undirected graph 
		is a set of two vertices
		
		An edge is placed twice, once for A->B
		B->A
	
	*/

public:
	edge();
	edge(float);
	edge(const edge&);
	edge& operator=(const edge&);

	void setWeightage(float);
	float getWeightage();

	void setFirstVertexID(const std::string&);
	void setSecondVertexID(const std::string&);

	std::string getFirstVertexID();
	std::string getSecondVertexID();

	~edge();
};


#include <boost/shared_ptr.hpp>
#include <vector>

#include <string>
#include "Edge.h"

typedef boost::shared_ptr<edge> edgePtr;

template <typename T>
class vertex
{
private:
	// Number of edge incident from this vertex
	int degree;
	// Vertex name
	std::string vertexID;
	// Vertex information
	T element;
	

	
	/* 
		This used to represent/store all edges 
		incident(attach/link) from/to this vertex
	*/	
	
public:
	std::vector<edgePtr> incidentEdge;

	vertex();
	vertex(const T& );

	void decreaseDegree();

	void setDegree();
	void setDegree(int);
	void setVertexID(const std::string& );
	void setElement(const T&);
	void setIncidentEdge(boost::shared_ptr<edge>& );

	int getDegree();
	const std::string getVertexID();
	const T getElement();
	std::vector<edgePtr>& getIncidentEdge();

	
	~vertex();
};
// =============================================
template <typename T>
vertex<T>::vertex() : degree(0), 
				vertexID(std::string("")), 
				element(T()), 
				incidentEdge(vector<edgePtr>())
{
}
// =============================================
template <typename T>
vertex<T>::vertex(const T& info) : degree(0), 
				vertexID(std::string()), 
				element(info),
				incidentEdge(vector<edgePtr>())
{
}
// =============================================
template <typename T>
vertex<T>::~vertex()
{
}
// =============================================
template <typename T>
void vertex<T>::decreaseDegree()
{
	--degree;
}
// =============================================
template <typename T>
void vertex<T>::setDegree()
{
	++degree;
}
// =============================================
template <typename T>
void vertex<T>::setDegree(int myDegree)
{
	degree = myDegree;
}
// =============================================
template <typename T>
void vertex<T>::setVertexID(const std::string& vertexName)
{
	vertexID = vertexName;
}
// =============================================
template <typename T>
void vertex<T>::setElement(const T& info)
{
	element = info;
}
// =============================================
template <typename T>
void vertex<T>::setIncidentEdge(boost::shared_ptr<edge>& userEdge)
{
	incidentEdge.push_back(userEdge);
}
// =============================================
template <typename T>
int vertex<T>::getDegree()
{
	return this->degree;
}	
// =============================================
template <typename T>
const std::string vertex<T>::getVertexID()
{
	return this->vertexID;
}
// =============================================
template <typename T>
const T vertex<T>::getElement()
{
	return this->element;
}
// =============================================
template <typename T>
std::vector<edgePtr>& vertex<T>::getIncidentEdge()
{
	return this->incidentEdge;
}



#include <vector>


// Forward Declaration minimize file dependecies
class edge;

template <typename T>
class vertex;

template <typename T, class edgeType = edge>
class graph
{
private:

// shared_ptr's template parameter is object 
	typedef boost::shared_ptr<vertex<T> > 
		vertexPtr;
	std::vector<vertexPtr > allVertex;
	
public:
	graph();

	void Insert(const T&, const std::string&, 
		 const std::string&, const float);
	void Remove(const std::string&);

	void display()const;

	~graph();
};

// =============================================
template <typename T, class edgeType>
graph<T, edgeType>::graph() 
	: allVertex(vector<vertexPtr>()) 
{
}
// =============================================
template <typename T, class edgeType>
graph<T, edgeType>::~graph()
{
}
// =============================================
template <typename T, class edgeType>
void graph<T, edgeType>::Insert(const T& infoVertex, 
			const std::string& vertexName,
			const std::string& linkVertexID,
			const float userCost)
{
	vertexPtr userVertex(new vertex<T>(infoVertex));
	userVertex->setVertexID(vertexName);

	if (this->allVertex.size() == 0 
		&& linkVertexID == ""
		&& userCost == 0)
	{
		allVertex.push_back(userVertex);
	}
	else
	{
		for (size_t loop=0;loop<allVertex.size();
			++loop)
		{
			if (allVertex[loop]->getVertexID() 
				== linkVertexID)
			{
				// First set
				shared_ptr<edge> firstEdge(new edge());
				
				firstEdge->setWeightage(userCost);
				firstEdge->setFirstVertexID(allVertex[loop]->getVertexID());
				firstEdge->setSecondVertexID(vertexName);
				
				allVertex[loop]->setIncidentEdge(firstEdge);
				allVertex[loop]->setDegree();


				// Second set
				shared_ptr<edge> secondEdge(new edge());

				secondEdge->setWeightage(userCost);
				secondEdge->setFirstVertexID(vertexName);
				secondEdge->setSecondVertexID(allVertex[loop]->getVertexID());
				
				// here
				allVertex.push_back(userVertex);
				allVertex.at(allVertex.size()-1)->setIncidentEdge(secondEdge);
				allVertex[allVertex.size()-1]->setDegree();
			}
		}
	}
}
// =============================================
template <typename T, class edgeType>
void graph<T, edgeType>::Remove(const std::string& vertexID)
{
	
	typedef vector<vertexPtr>::iterator aVeIte;
	aVeIte removeIte = allVertex.begin();
	aVeIte endIte = allVertex.end();
	
	size_t allVertexSize = allVertex.size();

	size_t loop=0;
	bool IsRemove = false;
	while (loop<allVertexSize && !IsRemove)
	{
		if (allVertex[loop]->getVertexID() 
			== vertexID)
		{
			// Get all incident edge from target remove vertex
			std::vector<edgePtr> myIncidentEdge;
			myIncidentEdge = 
				allVertex[loop]->getIncidentEdge();
			
			/* 
				Get all vertex incident from 
				target remove vertex	
				
			*/
			vector<string> decreaseVertex;
			for (size_t myLoop=0;
					myLoop<myIncidentEdge.size();
					++myLoop)
			{
				decreaseVertex.push_back
					(myIncidentEdge[myLoop]->getSecondVertexID());
			}
				
			typedef vector<edgePtr>::iterator vecIte; 
			vecIte	startIte = myIncidentEdge.begin();
			vecIte endtIte = myIncidentEdge.end();
			
			// Remove incident edge from target vertex
			// Error delete in myIncidentEdge but not allVertex
			if (!myIncidentEdge.empty())
			{
				myIncidentEdge.erase(startIte, endtIte);
				allVertex[loop]->incidentEdge.erase(
					allVertex[loop]->incidentEdge.begin(), 
					allVertex[loop]->incidentEdge.end());
			}
			else 
			{
				cerr << "Empty Incident Edge Remove\n";
			}

			// To decrease degree
			for (size_t outerLoop=0;
				outerLoop<allVertex.size();++outerLoop)
			{
				for (size_t sentinel=0;
					sentinel<decreaseVertex.size();
					++sentinel)
				{
					if (allVertex[outerLoop]->getVertexID() 
						== decreaseVertex[sentinel])
					{
						allVertex[outerLoop]->decreaseDegree();
					}
				}
			}
			// Remove Target vertex
		//	allVertex.erase(allVertex.begin() + loop);
			IsRemove = true;
		}
		++loop;	
	}
}
// =============================================
template <typename T, class edgeType>
void graph<T, edgeType>:: display()const
{
	cout << "\n\n";
	size_t vertexSize = allVertex.size();
	
	for (size_t loop=0;loop<vertexSize;++loop)
	{
		cout << allVertex[loop]->getVertexID()
			<< "["
			<< allVertex[loop]->getDegree()
			<< "]"
			<< " :"; 

		std::vector<edgePtr> myIncidentEdge;
		myIncidentEdge = allVertex[loop]->getIncidentEdge();
		
		size_t incidentEdgeSize = myIncidentEdge.size();
		for (size_t sentinel=0;sentinel<incidentEdgeSize;++sentinel)
		{
			cout << " " ;
			cout << myIncidentEdge[sentinel]->getSecondVertexID(); 	
		}
		cout << std::endl;
	}
}

Thanks for your help.

**Peter_APIIT** · January 13th, 2009, 02:55 AM

2. Does my code look correct to you in terms of graph implementation ?

Code:

std::vector<edgePtr> incidentEdge;

I found this quite difficult for me to do searching. Instead of storing edges, i think i should change to storing vertices.
Then, vertex class can store a bool IsVisited;

What do you think ?

Thanks.

**Peter_APIIT** · January 16th, 2009, 11:28 PM

I hope someone can really help me.

**Paul McKenzie** · January 17th, 2009, 01:24 AM

Originally Posted by Peter_APIIT

I hope someone can really help me.

Have you used the debugger? If so, what have you seen and what measures have you taken to fix whatever is wrong?

Having said this, here is some advice in general:

1) That is a lot of code that you wrote that you claim you need help for. I doubt anyone would have the time to actually take the code, compile, and run it. If so, good for them, but don't expect help with all of that code.

2) Given all the code that you wrote, at this stage, you should have been able to diagnose your own problems. There is a threshold that programmers must reach when they write their own code, and that threshold is when they get to the stage where they can solve their own programming problems. In all honesty, your code is at an advanced enough stage where you are supposed to figure these problems out yourself.

Regards,

Paul McKenzie

**Peter_APIIT** · January 17th, 2009, 11:04 PM

Yes, i do use debugger.

I found the problem and i solve it with declare the incidentEdge as public scope and directly delete with allVertex. Therefore, i looking for another better approach and Why this thing happen ?

Let me explain the problem as clear as i can.

Code:

template <typename T>
std::vector<edgePtr>& vertex<T>::getIncidentEdge()
{
	return this->incidentEdge;
}

std::vector<edgePtr> myIncidentEdge;
myIncidentEdge = allVertex[loop]->getIncidentEdge();

myIncidentEdge.erase(startIte, endtIte);

The problem is i what i erase in myIncidentEdge is not reflected in allVertex->incidentEdge.

But if i move the incidentEdge to public scope vertex class. Then, i remove it like this.

Code:

allVertex[loop]->incidentEdge.erase(
		allVertex[loop]->incidentEdge.begin(), 
		allVertex[loop]->incidentEdge.end());

and it has changes in allVertex.

The visual debugger shown myIncidnetEdge has nothing after erase.

2. Does my implementation look correct in term of graph representation ?
Thanks for your help.

**Peter_APIIT** · January 19th, 2009, 04:14 AM

Problem solved but not the second question.

2. Does my implementation look correct in term of graph representation ?

Vertex class stored a vector type of edge which incident from this particular vertex or i should store a individual vertex(Vertex 2 or 3 incident from 1)

1[2]: 2, 3 (vertex 2 and 3 cannot delete here)
2[2]: 1, 4
3[1]

Thanks for your help.

**Peter_APIIT** · January 21st, 2009, 04:16 AM

3. As pointed out by Scoott Meyers, we should not return pointer or references to private data.

My question is should i balance between access control or performance since references does not create a new copy ?

Below is my situation.

Code:

private:
std::vector<vertexPtr> allVertex;
public:	
const std::vector<typename myStd::graph<T>::vertexPtr>& getAllVertex()const;

template <typename T>
bool BFS(const graph<T>&, const std::string&, 
	const std::string& );

std::vector<typename myStd::graph<T>::vertexPtr> userVertex;
	userVertex = myGrp.getAllVertex();

The BFS is non MF, i called the getAllVertex() inside the definition and assign to a local vector.

This indirectly allow me alter the private data due to return references.

What is your opinion?
Create a new copy(value) or references.

Thanks for your help.

**Peter_APIIT** · January 24th, 2009, 10:07 PM

All problem previous discuss has been solved but now the new problem arise is

i have a graph class template;

Code:

template <typename T, class edgeType = edge>
class graph
{	
public:
/*
  shared_ptr's template parameter is object 
  and not pointer to object
*/
	typedef boost::shared_ptr<vertex<T> > 
		vertexPtr;
private:

	std::vector<vertexPtr> allVertex;

I want that when different type of edgeType is supplied, then i want instantiated different type of vertexPtr.

I have two type of edgeType, one is edge(undirected) and arcs(Directed).

Whenever user supplied, graph<int, arcs> DAG;, then in the

Code:

typedef boost::shared_ptr<arcs> arcsPtr;
typedef boost::shared_ptr<vertex<T, arcsPtr> > vertexPtr;

should have arcsPtr.

Then, if user graph<int> supplied this, then default vertexPtr should be used.

I hope this make sense to you all.

Traits or CRTP or any design patterns is greatly appreciated by me.

Thanks for your help.

Thread: C++ Graph Representation Problem

Thread Tools

Display

C++ Graph Representation Problem

Re: C++ Graph Representation Problem

Re: C++ Graph Representation Problem

Re: C++ Graph Representation Problem

Re: C++ Graph Representation Problem

Re: C++ Graph Representation Problem

Re: C++ Graph Representation Problem

Re: C++ Graph Representation Problem

Re: C++ Graph Representation Problem

Re: C++ Graph Representation Problem

Re: C++ Graph Representation Problem

Re: C++ Graph Representation Problem

Posting Permissions