Buszman Buszman - 2 months ago 8
Java Question

Generate directed graph without returning edges in java

I'm trying to make a directed graph generator to use it in LJF algorithm. The thing is that I have no idea how to avoid the returning edges (eg. if I got 1 -> 2 I don't want to have 2 -> 1). I only made a statement in

if
to avoid edges to the same node (eg. 1 -> 1). Another problem is that my generator sometimes leaves some nodes alone without any edges but I need at least one edge per node. What I want to reach is something similar to BST but there is no rule to have max 2 edges, it can be more.

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());
}
}
}
}


====EDIT====

After adding order to iterations:

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)));}
}


I got java.lang.NullPointerException exception on this line:

tasks.get(i).add(new Transmission(keys.get(i), keys.get(j)));}


I see that my newly added list is full of null elements, I attach then Task class:

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;
}


}

===EDIT====

Now I got the problem that my generator gives me cycles which I don't want to have. So, I added again chance to make a transmission but sometimes I got free nodes or to seperate graphs.

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

It is simple to avoid (2 -> 1) edes if you have (1 -> 2). For each edge (x -> y) assume that x < y.

Add ordering to iterations:

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));
    }
}

To solve the complete problem you need an alogorithm like this:

  1. N - set of non visited vertexes. All vertexes at the beginning.
  2. V - set of visited vertexes. Empty at the beginning.
  3. Take random vertex x from N.
  4. Add edge(s) (random vertex from V -> x) from second iteration.
  5. Add x to V and remove x from N.
  6. Continue to step 3 or quit.

Your graph will be oriented cycles-free.

Comments