Bdtjtk

I have implemented the force-directed algorithm made by Fruchterman and Reingold in C++, but I still get edge crossings.

I used the implementation that i found on this GitHub page.

This is the function that computes everything:

void Graph2::forceDirectedLayout2(double width, double height)

{

    m_t = 10 * sqrt(m_nodes.size());

    m_width = width;

    m_height = height;

    m_k = sqrt(m_width*m_height / m_nodes.size());

    m_iterations=700;



    for (size_t it = 0; it < m_iterations; it++) {



        for (int v = 0; v < m_nodes.size(); v++) {

            auto nodeV = m_nodes[v];

            nodeV->disp = Coord();

            for (int u = v+1; u < m_nodes.size(); u++) {



                auto nodeU = m_nodes[u];



                Coord delta = nodeV->pos - nodeU->pos;



                double distance = delta.length()+0.0001;

                if (distance > 1000) {

                    continue;

                }



                double repulsion = m_k*m_k / distance;

                nodeV->disp += delta / distance*repulsion;

                nodeU->disp -= delta / distance*repulsion;

            }



            for (int u = 0; u < m_nodes.size(); u++) {



                if (v > u) {

                    continue;

                }

                auto nodeU = m_nodes[u];

                Coord delta = nodeV->pos - nodeU->pos;

                double distance = delta.length()+0.00001;

                double attraction = distance*distance / m_k;

                nodeV->disp -= delta / distance*attraction;

                nodeU->disp += delta / distance*attraction;

            }

        }

        for (int i = 0; i < m_nodes.size(); i++) {

            double dispNorm = m_nodes[i]->disp.length();



            if (dispNorm < 1.0) {

                continue;

            }



            double capDisp = std::min(dispNorm, m_t);



            auto disp = m_nodes[i]->disp / dispNorm*capDisp;

            m_nodes[i]->pos += disp;

      }



        if (m_t > 1.5) {

            m_t *= 0.85;

        } else {

            m_t = 1.5;

        }

    }

}

From other examples I have seen, there aren't supposed to be any edge crossings.
Does anyone know how to fix this? Thanks

The algorithm you use is not guaranteed to eliminate edge crossings, even if the input is planar. E.g. this is an equilibrium state (for some parameters of algorithm):

If you have a guarantee that your graph is planar and you'd like to find its crossing-free drawing, then you may use C++ boost library and its implementation of straight line drawing of planar graphs:
https://www.boost.org/doc/libs/1_67_0/libs/graph/doc/straight_line_drawing.html

Perhaps you'll get a nice result if you combine your current approach with the straight line drawing algorithm as follows:

1. 
   

   Produce a straight line drawing of your graph:

   
   
   

   a. temporarily make it maximal planar by adding edges (make_maximal_planar)

   
   
   

   b. draw it without edge intersections using chrobak_payne_straight_line_drawing

   
   
   

   c. remove edges you added in 1.a.

   
   


2. 
   

   Use your implementation of Fruchterman and Reingold:

   
   
   

   a. initialise the positions of nodes using the result of step 1.

   
   
   

   b. run the force-directed layout algorithm.

   
   

My intuition is that it should produce nicer-looking results than just step 1., probably without introducing edge intersections. But that's only intuition, I don't know how to prove that formally.