Constrained layout algorithms in Cytoscape

[scootermorris]

Background

Most layout algorithms in Cytoscape rely on inherent network topology and only a crude set of spatial constraints (e.g., grid, circle). There are many cases when working with networks in Cytoscape where you want to be able to constrain layouts to user- or attribute-defined spaces.

Goal

This idea involves implementing layouts in Cytoscape that are constrained by:

• specific shapes
• basic shapes
• cellular templates (e.g., with subcellular organelles)
• attribute-driven Venn diagrams (e.g., to visualize attribute groupings and overlaps)
• specific “anchor” nodes
• user-defined (e.g., manually selected)
• attribute-defined (e.g., hubs or column values)
• etc...

These new options would be added to the existing Layout menu and leverage Node Table data in Cytoscape as well as shape geometries. Feel free to consider other layout enhancement as well in your proposal. For example, it would be very helpful to have layout "add-on" that slightly adjusts node positions to reduce overlaps or even node label overlap.

Difficulty Level: 1

No prior experience with Cytoscape development is required.

Technology and Skills

• Cytoscape
• Java
• Strong math background

  Potential Mentors

• Scooter Morris
• Alex Pico

  Contact

scooter@cgl.ucsf.edu

[Ayush1594]

SIr, I am an undergraduate student and I am interested in this project. I would like to know how to approach towards this project.

[scootermorris]

On 03/19/2016 11:55 PM, Ayush1594 wrote:

SIr, I am an undergraduate student and I am interested in this project. I would like to know how to approach towards this project.

— You are receiving this because you were assigned. Reply to this email directly or view it on GitHub https://github.com/nrnb/GoogleSummerOfCode/issues/41#issuecomment-198859208

Hi Ayush, The deadline is coming very, very fast, and if you haven't already started, it would be extremely difficult for you to pull together a reasonable proposal in just 5 days. If you still want to, and you have the time, I would start by downloading Cytoscape, look at the various layout algorithms that are already available, then you should download and build the Cytoscape source, and in particular explore how Layouts are integrated. Then, you should look at one of several papers on constrained layout algorithms and propose an implementation, timeline, and approach for how you would implement things. Note that one of the challenges of constrained layouts is that you'll need some form of UI to get the constraints from the user.

-- scooter

[AdrianBZG]

Hi @scootermorris ,

I'm a senior Computer Science university student from Spain, and I feel interested on this project for GSoC'17.

I have some algorithmic/mathematical background, looking at the project goal I have search for some constrained graph layout papers, and I have reached 'Constrained Graph Layout (Weiqing He, Kim Marriott); Contraints: An international Journal (1998)' [1], I want to know if the expected idea is to develop an algorithm like the one proposed on that paper. I'm expeting some guidelines to develop a good proposal, if possible.

[1] http://citeseerx.ist.psu.edu/viewdoc/download;jsessionid=27FC08034EF6F1234288EA387185741D?doi=10.1.1.91.246&rep=rep1&type=pdf

Thank you!

[AlexanderPico]

Hi Adrian,

Yes, this paper is exactly on point. Figures 2 and 12c reflect the types of results we're looking for in the case of "anchor" nodes that are user- or attribute-selected. In reading the paper quickly, it appears like "Model C" might be that way to go. A constrained solution for trees would also be relevant, but is a minor use case (so perhaps a "stretch goal" in your proposal). Not sure if this paper also addressed the use case of defining shapes or areas within which to constrain layouts, but that would also be very useful. Here is an example of shape constrained layout as a plugin to the old 2.x version of Cytoscape (not compatible with Cytoscape 3+): http://apps.cytoscape.org/apps/mosaic

[scootermorris]

Hi Adrian, Sorry -- I somehow missed your note! Yes, that paper is definitely on the right track, but I would suggest looking at some of the more recent work from the MArVL group (http://marvl.infotech.monash.edu) -- particularly their WebCoLa and libcola implementations of constraint-based layouts. Some additional papers to look at:

• Tim Dwyer, Kim Marriott, and Michael Wybrow. Topology preserving constrained graph layout. In Proc. 16th Intl. Symp. Graph Drawing (GD'08), volume 5417 of Lecture Notes in Computer Science, pages 230-241. Springer, 2009.
• Tim Dwyer, Kim Marriott, and Michael Wybrow. Dunnart: A constraint-based network diagram authoring tool. In Proc. 16th Intl. Symp. Graph Drawing (GD'08), volume 5417 of Lecture Notes in Computer Science, pages 420-431. Springer, 2009.
• Tim Dwyer, Kim Marriott, Falk Schreiber, Peter J. Stuckey, Michael Woodward, and Michael Wybrow. Exploration of networks using overview+detail with constraint-based cooperative layout. IEEE Transactions on Visualization and Computer Graphics, 14(6):1293-1300, 2008.
• Tim Dwyer and Kim Marriott. Constrained stress majorization using diagonally scaled gradient projection. In Proc. 15th Intl. Symp. Graph Drawing (GD '07), volume 4875 of Lecture Notes in Computer Science. Springer, 2008.

-- scooter

[khanspers]

Done