C++ Graph Representation Problem
 CodeGuru Home VC++ / MFC / C++ .NET / C# Visual Basic VB Forums Developer.com

# Thread: C++ Graph Representation Problem

1. Senior Member
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
*/

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 ?

2. Senior Member
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,
{
vertex<T>* userVertex = new vertex<T>(infoVertex);
userVertex->setVertexID(vertexName);

if (this->allVertex.size() == 0
{
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
*/

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);

3. Elite Member Power Poster
Join Date
Apr 1999
Posts
27,449

## Re: C++ Graph Representation Problem

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

4. Senior Member
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
*/

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 float userCost)
{
vertexPtr userVertex(new vertex<T>(infoVertex));
userVertex->setVertexID(vertexName);

if (this->allVertex.size() == 0
&& userCost == 0)
{
allVertex.push_back(userVertex);
}
else
{
for (size_t loop=0;loop<allVertex.size();
++loop)
{
if (allVertex[loop]->getVertexID()
{
// 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;

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.

5. Senior Member
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 float userCost)
{
vertexPtr userVertex(new vertex<T>(infoVertex));
userVertex->setVertexID(vertexName);

if (this->allVertex.size() == 0
&& userCost == 0)
{
allVertex.push_back(userVertex);
}
else
{
for (size_t loop=0;loop<allVertex.size();
++loop)
{
if (allVertex[loop]->getVertexID()
{
// 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
*/

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 float userCost)
{
vertexPtr userVertex(new vertex<T>(infoVertex));
userVertex->setVertexID(vertexName);

if (this->allVertex.size() == 0
&& userCost == 0)
{
allVertex.push_back(userVertex);
}
else
{
for (size_t loop=0;loop<allVertex.size();
++loop)
{
if (allVertex[loop]->getVertexID()
{
// 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;
}
}```
Last edited by Peter_APIIT; January 12th, 2009 at 10:43 PM.

6. Senior Member
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.

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

## Re: C++ Graph Representation Problem

I hope someone can really help me.

8. Elite Member Power Poster
Join Date
Apr 1999
Posts
27,449

## Re: C++ Graph Representation Problem

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

9. Senior Member
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 ?
Last edited by Peter_APIIT; January 17th, 2009 at 10:39 PM.

10. Senior Member
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]

Last edited by Peter_APIIT; January 21st, 2009 at 03:11 AM.

11. Senior Member
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.

Create a new copy(value) or references.

12. Senior Member
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.

#### Posting Permissions

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