我正在尝试制作一个有向图生成器，以便在ljf算法中使用它。问题是，我不知道如何避免返回的边缘（例如，如果我得到1->2，我不想有2->1）我只在if中做了一个声明，以避免同一节点的边（例如1->1）另一个问题是，生成器有时会让一些节点单独存在，而没有任何边，但每个节点至少需要一条边。我想达到的是类似于BST的东西，但没有规则有最多2条边，它可以更多。
public class Graph {
private final int maxT = 3;
private final int chance = 30; //chance to connect edges
Map<Task, List<Transmission>> tasks = new HashMap<Task, List<Transmission>>();
public Graph() {
Random r = new Random();
int range = r.nextInt(maxT) + 3; // number of nodes
for(int i = 0; i<range; i++){
List<Transmission> trans = new ArrayList<Transmission>();
tasks.put(new Task(i), trans);
}
System.out.println("Number of tasks: " + tasks.size());
for(Task key1 : tasks.keySet()){
for(Task key2 : tasks.keySet()){
if(key1 != key2 && r.nextInt(100) < chance)
tasks.get(key1).add(new Transmission(key1,key2));
}
}
}
public void printGraph(){
System.out.println("Generated graph:\n");
for(Task key : tasks.keySet()){
System.out.println(key.getId());
for(Transmission ts : tasks.get(key)){
System.out.println("\t" + ts.getT1().getId() + " -> " + ts.getT2().getId());
}
}
}
}
===编辑====
向迭代添加顺序后：
List<Task> keys = new ArrayList<Task>(tasks.keySet());
for(int i = 0; i < keys.size() - 1; i++){
for(int j = i + 1; j < keys.size(); j++){
tasks.get(i).add(new Transmission(keys.get(i), keys.get(j)));}
}
此行出现java.lang.nullPointerException异常：
tasks.get(i).add(new Transmission(keys.get(i), keys.get(j)));}
我看到我新添加的列表中充满了空元素，于是我附加了任务类：
import java.util.Random;
public class Task extends Node{
Random r = new Random();
int tstart; // start time
int tend; // end time
int size;
int deadline;
public Task(int id) {
super(id);
tstart = r.nextInt(5);
tend = r.nextInt(5);
size = r.nextInt(10);
deadline = r.nextInt(8);
}
public int getDeadline() {
return deadline;
}
public int getTstart() {
return tstart;
}
public int getTend() {
return tend;
}
public int getSize() {
return size;
}
}
==编辑====
现在我有一个问题，我的发电机给我周期，我不想有。所以，我又增加了一个传输的机会，但有时我得到了自由节点或分离图。
List<Task> keys = new ArrayList<Task>(tasks.keySet());
for(int i = 0; i < keys.size() - 1; i++){
for(int j = i + 1; j < keys.size(); j++){
if(r.nextInt(100) < chance && tasks.get(keys.get(i)).isEmpty())
tasks.get(keys.get(i)).add(new Transmission(keys.get(i), keys.get(j)));}
}
最佳答案
您可以使用由目标节点索引的映射，而不是每个Transmission的Tasks列表。然后，您可以轻松地执行检查，是否已经存在向后的边缘。此外，还可以添加一个条件，以便在节点没有边时始终生成边：
public class Graph {
private final int maxT = 3;
private final int chance = 30; //chance to connect edges
Map<Task, Map<Task, Transmission>> tasks = new HashMap<>();
public Graph() {
Random r = new Random();
int range = r.nextInt(maxT) + 3; // number of nodes
for(int i = 0; i<range; i++){
Map<Task, Transmission> trans = new HashMap<>();
tasks.put(new Task(i), trans);
}
System.out.println("Number of tasks: " + tasks.size());
for(Task key1 : tasks.keySet()){
for(Task key2 : tasks.keySet()){
if(key1 != key2
&& !tasks.get(key2).containsKey(key1) // Don't generate an edge, if there already is a reverse edge
&& (tasks.get(key1).isEmpty() // Always generate an edge, if there is none
|| r.nextInt(100) < chance))
{
tasks.get(key1).put(key2, new Transmission(key1,key2));
}
}
}
}
public void printGraph(){
System.out.println("Generated graph:\n");
for(Task key : tasks.keySet()){
System.out.println(key.getId());
for(Transmission ts : tasks.get(key).values()){
System.out.println("\t" + ts.getT1().getId() + " -> " + ts.getT2().getId());
}
}
}
}
编辑
新的解决方案试图将各种意见中讨论的所有要求都纳入其中：
public Graph() {
Random r = new Random();
int range = r.nextInt(maxT) + 3; // number of nodes
for(int i = 0; i<range; i++){
List<Transmission> trans = new ArrayList<Transmission>();
tasks.put(new Task(i), trans);
}
System.out.println("Number of tasks: " + tasks.size());
List<Task> keys = new ArrayList<Task>(tasks.keySet());
for(int i = 0; i < keys.size() - 1; i++) {
Task task1 = keys.get(i);
List<Transmission> task1Transmissions = tasks.get(task1);
task1Transmissions.add(new Transmission(task1, keys.get(i + 1)));
for(int j = i + 2; j < keys.size(); j++) {
if(r.nextInt(100) < chance)
task1Transmissions.add(new Transmission(task1, keys.get(j)));
}
}
}
关于java - 生成有向图而无需在Java中返回边，我们在Stack Overflow上找到一个类似的问题：https://stackoverflow.com/questions/39390928/