Построение ориентированного графа из файла

Question

Мне нужно прочитать в файле и построить из него ориентированный граф. Я работаю в C++. Файл выглядит так:

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

Первая строка означает, что есть рейс из SFA в SLC, который составляет 700 миль и стоит $59, и каждая строка следует этой формуле. Мне действительно трудно найти хороший способ сделать это. Любая помощь будет высоко ценится. Заранее спасибо.

Answer 1

Я предлагаю использовать Lemon, см. Руководство: http://lemon.cs.elte.hu/pub/tutorial/a00011.html

Вообще говоря вы разделяете структуру (график) и данные. Так что в случае лимона вы должны прочитать каждую строку, разделить ее на 4 поля (разделитель - это пробел). Во время чтения файла вы также должны поддерживать хеш или карту (например, std::unordered_map), чтобы быстро искать места назначения уже в графе (или использовать API графа для их поиска, но это будет медленнее).

Так:

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;

И тогда для каждого ряда:

//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

И это все. Смотрите руководство и документацию по Lemon, как использовать графовые алгоритмы, манипулировать графом и т. Д.