Erstellen eines gerichteten Graphen aus einer Datei

Question

Ich muss eine Datei einlesen und daraus einen gerichteten Graphen erstellen. Ich arbeite in C++. Die Datei sieht wie folgt aus:

SFA SLC 700 59 
SFO LV 420 39 
LAX LV 231 23 
LV SLC 362 29 
LAX SFO 344 39 
LAX SLC 581 57 
SFA SFO 679 67 
SFO SLC 605 19 
PHX DEN 586 65 
LV PHX 256 21 
DEN SFA 1026 72 
DEN LAX 844 69 
SLC DEN 379 49 
SLC SJC 585 29 
SJC SFO 51 19 

Die erste Zeile bedeutet, es ist ein Flug von SFA nach SLC, die 700 Meilen und kostet $ 59 und jede Zeile folgt dieser Formel. Mir fällt es wirklich schwer, einen guten Weg zu finden, dies zu tun. Jede Hilfe würde so sehr geschätzt werden. Vielen Dank im Voraus.

Answer 1

Ich schlage vor, mit Lemon, siehe Tutorial: http://lemon.cs.elte.hu/pub/tutorial/a00011.html

Generell Sie Struktur trennen (die Kurve) und die Daten. Also im Falle von Zitrone würden Sie jede Zeile lesen, teilen Sie es in 4 Felder (Trennzeichen ist das Leerzeichen). Während des Lesens der Datei sollten Sie auch den Hash oder die Map (z. B. std :: unordered_map) pflegen, um Ziele, die sich bereits im Diagramm befinden, schnell zu suchen (oder verwenden Sie die graph API, um sie zu finden, aber das wäre langsamer). So

:

ListDigraph g; 
ListDigraph::NodeMap<std::string> gDestinations(g); 
ListDigraph::ArcMap<int> gCosts(g); 
ListDigraph::ArcMap<int> gDistances(g); 
std::unordered_map<std::string, ListDigraph::Node> destinations; 

Und dann für jede Zeile:

//first read the line, split it be whitespace into 4 fields, e.g. into these 
std::string destFrom, destTo; 
int distance, cost; 

//first the structure 
auto itFrom = destinations.insert(destFrom, g.addNode()).first; //dest is the first or second field in your file 
auto itTo = destinations.insert(destTo, g.addNode()).first; //dest is the first or second field in your file 
ListDigraph::Arc route = g.addArc(*itFrom, *itTo); 

//then the data 
gDestinations[*itFrom] = destFrom; //well this could be done once if the place exists already, this s for brevity 
gDestinations[*itTo] = destTo; //dtto 
gDistances[route] = distance; //distance is the third field 
gCosts[route] = cost; //cost is the fourth field 

Und das ist es. Sehen Sie das Tutorial und die Lemon-Dokumentation, wie Sie Graphalgorithmen verwenden und den Graphen usw. manipulieren.