RFC Name : ... |
Editor(s): ... |
<<TableOfContents: execution failed [Argument "maxdepth" must be an integer value, not "[2]"] (see also the log)>>
About this document
This is an official Request for Comment (RFC) for a proposal to simplify the data structures used to represent meta nodes. It was originally written by Mike Smoot and Trey Ideker For details on RFCs in general, check out the Wikipedia Entry: Request for Comments (RFCs)
Status
"Not yet completely written"
How to Comment
To view/add comments, click on any of 'Comment' links below. By adding your ideas to the Wiki directly, we can more easily organize everyone's ideas, and keep clear records. Be sure to include today's date and your name for each comment. Here is an example to get things started: /Comment.
Try to keep your comments as concrete and constructive as possible. For example, if you find a part of the RFC makes no sense, please say so, but don't stop there. Take the extra step and propose alternatives.
Proposal
The core graph classes of cytoscape (giny.model) currently support the use of metanodes (described here MetaNodes_RFC) with approximately 50 separate methods in the GINY interface and its associated implementation. This proposal describes an approach to supporting metanodes that relies only on a basic graph data structure and the use of CyAttributes. The motivation for this approach is to simplify and clarify the underlying code and data model by deprecating the various meta methods.
Biological Questions / Use Cases
See MetaNodes_RFC for detailed descriptions of use cases.
Description
Our proposal centers around a few basic concepts:
A metanode is a regular CyNode with a CyAttribute (we'll call it ChildGraph) that points to a separate subgraph that contains the nodes and edges that are part of the metanode.
The child subgraph is a normal CyNetwork, just like any other graph.
- The child subgraph contains all of the nodes and edges that are part of the metanode (we'll call them proper nodes) as well as any neighbor nodes and edges. The proper nodes and neighbor nodes can be distinguished with attribute information.
- The basic operations that are supported are:
Definitions
This is the primary graph (which we'll call G) that we'll be refering to in our discussion:
Nodes a,b,c will be the nodes collapsed into a metanode.
We'll call the metanode m
Nodes x,y are adjacent nodes to the metanode.
Node z is a final node, not adjacent to the metanode.
Collapse MetaNode
Create a new CyNetwork (called G.1) consisting of proper nodes a,b,c and neighbor nodes x,y:
Create a new node m in graph G.
Create new edges based on old neighbor edges. Add edge x-m and m-y to G, because of x-a and c-y.
Delete nodes a,b,c and all adjacent edges from G resulting in:
Set ChildGraph attribute of node m to point to G.1
Set the ParentNode attribute of G.1 (assuming we support network attributes) to point to m.
The result is two graphs, G and G.1. G consists of nodes x,m,y,z and G.1 consists of x,a,b,c,y.
Expand MetaNode
Find ChildGraph of metanode m (called G.1).
Add all nodes and edges contained in G.1 to G.
Delete metanode m from G and all adjacent edges.
Visualization
- Visualizing either a collapsed or expanded metanode graphs is straightforward as each would appear as normal graphs, as seen above.
- Visualizing the "in between" state where the nodes contained in a metanode are visualized within a highlighted region indicating the metanode is slightly more difficult:
One option for this situation would be to display the nodes and edges of the metanode as a JPanel within the metanode (i.e. the region within the dashed red line would be a JPanel or put a different way G.1 would be a JPanel within m). This strategy would require careful layout of the subgraph so that the edges would appear to connect correctly. A means of accomplishing this would be to fix the positions of the neighbor nodes (x,y) in G.1 relative to their positions in G and then lay a,b,c out accordingly. When displaying G.1 within m instead of displaying 'x and y in G.1, those nodes would be cropped.
Backward Compatibility
We would need to continue to support many of the metanode methods in the core for some period of time, although they could all be deprecated and eventually removed.
Implementation Plan