我正在尝试创建 Traveling Salesman Problem 的模拟为此，我使用 GraphStream图书馆。我有一个 CreateGraph 类，它负责创建和维护图形。作为模拟的一部分，我必须交换两个城市(图形术语中的节点)，为此我正在做的是
- 获取与node1关联的边并将其存储在名为
edge_1的数组中 - 获取与node2关联的边并将其存储在名为
edge_2的数组中 - 从两个数组中删除重复的边并将其存储在名为
common的数组中 - 现在删除两个节点(这也会删除与它们关联的边)
- 再次创建两个节点，其 ID 与之前的节点相同
- 现在迭代edge_1并将其添加到node2，并对node1和edge_2执行相同的操作
- 现在在它们之间添加公共(public)边
大多数情况下一切都工作正常，但有时我没有获得与节点关联的所有边。参见下图(注意蓝色节点)
您可以在 IDE 的左下角看到与其关联的节点和边。
这是 CreateGraph 类
package graph;
/**
* Created by deepanshu on 6/1/16.
*/
import org.graphstream.ui.view.Viewer;
import sa.City;
import sa.Tour;
import sa.TourManager;
import org.graphstream.graph.*;
import org.graphstream.graph.implementations.SingleGraph;
import java.util.ArrayList;
import java.util.Iterator;
import java.util.Scanner;
import java.util.stream.Collectors;
public class CreateGraph {
protected String stylesheet =
"node { " +
"fill-color: green; text-color: blue; text-alignment: under;" +
"}" +
"edge { " +
"fill-color: red;" +
"}" +
"graph { "+
"fill-color: black;" +
" }";
private Graph graph;
public CreateGraph() {
graph = new SingleGraph("Simulated Annealing");
Viewer viewer = graph.display();
viewer.disableAutoLayout();
graph.addAttribute("ui.stylesheet", stylesheet);
graph.addAttribute("ui.quality");
graph.addAttribute("ui.antialias");
}
public void init() {
int totalNumberOfCities = TourManager.numberOfCities();
for (int i = 0; i < totalNumberOfCities; ++i) {
City city = TourManager.getCity(i);
int x = city.getX(), y = city.getY();
graph.addNode("" + x + ", " + y);
Node node = graph.getNode("" + x + ", " + y);
node.addAttribute("ui.label", node.getId());
node.setAttribute("x", x);
node.setAttribute("y", y);
// sleep();
}
}
public void set(Tour tour) {
ArrayList tour_real = tour.getTour();
int length = tour_real.size();
for (int i = 0; i < length - 1; ++i) {
City city_1 = (City)tour_real.get(i);
City city_2 = (City)tour_real.get(i + 1);
Node node_1 = graph.getNode("" + city_1.getX() + ", " + city_1.getY());
Node node_2 = graph.getNode("" + city_2.getX() + ", " + city_2.getY());
node_1.setAttribute("x", city_1.getX());
node_2.setAttribute("x", city_2.getX());
node_1.setAttribute("y", city_1.getY());
node_2.setAttribute("y", city_2.getY());
graph.addEdge(i + "", node_1, node_2, false);
// sleep();
}
}
private void addEdge(Iterator iterator, ArrayList<Edge> edges) {
while (iterator.hasNext()) {
edges.add((Edge)iterator.next());
}
}
private void addEdge(ArrayList<Edge> edges, Node node_1, Node node_2, ArrayList<Edge> changeEdge) {
for (Edge edge : edges) {
Node node0 = edge.getNode0();
Node node1 = edge.getNode1();
if (node_2.getId().equals(node1.getId())) {
graph.addEdge(edge.getId(), node_1, node0, false);
changeEdge.add(graph.getEdge(edge.getId()));
} else {
graph.addEdge(edge.getId(), node_1, node1, false);
changeEdge.add(graph.getEdge(edge.getId()));
}
}
}
private Node addNode(int x, int y) {
graph.addNode("" + x + ", " + y);
Node node_1 = graph.getNode("" + x + ", " + y);
node_1.setAttribute("x", x);
node_1.setAttribute("y", y);
node_1.addAttribute("ui.label", node_1.getId());
node_1.addAttribute("ui.style", "fill-color: blue; text-color: blue; text-alignment: under;");
return node_1;
}
private void removeCommon(ArrayList<Edge> edges_1, ArrayList<Edge> edges_2, ArrayList<Edge> common) {
for (Edge edge_1 : edges_1) {
common.addAll(edges_2.stream().filter(edge_2 -> edge_1.getId().equals(edge_2.getId())).map(edge_2 -> edge_1).collect(Collectors.toList()));
}
edges_1.removeAll(common);
edges_2.removeAll(common);
for (Edge edge : edges_1)
edge.addAttribute("ui.style", "fill-color: Green;");
for (Edge edge : edges_2)
edge.addAttribute("ui.style", "fill-color: Green;");
for (Edge edge : common)
edge.addAttribute("ui.style", "fill-color: Green;");
}
public void updateColor(ArrayList<Edge> changeEdge, Node node_1, Node node_2) {
for (Edge edge : changeEdge)
edge.addAttribute("ui.style", "fill-color: Red;");
node_1.addAttribute("ui.style", "fill-color: green; text-color: blue; text-alignment: under;");
node_2.addAttribute("ui.style", "fill-color: green; text-color: blue; text-alignment: under;");
}
public void update(City city_1, City city_2) {
ArrayList<Edge> changeEdge = new ArrayList<>();
int x_1 = city_1.getX(), y_1 = city_1.getY();
int x_2 = city_2.getX(), y_2 = city_2.getY();
Node node_1 = graph.getNode("" + x_1 + ", " + y_1);
Node node_2 = graph.getNode("" + x_2 + ", " + y_2);
ArrayList<Edge> edge_1 = new ArrayList<>();
ArrayList<Edge> edge_2 = new ArrayList<>();
ArrayList<Edge> common = new ArrayList<>();
addEdge(node_1.getEdgeIterator(), edge_1);
addEdge(node_2.getEdgeIterator(), edge_2);
removeCommon(edge_1, edge_2, common);
graph.removeNode(node_1);
graph.removeNode(node_2);
node_1 = addNode(x_2, y_2);
node_2 = addNode(x_1, y_1);
System.out.println("Node_1: " + node_1.toString());
System.out.println("Node_2: " + node_2.toString());
System.out.println("edge_1: " + edge_1.toString());
System.out.println("edge_2: " + edge_2.toString());
System.out.println("common: " + common.toString());
addEdge(edge_1, node_1, node_2, changeEdge);
addEdge(edge_2, node_2, node_1, changeEdge);
for (Edge edge : common) {
Node node1 = edge.getNode0();
Node node2 = edge.getNode1();
graph.addEdge(edge.getId(), node1, node2, false);
changeEdge.add(graph.getEdge(edge.getId()));
}
sleep();
updateColor(changeEdge, node_1, node_2);
sleep();
}
protected void sleep() {
try {
Thread.sleep(500);
Scanner scanner = new Scanner(System.in);
// scanner.nextLine();
} catch (Exception e) {
e.printStackTrace();
}
}
}
update 方法是两个节点交换发生的地方。
最佳答案
好吧，我自己发现了这个错误。错误就在这里
for (Edge edge : common) {
Node node1 = edge.getNode0();
Node node2 = edge.getNode1();
graph.addEdge(edge.getId(), node1, node2, false); <--- Replace it with
graph.addEdge(edge.getId(), node_1, node_2, false);
changeEdge.add(graph.getEdge(edge.getId()));
}
实际上我分配的是局部变量而不是节点的真实实例。
我将这个问题留在这里，供任何想要在 GraphStream 库中交换两个节点的人将来引用。
感谢您的宝贵时间。
关于java - 交换节点并添加新边在 GraphStream 中显示出奇怪的行为，我们在Stack Overflow上找到一个类似的问题： https://stackoverflow.com/questions/37587143/