Batch detecting of crossing edge

1

Hi,
When assigning problems to my students in graph theory, I sometimes write a script to generate dozens of different variants in order to prevent cheating. However, I don’t want to give fundamentally different exercises, since I want to maintain fairness.

What I usually do is give all students essentially the same graph, but with a random permutation of the node labels, and sometimes with slight random variations in the edge weights.

I would now like to take this a step further by rendering the same graph differently — for example, by assigning random initial positions to the nodes and letting Graphviz produce a distinct but aesthetically pleasing layout for each student. However, I would prefer that all students receive a graph with no edge crossings (since the graph is planar).

Of course, I can adjust the relevant settings to minimize the chances of crossings, but I would like to detect and discard any results that still contain them. While an occasional crossing might not make the exercise more difficult, I’d feel more confident that all students are receiving an equally clear and “nice” output if I can avoid this situation.

After carefully reading the documentation, I couldn’t find a practical way to do this. In a script, I could potentially:

  • Make the command-line tool abort with a specific exit code if edge crossings are detected;

  • Parse the -v (verbose) output;

  • Run the command once in a specific format (easier to interpret) before running it again;

  • Use an external tool to analyze the output;

  • etc.

Do you have any ideas for achieving my goal?

2

Finally found it; when using the “dot” engine with the -v option, the number of crossing edges is displayed. I can use the “dot” engine for producing many variants by playing with the “rank” feature.

3

Interesting. Hope this works out.

4

In case your plan doesn’t work as desired, maybe this might help: An Edge-Crossing program - is it useful? - #4 by steveroush

5

Thank you for the link; of course I wouldn’t need the whole machinery; I could probably write a simpler script but the idea is indeed useful for two reasons:

  • the verbose mode of the dot layout engine sometimes claims there is no crossing (because a slightly different curvature in one edge would indeed lead to a perfect display);
  • the verbose mode of sfdp or neato doesn’t tell anything about the number of crossing edges.