从文件构建有向图

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

一般来说，你将结构(图)和数据分开。因此，在使用lemon的情况下，您将读取每一行，将其拆分为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文档如何使用图形算法和操作图形等。