Hi Ben,
Sorry for the delay, I was very bussy these last few days. Attached to this mail you will find some drawings showing what I mean.
The first attachement [1] show the two most important graph concepts that are needed for circuit design: the support for hyper-edges, and the ports crossing hierarchical nodes.�
The hyper-edges are useful to represent physical wires (which are connected to a source, and then provide input to a number of sinks).�
The hierarchical crossings can be thought as the physical pins of an integrated circuit, that are plugged into a socket in order to integrate that circuit into a system.
The second, and third attachement are the same (only the format differs pdf vs png). They show a detailed example of the hierarchical structure that I imagine. The main elements of this graphs are: the leaf nodes, the edges, the hierarchical nodes, the pins, and the ports.�
The leaf nodes are just the typical graph nodes. The edges are just links between nodes.�
The hierarchical nodes are graphs themselves, but they can be connected one to another using edges. However these connections between hierarchical nodes are done through the pins present on their interface. If such a hierarchical node wants to be connected to the exterior it has to have pins so that the layout algorithm can be constrained to route the edges to these pins (which can be either free or have fixed positions).
The ports in my figure are just ways to group together a number of pins.
In the figure you will see three graphs (corresponding to three views on the leftmost graph).�
The first one (on the left) just represents the top-level graph with all hierarchical nodes collapsed. This graph itself has a number of ports so that it can be embedded in another one.�
The second one (in the middle) shows an expanded view of the central hierarchical node in the top-level graph. This one is expanded into another view.
The third one (in the right) shows yet another expanded view, this time of a node in the middle graph. This last graph contains two hierarchical nodes itself that are expanded in place.
Now the idea of edges crossing hierarchy boundaries through pins is that the inner-most hierarchical nodes can be layed out separately and then collapsed, their containers can be layed out just like a simple graph (in the case their nodes are collapsed). However if one node is a hierarchical one, and is expanded, the layout algorithm does not have to layout the contents inside this hierarchical node, it just layouts the whole graph considering the pins as fixed nodes to which it will route the links. This way when expanded the hierarchical nodes retain their initial layout, moreover this initial layout takes into account the fact that the node will be embedded into a �larger graph and thus it will place the pins on the boundary.
FYI the graphs shown in the last two attachements where automatically generated from a circuit design, they were imported into the Yed diagram editor, one by one, layed out semi-automatically (used force-based layout initially, an then moved a number of nodes manually to align them well - ex the straight edges were obtained by manually moving the nodes). Just imagine how boring this process is. Moreover since I had to represent the pins, and the ports just as plain graph nodes grouped together the layout algorithms don't have any idea that these nodes are special, thus they place them everywhere, even more if the groups are expanded their inner nodes are layouted along with the embedding hierarchy... resulting in a mess.�
Cheers,
Ciprian
References:
[1] Miro Sponemann, Hauke Fuhrmann, Reinhard von Hanxleden, and�Petra Mutzel.�
In David Eppstein and Emden Gansner, editors, Graph�Drawing, volume 5849 of Lecture Notes in Computer Science,�chapter 14.
Springer Berlin / Heidelberg, Berlin,�Heidelberg, 2010.
On Thu, Sep 27, 2012 at 3:35 PM, Ben Coman
<btc@openinworld.com> wrote:
Ciprian,
I have skimmed through those links but can't quite understand your comment "in order to preserve the connections passing through the hierarchy" Can you expand some more on that - perhaps with a mock up in a paint program?
If you are interested in following the development of Roassal, perhaps move your follow up to https://www.iam.unibe.ch/mailman/listinfo/moose-dev. <https://www.iam.unibe.ch/mailman/listinfo/moose-dev>
I have been very encouraged by the clean architecture and the responsiveness of the main developers to feature suggestions.
cheers, Ben
--
Dr. Ciprian TEODOROV
Ing�nieur�D�veloppement�CAO
t�l : 06 08 54 73 48
mail :�ciprian.teodorov@gmail.com
www.teodorov.ro