Построение ориентированного графа из файла
Мне нужно прочитать в файле и построить из него ориентированный граф. Я работаю в 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, и каждая строка следует этой формуле. Мне действительно трудно найти хороший способ сделать это. Любая помощь будет высоко ценится. Заранее спасибо.
Решение
Я предлагаю использовать Лимон, см учебник: 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, как использовать графовые алгоритмы, манипулировать графом и т. Д.
Другие решения
Других решений пока нет …
detector