3. Probleme mit "Graph Handling System"

Probleme mit "Graph Handling System"

  • C

    Hallo zusammen,

    leider bin ich recht unerfahren in der C-Programmierung und habe nun ein Problem mit GHS, dem sog. "Graph Handling System". GHS ist, wie der Name schon andeutet, ein Paket, welches zum Arbeiten mit Graphen verwendet werden kann.
    Für alle, die das nicht kennen (und ich gehe davon aus, dass es eine Menge sind), sei unter folgenden Adressen die Dokumentation und das Programm hinterlegt:

    [url=ftp://ftp-bvs.informatik.uni-oldenburg.de/pub/Manuals/
    GHSmanual-v3.0-beta2.201.ps.gz]Dokumentation[/url]
    GHS

    So, mein Programm soll nun folgendes tun:

    • Ausgehend vom Startknoten starten wir jeweils einen Thread für jeden abgehenden Kante.
    • Jeder Thread markiert den erreichten Knoten als besetzt, um Zugriffsverletzungen ausschließen zu können und gibt ihn nach erfolgreicher Bearbeitung wieder frei. Ist eine Kante als besetzt markiert, so wartet der entsprechende Thread auf die Freigabe durch den anderen Thread.
    • Es wird überprüft, ob der aktuelle Knoten bereits markiert wurde. Wenn er nicht markiert sein sollte, so markiere ihn mit der aktuellen Schalennummer und markiere den Bogen, der zu diesem Knoten geführt hat. Ist der Knoten bereits markiert, so überprüfe, ob die Markierung (also die Schalennummer aus einem anderen Thread) mit der des aktuellen Threads übereinstimmt. Wenn eine Übereinstimmung vorliegt, so markiere die Kante zu diesem Knoten, ansonsten beende den Thread an dieser Stelle.
    • Für jeden ausgehenden Bogen wird dieses Schema weiter fortgesetzt, bis alle Threads beendet sind.

    So, das Problem ist also nicht sonderlich schwer - jedenfalls wenn man sich den Grundlagen von C bewusst ist.

    Ich bin jetzt in der Lage einen Graph einzulesen - alles kein Problem. Ich kann den Namen des Graphen ausgeben usw. Aber wie kann ich nun auf eine Knoten (Edge) zugreifen? Ich bin einfach nicht in der Lage das mit der Referenz hinzubekommen - keine Ahnung warum.

    Kennt vielleicht jemand GHS oder kann mir sonst irgendwie weiterhelfen? Ich muss nur in der Lage sein von einem Knoten alle abgehenden Kanten (oder Bögen) zu erhalten und herausfinden zu welchen Knoten diese Kanten (oder Bögen) laufen.

    Gruß

    Jan

    0
  • C

    Wie durch ein Wunder bin ich jetzt weitergekommen - der Zugriff auf einen Knoten klappt!
    Jetzt muss ich den an meinen Thread übergeben und da hakt's auch gleich wieder.

    Ein

    printf("%s", vt-vtname);

    gibt im Hauptpogramm korrekt den Namen des Knotens aus.
    Jetzt erzeuge ich einen Thread:

    pthread_create(&p1, NULL, starteThread, &vt);

    Der Thread sieht wie folgt aus:

    void *starteThread(void *vt) {
printf("%s", *(VERTEX*)vt->vtname);
}

    Aber jetzt kriege ich ein "error: request for member vtname in something not a structure or union"

    Ich übergebe doch die Referenz, so dass das eigentlich klappen müsste, oder?

    0
  • E

    crackXs schrieb:

    void *starteThread(void *vt) {
printf("%s", *(VERTEX*)vt->vtname);
}

    Aber jetzt kriege ich ein "error: request for member vtname in something not a structure or union"

    Probiers mal so:

    void *starteThread(void *vt) {
printf("%s", ((VERTEX*)vt)->vtname);
}
    0
  • C

    Sehr gut - klappt!

    So, nun gehen die Probleme weiter, denn ich muss ja viele verschiedene Threads dynamisch öffnen (also einen richtigen Threadpool anlegen). Wie macht man das am besten? Braucht man für jeden Thread einen eigenen Identifier? Ich weiß vor Beginn ja nie wieviele parallele Wege es geben wird...
    Und dann zu einen Grundsätzlichen Problem: Die Threads sollen ja immer aufeinander warten (bis jeder durchgelaufen ist), macht man sowas mit Semaphoren? Könnte mir mal jemand ein Beispiel für sowas posten?
    Muss ich eigentlich jede Kante/Bogen und jeden Knoten bei der Bearbeitung sperren? Ist das Inkrementieren eines Zählers atomar?

    Gruß

    Jan

    0
Anmelden zum Antworten