This tool allows you to automatically group the nodes of a graph in accordance with one of the following criteria:
The chapter Settings of Section ‘Grouping’ gives a description of all controls which affect the
grouping. The computed groups can be depicted as group nodes and by using shared visual properties, the details are
described in Settings of Section ‘Presentation’.
Definitions
- Member of a Group
- A node which is part of a group is called member of this group.
- Path
- A path is a sequence of nodes in which two consecutive nodes are connected by an edge of the graph.
Grouping Types
Connected Components
A group is called connected, if there is a path from every member to every other member and all intermediate
nodes are also members of the group. The connected components of a graph are connected groups of maximum size, i.e.,
all nodes which are reachable from any member must be also members of the group. Every node of the graph is a member of
exactly one connected component.
Biconnected Components
Biconnected components are similar to (single) connected components but there must be two independent paths instead of
one between every pair of members. Unlike connected components which form distinct groups, two biconnected components
can share a common node. Since group nodes cannot be used in this case, yEd assigns such nodes to only one component.
Natural Clusters
A grouping into natural clusters should fulfill the following properties:
- each node is a member of exactly one group,
- each node should have many edges to other members of its group, and
- each node should have few or even no edges to nodes of other groups.
yEd features a general purpose clustering algorithm whose only setting allows you to adjust the weighting
between the quality of the grouping and the calculation time.
Details of the Algorithm. The algorithm is based on Edge Betweenness Clustering proposed by
Girvan and Newman. For the highest quality setting, it is used almost unmodified. In the central, recommended
position, the fast betweenness approximation of Brandes und Pich (Centrality Estimation in Large Networks) is
employed. Typically, this results in a tiny decrease in quality but a great increase in speed. To achieve the lowest running
time, a local betweenness calculation is used (Gregory: Local Betweenness for Finding Communities in Networks).
Sub-Trees
A sub-tree is a group characterized by following two properties. Its internal structure is a tree and at most one of
its members has edges to outside nodes. By definition, single nodes are not sub-trees. Optionally, the direction of
edges can be considered. In this case, the internal structure of the group must be a directed tree and the member
which has edges to outside nodes must be its root. Each node can be member of at most one sub-tree.
Chains
Chains are paths whose inner nodes have degree equal to 2, i.e., each inner node has exactly two edges, one to
its predecessor and one to its successor in the path. By definition, the first and the last node of the path are not
part of a chain. Optionally, the direction of edges can be considered. In this case, edges can only be used in their
direction. Each node can be member of at most one chain.
Settings in Section ‘Grouping’
Grouping Type
Selects the grouping type. The options are described in Grouping Types.
Consider Direction
Specifies whether the direction of edges should be considered for Sub-Trees and Chains.
Existing Groups
Defines how to handle existing groups. The alternatives are to ungroup all or the keep closed folders. It is possible
to preserve closed folders, since they can be treated like regular nodes. In general, open groups do not conform to
the selected grouping criterion and, therefore, must be ungrouped. The only exception is the Refinement of
Existing Groups.
Quality/Time Ratio
Controls the weighting between the quality of the grouping and the calculating time when computing natural clusters. The central position is recommended for most graphs since it combines
very good quality with low running time. For large graphs, it may be required to switch to an even faster setting.
Higher quality settings may be used for small graphs but calculating time will increase significantly.
Refine Existing Groups
Allows you to use the existing groups as a starting point for further refinements. In this process, existing groups are
sub-divided into smaller groups but nodes which initially belonged to different groups will never be assigned to the
same group. This setting is available only for natural clusters.
Settings in Section ‘Presentation’
Node Label Text
Assigns to all members of a group the same label text. This consists of the grouping type and a group ID. If the
setting Group Label Text is appropriately set, the ID is adopted from the group node.
Node Fill Color
Uses the node fill color to depict groups, i.e., only members of the same group are tinted with the same color. If the
setting Group Color is also activated, the color of a group node and its members is the same.
Group Nodes
Defines the type of group node to use. The available options are Opened Group, Closed
Folder, and None.
Group Label Text
Defines the text of the group label. Optionally, there is no label at all or the text consists of a combination of
group ID and member count. If the setting Node Label Text is also activated, the group ID is adopted
by its members.
Group Color
Sets different background colors for the labels of different group nodes. If the setting Node Fill
Color is also activated, the color of a group node and its members is the same.