Suche geeigneten Container oder sonstige Speichermöglichkeit

Euler

Guten Abend,

ich kämpfe mal wieder seit Ewigkeiten mit einem Problem rum. Und zwar geht es um Folgendes:

Ein Graph besteht aus Knoten und Kanten. Eine Kante wird beschrieben durch einen Anfangs- und einen Endknoten. Jeder Kante ist ein Gewicht zugeordnet. Ich möchte nun in einem Container die Kanten und ihre Gewichte speichern, d.h. ich will Tripel von Ganzzahlen speichern, z.B. (1,2,1) = Kante mit Anfangsknoten 1, Endknoten 2 und Gewicht 1. Und davon halt jede Menge.

Am geschicktesten wäre ne Lösung der Art

map<pair<int, int>, int>

, aber so Konstrukte gibt es ja in C++ nicht. Weiß da jemand Rat?

Danke

SeppJ

boost::graph. Das kommt auch mit einer ganzen Reihe von nützlichen Algorithmen.

Euler

SeppJ schrieb:

boost::graph. Das kommt auch mit einer ganzen Reihe von nützlichen Algorithmen.

Ja, die kenn ich, aber die soll ich nicht benutzen. Nur die STL nach Möglichkeit.

SeppJ

Euler schrieb:

SeppJ schrieb:

boost::graph. Das kommt auch mit einer ganzen Reihe von nützlichen Algorithmen.

Ja, die kenn ich, aber die soll ich nicht benutzen. Nur die STL nach Möglichkeit.

Warum das denn nicht? Der Sinn von boost::graph ist ja gerade der, dass es in der STL keinen geeigneten Container gibt. Wenn du das nicht benutzen willst, dann wirst du dir etwas eigenes schreiben müssen. Du kannst dir ja bei boost angucken wie die das gemacht haben (wobei der boost-Code wegen der vielen Templateprogrammierung meistens recht schwer leserlich ist). Die üblichen Verfahren, von denen man sich normalerweise das passende aussucht (sie haben alle Vor- und Nachteile), sind:
http://en.wikipedia.org/wiki/Adjacency_list
http://en.wikipedia.org/wiki/Incidence_list
http://en.wikipedia.org/wiki/Adjacency_matrix
http://en.wikipedia.org/wiki/Incidence_matrix

Euler

SeppJ schrieb:

Warum das denn nicht? Der Sinn von boost::graph ist ja gerade der, dass es in der STL keinen geeigneten Container gibt.

Man sagte mir, ich solle "keine exotischen Bibliotheken nutzen". Die boost::graph gehört da leider dazu War nicht meine Idee. Ich glaube, ich probier es jetzt mal mit ner eigenen Klasse für Kanten. Eventuell klappt ja mal was auf Anhieb bei mir

SeppJ

Naja, wenn man boost schon exotisch nennt, dann musst du wohl wirklich alles selbst schreiben. Dein Glück, dass wenigstens die STL mittlerweile zum Sprachstandard gehört (zumindest größtenteils). Immerhin kannst du dich darauf freuen, dass im nächsten Standard auch viele Teile von boost in den Sprachumfang aufgenommen werden.

ipsec

Euler schrieb:

Am geschicktesten wäre ne Lösung der Art
map<pair<int, int>, int>
, aber so Konstrukte gibt es ja in C++ nicht.

Sehe ich gerade den Wald nicht? Warum soll das nicht gehen?

Ansonsten, wie wäre

struct tripel
{
    int anfang, ende, gewicht;
};

vector<tripel> kanten

?

Oder habe ich jetzt das Problem falsch verstanden?

unskilled

weil imho der op< von pair auf beides prüft.
(also lhs.first < rhs.first && lhs.second < rhs.second )
also gilt idR !(paar1 < paar2) && !(paar2 < paar1), so ist aber gleichheit definiert.
also muss man nur einen eigenen op< übergeben (und davor definieren^^):

template<typename T>
bool pair_less(const T& lhs, const T& rhs)
{
  if(lhs.first == rhs.first)
    return lhs.second < rhs.second;

  return lhs.first < rhs.first;
}

ging das nicht auch mal schöner zu schreiben?

bb

Nexus

unskilled schrieb:

also muss man nur einen eigenen op< übergeben (und davor definieren^^):

template<typename T>
bool pair_less(const T& lhs, const T& rhs)
{
  if(lhs.first == rhs.first)
    return lhs.second < rhs.second;

  return lhs.first < rhs.first;
}

Die selbe Semantik hat aber auch operator< für std::pair aus der Standardbibliothek. Zuerst wird first verglichen, bei Gleichheit wird second verglichen.

unskilled

hmm... stimmt - zumindest wenn man cplusplus.com glaubt - wieder was dazu gelernt... ^^

also spricht ja wirklich nix ggn die map mit pair<int,int> als schlüssel!?

Euler schrieb:

Am geschicktesten wäre ne Lösung der Art
map<pair<int, int>, int>
, aber so Konstrukte gibt es ja in C++ nicht.

Was wäre daran jetzt geschickt? Ich sehe nur, dass es recht kurz wäre.

In deinem Fall hast du nur schnellen Zugriff auf ausgehende Kante, nicht auf eingehende. Je nach dem, wie du hast du außerdem logarithmische Zugriffszeiten auf bestimme Informationen, statt konstanter.

Eine bessere Implementierung wäre wohl eine mit einer doubly connected edge list. Falls du nur ausgehende Kanten brauchst, geht es noch ein wenig einfacher.

Edit: Das soll natürlich nicht heißen, dass du deine Lösung nicht verwenden sollst, falls sie für deinen Fall ausreichend ist. Eine bessere Implementierung ist auch mit mehr Implementierungsaufwand verbunden, wenn du boost nicht verwenden darfst.

Ich habe das jetzt mit ner eigenen Klasse geregelt, also kann ich jetzt auch nen normalen Vektor nehmen, so in etwa:

vector<Kante *> kanten

Das Problem, was ich damit halt habe, ist, dass in diesem Vektor gewisse Kanten doppelt eingefügt werden im Laufe meines Programms. Ich könnte zwar das Programm so umschreiben, dass das nicht passiert, aber das ist zur Laufzeit ziemlich aufwendig und kompliziert. Dann habe ich versucht mit unique die doppelten Kanten zu entfernen. Aber das funktioniert bei mir irgendwie nur, wenn im Vektor Ganzzahlen sind. Ich hab das folgendermaßen probiert:

vector<int> kanten;
// ... füge Kanten ein
  vector<int>::iterator it;
  it = unique (kanten.begin(), kanten.end()); 
  kanten.resize( it - kanten.begin() );

Wenn ich das so mache, dann entfernt er doppelte Elemente. Speichere ich jetzt meine Kanten im Vektor als Kanten (bestehend aus 3 int-Werten), dann entfernt er die doppelten leider nicht. Deswegen - und weil ich halt die boost nicht verwenden darf - wollte ich eben sowas wie die multimap<int, int, int> oder so haben. Das war eigentlich die ursprüngliche Motivation.

Nexus

Warum nimmst du nicht std::set ? Und warum Zeiger auf Kanten statt Kanten?