java - 在java中生成不返回边的有向图

Question

我正在尝试制作一个有向图生成器以在 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)));}
    }

Answer 1

如果您有 (1 -> 2)，则很容易避免 (2 -> 1) edes。对于每条边 (x -> y)，假设 x < y。

为迭代添加顺序:

List<T> keys = new ArrayList<>(map.keySet());
for (int i = 0; i < keys.size() - 1; i++) {
    for (int j = i + 1; j < keys.size(); j++) {
        make new Transmission(keys.get(i), keys.get(j));
    }
}

要解决完整的问题，您需要这样的算法:

1. N - 一组未访问的顶点。所有顶点都在开头。
2. V - 已访问顶点集。开头为空。
3. 从 N 中随机取顶点 x。
4. 从第二次迭代中添加边(来自 V -> x 的随机顶点)。
5. 将 x 添加到 V 并从 N 中删除 x。
6. 继续第 3 步或退出。

您的图表将无循环定向。