Layout proposal: nodes "clustered" by groups

[Muntaner]

In various projects where I used VisJS, I often had the need to implement a node clustering feature based on the groups. I'm not talking about the already implemented clustering feature where one node can contain other nodes, but a layout which places nodes of the same group in the same region of space in VisJS canvas. I also reported this "problem" in an issue on the original VisJS GitHub project.

One good example where you can see what I mean for this is the world cup example hosted on the site, where all the nodes are nicely clustered and "all nearly placed" based on their group. But... in the examples, the effect is obtained by the physics engine - as far as I understood - which tends to place highly connected components all together, while I needed a feature where the user simply puts some groups to the nodes and VisJS magically places them in a clustered way.

So, after some experimenting and having fun with VisJS, I came up with a prototypical implementation for this layout, which I'll describe there in a form of simple list of steps.

In short, the algorithm for the feature works by dividing the canvas space where VisJS places the nodes and programmatically assigning xy positions to all the nodes.

1. The space where VisJS works is considered to be a circle that gets sliced in n partitions, where n is the number of the distinct groups specified in the dataset of nodes. This is simply done by slicing the 360° space for the number of groups with some basic trigonometry.
2. Each of those partitions of space is related to a group of the nodes and has its own center. XY positions of nodes are then calculated in order to be placed on the circumference of such partitions, with the radius of the partition scaled according to how much nodes belong to that group partition (a group of two nodes will get a smaller partition compared to a partition related to a 50 nodes group). Still, this is done by using some trigonometric basic concepts.
3. Physics engine is disabled in order to place the nodes in the xy calculated positions.
4. (optional?) I also used a "fancy" way to visualize the obtained clusters by using a convex hull algorithm. Clusters of node are surrounded within a colored polygon (this is done on the canvas in the afterDrawing function). This can be CPU intensive because convex hull is calculated for each rendering frame for each group, but works pretty well in practice.
5. Result is that different groups of nodes are placed and clustered in circles, placed around the VisJS canvas, amongly spaced, independently from their connections/edges (screenshots attached).

I implemented such prototype in a local minimal project, and I'm attaching some screenshots to show the results.

Problems:

• is this a really needed layout or it is useful only in niche/rare use cases? :) is all of this a not needed overkill?
• design and produce a general version of the algorithm which responds well to highly populated groups and high variance between the population of the groups

400 nodes, 8 groups 2 groups clusters 4 groups clusters Convex hull detail

[Thomaash]

I can't really image why someone would do this but that may be just my limited imagination. Could you, please, showcase some projects that good make use of it? Because to me it seems quite weird and the edges go all over the place in a very chaotic manner. Seems really hard to navigate. Though I can't say anything definitive before I actually see it in action and also the code anyway.

In the future I'd like to have the layouts reworked into modular design and custom layout support (something like network.addLayout("custom-layout-name", customLayoutFunction);). We could then provide a library with all kinds of niche layouts (like this one) without cluttering the library with code vast majority of people will never use.

[mojoaxel]

Hi Michele! Thanks for opening this issue! Please feel free to also share your implementation progress e.g. in a draft pull-request.

As @Thomaash already mentioned it would also be useful to describe how these kind of layout could be used.

[szabi]

@Muntaner, I'd imagine creating densely connected subgraphs with hidden layers cateters very well for placing them close via the physics engine. You can have physically active (present) but hidden edges.

edges.push({
  from: 1,
  to: 2,
  label: "1--2",
  hidden: true
//        ^^^^
});

Did you experiment with that?

[clem-41]

I actually really, really need such a feature! I thought it was already implemented, because I don't really see the point of having groups of nodes if the groups don't "regroup" the nodes in the same area... now I have this gigantic network with nodes from groups scattered all around when I really need them to be in separate areas, because right now you can't see anything, there's way too much information.

You can see my network here: https://clemsmusic.com/thechart/chart_example.php The nodes are characters, and the groups are shows that these characters belong to. When you click on a node, a popup appears, and if you click on the name of the show in the popup, the nodes from the group (= the characters from the show) appear in red. You can see they're not in the same area at all... which makes it all really hard to read.

