Jeżeli sensownie stworzysz implementacje grafu to cała procedura jest prymitywna:
#include <algorithm>
#include <iostream>
#include <sstream>
#include <list>
#include <set>
using namespace std;
string str(unsigned n)
{
stringstream ss;
ss<<n;
return ss.str();
}
class graph
{
public:
class node;
class edge
{
private:
string name;
node &src,&dst;
public:
edge(const string &name,node &src,node &dst):name(name),src(src),dst(dst) {}
string Name()const { return name; }
node &Src()const { return src; }
node &Dst()const { return dst; }
friend class node;
friend class graph;
};
class node
{
public:
typedef list<edge*>::iterator srciterator;
typedef list<edge*>::iterator dstiterator;
private:
string name;
list<edge*> src,dst;
public:
srciterator srcbegin() { return src.begin(); }
srciterator srcend() { return src.end(); }
dstiterator dstbegin() { return dst.begin(); }
dstiterator dstend() { return dst.end(); }
unsigned srcid,dstid;
node(const string &name):name(name),srcid(0),dstid(0) {}
string Name()const { return name; }
friend class graph;
};
typedef list<node>::iterator nodeiterator;
typedef list<edge>::iterator edgeiterator;
private:
list<node> nodes;
list<edge> edges;
graph(const graph &) {} // not implemented
void operator=(const graph &) {} // not implemented
public:
graph() {}
nodeiterator nodebegin() { return nodes.begin(); }
nodeiterator nodeend() { return nodes.end(); }
edgeiterator edgebegin() { return edges.begin(); }
edgeiterator edgeend() { return edges.end(); }
node *find(const string &name)
{
for(list<node>::iterator i=nodes.begin();i!=nodes.end();++i) if(i->name==name) return &*i;
return 0;
}
node &make(const string &name)
{
node *tmp=find(name);
if(!tmp)
{
nodes.push_back(node(name));
tmp=&nodes.back();
}
return *tmp;
}
void connect(const string &what,node &src,node &dst)
{
edges.push_back(edge(what,src,dst));
src.dst.push_back(&edges.back());
dst.src.push_back(&edges.back());
}
void connect(const string &what,const string &src,const string &dst)
{
connect(what,make(src),make(dst));
}
bool convertable()
{
unsigned nr=0;
for(nodeiterator i=nodebegin();i!=nodeend();++i)
{
i->dstid=0;
i->srcid=i->src.size()?0:++nr;
}
for(edgeiterator i=edgebegin();i!=edgeend();++i)
{
unsigned srcid=i->src.dstid,dstid=i->dst.srcid;
if(srcid)
{
if(dstid) return false;
i->dst.srcid=srcid;
}
else if(dstid)
{
i->src.dstid=dstid;
}
else
{
i->src.dstid=i->dst.srcid=++nr;
}
}
return true;
}
bool orig(graph &g)
{
if(convertable())
{
for(nodeiterator i=nodebegin();i!=nodeend();++i)
{
g.connect(i->name,str(i->srcid),str(i->dstid));
}
return true;
}
return false;
}
};
int main()
{
graph g;
g.connect("1","A","B");
g.connect("2","B","C");
g.connect("3","C","E");
g.connect("4","E","F");
g.connect("5","F","B");
g.connect("6","B","D");
g.connect("7","D","F");
for(graph::nodeiterator i=g.nodebegin();i!=g.nodeend();++i)
{
for(graph::node::dstiterator d=i->dstbegin();d!=i->dstend();++d)
{
cout<<i->Name()<<" -> "<<(*d)->Name()<<" -> "<<(*d)->Dst().Name()<<endl;
}
}
cout<<endl;
graph G;
g.orig(G);
for(graph::nodeiterator i=G.nodebegin();i!=G.nodeend();++i)
{
for(graph::node::dstiterator d=i->dstbegin();d!=i->dstend();++d)
{
cout<<i->Name()<<" -> "<<(*d)->Name()<<" -> "<<(*d)->Dst().Name()<<endl;
}
}
return 0;
}
http://ideone.com/ByAOwP