## page was renamed from Cytoscape_3.0/HyperEdges
## This template may be useful for creating new Discussion pages
## This is a wiki comment - leave these in so that people can see them when editing the page

|| '''Discussion Title''' : Hyperedges || '''Editor(s)''': Michael Creech ||

<<TableOfContents([2])>>

== About this document ==

This document considers some of the issues with adding hyperedges to
Cytoscape 3. These issues are presented by looking at the
feedback and lessons learned in implementing the !HyperEdgeEditor
plugin.

=== Introduction and Terminology ===

A hyperedge is an Edge that connects two or more
Nodes. Hyperedges may be useful for representing more complex
structures like reactions and protein complexes.

Since this document makes heavy reference to the [[HyperEdgeAPI]], a good
familiarity with the existing !HyperEdgeEditor plugin is
essential. See the [[#anchorname|References]] section for information on how to
familiarize yourself with this plugin.

The !HyperEdgeEditor plugin, adds hyperedge functionality to Cytoscape 2.6 (referred to here as the ''plugin model''). The future Cytoscape 3 hyperedge model will be referred to as the ''C3
model''.  There is a skeleton framework for the C3 model in fastGraphCy3 trunk (http://chianti.ucsd.edu/svn/csplugins/trunk/ucsd/mes/fastGraphCy3/src/org/cytoscape/model/).

== How to Discuss ==

To view/add discussion 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. Try to keep the discussion as concrete and constructive as possible.  Be sure to include today's date and your name for each comment.  

== References ==
  

The !HyperEdgeEditor plugin adds an underlying hyperedge model (the
!HyperEdge API) to Cytoscape 2.6, along with a very simple editor for
creating and editing hyperedges. More information can be obtained on the !HyperEdgeEditor plugin from the following sources:

 1. See [[HyperEdgeAPI]] for more info about the underlying hyperedge model.
 1. !JavaDocs for the hyperedge model is available at [[http://www.cytoscape.org/agilent/build/api-docs/index.html|Java HyperEdge API Java Documents]].
 1. Source code for the hyperedge model is available via SVN from {{{grenache.ucsd.edu/cellar/common/svn/csplugins/trunk/agilent/creech/HyperEdge}}}.
  See {{{cytoscape.hyperedge.HyperEdge}}} for an overall description of terms and assumptions.
 1. Source code for the hyperedge editor is available via SVN from {{{grenache.ucsd.edu/cellar/common/svn/csplugins/trunk/agilent/creech/HyperEdgeEditor}}}
 1. Once the !HyperEdgeEditor is loaded in Cytoscape, two sample hyperedge networks are available via File->Import->!HyperEdge Sample Networks. This will build two hyperedge networks--Glycolysis Reaction network and a Krebs Cycle network. You can look at the source code that generates these two networks in {{{cytoscape.hyperedge.editor.SampleNetworks.java}}}


== Discussion ==

=== Looking at the Plugin Model Assumptions ===

Following are a set of assumptions that were developed with the plugin model (we kept going around in circles on various issues until we wrote up a list of our assumptions).  Each assumption is considered with respect to its implications on the C3 model:

 1. ''Hyperedges are mutable.''

 <<BR>>The plugin model has mutable hyperedges with the ability to add and remove edges and nodes. Two situations where mutability is desired are:

  a. when you don't have all the edges, nodes and other hyperedges defined to build the complete hyperedge (especially in the chicken-or-the-egg case of connecting two hyperedges).

  a. when editing hyperedges--incrementally adding, removing, and connecting hyperedges to other structures.

 If the C3 model defines !CyHyperEdges to be immutable, like !CyEdges, then there must be a way to deal with a) and b) or there must be good evidence that a) and b) can  be restricted.


 1. ''A Hyperedge may have more than one !CyNode with the same !CyEdge interaction type.''

 First, a digression. This brings up the more fundamental question of how hyperedges are semantically structured--how are parts of the hyperedge defined, referenced, and traversed? Structure is obviously needed. For example, is you are building a Krebs Cycle, you might want to define hyperedges containing products, mediators, and substrates. If you are building something else, the structuring may be completely different. Without structure, how would you ask, if the 'product' of a given hyperedge was the !CyNode 'CO2'?

 The plugin model uses ''interaction types'' to define structure. An interaction type is just a String that represents the role a Node plays within a hyperedge (in the implementation, this translates to a !CyEdge attribute named "interaction" being added to the !CyEdge). These interaction types are used my many plugin model operations to allow construction and searches.

 For the C3 model, if no scheme is provided for structuring hyperedges, the API is certainly simplified. However, each set of users will be forced to come up with their own conventions for determining hyperedge structure and will also have to supply middleware code to construct, traverse, and search their hyperedges.

 Back to this assumption, given this definition of interaction types, this assumption states that a hyperedge may have two different !CyNodes with the same interaction type. This is needed to allow things like reactions to have multiple catalysts, inhibitors or activators in a reaction.

 1. ''A Hyperedge may have more than one !CyEdge to the same !CyNode.''

 <<BR>>In some reactions, a component can play multiple roles in the same reaction. For example, in the Glycolysis reaction, Ca2+ acts as both an inhibiting and activating modulator for pyruvate kinase I.

 The plugin model handles this assumption by the fact that a hyperedge may contain two or more CyEdges to the same node--each with a different interaction type.

 For the C3 model, this implies that a !CyHyperEdge must be able to have duplicate source and target nodes and there must be a way to specify separate attributes for each sub-edge. So, in the above example, a hyperedge would have two (sub)edges to the !CyNode ''Ca2+'', one with one attribute type (e.g., inhibiting) and the other with a different attribute type (activating) and we would need to be able to choose one and manipulate it independent from the other. 

 1. ''A Hyperedge has exactly one !ConnectorNode.''

 <<BR>>The plugin model uses existing !CyEdges and !CyNodes to construct hyperedges. On the surface, you might think that for the C3 model you'd want to throw out these !ConnectorNodes and just have hyperedges contain lists of source and target nodes. However, there are some major advantages to keeping the !ConnectorNodes and some challenges if we remove them:

  a. Advantage: Allows peaceful and incremental integration with !CyNetworks, !CyNodes, and !CyEdges.

  When using !ConnectorNodes, there are no new fundamental structures that every mechanism within Cytoscape needs to handle before hyperedges are integrated into Cytoscape. This is because the components of every hyperedge are just common !CyNodes and !CyEdges. The level of integration of the !ConnectorNode-based hyperedges can be slowly increased, starting with low-level integration for tracking hyperedges (creation and deletion) and then adding visual style, filtering, layout, and any other additions required.

  a. Challenge: How do we connect hyperedges together?

  !ConnectorNodes are like any other node and can be used to connect one hyperedge to another. One situation where this is needed is where one or more hyperedges represent a reaction that is the catalyst of another reaction (see Glycolysis Reaction example in the !HyperEdgeEditor plugin).


 1. ''A hyperedge !ConnectorNode may be used as a regular !CyNode within another hyperedge.''

 <<BR>>In the plugin model, this is fundamental to linking one hyperedge to another. This also gives an existing object from which to hang attributes that represent the entire hyperedge without having to create a new category of attributes (those hanging on hyperedge objects).

 1. ''A hyperedge is associated with one or more !CyNetworks.''

 <<BR>>If hyperedge's follow the rest of the Cytoscape 3.0, then they would not be shared across !CyNetworks. This would simplify this assumption to:
  <<BR>>''A hyperedge is associated with one !CyNetwork.''
 <<BR>>This would simplify the existing plugin model API by removing or reducing various methods dealing with hyperedges within !CyNetworks.


 1. ''The only shared !CyEdges in a hyperedge are those connecting two !ConnectorNodes (hyperedges) that must exist in the same !CyNetwork.''

 <<BR>> Since for Cytoscape 3.0 , hyperedges would not be shared across networks, this could be simplified to:
  <<BR>>''The only shared !CyEdges in a hyperedge are those connecting two !ConnectorNodes (hyperedges).''
 <<BR>>In the plugin model, there is an important implicit assumption here, in that there is only one ''shared'' !CyEdge that connects two hyperedges--each hyperedge doesn't hold its own separate instance of a !CyEdge that connects the other hyperedges. This was found to be more managable then having two separate !CyEdges for the connection.


 1. ''If hyperedge A connects to hyperedge B via a shared edge, both A and B can only exist in one (and the same) !CyNetwork.''

 <<BR>>For the C3 model, this is implied since hyperedges are not shared (see #6).

 1. ''A regular Cytoscape !CyEdge may directly connect to a hyperedge !ConnectorNode, but it will not be considered part of the hyperedge.''

 <<BR>>In the plugin model, we allow ConnectorNodes to be like any other node and have !CyEdges connecting them. Is there really a good case for users wanting to connect !ConnectorNodes with regular !CyEdges, or should this sort of operation be banned? If banned and if !ConnectorNodes are used in the C3 model, then checks will need to be made concerning hyperedges in the regular CyEdge creation code. 

 1. ''Hyperedges are shared, in that any change to a hyperedge existing in more than one !CyNetwork is reflected in all !CyNetworks to which the hyperedge belongs.''

 <<BR>>For the C3 model, this is implied since hyperedges are not shared (see #6).

 1. ''Hyperedges can co-exist with !CyEdges and !CyNodes in !CyNetworks.''

 <<BR>>For the plugin model, this is implicitly true. As for the C3 model, how important is it that hyperedges co-exist with regular edges in networks?

=== Integrating Hyperedges into Cytoscape ===

How should hyperedges appear in the API within Cytoscape? A few possibilities are: 

 1. Integrate the plugin model's API into the Cytoscape 3.0 core.

 <<BR>>This has some advantages as discusses in Assumption 4. Required changes to the plugin model would include:
  a. Updating the API to remove sharing of hyperedges across !CyNetworks.
  a. Removing complex event handling that allows tracking of deleted hyperedges within the plugin.
  a. Reviewing and possibly removing other secondary state and methods deemed uneeded for the C3 model. 
  a. Various package and naming changes (e.g., !HyperEdge-->!CyHyperEdge). 
 
 1. Segregate hyperedges from regular networks and have them available only in special !CyHyperEdgeNetworks.

 <<BR>>These networks would allow !CyNodes and !CyHyperEdges. This would help localize the complexity of hyperedges by confining them to special networks. This does complicate things in that there would be two types of !CyNetworks and the various operations for copying things from one network to another are more complex. There is also a major user question as to whether hyperedge users would require mixing of the hyperedges with reqular nodes and edges.

 1. Create a new !CyHyperEdge that does not use plugin model-type !ConnectorNodes or regular !CyEdges

 <<BR>>If an attempt is made in this direction, it should address the various issues discussed in this document.

  a. Variation: Define a !CyHyperEdge that extends !CyEdge.

  <<BR>>We feel this would be a mistake from a design standpoint since hyperedges are generalizations of !CyEdges, not specializations. Also, we think it would be confusing in that {{{getSource()}}}, {{{getTarget()}}} don't really make sense (would have to return an arbitrary value).