Random segfault with LayoutStatistics::numberOfCrossings

[Sebastian]

Greetings,

I'm currently experimenting with different algorithms to reduce crossings in upward planar straight-line drawings on a grid. Since I'm doing most of the algorithm myself I mostly use ogdf to hold my data and to get different measures for my graphs like the number of crossings using the LayoutStatistics.

While those numbers match with the expected results in my initial data, by moving nodes at random I encountered multiple problems:

1. For once the entire program segfaults every so often seemingly at random during the insectionGraph function. While some overlapping edges ran fine, some others did not. I tried to circumvent this by introducing a minimum degree between neighboring edges, which reduced the number of crashes but did not stop them entirely. I know of the warning for those functions, but is dosent seem to apply to my problems, since it does crash sometimes with no overlapping edges at all.

2. For those graphs that do not crash the numberOfCrossings result does not match the actual data anymore.

My current setup reduced to the minimum problem looks something like this:

    Graph G;  
                                                                                                               
    GraphAttributes GA(G,                
        GraphAttributes::nodeGraphics |                                  
        GraphAttributes::edgeGraphics |                                  
        GraphAttributes::nodeStyle |                          
        GraphAttributes::edgeStyle |                      
        GraphAttributes::nodeId);

    /* * manually adding nodes with "G.newNode();" and
      setting x,y,width,height in G
       * adding edges without any any additional data
       * saving all nodes in container "nodes" */

    for(int i = 0; i<1000){
        node n = nodes[rand() % numberOfNodes];
        GA.y(n) = rand() % gridHeight;
        GA.x(n) = rand() % gridWidth;    
   
        // saving the graph as svg

        auto crossings = LayoutStatistics::numberOfCrossings(GA);  
        int cross = Math::sum(crossings);  
        if (cross > 0)  
           cross /= 2;
    }

    // export graph

Either it will crash a some point with no obvious reason visible in the svg or the number of crossings dosent match the actual data/picture.

[Dagobert Smart]

Hello Sebastian,

the problem appears to be a heap-use-after-free in LayoutStatistics_intersect.cpp, line 522 (allocated in line 596, free'd in line 545).

Unfortunately, that is some old code that the current developers are not very familiar with. The problem has been added to the OGDF issue tracker; however, it will probably not be fixed very soon since there are other issues with a higher priority right now.

With the following code, I can reproduce the error consistently:

#include <ogdf/basic/graph_generators.h>
#include <ogdf/basic/LayoutStatistics.h>
#include <ogdf/basic/Math.h>
#include <ogdf/fileformats/GraphIO.h>

using namespace ogdf;

int main() {
    Graph G;
    GraphAttributes GA(G, GraphAttributes::all);
    randomSimpleGraph(G, 15, 40);

    for (int i = 0; i < 1000; i++){
        for (node v : G.nodes) {
            GA.x(v) = randomNumber(0,500);
            GA.y(v) = randomNumber(0,500);
        }

        GraphIO::write(GA, "crossings.svg", GraphIO::drawSVG);

        auto crossings = LayoutStatistics::numberOfCrossings(GA);
        int cross = Math::sum(crossings);

        std::cout << (cross > 0 ? cross/2 : cross) << std::endl;
    }
    return 0;
}

Best regards,

Dagobert