fork(1) download
copy 
  1. #include <algorithm>
  2. #include <iostream>
  3. #include <sstream>
  4. #include <list>
  5. #include <set>
  6. using namespace std;
  7.  
  8. string str(unsigned n)
  9.   {
  10.    stringstream ss;
  11.    ss<<n;
  12.    return ss.str();
  13.   }
  14.  
  15. class graph
  16.   {
  17.    public:
  18.    class node;
  19.    class edge
  20.      {
  21.       private:
  22.       string name;
  23.       node &src,&dst;
  24.       public:
  25.       edge(const string &name,node &src,node &dst):name(name),src(src),dst(dst) {}
  26.       string Name()const { return name; }
  27.       node &Src()const { return src; }
  28.       node &Dst()const { return dst; }
  29.       friend class node;
  30.       friend class graph;
  31.      };
  32.    class node
  33.      {
  34.       public:
  35.       typedef list<edge*>::iterator srciterator;
  36.       typedef list<edge*>::iterator dstiterator;
  37.       private:
  38.       string name;
  39.       list<edge*> src,dst;
  40.       public:
  41.       srciterator srcbegin() { return src.begin(); }
  42.       srciterator srcend() { return src.end(); }
  43.       dstiterator dstbegin() { return dst.begin(); }
  44.       dstiterator dstend() { return dst.end(); }
  45.       unsigned srcid,dstid;
  46.       node(const string &name):name(name),srcid(0),dstid(0) {}
  47.       string Name()const { return name; }
  48.       friend class graph;
  49.      };
  50.    typedef list<node>::iterator nodeiterator;
  51.    typedef list<edge>::iterator edgeiterator;
  52.    private:
  53.    list<node> nodes;
  54.    list<edge> edges;
  55.    graph(const graph &) {} // not implemented
  56.    void operator=(const graph &) {} // not implemented
  57.    public:
  58.    graph() {}   
  59.    nodeiterator nodebegin() { return nodes.begin(); }
  60.    nodeiterator nodeend() { return nodes.end(); }
  61.    edgeiterator edgebegin() { return edges.begin(); }
  62.    edgeiterator edgeend() { return edges.end(); }
  63.    node *find(const string &name)
  64.      {
  65.       for(list<node>::iterator i=nodes.begin();i!=nodes.end();++i) if(i->name==name) return &*i;
  66.       return 0;
  67.      }
  68.    node &make(const string &name)
  69.      {
  70.       node *tmp=find(name);
  71.       if(!tmp)
  72.         {
  73.          nodes.push_back(node(name));
  74.          tmp=&nodes.back();
  75.         }
  76.       return *tmp;
  77.      }
  78.    void connect(const string &what,node &src,node &dst)
  79.      {
  80.       edges.push_back(edge(what,src,dst));
  81.       src.dst.push_back(&edges.back());
  82.       dst.src.push_back(&edges.back());
  83.      }
  84.    void connect(const string &what,const string &src,const string &dst)
  85.      {
  86.       connect(what,make(src),make(dst));
  87.      }
  88.    bool convertable()
  89.      {
  90. 	  unsigned nr=0;
  91.       for(nodeiterator i=nodebegin();i!=nodeend();++i)
  92. 	    {
  93.          i->dstid=0;
  94.          i->srcid=i->src.size()?0:++nr;
  95. 	    }
  96.       for(edgeiterator i=edgebegin();i!=edgeend();++i)
  97.         {
  98.          unsigned srcid=i->src.dstid,dstid=i->dst.srcid;
  99.          if(srcid)
  100.            {
  101.             if(dstid) return false;
  102.             i->dst.srcid=srcid;
  103.            }
  104.          else if(dstid)
  105.            {
  106.            	i->src.dstid=dstid;
  107.            }
  108.          else
  109.            {
  110.            	i->src.dstid=i->dst.srcid=++nr;
  111.            }
  112.         }
  113.       return true;
  114.      }
  115.    bool orig(graph &g)
  116.      {
  117.       if(convertable())
  118.         {
  119.          for(nodeiterator i=nodebegin();i!=nodeend();++i)
  120. 		   {
  121. 		   	g.connect(i->name,str(i->srcid),str(i->dstid));
  122. 		   }
  123. 		 return true;
  124.         }
  125.       return false;
  126.      }
  127.   };
  128.  
  129. int main() 
  130.   {
  131.    graph g;
  132.    g.connect("1","A","B");
  133.    g.connect("2","B","C");
  134.    g.connect("3","C","E");
  135.    g.connect("4","E","F");
  136.    g.connect("5","F","B");
  137.    g.connect("6","B","D");
  138.    g.connect("7","D","F");
  139.    for(graph::nodeiterator i=g.nodebegin();i!=g.nodeend();++i)
  140.      {
  141.       for(graph::node::dstiterator d=i->dstbegin();d!=i->dstend();++d)
  142.         {
  143.          cout<<i->Name()<<" -> "<<(*d)->Name()<<" -> "<<(*d)->Dst().Name()<<endl;
  144.         }
  145.      }
  146.    cout<<endl;
  147.    graph G;
  148.    g.orig(G);
  149.    for(graph::nodeiterator i=G.nodebegin();i!=G.nodeend();++i)
  150.      {
  151.       for(graph::node::dstiterator d=i->dstbegin();d!=i->dstend();++d)
  152.         {
  153.          cout<<i->Name()<<" -> "<<(*d)->Name()<<" -> "<<(*d)->Dst().Name()<<endl;
  154.         }
  155.      }
  156.    return 0;
  157.   }
Success #stdin #stdout 0s 3484KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
B -> 2 -> C
B -> 6 -> D
A -> 1 -> B
C -> 3 -> E
E -> 4 -> F
F -> 5 -> B
D -> 7 -> F

3 -> C -> 4
3 -> D -> 5
2 -> B -> 3
1 -> A -> 2
4 -> E -> 5
5 -> F -> 2
https://ideone.com/ByAOwP
language:
C++ (gcc 8.3)
created:
10 years ago
visibility:
public

Share or Embed source code

Discover > Sphere Engine API

The brand new service which powers Ideone!

Discover > IDE Widget

Widget for compiling and running the source code in a web browser!