Graf sprzężony a graf oryginalny

0

Witam,
napisałam program sprawdzający czy sczytany graf jest grafem sprzężonym. W kolejnym kroku chciałabym, bym graf sprzężony był przekształcany na swój graf oryginalny. Moją reprezentacją grafową jest macierz sąsiedztwa ( ale nie ma to najmniejszego znaczenia, jestem w stanie szybko zmienić reprezentację, jeśli macierz jest wg. was złym pomysłem).
Teoretycznie ilość kartek, które zapisałam grafami i ich reprezentacją mogę już liczyć w miliardach dm^3 straconego przez ziemię tlenu.
Tutaj jest teoria : graf oryginalny a sprzężony

może ktoś jest wstanie mi podpowiedzieć, w jaki sposób powinnam sprawdzać czy np. krawędź 1 - 2 następnie wchodzi do 2 - 3 bym mogła utworzyć w grafie oryginalnym nową krawędź 1(1,2) - 2(2,3) ?

2

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

1

Program również wykonuje transformację dla niepoprawnych instancji. Gdy do istniejącego grafu dodamy łuk g.connect("8","D","G"), to przestaje być on grafem sprzężonym i dla niego nie można znaleźć grafu oryginalnego, a program znajduje.

Jeżeli jednak będziemy mu podawać tylko poprawne instancje, czyli grafy sprzężone to wynik zostanie znaleziony tylko dla niektórych. Gdy zrobimy z niego graf sprzężony teraz dodając drugi łuk g.connect("9","E","G") (czyli do przedstawionego rozwiązania dwa łuki: g.connect("8","D","G"), g.connect("9","E","G")), graf jest sprzężony, ale dla niego rozwiązania nie otrzymamy.

1 użytkowników online, w tym zalogowanych: 0, gości: 1