I was attempting to implement Fruchterman and Reingold algorithm in Java, but for some reasons, the coordinate of output vertices sometimes occupy the same coordinates, which is not something this algorithm would want. Where did I go wrong?
Coordinate object (vector)
public class Coordinates {
private float x;
private float y;
public Coordinates(float xx, float yy){
x = xx; y = yy;
}
public float getX() {
return x;
}
public void setX(float x) {
this.x = x;
}
public float getY() {
return y;
}
public void setY(float y) {
this.y = y;
}
public String toString(){
return x+" "+y;
}
public Coordinates subtract(Coordinates c){
return new Coordinates(x-c.x, y - c.y);
}
public Coordinates add(Coordinates c){
return new Coordinates(x + c.x, y + c.y);
}
public Coordinates unit(){
if(length() == 0)
return new Coordinates(0.000001f,0.0000001f);
else
return new Coordinates(x/(float)Math.sqrt(x*x + y*y),y/(float)Math.sqrt(y*y + x*x));
}
public float length(){
return (float)Math.sqrt(x*x + y*y);
}
public float distance(Coordinates c){
return (float) Math.sqrt((x-c.x)*(x-c.x) + (y-c.y)*(y-c.y));
}
public Coordinates scale(float k){
return new Coordinates(k*x,k*y);
}
}
Node object
import java.util.LinkedList;
public class Node {
private LinkedList<Node> incidentList; //has 30 elements for 30 vertices. 1 if incident, 0 if not
private int color;
private Coordinates coord;
private Coordinates disp;
public Coordinates getDisp() {
return disp;
}
public void setDisp(float x, float y) {
disp.setX(x);
disp.setY(y);
}
public void setDisp(Coordinates d) {
disp = d;
}
private int id;
public Node(){
incidentList = new LinkedList<Node>();
color = 0;
coord = new Coordinates(0,0);
disp = new Coordinates(0,0);
id = -1;
}
public int getId() {
return id;
}
public void setId(int id) {
this.id = id;
}
public LinkedList<Node> getIncidentList() {
return incidentList;
}
public void addEdge(Node n) {
incidentList.add(n);
}
public void removeEdge(Node n){
incidentList.remove(n);
}
public int getColor() {
return color;
}
public void setColor(int color) {
this.color = color;
}
public Coordinates getCoord() {
return coord;
}
public void setCoord(float x, float y) {
coord.setX(x);
coord.setY(y);
}
public int getDegree(){
return incidentList.size();
}
public boolean isAdjacent(Node n){
return incidentList.contains(n);
}
}
Graph object (with layout algorithm function frlayout)
import java.util.ArrayList;
import java.util.Random;
public class MyGraph{
private final int DISRESPECT = -1;
private final int MORECOLOR = -3;
private final float EPSILON = 0.003f;
private ArrayList<Node> graphNodes; //maximum of 30 vertices
private int nVertices = 0;
private int score = 50;
int maxColor = 0;
int[] colorPopulation = new int[15];
double boundx, boundy, C;
public double getBoundx() {
return boundx;
}
public void setBoundx(double boundx) {
this.boundx = boundx;
}
public double getBoundy() {
return boundy;
}
public void setBoundy(double boundy) {
this.boundy = boundy;
}
public double getC() {
return C;
}
public void setC(double c) {
C = c;
}
public int getScore() {
return score;
}
public void setScore(int score) {
this.score = score;
}
public int getnVertices() {
return nVertices;
}
public MyGraph(){
graphNodes = new ArrayList<Node>();
}
public ArrayList<Node> getGraphNodes() {
return graphNodes;
}
//add a new node into the graph
//also set the id of that node
public void addNode(Node n){
graphNodes.add(n);
n.setId(nVertices++);
}
public void addEdge(Node n1, Node n2){
n1.addEdge(n2);
n2.addEdge(n1);
}
//randomly generate a graph with parsity
public void randomGenerating(double parse){ //parse is between 0 and 1
Random gen = new Random(System.currentTimeMillis());
int tempNVertices = 6; //CHANGE HERE TO BECOME A RANDOM NUMBER
for(int i = 0; i< tempNVertices; i++){
Node n = new Node();
float x = 0,y = 0;
while(true){
boolean flag = true;
x = gen.nextFloat();
y = gen.nextFloat();
for(int j = 0; j < i; j++){
if(x*boundx == graphNodes.get(j).getCoord().getX() && y*boundx == graphNodes.get(j).getCoord().getY())
flag = false; break;
}
if (flag)
break;
}
n.setCoord((float)(x*boundx),(float)(y*boundy));
addNode(n);
}
for(int i = 0; i < tempNVertices; i++){
for(int j = i + 1; j < tempNVertices; j++){
if(gen.nextDouble() < parse){
addEdge(graphNodes.get(i),graphNodes.get(j));
}
}
}
}
public void frLayout(){
double w = boundx, h = boundy;
double area = w*h;
double k = C*Math.sqrt(area/nVertices);
double temperature = 1000;
for(int i = 0; i < nVertices; i++)
System.out.println(graphNodes.get(i).getCoord().getX()+" "+graphNodes.get(i).getCoord().getY());
System.out.println("------------------------------");
for(int m = 0; m< 900; m++){
for(int i = 0; i < nVertices; i++){
Node v = graphNodes.get(i);
v.setDisp(0,0);
for(int j = 0; j< nVertices; j++){
Node u = graphNodes.get(j);
if(i!= j){
Coordinates delta = v.getCoord().subtract(u.getCoord());
double myFr = fr(u,v,k);
v.setDisp(v.getDisp().add(delta.unit().scale((float)myFr)));
if(Double.isNaN(v.getDisp().getX())){
System.out.println("PANIC: "+u.getCoord().getX()+" "+u.getCoord().getY()+" "+delta.getX()+" "+v.getCoord().getX());
return;
}
}
}
}
for(int i = 0; i < nVertices; i++){
Node v = graphNodes.get(i);
for(int j = i+1; j< nVertices; j++){
Node u = graphNodes.get(j);
if(v.isAdjacent(u)){
Coordinates delta = v.getCoord().subtract(u.getCoord());
double myFa = fa(u,v,k);
v.setDisp(v.getDisp().subtract(delta.unit().scale((float)myFa)));
u.setDisp(u.getDisp().add(delta.unit().scale((float)myFa)));
}
}
}
for(int i = 0; i< nVertices; i++){
//actually adjusting the nodes
Node v = graphNodes.get(i);
if(i == 0){
System.out.println(v.getCoord().getX()+" "+v.getCoord().getY());
Coordinates disp = v.getDisp().unit().scale((float)Math.min(v.getDisp().length(), temperature));
System.out.println(">>"+disp.getX()+" "+disp.getY());
}
Coordinates newCoord = (v.getCoord().add(v.getDisp().unit().scale((float)Math.min(v.getDisp().length(), temperature))));
v.setCoord(newCoord.getX(), newCoord.getY());
// //prevent from going outside of bound
// float x = (float)Math.min(w, Math.max(0,v.getCoord().getX()));
// float y = (float)Math.min(h, Math.max(0, v.getCoord().getY()));
//
// v.setCoord(x,y);
if(i == 0){
System.out.println(v.getCoord().getX()+" "+v.getCoord().getY());
}
}
temperature *= 0.9;
System.out.println("TEMPERATURE = "+temperature);
}
for(int i = 0; i< nVertices; i++){
Node v = graphNodes.get(i);
System.out.println(v.getCoord().getX()+" "+v.getCoord().getY());;
}
}
private double fa(Node ni, Node nj, double k){
double distance = ni.getCoord().distance(nj.getCoord());
return distance*distance/k;
}
private double fr(Node ni, Node nj, double k){
double distance = ni.getCoord().distance(nj.getCoord());
return k*k/(distance+0.000001);
}
public static void main(String[] args){
MyGraph grph = new MyGraph();
grph.setBoundx(480);
grph.setBoundy(480);
grph.setC(1);
grph.randomGenerating(1);
grph.frLayout();
}
}
Apologies for the overly long question. I tried tutorials on net, but couldn't get anywhere closer to figuring out what's going wrong. Note that when finding unit vector, if a vector is zero (0,0), I make it a very small, non-zero vector so that when two vertices are close to one another, they will repel violently just as the author of the algorithm hoped.
Any instructions would be appreciated.
I found my bug. I was taking square root of the distance twice while computing the attraction and repulsion forces as well as a few other smaller bugs. I posted the corrected code in my question. Hopefully anyone out there attempting this algorithm will find it useful. Note that by removing the boundary, we let the graph free to evolve, it could produce better shape. Once obtaining the resulting graph, we could always translate/scale it so that it fit into whatever dimension required.