Java:如何解析文件以获得边以生成图

Question

我在从文件读取数据时遇到问题。目前，我正在程序内添加边，该程序根据边列表生成图表。但是，我希望我的程序从文件中读取边来创建图形(逐行读取 .txt 文件)

.txt 文件看起来像这样:

0, 1
0, 4
1, 2
1, 3
1, 4
2, 3
3, 4

该程序的示例代码如下所示:

import java.util.*; 

class GraphIO { 

    static void addEdge(ArrayList<ArrayList<Integer> > adj, 
                        int u, int v) 
    { 
        adj.get(u).add(v); 
        adj.get(v).add(u); 
    } 

    static void printGraph(ArrayList<ArrayList<Integer> > adj) 
    { 
        for (int i = 0; i < adj.size(); i++) { 
            System.out.println("\nAdjacency list of vertex" + i); 
            for (int j = 0; j < adj.get(i).size(); j++) { 
                System.out.print(" -> "+adj.get(i).get(j)); 
            } 
            System.out.println(); 
        } 
    } 

    public static void main(String[] args) 
    { 
        int V = 5;
        ArrayList<ArrayList<Integer> > adj  
                    = new ArrayList<ArrayList<Integer> >(V); 

        for (int i = 0; i < V; i++) 
            adj.add(new ArrayList<Integer>()); 

        addEdge(adj, 0, 1); 
        addEdge(adj, 0, 4); 
        addEdge(adj, 1, 2); 
        addEdge(adj, 1, 3); 
        addEdge(adj, 1, 4); 
        addEdge(adj, 2, 3); 
        addEdge(adj, 3, 4); 

        printGraph(adj); 
    } 
} 

有人有建议吗？

Answer 1

编辑:我添加了 List这次又打来了addEdge这次正确。抱歉，我上次忽略了方法签名。

在 while 循环中，当您读取新行时，您可以在解析读取行中的数字后在此处添加一条边:

while (reader.hasNextLine()) {
    String[] nums = reader.nextLine().split(", ");
    addEdge(adj, Integer.parseInt(nums[0]), Integer.parseInt(nums[1]));
}

尝试后你还需要一个捕获。

旁注:我认为您不应该跳过一行，但我不知道这是否是您的程序应该做的特定事情。

您的addEdge方法应该如下所示，以确保您的 List全部填满了ArrayList s 并且您没有得到 IndexOutOfBoundsException .

static void addEdge(List<List<Integer>> adj, int u, int v) {
  int bigger = (u > v ? u : v) + 1;
  //Keep increasing the size until it's right
  while (adj.size() < bigger) adj.add(new ArrayList<>());
  adj.get(u).add(v);
  adj.get(v).add(u);
}

并且你的主要方法必须稍微改变。由于您不知道顶点数，因此您只需创建一个空的 ArrayList默认容量。声明adj如List<List<Integer>>没有必要 - 您仍然可以使用ArrayList ，但是List是其他类实现的接口(interface)，并不是绝对需要使用 ArrayList在这里，所以我用了它。

我还删除了 reader.nextLine()因为您要丢弃该数据，并且该边缘不会被注册。

  List<List<Integer>> adj = new ArrayList<>();

  File input = new File("filename"); //Define the input file with "filename"
  try {
   Scanner reader = new Scanner(input); //read in the file

   while (reader.hasNextLine()) {
    String[] nums = reader.nextLine().split(", ");
    addEdge(adj, Integer.parseInt(nums[0]), Integer.parseInt(nums[1]));
   }
   printGraph(adj);
   reader.close();
  } catch (IOException e) {
   throw new RuntimeException(e);
  }

输出:

Adjacency list of vertex0
 -> 1 -> 4

Adjacency list of vertex1
 -> 0 -> 2 -> 3 -> 4

Adjacency list of vertex2
 -> 1 -> 3

Adjacency list of vertex3
 -> 1 -> 2 -> 4

Adjacency list of vertex4
 -> 0 -> 1 -> 3

但是，该程序非常依赖 txt 中的边的顺序。文件，所以我宁愿这样做。它不是很高效，它使用 Maps 和 Sets 而不是 ArrayLists，但对我来说感觉更清晰。

static void addEdge(Map<Integer, Set<Integer>> adj, int u, int v) {
  //If it doesn't already exist, add the set of adjacent vertices here
  if (!adj.containsKey(u)) adj.put(u, new HashSet());
  if (!adj.containsKey(v)) adj.put(v, new HashSet());

  adj.get(u).add(v);
  adj.get(v).add(u);
 }

 static void printGraph(Map<Integer, Set<Integer>> adj) {
  for (int u : adj.keySet()) {
   System.out.println("\nAdjacency list of vertex" + u);
   for (int v : adj.get(u)) {
    System.out.print(" -> " + v);
   }
   System.out.println();
  }
 }

 public static void main(String[] args) {
  Map<Integer, Set<Integer>> adj = new HashMap<>();

  File input = new File("filename");
  try {
   Scanner reader = new Scanner(input); //read in the file

   while (reader.hasNextLine()) {
    String[] nums = reader.nextLine().split(", ");
    addEdge(adj, Integer.parseInt(nums[0]), Integer.parseInt(nums[1]));
   }
   printGraph(adj);
   reader.close();
  } catch (IOException e) {
   throw new RuntimeException(e);
  }
 }