我正在尝试创建旅行推销员问题的模拟，为此我正在使用GraphStream库。我有一个类 CreateGraph 负责创建和维护图形。作为模拟的一部分，我必须交换两个城市（图中的节点），为此我正在做的是
- 获取与 node1 关联的边并将它们存储在名为的数组中
edge_1 - 获取与 node2 关联的边并将它们存储在名为的数组中
edge_2 - 从两个数组中删除重复的边并将它们存储在名为的数组中
common - 现在删除两个节点（这也将删除与它们关联的边）
- 再次创建两个节点，其 id 与以前的节点相同
- 现在遍历 edge_1 并将其添加到 node2 并对 node1 和 edge_2 执行相同的操作
- 现在在它们之间添加公共边
大多数情况下一切正常，但有时我没有得到与节点相关的所有边缘。见下图（注意蓝色节点）
您可以在 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方法是两个节点交换发生的地方。