search

tgdwyer / WebCola

Javascript constraint-based graph layout
http://marvl.infotech.monash.edu/webcola/
MIT License
2.02k stars 258 forks source link

how to prioritse avoiding overlaps over link length #274

Closed colin-combe closed 5 years ago

colin-combe commented 5 years ago

Hi, I am trying to create a layout that behaves more like the Sugiyama layout than the flowLayout that is already present in Cola (even though I've found some power point slides of yours that show the Sugiyama layout's disadvantages).

To this end, I'd like Cola to heavily prioritse avoiding overlaps over link length. Is there a way to do this? (i.e. to say 'the links should be as short as possible but as long as is needed to avoid overlaps'),

cheers, Colin

gordonwoodhull commented 5 years ago

(Not the library author.)

I don't think that Cola even counts edge crossings, so it would be hard to optimize for them. It happens to do well on edge crossings, sometimes better than Sugiyama, completely by accident.

I'm sure you are aware that dagre is an implementation of the Sugiyama algorithm. There may be others (besides graphviz of course).

colin-combe commented 5 years ago

sorry, I should have been clearer - I meant avoiding overlaps of nodes (the constraints added when you call .avoidOverlaps(true)) rather than avoiding overlapping/crossing edges

yes, I've been looking at dagre also

I'm wondering if something similar can be done by just creating alignment contraints on the nodes based on their maximum depth in the DAG

I was doing it this way partly to learn about how to work with constraints in cola.js

gordonwoodhull commented 5 years ago

Aha, gotcha. In my experience, when everything is working properly, avoidOverlaps works and no nodes will overlap. However, there are bugs with updating layouts, and also the danger of conflicts.

There are issues with doing incremental layout where you run layout multiple times with updates to the nodes/edges - see #166 & #118 for some information on how to avoid these problems.

Constraints are absolute and unless they have conflicts, they will always be obeyed. There is no such thing as prioritizing constraints, although it does matter which order they get applied. E.g. flow constraints are run on their own first, and then later with overlap constraints, because flow should have more effect. But if everything is working, then all constraints will be satisfied.

Conflicts are the big problem - if the constraints have any cycles, then cola silently fails to apply some of the constraints. It's difficult to diagnose what is going wrong except to remove constraints until it works again.

I suspect this issue is a duplicate of #257. Perhaps overlap constraints could somehow cause a cycle with flow constraints? I hope not.

Again, I'm just a layman, so I apologize if I am saying anything inaccurate.

colin-combe commented 5 years ago

thanks for this - at first glance, I think it is #166

colin-combe commented 5 years ago

yes, deleting state as suggested here: https://github.com/tgdwyer/WebCola/issues/166#issuecomment-204032041 seems to have solved my problems

gordonwoodhull commented 5 years ago

Great. Does setting no groups d3cola.groups([]) also fix it?

Please go ahead and close this issue if it's a dupe.

colin-combe commented 5 years ago

Does setting no groups d3cola.groups([]) also fix it?

It does

dilshadurrahman58 commented 4 years ago

I am trying to get a tree-like structure for my Graph. Initially, I was thinking of using the alignment constraint to get the graph but later I found out that I can not really have a multilayer graph using alignment constraint. What should I do? The graph looks like this: 100367195_724967304991058_6956710940540665856_n (1)

colin-combe commented 4 years ago

@dilshadurrahman58 - did you try cola's built in flowLayout?

dilshadurrahman58 commented 4 years ago

@colin-combe thank you. I have tried the built-in layout but I need to get the nodes at the same level like I mentioned in the picture. I am not getting the exact same thing. I thought it would be possible to get the desired graph using some constraints. But I am not sure which constraint should I use. I mean how can I manipulate the position of the nodes so that they can be separated by level?

dilshadurrahman58 commented 4 years ago

@colin-combe I think there is something to do with the AvoidOverlap constraint. When I am avoiding the overlap among the nodes of the graph, I am not getting the layout that I need using the build-in flowLayout. But when I am not using the AvoidOverlap constraint i.e. AvoidOverlap(false), I am getting the layout I need but the nodes are overlapping. I am not getting a way out of this.

gordonwoodhull commented 4 years ago

Hi @dilshadurrahman58, I have encountered that before. I believe the problem is that using both kinds of constraints can cause cycles in the constraint graph. Once there are cycles, some of the constraints will simply be dropped.

It's very confusing and unfortunately there are no tools built-in to debug these situations.

Sorry I don't have a solution for you - just a probable diagnosis. I had some comments above which may also help with this situation.