Hello to all, i have difficulties in coding the graph problem.
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.
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.
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.
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 complete 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;
}
}
2. Does my code look correct to you in terms of graph implementation ?
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.
13-Jan-2009, 23:57
Problems with the Navy (Officers) by crystalattice
Similar Threads
