将文件中的邻接表读入多图

Question

所以我有这个邻接表：哥伦布节点到芝加哥节点的距离为 .5 等等

Columbus,Chicago,0.5
Columbus,Miami,2.0
Chicago,NewYork,1.5
Chicago,Boston,2.0
Chicago,StLouis,0.5
Chicago,Denver,2.5
Chicago,Seattle,3.0
Boston,NewYork,0.5
StLouis,Atlanta,1
StLouis,Dallas,1.0
Atlanta,Dallas,1.0
Atlanta,Miami,1.0
Dallas,Miami,2.0
Dallas,LosAngeles,2.5
LosAngeles,SanFrancisco,1.0
LosAngeles,LasVegas,0.5
SanFrancisco,LasVegas,1.0
SanFrancisco,Seattle,2.0
SanFrancisco,Denver,2.0
Denver,LasVegas,1.0
Denver,Seattle,2.0

我有以下方法从 txt 文件中读取上面的列表。这会将列表添加到多映射 adj_list 但缺少这一部分：

"Note that each path between nodes is listed only once, but each path needs to be added twice to the adjacency list. For example, the file lists a path between Columbus and Chicago on the first line. This needs to be added to the adjacency list for Columbus as a path with a destination of Chicago AND it needs to be added to the adjacency list for Chicago with a destination of Columbus"

    public static Map<String, List<Path>> readPathsFromFile(Scanner inFile) {
    Map<String, List<Path>> adj_list =  new TreeMap<String, List<Path>>();
    ArrayList<Path> list1 = new ArrayList<Path>();

    while (inFile.hasNext()){ // TO- DO add parts for both ways.
        String input = inFile.nextLine();
        String[] token = input.split(",");

        if(!adj_list.containsKey(token[0])){
            list1 = new ArrayList<Path>();
            Path path2 = new Path(token[1],Double.parseDouble(token[2]));   
            list1.add(path2);
            adj_list.put(token[0], list1);

        }else{
            Path path = new Path(token[1],Double.parseDouble(token[2]));    
            list1.add(path);
        }

    }

    return adj_list;
}

所以，我的问题首先是上面的方法是开始的好方法，如果是的话，我该如何修改这个方法，让它在两个方向上向我的列表添加节点，而不仅仅是列表的顺序？

编辑：更清楚我想要什么。

例如最终我会有：旧金山：（拉斯维加斯：1.0），（西雅图：2.0），（丹佛：2.0）

我有那个部分，但需要的是：

旧金山：（洛杉矶：1.0），（拉斯维加斯：1.0），（西雅图：2.0），（丹佛：2.0）

即LosAngeles 有一个连接到 San Francisco 的节点，但它没有在 adj 列表中为 San Francisco 明确列出。谢谢！

Answer 1

您需要小心 ArrayList<Path> list1。如果你输入

Columbus,Chicago,0.5
Chicago,NewYork,1.5
Columbus,Miami,2.0

你会得到一张

的地图

Columbus (Chicago,0.5)
Chicago (NewYork,1.5),(Miami,2.0)

因为在读取第 3 行时，list1 数组是芝加哥数组（在第 2 行中创建）。您的 token[0] 是已知的（是的，由于第 1 行，地图中已经有一个哥伦布条目），因此您直接跳到将 (Miame,2.0) 距离添加到 list1 -- 芝加哥列表。

以下代码通过在 while 循环之外删除列表并每次都从地图中获取正确的列表来解决上述问题和您提出的问题。

public static Map<String, List<Path>> readPathsFromFile(Scanner inFile) {
  Map<String, List<Path>> adj_list =  new TreeMap<String, List<Path>>();

  // You do not need a list here
  // ArrayList<Path> list1 = new ArrayList<Path>();

  while (inFile.hasNext()){ // TO- DO add parts for both ways.
    String input = inFile.nextLine();
    String[] token = input.split(",");

    // 1.) Take care of 0 -> 1
    // Try and fetch the list from your treemap saved under 0
    List<Path> token0List = adj_list.get(token[0]);

    // If there was no list previously saved, you have a null value now
    if(token0List == null){

        // since there was no list previously saved,
        // create a new (empty) one and save it in the tree
        token0List = new ArrayList<Path>();
        adj_list.put(token[0], token0List );

    }

    // At this point of time, you can be sure that the token0List
    // exists and is saved correctly in the tree.

    // now you only need to add the 0 -> 1 path to the list
    // and you are done with this part of the saving.
     Path path = new Path(token[1],Double.parseDouble(token[2]));    
    token0List .add(path); // finish 0 -> 1


    // 2.) Take care of 1 -> 0
    // same procedure as 0 -> 1, only that you are swapping 
    // token[0] and token[1]
    List<Path> token1List = adj_list.get(token[1]);
    if(token1List == null){
        token1List = new ArrayList<Path>();
        adj_list.put(token[1], token1List );

    }
     Path path2 = new Path(token[0],Double.parseDouble(token[2]));    
    token1List .add(path2); // finish 1 -> 0



  }

  return adj_list;
}

将文件中的邻接表读入多图

Reading an adjacency list from a file into a multimap

java

data-structures

adjacency-list