Diff for "SimplifiedMetaNodeDataStructureRFC"

TableOfContents([2])

About this document

This is an official Request for Comment (RFC) for Add your text here

For details on RFCs in general, check out the [http://www.answers.com/main/ntquery?method=4&dsid=2222&dekey=Request+for+Comments&gwp=8&curtab=2222_1&linktext=Request%20for%20Comments 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 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:

  • Collapse MetaNode - Manually select or otherwise choose a subset of nodes in a graph that will form a metanode and collapse them into a metanode.

  • Expand MetaNode - Given a metanode in a graph, expand the metanode into its constituent nodes and edges.

Definitions

• This is the primary graph we'll be refering to in our discussion: http://chianti.ucsd.edu/mes/basic_network.png

• We'll call this graph G.

• 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

1. Create a new CyNetwork (called G.1) consisting of proper nodes a,b,c and neighbor nodes x,y:

http://chianti.ucsd.edu/mes/basic_sub_network.png

1. Create a new node m in graph G.

2. Create new edges based on old neighbor edges. Add edge x-m and m-y to G, because of x-a and c-y.

3. Delete nodes a,b,c and all adjacent edges from G resulting in:

http://chianti.ucsd.edu/mes/basic_metanode_network.png

1. Set ChildGraph attribute of node m to point to G.1

2. Set the ParentNode attribute of G.1 (assuming we support network attributes) to point to m.

3. 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

1. Find ChildGraph of metanode m (called G.1).

2. Add all nodes and edges contained in G.1 to G.

3. Delete metanode m from G and all adjacent edges.

Visualization

Backward Compatibility

Implementation Plan

• ["/Implementation Plan"]