So I vote a big YES to this kind of layout!

[Thomaash]

Hi @clem-41,

could you provide some more info about this? Ideally disable physics, position the nodes the way you want and post before and after screenshots. If you want some background highlighting of groups, borders or so sketch it there too (it doesn't have to be pretty or contain a million nodes, just to show what you want so that we're all on the same boat).

Thanks.

PS: If you want to know why it makes sense to have groups of nodes that don't group in the same area look on https://thomaash.github.io/me/#/canvas. There is a group for computers, a group for switches, another group for ports and so on.

[Thomaash]

An idea here: We already have groups and clusters. Could we call this districts? Thumbs up? Thumbs down? Better names?

[clem-41]

Yes I think districts is a good name for this.

In my specific case, I don't need a precise shape for the districts (like the circles from Muntaner's post). I just want the nodes to stay in the same area, next to the nodes from the other groups.

Here's what my network looks like now: the nodes that belong to a same group aren't next to each other, they're all scattered across the network.

And here's what I would like to get (I only detached the nodes of three groups from the rest of the nodes to show you what it would look like): roughly the same presentation, but with nodes from a group next to the other nodes of the same groups. (Please note that the red borders are just here to show the different groups of nodes, but I don't want them to appear on the network)

[Thomaash]

This is mostly brainstorming but:

• A node could belong to a district.
• All nodes in each district would be positioned in isolation.
• All first level districts (districts of nodes) would be positioned.
• All second level districts (districts of districts of nodes) would be positioned.
• All third level districts (districts of districts of districts of nodes) would be positioned.
• And so on.
• All top level districts and nodes not belonging to any district would be positioned.
• Absolute positions would be written into the nodes.

Each district would be done independently in isolation (parallelization opportunity here). This would allow different configurations, layout algorithms etc. for each district. I don't see a difference between a node and a district for layouting (a node has some bounding box and position, a district has some bounding box and position). This could easily be implemented as recursive algorithm running from bottom to top. Basically solving this and #136 in one go.

The districts could have some basic optional styling:

• borders,
• labels,
• backgrounds.

