Integration of Streetlayout as an optional layout algorithm

[lurichte]

Feature request

Description

Referring to issue #788

The user should have the possibility to switch the layout between the standard Squarified TreeMap and a street layout, where file nodes are displayed as buildings and directories are displayed as streets. A street layout has the advantage of a more apparent directory structure and stable positioning of nodes after metric changes.

A layout algorithm only influences the position and shape of a node's base area. Therefore the following 2D representations show the concepts of both proposed layouts algorithms.

Squarified TreeMap representations use less space, but nodes overlap each other, resulting in a less obvious directory structure representation. With this approach nodes are layed out to be "square-like" e.g. have aspect ratios near 1. This comes at the cost of the nodes' initial order, which has to be altered for the algorithm to produce good results. By sorting nodes by their size, a node's position inside the TreeMap is rather unstable for new images after metric changes.

Street Layouts tend to produce results that are larger in size than TreeMap layouts. A leaf nodes base area can have any form, but the most obvious is a square. This is for city metaphor reasons and node comparability. By streets branching from each other, all linked to a main "root street", the projects directory structure can be followed through when looking for a specific node. This results in stable results for the nodes' positions.

To compare 2D layouts side by side, this tool can be used.

Acceptance criteria

• layout can be switched to street layout

Open questions

• Since treemaps use the given space more efficiently than the street layout, should there be an option to substitute streets for treemaps at a certain depth into the project tree to reduce the overall size of the layout?

This would result in a layout like this in CodeCharta-Visualization 03/2020 with a custom Squarified TreeMap implementation and TreeMaps for direcotries with a depth > 3:

• Can the TreeMapGenerator be modified to create treemaps at a specified position? The Street Layout implementation can already create TreeMaps inside the Street structure. If we use the existing implementation, we can use the functionality already available to us. On the other hand, different TreeMap types and adjustments in the algorithm are possible with a custom implementation.
• The layouts have a huge difference in size. Does the size of the street layout have to be scaled up or does the treemap layout have to be scaled down? With the mapSize attribute inside the treeMap settings one can specify the size of the TreeMap. This is not easily possible for a Street Layout since the size of the resulting layout is dependent on the project's size and structure. The Street Layout currently uses raw metric values and applies no scaling to a node's size. Is scaling for the
  TreeMap required, if zooming in and out is a subjectively more intuitive approach to look at smaller structures?

[Richargh]

I love this PR. Been looking forward to this for a looong time. Ever since testville implemented a three-layer deep street layout but it was not able to render deeper structures.

A couple of suggestions:

1. The old treeview algorithm compacts folders that are empty and does not show as fodlers. You can see this in the analysis map where the "export/CSVExporter" is compacted and then "src/main/kotlin/de/..." is also compacted. Does the streetlayout respect this compacting?
2. Can we color the streets plus the floor of the treemap? In CC this is done through he right click menu.
3. can we make the root street more distinct? Our sister project testville gave it "lanes" but that is only one idea.
4. Can we have more margin between the buildings? The old algorithm uses the value set in the size metric.
5. I'd like to try another approach different to TMStreet. I like that at a certain point treemaps are rendered but I would like to change the condition. How about we change the slider: display a treemap when the folder has less than x files? That should make it a viable option even for very unbalanced file structures. For an example see below.

Suppose we have the following structure:

root

• de/maibornwolff/codecharta // folder is compacted
  -- map
  --- mapservice.ts
  --- mapservice.test.ts
  -- blacklist
  --- blacklistservice.ts
  --- blacklistservice.test.ts
  -- layout
  --- treemap
  ---- treemap.ts
  --- streetmap
  ---- streetmap.ts
  -- package.json
  -- etc.

For x=2 We could show a treemap for map and blacklist. But for de/maibornwolff/codecharta we would show a streetmap. For this to be viable we'd also have to implement something that checks if a folder and subfolders has less than x files, and then show a treemap. We'd show a treemap for layout for example even though the files are in sub-folders because it only has 2 files in total.

[alschmut]

A short side note to the points 1. The compact folders should be implemented, as they are generated before we decide which layout algorithm to use. I am also voting for your other suggestions 👍

Though, I would suggest to merge small portions of acceptable (maybe partially disabled) features (MVPs) in order to have smaller separate PRs. This will reduce reviewing time and the chance for merge conflicts. Also every CC developer will be more involved in smaller feature decisions through each small readable PR (:

[Richargh]

You put the new layout in the settings right? Mark it as experimental and merge the PR. I also like smaller PRs because I get to try the feature sooner :)

Some things like my layout suggestions are a lot more experimental in nature. What are the optimal settings for the street layout? How can we make it better than the classical treemap algorithm? This might create a very small PR but require lots of tinkering.

[Richargh]

