3. Attributierte Graphen

Attributierte Graphen

  • ?

    Hallo C++ Gemeinde,

    ich brauche eure Hilfe wegen der Umsetzung von Graphen in Quellcode. Es gibt ja unterschiedliche Modelle, wie man Gerichtete und Ungerichtete Graphen programmiertechnisch umsetzen kann, einmal mittels sog. "Adjazenz-Matrix" und dann als dynamische Datenstruktur als "Adjazenz-Liste"

    Ich bearbeite im Moment die Adjazenz-Liste und dabei sollen "Knoten" und "Kanten" so miteinander verbunden werden, dass ein Gerichteter Graph entsteht.

    Als einfaches Beispiel habe ich mir erstmal drei Knoten ausgedacht, die so miteinander verbunden sind:
    Man kann von Knoten 1 -> 2 und auch von 2 -> 1 zurueck,
    weiterhin geht es von 2 -> 3, aber nicht umgekehrt,
    und von 3 -> 1, aber nicht umgekehrt.
    Um zu den einzelnen Knoten hin- und her zu gelangen, kostet es natuerlich immer etwas...

    Als Datenstruktur habe ich folgende ueberlegt:

    struct Knoten {
  int id;  // Numerierung des Knotens
  Kante *first;
  Knoten *next;
};

struct Kante {
  int kosten;  // Kosten fuer Verbindung zwischen zwei Knoten
  Knoten *knot;
  Kante *next;
};

    Als Entwicklungsumgebung habe ich bisher Turbo C++ Version 3.0 (von 1992) ausprobiert und alternativ auch noch Dev-C++ Version 5 (4.9.9.2)

    In beiden Programmen hat der Compiler den Code nicht akzeptiert, Turbo C++ meckerte, weil der (Zeiger-)Datentyp "Kante" in Knoten noch nicht bekannt sei, Dev-C++ hats gar nicht hingekriegt...

    Ich weiss im Moment nicht richtig weiter, ich hab zwar schon 7 Jahre Programmiererfahrung in (Turbo) Pascal, programmier C++ aber erst seit etwa 2 Jahren. Gibt es vielleicht eine Moeglichkeit, einen Zeiger auf den struct "Kante" als leeren Typ oder FORWARD (wie in Pascal) vor "Knoten" zu deklarieren, sodass dieser Typ schon bekannt ist?

    Waere super nett, wenn ihr mir helfen koenntet 🙂

    0
  • Mod

    80iesGuy schrieb:

    Ich weiss im Moment nicht richtig weiter, ich hab zwar schon 7 Jahre Programmiererfahrung in (Turbo) Pascal, programmier C++ aber erst seit etwa 2 Jahren. Gibt es vielleicht eine Moeglichkeit, einen Zeiger auf den struct "Kante" als leeren Typ oder FORWARD (wie in Pascal) vor "Knoten" zu deklarieren, sodass dieser Typ schon bekannt ist?

    Ja, das geht:

    struct Kante;

struct Knoten {
  int id;  // Numerierung des Knotens
  Kante *first;
  Knoten *next;
};

struct Kante {
  int kosten;  // Kosten fuer Verbindung zwischen zwei Knoten
  Knoten *knot;
  Kante *next;
};

    Und dir ist diese (grundlegende) Technik in 2 Jahren C++ noch nie begegnet? Wow.

    0
  • P

    Warum struct? c++ lebt von Klassen 🙂

    #include <iostream>
using std::cout;
using std::endl;
#include <vector>
using std::vector;

class Knoten {
public:
    Knoten(int _id) : id(abs(_id)) {}

    unsigned int id;
};

class Kante {
public:
    Kante(Knoten * _from, Knoten * _to) : from(_from), to(_to) {}

    Knoten * from, * to;
};

class Netz {
public:
    Netz () {}

    void addKante(Kante * kante)
    {
        int id1 = kante->from->id;
        int id2 = kante->to->id;

        // iter wäre schöner, grad kein Bock :)
        for(unsigned int tmp=0;tmp<knots.size();++tmp)
        {
            if (knots[tmp]->id == id1)
            {
                // Knoten mit gleicher ID besteht bereits, lösche neuen und biege biege Pointer auf alten Knoten um
                delete kante->from;
                kante->from = knots[tmp];
                id1 = -1;
            }
            else if (knots[tmp]->id == id2)
            {
                // Knoten mit gleicher ID besteht bereits, lösche neuen und biege biege Pointer auf alten Knoten um
                delete kante->to;
                kante->to = knots[tmp];
                id2 = -1;
            }
        }

        for(unsigned int tmp=0;tmp<edges.size();++tmp)
        {
            if (edges[tmp]->to->id == kante->to->id  &&
                edges[tmp]->from->id == kante->from->id)
            {
                cout << "Kante doppelt!" << endl;
                return;
            }
        }

        if (id1!=-1) {
            cout << "Knoten mit id " << id1 << " hinzugefügt" << endl;
            knots.push_back(kante->from);
        }
        else if (id2!=-1)
        {
            cout << "Knoten mit id " << id2 << " hinzugefügt" << endl;
            knots.push_back(kante->to);
        }

        edges.push_back(kante);
        cout << "Kante " << kante->from->id << " -> " << kante->to->id << " hinzugefügt." << endl;

    }