And someone would have to go, throw away all the algorithms (they're poorly documented and in ancient JS, plus having them in TS would be nice, also the people who wrote them are long gone) and write brand new ones. I think that adapting what we have for such drastic change would be more work though as always I may be wrong.

PS: There's no exact algorithm behind this. If I'm missing something important, please tell.

[clem-41]

I'm really not good at this so I can't tell you if something's missing, but what you said sounds good so far! I hope Muntaner comes back here soon so that they can give their opinion on this.

I'm guessing this will take a while to do, right?

[Thomaash]

Yeah, this will take a while. Especially since I want to solve a few other issues first.

PS: Contributions are always welcome and deeply appreciated. Just saying in case anyone has some free time.

[rsshilli]

This is very useful! I want to add another use case / some more ideas for this feature. We use vis.js for helping create better/cheaper/safer medications in the pharmaceutical industry (qbdvision.com). This example below is test data that's dumbed down a lot. Imagine here that we're analyzing how to create a better cake:

So at the top are the "Final Quality Attributes" of the cake. This is an analysis of the cake after it's made, like the external color, gluten content, etc. On the left are the attributes of the incoming materials (think flour, eggs, etc), and on the bottom are the important things to measure at each stage of making the cake. In this very contrived example, you might mix the dry ingredients separately from the wet ingredients, then mix them all together. You'll have different mixing times, as well as different measurements of fat content, etc. This graph helps scientists figure out what they understand, what they don't understand and how it's all related. The context of which attributes are in which steps of the manufacturing process is very, very helpful. Real-world examples are obviously much, much more complex.

I've created the above grey boxes listening to the beforeDrawing event and drawing the boxes on the canvas. My users would love to drag and drop those grey boxes around, in order to move the manufacturing steps around and think through different ways to solve various problems. This feature literally can help design cures to many terrible diseases, including cancer.

[Thomaash]

Hi @rsshilli,

thanks for your use case. This is pretty much exactly what I imagine this to look like. It's great to have it on a nice picture and to know there are many people who would use it.

[meshy]

This would be great for me too. My use-case for this would be for generating database entity relationship diagrams, where clusters of tables are grouped together into "apps" (in Django terminology).

This would be a particularly nice use for it, as most of the connections would most likely be within the app-groups.

[ccamacho]

Hi @rsshilli by any chance, do you have an example for rendering the network like you have in https://github.com/visjs/vis-network/issues/203#issuecomment-571164712 ?

Thanks!

[rsshilli]

@ccamacho No, unfortunately, I don't. It's quite a bit of code in a private repository.

The gist though is to figure out how to lay everything out and then:

• listen to the "beforeDrawing" event to use raw drawing events to draw the boxes

      network.on("beforeDrawing", this.onBeforeGraphDrawing);

• listen to the "dragStart" event to figure out if one of the boxes is being dragged

      network.on("dragStart", this.onDragStart);

Then if the user is dragging the box, select the all of the nodes so they're dragging that instead:

  onDragStart(event) {
    // Search for a container box that might be clicked on.
    const canvasPosition = event.pointer.canvas;
    const allNodeIdsInContainerBox = this.getAllNodeIdsInContainerBoxAt(canvasPosition);

    if (allNodeIdsInContainerBox) {
      window.network.selectNodes(allNodeIdsInContainerBox);
    }
  }

As they drag the nodes around now, the box will still keep getting drawn using the beforeDrawing event as they drag the items around the screen.

Hopefully, that helps.

[chichistrong]

I totally need this for my project. I am currently working on a dependency mapping tool and I want the user to be able to arrange dependencies by it’s group, if they want to. Just like in your example layout. I am surprised nobody has ever thought of adding this to vis us before, but goodness I need this.

[nlinton]

This would also be really useful for infectious disease epidemiology, where individual cases are connected to some other cases, but then also might be connected to (or only connected to) a "cluster" (i.e. a location or event associated with multiple cases).

[monicaraghuwanshi]

I also have a similar usecase. Would be great if it is possible.

[aguinaldoabbj]

In various projects where I used VisJS, I often had the need to implement a node clustering feature based on the groups. I'm not talking about the already implemented clustering feature where one node can contain other nodes, but a layout which places nodes of the same group in the same region of space in VisJS canvas.

One good example where you can see what I mean for this is the world cup example hosted on the site, where all the nodes are nicely clustered and "all nearly placed" based on their group. I also reported this "problem" in an issue on the original VisJS GitHub project. But... in the examples, the effect is obtained by the physics engine - as far as I understood - which tends to place highly connected components all together, while I needed a feature where the user simply puts some groups to the nodes and VisJS magically places them in a clustered way.

So, after some experimenting and having fun with VisJS, I came up with a prototypical implementation for this layout, which I'll describe there in a form of simple list of steps.

In short, the algorithm for the feature works by dividing the canvas space where VisJS places the nodes and programmatically assigning xy positions to all the nodes.

1. The space where VisJS works is considered to be a circle that gets sliced in n partitions, where n is the number of the distinct groups specified in the dataset of nodes. This is simply done by slicing the 360° space for the number of groups with some basic trigonometry.
2. Each of those partitions of space is related to a group of the nodes and has its own center. XY positions of nodes are then calculated in order to be placed on the circumference of such partitions, with the radius of the partition scaled according to how much nodes belong to that group partition (a group of two nodes will get a smaller partition compared to a partition related to a 50 nodes group). Still, this is done by using some trigonometric basic concepts.
3. Physics engine is disabled in order to place the nodes in the xy calculated positions.
4. (optional?) I also used a "fancy" way to visualize the obtained clusters by using a convex hull algorithm. Clusters of node are surrounded within a colored polygon (this is done on the canvas in the afterDrawing function). This can be CPU intensive because convex hull is calculated for each rendering frame for each group, but works pretty well in practice.
5. Result is that different groups of nodes are placed and clustered in circles, placed around the VisJS canvas, amongly spaced, independently from their connections/edges (screenshots attached).

I implemented such prototype in a local minimal project, and I'm attaching some screenshots to show the results.

Problems:

• is this a really needed layout or it is useful only in niche/rare use cases? :) is all of this a not needed overkill?
• design and produce a general version of the algorithm which responds well to highly populated groups and high variance between the population of the groups

