C++ Graph Representation Problem

 DevX Home Today's Headlines   Articles Archive   Tip Bank   Forums

# Thread: C++ Graph Representation Problem

1. Registered User
Join Date
May 2007
Posts
843

## 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 incident from the 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(T element);

~vertex();
};```

edge.h

Code:
```/* arcs is directed edge
edge is undirected
*/
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();
};```
graph.h

Code:
```template <typename T, class edgeType = edge>
class graph
{
private:
std::vector<vertex*> allVertex;
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. Registered User
Join Date
Dec 2007
Posts
401
> How to represent undirected edge in C++ ? (Simple/Flexible)

here is a simple (not the most efficient) way.
in each node, have two separate edge sequences; one having all the out-edges and another having the in-edges.
treat an undirected graph as a bidirectional graph; each edge will appear in both an out-edge and in-edge list

for more flexible alternatives, see:
http://www.boost.org/doc/libs/1_37_0...uick_tour.html
http://www.boost.org/doc/libs/1_37_0...ency_list.html

3. Registered User
Join Date
May 2007
Posts
843
Do you say something like this ?

1: 2
2: 1

That's means when i want to insert vertex 2 connected to vertex 1(1 to 2). I also need to insert 1 in order for 2 to 1.

Is this was you saying ?

Does my implementation correct or any suggestion ?

Code:
```aGrp.Insert("asd", "", "");
template <typename T, class edgeType>
void graph<T, edgeType>::Insert(const T& infoVertex,
const std::string& vertexName,
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>::push_back' : cannot convert parameter 1 from 'vertex<T> *' to 'vertex *const &' d:\c++\data structure\graph\graph\graph.h 56
Thanks.
Last edited by Peter_APIIT; 01-05-2009 at 05:57 AM. Reason: Add some information

4. Registered User
Join Date
May 2007
Posts
843
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 complete code.

Code:
```class edge
{
private:
float weightage;
std::string firstVertexID;
std::string secondVertexID;
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>
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);
}

#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;
}
}```

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; 01-15-2009 at 05:51 AM.

5. Registered User
Join Date
May 2007
Posts
843
I hope someone can help me.

6. Senior Member
Join Date
Dec 2003
Posts
3,366
I dont know. Looking correct and being correct are just a semicolen apart. Graphs are pretty simple *data structures* and I am sure your class handles *that* OK, but the associated algorithms are extremely complex. What you have seems ok, but I have no idea, what happens when you try to do something with it all? Can you test it and let us know if theres a problem we can look for?

Making a marked field for visited nodes is valid and should work, or you can get barbaric with it and make a second data structure to test for simple stuff like "is value X in that cloud of data??" --- that is my normal approach to such things, a pointer in a linear data structure to all the nodes so you can get to any of em fast and can do things like sort, search, etc simply by just sorting a list of pointers etc.

7. Registered User
Join Date
May 2007
Posts
843
I have two problem bother me right now.

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

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]

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.

A billion thanks for your help.

8. Senior Member
Join Date
Dec 2003
Posts
3,366
1) the class looks like it implements a graph to me.

2) If you need to access it, modify it, etc, make it public. I hate having to hack someones class to get at private data, if the user needs it, it needs to be public. If you do not like that, you can make do nothing setter/getter functions that effectively make it public while pretending to hide the very data they return for "good design". I only make getters and setters if they do something (testing for valid values). But you probably do not want to follow me on this. Generally, most folks will say make all data private then turn around and expose it with functions to make it public again, effectively.

9. Registered User
Join Date
May 2007
Posts
843
If you do not like that, you can make do nothing setter/getter functions that effectively make it public while pretending to hide the very data they return for "good design"
Are you mean that getter() function is a method to access private data(seem to be private) but they are actually is public ?

Code:
```template <typename T>
bool myStd::BFS(const graph<T>& myGrp,
const std::string& startVertex,
const std::string& endVertex)
{
std::queue<myStd::graph<T>::vertexPtr> cont;

int totalVertex = static_cast<int>(myGrp.getAllVertex().size()),
loop=0;
bool isFound = false;

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

// Search start vertex and push it to queue
/*	while (loop<totalVertex && !isFound)
{
if (userVertex[loop]->getVertexID()
== startVertex)
{
cont.push(userVertex[loop]);
isFound = true;
}
++loop;
}
*/
cont.push(userVertex[0]);

// Start operation on queue
boost::shared_ptr<vertex<T> > aVertex;
bool isConnected = false;

while (!cont.empty() && !isConnected)
{
aVertex = cont.front();
cont.pop();

int edgeSize = static_cast<int>(aVertex->getIncidentEdge().size());
std::vector<edgePtr> myEdge;
myEdge = aVertex->getIncidentEdge();

vector<string> incidentVertex;

for (int loop=0;loop<edgeSize;++loop)
{
if (myEdge[loop]->getSecondVertexID() == endVertex)
{
isConnected = true;
}
else
{
// enqueue incident vertex string
incidentVertex.push_back(myEdge[loop]->getSecondVertexID());
}
}

// push incident vertex to cont
int counterLoop=0;
bool isAllPush = false;
while (counterLoop<totalVertex && !isAllPush)
{
int innerLoop=0;
while (innerLoop<static_cast<int>(incidentVertex.size())
&& !incidentVertex.empty())
{
if (userVertex[counterLoop]->getVertexID()
== incidentVertex[innerLoop])
{
incidentVertex.erase(incidentVertex.begin() + innerLoop);
cont.push(userVertex[counterLoop]);
}
++innerLoop;
}

if (incidentVertex.empty())
{
isAllPush = true;
}
++counterLoop;
}
}

return isConnected;
}```
This is the code for BFS. This code is very complicated due to i store the string from Vertex to string vertex.
I think it is easier to use pointer but in case of undirected graph, deadlock occured

if A point to B
if B point to A. Then how shared_ptr deal with this kind of problem.

Does it is a mandatory to have a IsVisited variable in BFS or DFS ?

I don't want to over complicated the class design just to add one variable to class vertex. Do you have any other approach ?
I think to map VertexID to boolean value
map<string, bool>; This allow me to know whether a vertex is visited or not.

Thanks.
Last edited by Peter_APIIT; 01-22-2009 at 04:50 AM.

10. Senior Member
Join Date
Dec 2003
Posts
3,366
I do not have a better approach, I do not need graphs and have not had to make one so I am rusty on all the algorithms for them.

Yes, this:

class bloated
{
int i;
public:
int get_i(){return i;}
void set_i(int val){i = val;}
}

as far as I know, this is the recommended way to do it. I typically just make i public since it *is* effectively public -- and again, I think that habit comes from all the math I do, I find it frustrating to have
(something.set_val(other.get_val()* yetanotha.get_val())/ third.get_val();
compared to
(something.i*other.i) / third.i;

.... even simple expressions like this become HUGE with well named accessor methods.
Its nearly three times longer, and that was just a trivial (yet representative) example.

11. Registered User
Join Date
May 2007
Posts
843
Thanks for help.