    void out()
    {
        for(unsigned int tmp=0;tmp<knots.size();++tmp)
            std::cout << "Knoten " << knots[tmp]->id << std::endl;
cout << endl;
        for(unsigned int tmp=0;tmp<edges.size();++tmp)
            std::cout << "Edge: " << edges[tmp]->from->id << " -> " << edges[tmp]->to->id << std::endl;

    }
private:
    vector<Knoten* > knots;
    vector<Kante* > edges;
};

// main
int main(int , char** )
{
    Netz n;

    n.addKante(new Kante(new Knoten(1),new Knoten(2)));
    n.addKante(new Kante(new Knoten(1),new Knoten(5)));
    n.addKante(new Kante(new Knoten(5),new Knoten(1)));
    n.addKante(new Kante(new Knoten(3),new Knoten(1)));
    n.addKante(new Kante(new Knoten(1),new Knoten(5)));

    n.out();
}

    Kosten und Ausgabe überlass ich dir zum Knobeln 😉

    my 5cc

    EDITED: SyntacticSugar 🙂 Ausgaben die sagen was passiert.
    EDITED: Speicherleck beseitigt (beim adden von Kanten mit existenten KnotenIDs

    0
  • ?

    hab bisher mit C++ noch nicht so viel programmiert, nur immer einfache Sachen, da ich lieber mit Turbo Pascal gearbeitet habe.
    ich probiers mal aus. Letztens hab ich das so aehnlich schonmal programmiert, hab aber zwei leere geschweifte Klammern geschrieben. Da hat der Compiler gemeckert...

    0
  • Mod

    80iesGuy schrieb:

    hab bisher mit C++ noch nicht so viel programmiert, nur immer einfache Sachen, da ich lieber mit Turbo Pascal gearbeitet habe.
    ich probiers mal aus. Letztens hab ich das so aehnlich schonmal programmiert, hab aber zwei leere geschweifte Klammern geschrieben. Da hat der Compiler gemeckert...

    Das wäre dann auch eine Definition und keine Deklaration gewesen. Ich weiß nicht, ob man die Begriffe bei Pascal auch so verwendet. Falls dir das nichts sagen sollte, mach dich mal kundig was mit diesen Worten gemeint ist.

    0
  • ?

    Ja, definiert meinte ich 😉
    C++ ist doch eine gewisse Umgewoehnung. Jedenfalls hab ich jetzt schonmal dank eurer Hilfe das erste Minimalprogramm, um Knoten anzulegen. Ich habe das bisher mit Klassen noch nicht gemacht, weil es von der Aufgabenstellung der Uebungsaufgabe (Uni Studium, Klausur am 11.03.) mit den structs vorgegeben ist. Als Loesung haben wir da die Adjazenz-Matrix schonmal gemacht, die Liste natuerlich wieder nicht 😉

    So siehts im Moment aus:

    #include <conio.h>
#include <iostream.h>

struct Knoten;

struct Kante {
  int kosten;
  Knoten* knot;
  Kante* next;
};

struct Knoten {
  int id;
  Knoten* next;
  Kante* first;
};

Knoten *Anfang, *Aktuell;  // Anfang, um den ersten Knoten zu finden

void NeuerKnoten(Knoten *Root, int nr) {
  Knoten *hilf=new Knoten;
  hilf->id=nr;
  hilf->next=NULL;
  hilf->first=NULL;
  if (Root==NULL) {
    Root=hilf;
    Anfang=Root;
    Aktuell=Root;
  }
  else {
    Aktuell->next=hilf;
    Aktuell=Aktuell->next;
  }
}

void PrintKnoten(Knoten *Root) {
  Knoten *hilf=new Knoten;
  hilf=Root;
  while (hilf!=NULL) {
    cout<<hilf->id<<endl;
    hilf=hilf->next;
  }
}

int main() {
  clrscr();
  cout<<"Knoten und Kanten"<<endl;
  Anfang=NULL;  Aktuell=NULL;

  NeuerKnoten(Anfang,1);
  NeuerKnoten(Anfang,2);
  NeuerKnoten(Anfang,3);

  PrintKnoten(Anfang);

  getch();
  return 0;
}

    Das mit den * und & ist noch etwas kniffelig, da bin ich von Pascal her immer das ^Symbol gewoehnt 😃

    0
  • P

    Hab meinen source noch ein bisserl ausgeschmückt, dann sieht man in der Ausgabe besser was er mach 😉

    Was c++ angeht ... da sind mE die <xyz.h> includes verpönt - es gibt für fast alles <xyz>

    Wenn die Arbeit sagt: STRUCT dann musst du, aber psst, guck mal:

    struct Net {
public:
Net(int a) : mA(a) {}
int A(){return mA;}
private:
int mA;
};

// main
int main(int , char** )
{
    Net N = Net(4);
    cout << N.A();
}

    So groß ist der Unterschied nicht ... wo genau der liegt bin ich aber auch zu faul nachzuschaun; ich arbeite lieber mit class als struct.

    0
  • 8

    Hallo padreigh,

    ich versuch dein Programm gleich mal zu testen. Obs in Turbo C++ laeuft, mal schauen, sonst versuch ich es mit Dev-C++

    Kann man eigentlich bei einem Beitrag hier auch Quelltexte etc. als Anhang machen? Weiss nicht, ob es so guenstig ist, immer den gesamten Quelltext in den Beitrag reinzukopieren 🙂

    ...hab mich gleich mal registriert 😉

    Edit: ich versuch alles erstmal einfach zu machen, Klassen mit Konstruktoren und Destruktoren kenn ich zwar, hab aber noch nicht viel mit gearbeitet. Also in C++ bin ich da noch auf dem Anfaenger-Niveau, bei Turbo Pascal kann ich mich schon guten Gewissens zu den Fortgeschrittenen zaehlen 😉

    In Dev-C++ hab ichs gleich zum Laufen gebracht, aber bei manchen Stellen blick ich doch nich so ganz durch... :p

    0
  • 8

    Hallo Leute,

    habe das Problem jetzt geloest. Es ist bestimmt noch nicht perfekt, aber fuer die gegebene Aufgabenstellung reichts 😉
    Werde mich auf jeden Fall weiter mit der Sprache C++ beschaeftigen :p

    Die Knoten lege ich so an:

    void NeuerKnoten(Knoten* Root, int nr) {
  Knoten* hilf=new Knoten;

  hilf->id=nr;
  hilf->next=NULL;
  hilf->first=NULL;

  if (Root==NULL) {
    Root=hilf;
    Anfang=Root;
    Aktuell=Root;
  }
  else {
    Aktuell->next=hilf;
    Aktuell=Aktuell->next;
  }
}

    Die Kanten habe ich so realisiert:

    void NeueKante(int start, int ziel, int betrag) {
  // Adressen des Start- und Zielknotens ermitteln und speichern
  Knoten* k1=Anfang;
  while ((k1!=NULL) && (k1->id<start)) k1=k1->next;
  Knoten* k2=Anfang;
  while ((k2!=NULL) && (k2->id<ziel)) k2=k2->next;

  // Neue Kante anlegen
  if ((k1!=NULL) && (k2!=NULL)) {
    Kante* hilf=new Kante;

    hilf->kosten=betrag;
    hilf->knot=NULL;
    hilf->next=NULL;

    if (k1->first==NULL) {
      k1->first=hilf;
      hilf->knot=k2;
    }  // if
    else {
      Kante* letzter=k1->first;
      while (letzter->next!=NULL) letzter=letzter->next;
      letzter->next=hilf;
      hilf->knot=k2;
    }  // else

  }  // if (k1 && k2)
}

    Die Ausgabe logischerweise auch etwas anders:

    void PrintNetz(Knoten *Root) {
  Knoten *kn=Root;
  Kante *edg;

  while (kn!=NULL) {

    edg=kn->first;

    while (edg!=NULL) {
      cout<<"Von "<<kn->id<<" nach "<<edg->knot->id;
      cout<<" kostet: "<<edg->kosten<<endl;
      edg=edg->next;
    }

    kn=kn->next;
  }
}

    Vielen Dank fuer die Ratschlaege und Hinweise. Wie gesagt, es sollte halt was einfaches sein, nix kompliziertes mit Klassen und so 🙂
    Eine Umsetzung mit Klassen werde ich aber zu Trainingszwecken auch machen 😃
    Der Code bietet auch noch reichlich Optimierungspotential. Eine gescheite Loeschroutine, die den Speicher wieder frei gibt, fehlt auch noch, das krieg ich hin.
    Fuer dieses Forum hier auf jeden Fall 👍

    0
Anmelden zum Antworten