An Edge-Crossing program - is it useful?

Help
1

I’ve created a “demo-quality” (kludge-upon-kludge) program to display edge crossings.
Far from perfect, very inefficient (runs in seconds or minutes), can’t handle large graphs (it crashes), often produces questionable results, …

The question: Does anyone have a use for an improved version of such a program?

inet.labeled
inet.labeled791×1008 79.8 KB

go-package.labeled
go-package.labeled1086×720 114 KB

1 Like
2

This is interesting. How was it written?

Sometimes it might be useful to generate symbols to indicate locations where edges cross but don’t connect, like these examples

image
image195×181 1.38 KB

image
image253×199 536 Bytes

3

This is how the thing works. I was sober during this effort, but hard to prove. All the heavy lifting is done with bitmap image manipulation.

  1. create an SVG of the graph of interest
  2. strip all nodes and text from SVG
  3. give each edge a unique color (16M+ possible)
  4. create a copy of modified SVG, but with edges in reverse order!
  5. convert the two SVG files to bitmaps
  6. XOR the two bitmaps (This is the key. The two bitmaps differ ONLY where the edges intersected and were drawn in reverse order) Now we have a color bitmap image that only shows where the intersections are.
    (now, lots of fiddly stuff)
  7. convert the color XOR bitmap to 1-bit-per-pixel bitmap
  8. try to count the intersections. This is surprisingly challenging, especially as the graphs get larger.
  9. enlarge the size of the XOR blobs, to make them more visible
  10. color the (enlarged) bitmap
  11. convert the original (unedited) SVG to a raster (bitmap)
  12. overlay the colored blob image onto the raster (bitmap) version of the original SVG
  13. create a label image with filename and blob count
  14. append the label to the overlay image

Almost all of it is done with netpbm and imagemagick, plus some gawk and bash
The first few steps could have been done “inside” Graphviz, but this was all done by processing the SVG

2 Likes
4

The scheme described above can probably be extended to identify the intersection edges (based on edge colors), but TBD.
Likewise, cleaning-up (simplifying) long intersections of nearly parallel edges is very TBD.

Stephen’s suggestion of non-connecting edges might be better implemented using algebra - at least if all the edges consisted of straight-line segments. But this seems to be effectively an N-squared problem - compare every edge segment to every other edge segment. Clever programming can probably save many cycles, but I’m out of clever.
Finding intersections of non-straight splines would appear to be even more challenging.

5

That’s clever. I wouldn’t change a thing right away.

Wondering about plugging the points into a spatial data structure, and using pixel colors to identify specific crossings and to filter unintended spline overlaps.

Wonder how much of this could be done inside graphviz itself. If we wanted to render the layout into an image used internally for this, is that convenient, can it be done somewhat portably?