java - Fruchterman 和 Reingold 算法顶点在输出中占据相同位置(图形布局)

Question

我试图用 Java 实现 Fruchterman 和 Reingold 算法，但由于某些原因，输出顶点的坐标有时会占用相同的坐标，这不是该算法想要的。我哪里出错了？

坐标对象( 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);
    }
}

节点对象

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对象(带布局算法函数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();
    }

}

对于过长的问题深表歉意。我尝试了网上的教程，但无法更接近于找出问题所在。请注意，在寻找单位 vector 时，如果 vector 为零(0,0)，我将其设为非常小的非零 vector ，以便当两个顶点彼此靠近时，它们会像作者一样剧烈排斥算法希望。

如有任何说明，我们将不胜感激。

Answer 1

我找到了我的错误。在计算吸引力和排斥力以及其他一些较小的错误时，我对距离进行了两次平方根计算。我在我的问题中发布了更正后的代码。希望尝试此算法的任何人都会发现它有用。请注意，通过移除边界，我们让图形自由进化，它可以产生更好的形状。一旦获得结果图，我们总是可以对其进行平移/缩放，使其适合所需的任何维度。