It isn't a graph if it doesn't have nodes and edges. We have our
nodes and edges as separate images. This information isn't really
enough though to tell what's connected, as there is no point where
an (x, y) value is white in both images. To counter this, we have
to cheat a little bit.
A valid approach would be to use the Morphology plugin's
option to expand the edges, then check if it collides
with any nodes. But we have to be very careful, as the dilation may
result in 2 edges joining together.
The solution? Make a temporary image for each edge detected by the
plugin. I'm not going to paste like 5
images here, but we're going to have 1 image per set that was found
with that plugin. This way, we can dilate any of them as much as we
wish and there won't be any overlap. Perfect!
Here's one edge that was detected, put in its own image, and then
Now then, we can build the graph. Scan through every white pixel
and use the Connected Component's "find" function to check if we
have collided with a node. If so, add it to a list. After scanning
all pixels, if the list size is 2 (if the edge only met with 2
nodes), then the 2 nodes that the edge collided with are connected.
You are going to repeat this for every edge image. Discard the ones
where it collides with either more or less than 2 nodes, as they
are invalid. In the end, you will have your graph generated. I had
mine output debug data to make sure that they are connected, and it
gave me this:
[1 -> 3]
[2 -> 3]
[1 -> 4]
[2 -> 5]
[3 -> 4]
It's counting nodes from left-to-right, top-to-bottom by the very
nature of the Connected Components
plugin. Let's number the
ones in the image and see if they line up...
Those 5 edges definitely match up! We have successfully generated
a graph straight from an image.
Now that we have nodes and their edges constructed, we can easily
run DFS on the graph to go from one node to another. The best part
is that we can specify the "to" and "from" points with pixels
because the Connected Components "find" function will give the
index of the node at a current pixel.