400 nodes, 8 groups 2 groups clusters 4 groups clusters Convex hull detail

Are those World Cup 2014 examples really based on the physics engine? I can't see where. One of the examples, the physics engine is turned off:

I have a use case that would benefit a lot from such a kind of node organization. I have a complete graph and I'd like to cluster nodes on the same group together, hide all inter-cluster edges but keeping edges with a higher weight attribute.

[Muntaner]

Hi! I don't know what's the status of the proposal, but I just wanted to give a brief update: in my free time I implemented an alternative layout which places districts and nodes inside them in squared shapes. It could be useful for some use cases or give better visualization of some grouped networks. The algorithm principle is the same, I just changed the way partitions (groups) and nodes are disposed in the canvas.

If you want to play around with the implementation, here it is a codebox with configurable parameters (both for network and districts): https://codesandbox.io/s/visjs-districts-qk5zb. As you can see, it is possible to tweak parameters related to the network (groups, nodes, edges) and the districts algorithm, and also choose the original layout (circles) vs the new one (square).

As you can see some stuff needs to be manually tweaked (districts distance and size) especially in the cases where the districts algorithm does not always respond well (for example, big number of nodes and low number of groups seems to be a tricky situation). I think the parameters could be tweaked around the size of each group and the number of nodes, but any suggestions are welcome there.

[aguinaldoabbj]

@Muntaner Great work! I believe this is a long-waited feature for some vis.js users. Is there a code repo?

[Muntaner]

@Muntaner Great work! I believe this is a long-waited feature for some vis.js users. Is there a code repo?

I used to have a repo for this feature, but I realized I really don't have the time to dedicate to the project in order to polish it and properly find a way to integrate it with the VisJS codebase and I decided to close it.

All the code (raw, rough, untested, whatever :P ) that produces the districts we discussed in this ticket is available in the codebox I linked in the previous comment. It must not be considered at all production-ready code, but a quick way to implement the feature on top of the existing VisJS release - no need to hijack in the original code or patch it. It would be great if anyone with more time and dedication could start from that dirty implementation and improve it, and eventually understand if it can be someway integrated with the existing library.

[ooker777]

For a quick hack, how about making invisible edges and let the physic algorithm decides the positions?

[Muntaner]

For a quick hack, how about making invisible edges and let the physic algorithm decides the positions?

I think this could work, but I never tested it and can see some quirks there... for example, how to decide the number of edges per group? Connecting all of the nodes could be super-heavy for the physics engine, I guess. And so, this could scale very badly with huge networks/many nodes and groups.

[ooker777]

Another example case

For a directed graph there will be source points, which have the in-degree=0. I want to group all nodes that are descendants of a source point together, and draw a border outside of them. So a graph with many source points will have many components like that. And if a node is a descendant of many source points, then it will be in the intersect of many components.

This is also asked in Stack Overflow: Bordered group of nodes in a network graph?

[Muntaner]

Another example case

For a directed graph there will be source points, which have the in-degree=0. I want to group all nodes that are descendants of a source point together, and draw a border outside of them. So a graph with many source points will have many components like that. And if a node is a descendant of many source points, then it will be in the intersect of many components.

This is also asked in Stack Overflow: Bordered group of nodes in a network graph?

This proposal would probably solve the "group all descendants together" requirement, but you would still need some tweaks and customization to correctly place the source points and to correctly implement the intersection part.

[xmedeko]

Our use case is: we have (about 10-200) projects (vertices) with dependencies (edges). Projects are organized in (about 3-10) groups. We want to show and edit project dependencies (edges). However the projects - vertices should be in a "group" bubble (rectangle), so that a user can find it quickly. (Vertices may be placed anywhere inside a group bubble, it's not necessary to put them on the border.)

Maybe this feature could be called "opened cluster"?