如何使用输入文本文件创建邻接矩阵来表示有向加权图 [java]?
how to create an adjacency matrix, using an input text file, to represent a directed weighted graph [java]?
我很难弄清楚如何从输入文件创建邻接矩阵。输入文件应该表示节点的有向加权图。
目的是创建一个可以进行迭代深度优先搜索的程序,但我真的卡在了作业的数据输入部分。
输入文本文件应该如下所示:
每个节点由两行文本表示。例如最上面一行,第一个'S'是节点的名称,第二个'S'表示它是一个起始节点,第三个'n'表示它是一个常规节点,而不是目标节点,它将由 'g'.
表示
第二行是连接到'S'的两个节点,第一个是'B',加权距离为1,第二个是'E',加权距离为2 .
第三行应该是空白,重复了这个模式。
S S n
B 1 E 2
B N n
C 2 F 3
C N n
D 2 GA 4
D N n
GA 1
E N n
B 1 F 3 H 6
F N n
I 3 GA
3 C 1
GA N g
H N n
I 2 GB 2 F 1
I N n
GA 2 GB 2
GB N g
我真的坚持这一点。我一直在使用缓冲 reader 扫描文件,但我一直想知道使用扫描仪是否会更容易。
我目前正在尝试创建具有名称属性的 Node 对象,并且可能使用某种 linked 列表创建与其他相邻 Node 对象的 link。我也考虑过使用节点对象数组,但我真的不确定如何表示哪些节点连接到哪些其他节点以及如何使用二维数组将其构建到邻接矩阵中。
任何建议将不胜感激,我是新手所以如果我的问题对其他人不具有学术重要性,我深表歉意
编辑:我的代码是这样的:
public void actionPerformed(ActionEvent e)
{
if(e.getSource() == openButton)
{
returnVal = fileChooser.showOpenDialog(null);
if(returnVal == JFileChooser.APPROVE_OPTION)
{
selected_file = fileChooser.getSelectedFile();
String file_name = fileChooser.getSelectedFile().getName();
file_name = file_name.substring(0, file_name.indexOf('.'));
try
{
BufferedWriter buff_writer = null;
File newFile = new File("."+file_name+"_sorted.txt");
boolean verify_creation = newFile.createNewFile();
//if (verify_creation)
// System.out.println("file created successfully");
//else
// System.out.println("file already present in specified location");
file_reader1 = new BufferedReader(new FileReader(selected_file));
file_reader2 = new BufferedReader(new FileReader(selected_file));
FileWriter file_writer = new FileWriter(newFile.getAbsoluteFile());
buff_writer = new BufferedWriter(file_writer);
//find the number of nodes in the file
while( (currentLine = file_reader1.readLine()) != null)
{
k++;
System.out.println("value of k: " + k);
}
nodeArray = new Node[k];
while( (currentLine = file_reader2.readLine()) != null)
{
//System.out.print(currentLine);
String[] var = currentLine.split(" ");
nodeArray[x] = new Node(var[0], var[1], var[2]);
nodeArray[x].setLink1(new Node(var[3], null, null));
}
buff_writer.close();
file_writer.close();
}
catch (Exception e1)
{
e1.printStackTrace();
}
}
}
编辑#2
我的节点对象看起来像这样:
public Node(String n, String t1, String t2)
{
name = n;
type1 = t1;
type2 = t2;
link1 = null;
link2 = null;
link3 = null;
link4 = null;
link5 = null;
link6 = null;
事实是:您不想在这里使用二维数组。您想退后一步,design/model 一个适合您正在工作的 "actual problem" 的 class/data 结构。
换句话说:您的问题是关于表示节点和边的图形。所以,一些让你前进的技巧..
让我们开始:
enum NodeType { START, GOAL, NORMAL ; }
public class Node {
private final String name;
public Node(String name) {
this.name = name;
以上为您提供了一种合理区分不同类型节点的方法。然后我们从节点的表示开始。显然,它的名称是固定的——您不想在节点创建后更改其名称。那么你有 setter 喜欢
public void setType(NodeType type) ...
还有更多字段,
private final Map<Node, Integer> neighbors = new HashMap<>();
以及添加新邻居的方法:
public void addNeighborNode(Node node, int weight) {
neighbors.put(node, weight);
[ 备案:理论上,您可以创建一个 class 通过构造函数获取所有信息,避免使用 setter 方法。这有一定的优势,但使事情变得更复杂;我想...我在这里向您展示的内容已经够复杂了 ;-) ]
这里的整个想法 - 将 PARSING 与 represent/build 对象的方式分开。当然,在某些时候您必须读取该字符串,然后从中构建节点对象。
但你最好从上面的节点 class 开始,因为这样你就可以 构建 一个图形......而无需解析文本文件:
Node n1 = new Node("n1");
n1.setType(NodeType.START);
Node n2 = new Node("n2");
n2.setType(NodeType.GOAL);
n1.setNeighborNode(n2, 5);
换句话说:首先你为图表构建一个漂亮的 "class model"。你可以像上面那样编写测试代码。当所有这些都起作用时;然后编写读取该输入文件的代码并将其转换为构建图形所需的方法调用!
长话短说:当然,解析该文本文件很重要,但您应该不关注它。相反:请多多考虑数据的 class 模型 first。那就是你可以学到最多的东西,并且在实验中获得最大的乐趣。拉入字符串并将其转换为对象,即 "work"。先玩得开心!
我很难弄清楚如何从输入文件创建邻接矩阵。输入文件应该表示节点的有向加权图。
目的是创建一个可以进行迭代深度优先搜索的程序,但我真的卡在了作业的数据输入部分。
输入文本文件应该如下所示:
每个节点由两行文本表示。例如最上面一行,第一个'S'是节点的名称,第二个'S'表示它是一个起始节点,第三个'n'表示它是一个常规节点,而不是目标节点,它将由 'g'.
表示第二行是连接到'S'的两个节点,第一个是'B',加权距离为1,第二个是'E',加权距离为2 .
第三行应该是空白,重复了这个模式。
S S n
B 1 E 2
B N n
C 2 F 3
C N n
D 2 GA 4
D N n
GA 1
E N n
B 1 F 3 H 6
F N n
I 3 GA
3 C 1
GA N g
H N n
I 2 GB 2 F 1
I N n
GA 2 GB 2
GB N g
我真的坚持这一点。我一直在使用缓冲 reader 扫描文件,但我一直想知道使用扫描仪是否会更容易。
我目前正在尝试创建具有名称属性的 Node 对象,并且可能使用某种 linked 列表创建与其他相邻 Node 对象的 link。我也考虑过使用节点对象数组,但我真的不确定如何表示哪些节点连接到哪些其他节点以及如何使用二维数组将其构建到邻接矩阵中。
任何建议将不胜感激,我是新手所以如果我的问题对其他人不具有学术重要性,我深表歉意
编辑:我的代码是这样的: public void actionPerformed(ActionEvent e) {
if(e.getSource() == openButton)
{
returnVal = fileChooser.showOpenDialog(null);
if(returnVal == JFileChooser.APPROVE_OPTION)
{
selected_file = fileChooser.getSelectedFile();
String file_name = fileChooser.getSelectedFile().getName();
file_name = file_name.substring(0, file_name.indexOf('.'));
try
{
BufferedWriter buff_writer = null;
File newFile = new File("."+file_name+"_sorted.txt");
boolean verify_creation = newFile.createNewFile();
//if (verify_creation)
// System.out.println("file created successfully");
//else
// System.out.println("file already present in specified location");
file_reader1 = new BufferedReader(new FileReader(selected_file));
file_reader2 = new BufferedReader(new FileReader(selected_file));
FileWriter file_writer = new FileWriter(newFile.getAbsoluteFile());
buff_writer = new BufferedWriter(file_writer);
//find the number of nodes in the file
while( (currentLine = file_reader1.readLine()) != null)
{
k++;
System.out.println("value of k: " + k);
}
nodeArray = new Node[k];
while( (currentLine = file_reader2.readLine()) != null)
{
//System.out.print(currentLine);
String[] var = currentLine.split(" ");
nodeArray[x] = new Node(var[0], var[1], var[2]);
nodeArray[x].setLink1(new Node(var[3], null, null));
}
buff_writer.close();
file_writer.close();
}
catch (Exception e1)
{
e1.printStackTrace();
}
}
}
编辑#2
我的节点对象看起来像这样:
public Node(String n, String t1, String t2)
{
name = n;
type1 = t1;
type2 = t2;
link1 = null;
link2 = null;
link3 = null;
link4 = null;
link5 = null;
link6 = null;
事实是:您不想在这里使用二维数组。您想退后一步,design/model 一个适合您正在工作的 "actual problem" 的 class/data 结构。
换句话说:您的问题是关于表示节点和边的图形。所以,一些让你前进的技巧..
让我们开始:
enum NodeType { START, GOAL, NORMAL ; }
public class Node {
private final String name;
public Node(String name) {
this.name = name;
以上为您提供了一种合理区分不同类型节点的方法。然后我们从节点的表示开始。显然,它的名称是固定的——您不想在节点创建后更改其名称。那么你有 setter 喜欢
public void setType(NodeType type) ...
还有更多字段,
private final Map<Node, Integer> neighbors = new HashMap<>();
以及添加新邻居的方法:
public void addNeighborNode(Node node, int weight) {
neighbors.put(node, weight);
[ 备案:理论上,您可以创建一个 class 通过构造函数获取所有信息,避免使用 setter 方法。这有一定的优势,但使事情变得更复杂;我想...我在这里向您展示的内容已经够复杂了 ;-) ]
这里的整个想法 - 将 PARSING 与 represent/build 对象的方式分开。当然,在某些时候您必须读取该字符串,然后从中构建节点对象。
但你最好从上面的节点 class 开始,因为这样你就可以 构建 一个图形......而无需解析文本文件:
Node n1 = new Node("n1");
n1.setType(NodeType.START);
Node n2 = new Node("n2");
n2.setType(NodeType.GOAL);
n1.setNeighborNode(n2, 5);
换句话说:首先你为图表构建一个漂亮的 "class model"。你可以像上面那样编写测试代码。当所有这些都起作用时;然后编写读取该输入文件的代码并将其转换为构建图形所需的方法调用!
长话短说:当然,解析该文本文件很重要,但您应该不关注它。相反:请多多考虑数据的 class 模型 first。那就是你可以学到最多的东西,并且在实验中获得最大的乐趣。拉入字符串并将其转换为对象,即 "work"。先玩得开心!