![[personal profile]](https://www.dreamwidth.org/img/silk/identity/user.png){kind=small}
elfsMy current work assignment involves dynamically rendering a directed graph with potentially both cycles and disconnects. A "graph" in this case is a mathematical construct of nodes and connectors; "directed" means the connectors go in one direction, from one node to another. A "disconnected" graph means there may be subgraphs for which one cannot, starting from an arbitrary node, traverse the list of nodes to reach another arbitrary node; there isn't a connector between the two subgraphs. A graph with "cycles" is one where it's possible to end up in a loop, going around and around and around.
Drawing this beast on the screen aesthetically is considered a Hard Problem, but fortunately, there are a number of papers on it with "good enough" solutions. The best seems to be Alaa K. Ismaeel's Dynamic Hierarchical Graph Drawing.
According to the book, there are a few steps one must take: (1) figure out all of the disconnected subgraphs; (2) figure out if any of the subgraphs have cycles; (3) break the cycles, but remember what you broke so you can put it back; (4) figure out at what "depth" each node should be; (5) re-arrange the nodes such that you minimize the number of connectors that "cross" each other; (6) lay out the nodes with enough distance between them. I'm up to (3), and even managed to get it to successfully and correctly break the cycles in a Petersen Graph without damaging the graph's internal logic.
Man, that was fun. Well, on to the rest of it tomorrow.
Drawing this beast on the screen aesthetically is considered a Hard Problem, but fortunately, there are a number of papers on it with "good enough" solutions. The best seems to be Alaa K. Ismaeel's Dynamic Hierarchical Graph Drawing.
According to the book, there are a few steps one must take: (1) figure out all of the disconnected subgraphs; (2) figure out if any of the subgraphs have cycles; (3) break the cycles, but remember what you broke so you can put it back; (4) figure out at what "depth" each node should be; (5) re-arrange the nodes such that you minimize the number of connectors that "cross" each other; (6) lay out the nodes with enough distance between them. I'm up to (3), and even managed to get it to successfully and correctly break the cycles in a Petersen Graph without damaging the graph's internal logic.
Man, that was fun. Well, on to the rest of it tomorrow.
