Add a Group entity

[matthiasnoback]

This relates to #39.

I decided to break BC and introduce a new entity to represent a Group.

Design choices:

• A group is unique in the entire graph.
• An entity doesn't have to be in a group.
• A group can use its Graph to find out which vertices are also in it.
• A group has to be created before it can be used (same for vertices).

[matthiasnoback]

Please let me know what you think, @clue! Once we have this in the library, I'll make sure to update the Graphviz class from the other package so it will use the layout and label attributes as set on the Group. As I mentioned in the PR description, this breaks BC and has to be released as a new major version. Hope you don't mind :)

I didn't check compatibility with the algorithms package.

Thanks for your work on this package by the way, it's very useful.

[clue]

@matthiasnoback Thank you very much for this high-quality PR and for your patience!

There's not much to add from a code review perspective, the code looks great. However, the reason why I was a bit hesitant with the review is because I'm not quite sure about the project direction to be frank.

It's my understanding we're removing most of the mathematical graph properties #114 and #131 with upcoming versions and the group ID is (currently) mostly used as a mathematical concept (bipartit graphs etc.).

What do you think about this, what feature do groups really provide that can't be solved in a different way?

[matthiasnoback]

Hi Christian, thanks! I didn't think about math, just wanted to define a graph in code, and render it using Graphviz. This seemed to be the right place to enable that. A group needs styling options just like a vertex has, and a way to describe it. The use case I had in mind was static analysis: show a diagram of classes (vertices) in a layer (group), and how they are related to classes in other layers.

[Sebobo]

I have the similar use case for visualising the content type architecture for a graph based CMS. Currently I replace the group ids after converting the graph to graphviz which is a bit cumbersome.

In some views the groups are helpful to see which types belong to which plugin and in other views the clusters are relevant to see the dependencies.

[clue]

Thanks @matthiasnoback and @Sebobo, I think both of you are bringing some very good input!

I wonder if what we're discussing here is really a structural property of the graph or just a way to help visualize the graph structure. The former seems tempting at first, but I couldn't find any mathematical background to back this, expect perhaps for bipartit graphs which would suggest this is more of a property of each vertex. The latter option might be a bit harder to understand at first, but I'd argue that it might actually make more sense in the long run: Instead of adding any objects in this graph library (think subgraphs, nested subgraphs and their relation to vertices, edges and attributes) we could simply resort to a simple set of attributes that mostly seem to apply to vertices (and perhaps a way to apply styling to a group of vertices at once as discussed in #39).

114 suggests all mathematical properties will be replaced with simple attributes in the future, so the group attribute could be used like this (pseudo code):

$vertexA->setAttribute('group', 'first');
$vertexB->setAttribute('group', 'second');

Additionally, we may then find a way to apply graphviz styling options to a group like this (pseudo code):

$graph->setAttribute('graphviz._group.first.label', 'First group');
$graph->setAttribute('graphviz._group.first.color', 'red');

I'm not sure I like the suggested naming convention, but other than that I can see how this could work out. Nested subgraphs might be slightly harder, perhaps it's best to keep them out of the equation for now? What do you think? :+1:

Short link dump: https://graphviz.gitlab.io/_pages/Gallery/directed/cluster.html, http://www.graphviz.org/doc/info/lang.html, https://stackoverflow.com/questions/54595740/nested-directed-subgraphs

[matthiasnoback]

I think the problem is the intention of this library. I thought it just offered a way to define graph-like structures, ignoring the mathematical aspects, making it easy to produce input for Graphviz. That's how I wanted to use it, but I was missing a proper Group entity. I don't think converting everything to attributes is a good idea. I understand why you'd want it, but it removes meaningful operations from these objects. Things become too generic, and hard to get right as well: you'd have to remember the attribute names that have a special meaning, or actually read the code to find out what the API has to offer.

To be completely honest, I'm not waiting for my PR to be merged or anything. I just wanted to make something work on my machine and produce the kind of output I was looking for, and I tried to contribute it back to the project. So please feel free to deviate and do anything that makes maintenance/other use cases easier.

[Sebobo]

Have a similar opinion like @matthiasnoback.

I also know one big issue with defining tree like attributes as it causes issues when the group identifier contains characters that affect the structure. This would for example happen with my.group. So this should be validated or will definitely cause issues. In another project we have a similar issue and it causes regular debugging sessions as the configuration gets mixed up.

[clue]

Again thanks for your input, I think you're raising some very valid concerns! To be perfectly clear, I do want to support the use cases you have in mind as part of this package, even though this might have a mathematical perspective.

I still think grouping vertices is not a structural property of the graph (it doesn't have an "identity"), but something that concerns the rendering of the graph. As such, I've just filed https://github.com/graphp/graphviz/issues/38 to discuss how this could be solved in the GraphViz library instead. For example, this could potentially allow us to group subgraphs/clusters by arbitrary attributes, instead of just a single "group" property. Let me know what you think about this :+1:

I believe this has been answered, so I'm closing this for now. Please come back with more details if this you still think this is an issue and we can reopen this :+1:

[matthiasnoback]

Yes, sounds good. Good luck!