Another question: does the streetmap use a good old hand-written treemap algo or the library one? Because in another PR I'd love for us to have our own treemap algorithm where we can place large margins between folders of more than 100 files and small margins inside folders of only 10 files.

[lurichte]

Hi @Richargh

1. Yes, nodes that don't have children nodes or whose children.length is 0 are skipped in the layout creation. If you discover the layout displaying empty folders, this is not intended and probably a bug.

2. Yes, nodes can be colored like shown in the following picture. This functionality has not been atlered.

3. Should the root street be even wider than the rest? Currently the calculation of a street's width is done by the following rational function width = 10 / (depth + 1). In this way the root streets width is always at 10, while streets deeper into the project have widths of 5, 3.3, 2.5, 2,... These values might have to be adjusted again, if we decide to scale the size of the street layout like described in the ticket.
   For lanes, textures on street nodes should also be possible to apply through three.js, but I would have to investigate deeper on how that would work.

4. Do you mean margins between buildings located at streets or in treeMap buildings inside the TMStreet-Layout? For treeMaps inside the TMStreet-Layout, I used the same margins we used in the classic treeMap algorithm. They however are still scaled differently, because of the layouts' overall size difference like described in the ticket.
   A margin between buildings located at streets can be added aswell.

5. I like your suggestion to create treeMaps for folder nodes that have only x files under them. I implemented your idea and those are the resulting layouts for the project CC-Visualization. Please let me know your thoughts on them:

TMStreet Layout with TreeMaps for folder nodes with <=50 files

TMStreet Layout with TreeMaps for folder nodes with <=100 files

TMStreet Layout with TreeMaps for folder nodes with <=150

[Richargh]

3. Should the root street be even wider than the rest?

The function looks good to me. But maybe the root should be double the size from the next, or maybe a different color to make it easier to find. Or elevated a bit. I think we should just leave it for now like this and experiment later in a different PR like Alex suggested. Don't investigate textures now :)

4. Do you mean margins between buildings located at streets or in treeMap buildings inside the TMStreet-Layout?

I think both.
It might look better if the buildings were standing a bit apart from their streets. Maybe a small, non-adjustable margin of 1 at all depths?
And for TreeMap buildings I'd like a different way. I just viewed them from the top. Can we have different folder margins if the folder has <50 buildings, <100 buildings, <500 buildings, or <1000 buidlings? That would put bigger margins around folders that are more "important" and make them more distinct and noticable in the map. Probably :)

5. I like your suggestion to create treeMaps for folder nodes that have only x files under them.

Looks good in the images. I tried the branch "feature/street-map-layout" but couldn't see it in the commit log.

6. This one is new. Why is the root not always in the center? In your example images for example. If root does not have files and only one folder attached to it, it shouldn't look like in your screenshot right? It should be compacted. Or look at the screenshot below. Why is that? Can we "fix" this somehow?

7. Another question: does the streetmap use a good old hand-written treemap algo or the library one? Because in another PR I'd love for us to have our own treemap algorithm where we can place large margins between folders of more than 100 files and small margins inside folders of only 10 files.

[lurichte]

A short side note to the points 1. The compact folders should be implemented, as they are generated before we decide which layout algorithm to use. I am also voting for your other suggestions 👍

Yes, I think the folders should be compacted before the algorithms happen. But @Richargh is right, I added a function I used in my initial implementation of the layout to skip folders with a child node of the same size and concat their names divide by '/'. I forgot to put it into CodeCharta it seems.

You put the new layout in the settings right? Mark it as experimental and merge the PR. I also like smaller PRs because I get to try the feature sooner :)

Should there be an option for treeMaps to be generated by depth or by the number of files? The option for depth already exists while for number of files I would have to add it in.

Another question: does the streetmap use a good old hand-written treemap algo or the library one? Because in another PR I'd love for us to have our own treemap algorithm where we can place large margins between folders of more than 100 files and small margins inside folders of only 10 files.

Currently the TMStreet layout uses a "hand-written" one. Actually there are three different TreeMap implementations already added in but there is no option in the ui to choose one yet. The TreeMaps are Squarified, SliceAndDice and Strip.
Like described in the ticket, I am not using the existing TreeMapGenerator because it would need to be able to place TreeMaps at a specific location.

The function looks good to me. But maybe the root should be double the size from the next, or maybe a different color to make it easier to find. Or elevated a bit. I think we should just leave it for now like this and experiment later in a different PR like Alex suggested. Don't investigate textures now :)

Okay, I'll leave it for now.

I think both. It might look better if the buildings were standing a bit apart from their streets. Maybe a small, non-adjustable margin of 1 at all depths?

I added a fixed margin for buildings.

And for TreeMap buildings I'd like a different way. I just viewed them from the top. Can we have different folder margins if the folder has <50 buildings, <100 buildings, <500 buildings, or <1000 buidlings? That would put bigger margins around folders that are more "important" and make them more distinct and noticable in the map. Probably :)

