-
January 19th, 2010, 01:04 AM
#1
Kindly help me simplify the following graph class
I have been studying graphs currently and came across a way to implement it.
Code:
#include<iostream>
#include<vector>
#include<string>
#include<map>
#include<functional>
#include<cstdlib>
using namespace std;
struct vertex;
struct edge
{
vertex *dest;
double cost;
edge(vertex *a=NULL, double b=0)
{
dest=a;
cost=b;
}
};
struct vertex
{
string name;
vector<edge> adj;
vertex(string s)
{
name=s;
}
};
class graph
{
public:
typedef map<string, vertex *,less<string> > vmap;
vmap work;
void addvertex(const string&);
void viewvertex();
void addedge(const string& from, const string& to, double cost);
void viewcostofedge(const string &from, const string &to);
};
void graph::addvertex(const string &name)
{
vmap::iterator itr=work.begin();
itr=work.find(name);
if(itr==work.end())
{
vertex *v;
v= new vertex(name);
work[name]=v;
return;
}
cout<<"\nVertex already exists!";
}
void graph::viewvertex()
{
vmap::iterator itr=work.begin();
for(;itr!=work.end();itr++)
{
cout<<"\n"<<itr->first;
}
}
void graph::addedge(const string& from, const string& to, double cost)
{
vertex *f=(work.find(from)->second);
vertex *t=(work.find(to)->second);
edge added(t,cost);
f->adj.push_back(added);
}
void graph::viewcostofedge(const string &from, const string &to)
{
vmap::iterator itr=work.find(from);
vector<edge> v=(itr->second)->adj;
vector<edge>::iterator itr1=v.begin();
vertex *p;
for(;itr1!=v.end();itr1++)
{
if(((*itr1).dest)->name==to)
cout<<"\nThe cost is:-"<<(*itr1).cost;
}
}
int main()
{
int ch;
graph g;
string name;
string string1,string2;
double cost;
do
{
cout<<"\n\n\n1.Add Vertex\n2.View Vertex\n3.Add Edge\n4.View Cost\n5.Exit\nEnter choice:-\n\n\n";
cin>>ch;
switch(ch)
{
case 1:
cout<<"\nEnter the name of the vertex:-";
cin>>name;
g.addvertex(name);
break;
case 2:
g.viewvertex();
break;
case 3:
cout<<"\nEnter the spot:-";
cin>>string1;
cout<<"\nEnter the destination!";
cin>>string2;
cout<<"\nEnter cost:-";
cin>>cost;
g.addedge(string1,string2,cost);
break;
case 4:
cout<<"\nEnter the spot:-";
cin>>string1;
cout<<"\nEnter the destination!";
cin>>string2;
g.viewcostofedge(string1,string2);
break;
case 5:
exit(0);
default:
cout<<"\nWrong Choice!";
}
}while(1);
}
As you can see, the program seems overly complicated with all those refrences to other class. Can you help me simplify this class?
-
January 19th, 2010, 11:55 AM
#2
Re: Kindly help me simplify the following graph class
That class certainly could be improved from both a data structure and C++ specific point of view. But there are many ways to implement graph representations. What exactly do you think is "overly complicated"?
About the "references to other class", what do you mean? Is it because there is an edge, vertex and a graph class? If so, doing it this way (having one class to represent edges, another to represent vertices and the actual graph class) is a quite common strategy.
-
January 21st, 2010, 07:44 AM
#3
Re: Kindly help me simplify the following graph class
When I meant 'overly' complicated, check this for example->
Code:
void graph::viewcostofedge(const string &from, const string &to)
{
vmap::iterator itr=work.find(from);
vector<edge> v=(itr->second)->adj;
vector<edge>::iterator itr1=v.begin();
vertex *p;
for(;itr1!=v.end();itr1++)
{
if(((*itr1).dest)->name==to)
cout<<"\nThe cost is:-"<<(*itr1).cost;
}
}
To access the destination's name, I had to do so much of work.
Suggets a few improvements please as you stated.
Posting Permissions
- You may not post new threads
- You may not post replies
- You may not post attachments
- You may not edit your posts
-
Forum Rules
|
Click Here to Expand Forum to Full Width
|