C++ Graph Representation Problem
CodeGuru Home VC++ / MFC / C++ .NET / C# Visual Basic VB Forums Developer.com
Results 1 to 12 of 12

Thread: C++ Graph Representation Problem

  1. #1
    Join Date
    Apr 2007
    Location
    Mars NASA Station
    Posts
    1,436

    C++ Graph Representation Problem

    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.
    Thanks for your help.

  2. #2
    Join Date
    Apr 2007
    Location
    Mars NASA Station
    Posts
    1,436

    Re: C++ Graph Representation Problem

    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.
    Thanks for your help.

  3. #3
    Join Date
    Apr 1999
    Posts
    27,426

    Re: C++ Graph Representation Problem

    Quote Originally Posted by Peter_APIIT View Post
    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

  4. #4
    Join Date
    Apr 2007
    Location
    Mars NASA Station
    Posts
    1,436

    Re: C++ Graph Representation Problem

    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 ?
    Last edited by Peter_APIIT; January 12th, 2009 at 04:27 AM.
    Thanks for your help.

  5. #5
    Join Date
    Apr 2007
    Location
    Mars NASA Station
    Posts
    1,436

    Re: C++ Graph Representation Problem

    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.
    Last edited by Peter_APIIT; January 12th, 2009 at 10:43 PM.
    Thanks for your help.

  6. #6
    Join Date
    Apr 2007
    Location
    Mars NASA Station
    Posts
    1,436

    Re: C++ Graph Representation Problem

    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.
    Last edited by Peter_APIIT; January 13th, 2009 at 02:02 AM.
    Thanks for your help.

  7. #7
    Join Date
    Apr 2007
    Location
    Mars NASA Station
    Posts
    1,436

    Re: C++ Graph Representation Problem

    I hope someone can really help me.
    Thanks for your help.

  8. #8
    Join Date
    Apr 1999
    Posts
    27,426

    Re: C++ Graph Representation Problem

    Quote Originally Posted by Peter_APIIT View Post
    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

  9. #9
    Join Date
    Apr 2007
    Location
    Mars NASA Station
    Posts
    1,436

    Re: C++ Graph Representation Problem

    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.
    Last edited by Peter_APIIT; January 17th, 2009 at 10:39 PM.
    Thanks for your help.

  10. #10
    Join Date
    Apr 2007
    Location
    Mars NASA Station
    Posts
    1,436

    Re: C++ Graph Representation Problem

    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.
    Last edited by Peter_APIIT; January 21st, 2009 at 03:11 AM.
    Thanks for your help.

  11. #11
    Join Date
    Apr 2007
    Location
    Mars NASA Station
    Posts
    1,436

    Re: C++ Graph Representation Problem

    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.
    Thanks for your help.

  12. #12
    Join Date
    Apr 2007
    Location
    Mars NASA Station
    Posts
    1,436

    Re: C++ Graph Representation Problem

    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.
    Thanks for your help.

Posting Permissions

  • You may not post new threads
  • You may not post replies
  • You may not post attachments
  • You may not edit your posts
  •  


Azure Activities Information Page

Windows Mobile Development Center


Click Here to Expand Forum to Full Width

This is a CodeGuru survey question.


Featured


HTML5 Development Center