Sounds like a very good idea for another pull request :)

Looks good in the images. I tried the branch "feature/street-map-layout" but couldn't see it in the commit log.

Sorry, my bad. I did not push the changes. Now you should see the changes.

Why is the root not always in the center?

The root street is created at the "center" and all descendants from that node are added to both sides of the street. If there are not enough descendants from a street node, there might be only nodes on one side of the street making it seem that the root street is not always centered.

In your example images for example. If root does not have files and only one folder attached to it, it shouldn't look like in your screenshot right? It should be compacted. Or look at the screenshot below. Why is that? Can we "fix" this somehow?

Yes you are right! I "fixed" it by adding the function I was missing for compacting the folders.

Here's a picture of the current layout with margins for buildings and treemap root nodes, compacted diretories and treemaps for folders with <= 100 files.

[Richargh]

Should there be an option for treeMaps to be generated by depth or by the number of files?

I think number of files makes the most sense. I'd skip the depth option and make number of files the default criteria. How did you implement it: does it make a treemap for a single folder or even for folders inside folders like in my example above? --> "checks if a folder and subfolders has less than x files, and then shows a treemap. We'd show a treemap for layout for example even though the files are in sub-folders because it only has 2 files in total."

Currently the TMStreet layout uses a "hand-written" one.

Perfect, then we can modify the hand-written layout as well.

Actually there are three different TreeMap implementations already added in but there is no option in the ui to choose one yet.

If the code is already in the code-base then please also make it selectable.

The root street is created at the "center" and all descendants from that node are added to both sides of the street. If there are not enough descendants from a street node, there might be only nodes on one side of the street making it seem that the root street is not always centered.

I don't get it. You mean if the subfolder only has 5 descendants it will only show up as a mini-street?

I think we should experiment a bit more with the street-placement in future PRs to better render "unbalanced" file trees.

Yes you are right! I "fixed" it by adding the function I was missing for compacting the folders.

Cool thank you.

[lurichte]

I think number of files makes the most sense. I'd skip the depth option and make number of files the default criteria.

I removed the TreeMap Start Depth option and replaced it with a slider for a maximum number of files for a TreeMap. Folder nodes are created as streets unless they have less file descendants than that number. I set the default value to 100 and let the user input values between 1 and 1000.

How did you implement it: does it make a treemap for a single folder or even for folders inside folders like in my example above?

In my implementation a folder node is tested whether its subtree contains more file node descendants than the specified number. It counts all direct and indirect descendants.
Let's say we want to have max. 5 file nodes for treemaps. If a folder's subtree contains more, a street is created. For de/maibornwolff/codecharta we would create a street, because there are more than 5 files inside the folder's subtree. For map, blacklist and layout, which have two files each, a treemap is created.

If the code is already in the code-base then please also make it selectable.

I guess that would also be part of another pull request then?

I don't get it. You mean if the subfolder only has 5 descendants it will only show up as a mini-street?

No, street creation is not depending on the number of its children. To place a street inside the street layout, you must first know the size of its child nodes. This is why streets, buildings and treemaps need a boundingbox. When you know the dimensions of its child nodes, they have to be split to two rows (each side of the street). This happens by first calculating their boundingboxes' summed side lengths and then putting nodes into the first row until half of this length is exceeded. All remaining nodes are placed in the second row.

The problem with that can be that a folder's children may only contain one large folder and several smaller files. In this case the small files do not exceed half the summed side lengths of all children and is placed in the first row aswell. The other row remains empty and unbalanced streets happen.

Sorry if that's still not clear. Maybe these images help:

This is the way child nodes are placed at streets:

These are all child nodes side by side with their metric values. The line shows the summed side lengths and the marker shows its center:

[Richargh]

I set the default value to 100 and let the user input values between 1 and 1000.

👍

In my implementation a folder node is tested whether its subtree contains more file node descendants than the specified number.

👍

I guess that would also be part of another pull request then?

That depends. If the code is in the code base it should be selectable in this PR. Otherwise it's just dead code. If it's not selectable the code should not be part of this PR but added with a new PR :)

The problem with that can be that a folder's children may only contain one large folder and several smaller files. In this case the small files do not exceed half the summed side lengths of all children and is placed in the first row aswell. The other row remains empty and unbalanced streets happen.

I might just understand that. ;) I still we think we should play with this in future PRs.

[lurichte]

That depends. If the code is in the code base it should be selectable in this PR. Otherwise it's just dead code. If it's not selectable the code should not be part of this PR but added with a new PR :)

Okay, to keep the PR smaller, I removed the alternative treemap algorithms for now. We can add them in a future PR.

I might just understand that. ;) I still we think we should play with this in future PRs.

We absolutely should. I think there is room for a lot of optimizations!