TableOfContents()

This is the homepage of the Cytoscape 3.0 Model layer design discussion.

Model Layer definition

The model layer contains the object/data model for core data structures useful for Cytoscape or Cytoscape-like software.

Component Modules

• Graph
• Attributes
• Identifier policy (for objects that need to be referenced, like nodes/edges)
• Hypergraph? (is this different from Graph? see open issues)
• Groups? (is this different from Graph? see open issues)
• Project?

Requirements

Core structure of the Model layer

• APIs should be easy to use. Use case: to reduce bugs and duplicated code (from cyto2 experience)
• Minimize dependencies between APIs. Use case: to reduce maintenance work (from cyto2 experience)

• API dependencies must be acyclic!!!!

  • (SK - I do not agree that this is true for API's within a module. It is absolutely true between modules however)

• APIs should be non-redundant (i.e. don't create multiple APIs for the same model unless there is a clear use case). Use case: easier for core developers and plugin writers to work with (from cyto2 experience)

Open issues

• Should the APIs be loosely coupled (e.g. just via shared IDs) or strongly coupled e.g. by imports and shared data structure use?
• Should there be a plugin writer API on top of a streamlined core API or just one API for everyone.
  • Gary: I strongly suggest having just one API for everyone. There is no real differentiation between core and plugin developers, as they both need easy to use APIs to avoid bugs and maintenance headaches - a single, clean, powerful API will keep the core clean and the plugins clean.

Network/Graph

• Is extremely fast and memory efficient for creating and updating. Use case: large graphs up to millions of nodes
• Support for a multi-graph. Use case: represent basic networks with graph, multiple types of edges in a protein interaction network with a multi-graph.
• Support for hypergraph. Use case: biochemical reactions using hypergraph.
• Support for nested graphs. Use case: protein complexes using nested graph.
• Ability for user to determine what type of graph they are working with: e.g. graph, multi-graph, hypergraph, nested graph (contains groups). Use case: algorithm writer needs to know this so they avoid running an algorithm on an incompatible input data structure.

Open issues

• How do we implement more complex graphs e.g. hypergraphs at the same time as regular graphs?
  • Possible solutions are:
    • have different classes for each that inherit from the most general class;
    • overlay all types on one simple graph model e.g. use one graph model with special flags for nodes and edges; have a loose association of classes linked only by node and edge IDs, where the more complex model maintains its own consistency if related models are changed. Note: a hypergraph is not a type of graph - it is the other way around.
    • Don't support hypergraphs at all. I think that hypergraphs are a very complicated abstraction and possibly not the correct one for biochemical reactions.

• How should these related aspects of the model be kept consistent e.g. are events needed in the core? Yes, events are needed in the core for the network model to communicate state changes to classes that depend on the network (but not vice versa).

• Should nodes be shared between networks or not?
• Should the node label be in attributes or in the node?
• What is the largest size of network we should consider in our design (order of magnitude)? Millions of nodes/edges?

Design Ideas

• Have both a fast core graph implementation and a higher-level object oriented network API that makes it easier to manipulate networks for plugin writers. The latter is more memory and CPU intensive, so would have a lazy implementation.

Two proposals have been made but not fully integrated and neither is necessarily final:

Model API Proposal #1

• Here is a proposed network API that includes an multi-graph implementation, but not a hypergraph or nested-graph. http://chianti.ucsd.edu/svn/csplugins/trunk/ucsd/mes/api/

• See GraphPerspectiveToCyNetwork for details on other issues.

Model API Proposal #2

[http://www.cgl.ucsf.edu/home/scooter/Cy3/ JavaDocs] http://chianti.ucsd.edu/svn/csplugins/trunk/ucsf/scooter/cy3PluginAPI This proposal includes all of the interfaces that the graph module is expected to contain, including graph objects, attributes, projects and potentially groups. The basic idea is a two-level API.

• Top level (org.cytoscape.model) provides a clean model for accessing and manipulating Cytoscape networks. It includes the familiar CyNetwork, CyNode, CyEdge, and CyAttribute interfaces, in addition to support for CyHyperEdge and CyGroups. CyProject is an interface that is a first step towards documenting data provenance, and providing an interface to the information that is currently held within CytoscapeSession.

• Lower-level API (org.cytoscape.model.graph) consists of a single object: Graph. A Graph is a very low level interface, providing access to integer arrays of nodes and arrays of edges, and basic connectivity. A Graph can be used when performance is critical, but in general plugin writers will not have to deal with/think about it.

• All networks, nodes, and edges are represented by integer identifiers that are unique to this session. CyNetwork does not provide an interface to the associated Graph -- they are implicitly linked by their shared network identifiers. Similarly the correspondence between CyNodes and nodes in the Graph is solely their shared node identifiers. CyNetwork does not inherit from Graph, but the CyNetwork implementation is based on the Graph API. One of the strengths of this approach is that CyNodes and CyEdges can be created lazily by calls to CyNetwork. This allows us to read in very large graphs without the overhead of CyNode and CyEdge objects for every node and edge in the graph. Note that the inclusion of getNodesByAttribute and getEdgesByAttribute methods in CyNetwork allows us to only create CyNodes and CyEdges for subsets of the Graph.

A couple of other things to note:

• Flags: Saw a requirement to include the capability to set, clear, and test flags on nodes and edges. We may want to broaden this. Currently, these flags can be used to determine some information about the nodes and edges, including whether this node represents a group, or is a housekeeping node (such as a hyperEdge connector node), or whether this Edge is actually a HyperEdge. As I thought about this, it may provide us with a way to add special nodes and edges in the future without needing significant changes to the API. They are also important in that they allow us to generalize some of the special features of Groups and HyperEdges for other things.

• Groups: A CyGroup is implemented as an extension of a CyNode. This has some interesting advantages. For example, if we are dealing with a "metaNode", that is, a node that represents a subnetwork, we can set the HOUSEKEEPING flag on the node when it's not collapsed, and it will not be included in node traversal (which is shouldn't be). This is similar in concept to our current "hidden" node approach without the confusing semantics that mix model with view. Another point of discussion: does it make sense to be able to ask a node what groups it's a member of? Since nodes can be in multiple groups, getting the list of groups for a node turns out to be a very common operation, on the other hand, having a getGroupList method in the node interface ties CyNode to CyGroup in a way that might not be appropriate.

• HyperEdges: similarly, a CyHyperEdge is an edge that extends CyEdge by adding additional sources and targets. The connecting node that provides the connectivity could be marked as a "HOUSEKEEPING" node and excluded from node lists, etc. In the case of HyperEdges in particular, I'm proposing that the methods in CyNode and CyNetwork that depend on edge connectivity be smart enough to support hyperedges (e.g. getNeighborList would not return the node providing hyperedge connectivity, but would return the targets of that node).

• CyAttributes: there is a lot of discussion about CyAttributes, so what I have here should be considered only a placeholder. I do think that it makes sense to have both local and global CyAttributes. Local CyAttributes are pretty easy to figure out -- they are just indexed by the network, node, edge integer. Global CyAttributes are particularly difficult because there is no standard key we can use, so they will probably need to be indexed by some well-known local attribute (CANONICAL NAME?).

Attributes

The CyAttributes interface shouldn't be terribly different from what it is now. It basically has 3 different methods, similar to a Map interface:

• getAttribute()
• setAttribute()
• containsAttribute()

In one way or another, the interface will need to support the use of primitive types but also limit the allowed types of attributes to those pre-defined values. In general we want to support 4 primitive types which facilitate inter-plugin communication:

• int
• float
• String
• boolean

Then

• Lists of primitive types.
• Maps of primitive types.

Finally, we would also like to support the recursive definition of these classes to support arbitrary types composed of the 4 primitive types:

• Lists of Lists or Maps of primitive types.
• Maps of Lists or Maps of primitive types.

Other requirements include:

• Is fast for writing and reading and is memory efficient. Use case: large gene expression data sets
• Ability to optionally backend attributes to a database. Use case: large gene expression data sets

Note: several API's were proposed through email attachments and have not yet been added here. Be sure to look back through email discussions on attributes to find them.

Open issues

The central dilemma of the Model API design is how the Attributes module relates to the Network module. In 2.x era Cytoscape, there is no explicit relationship between these modules. Attributes don't (explicitly) depend on Network and Network doesn't depend on Attributes. However, there is an implicit dependency connecting the two through the use of string identifiers. This means that Attributes effectively depends on a Network model that uses strings to identify graph objects.

• What requirements are not met by current CyAttributes class (it seems to meet most current requirements)

  • Large amounts of boilerplate code.
    • Any time where case statements are needed to evaluate how to behave with a certain attribute type. A brief check tells me this happens in the vizmapper, layouts, several parsers, and all over the implementation of attributes. This is especially problematic because most case statements don't account for all attribute types, which leads to things being mishandled.

    • The implementation of CyAttributes where all of the setAttribute methods are nearly identical. And so are the getAttribute methods. This is exactly the sort of thing that generics were designed for.

  • The current global CyAttributes objects result in many very problematic dependencies that aren't apparent in interfaces. Because access to the CyAttributes objects are from a single static method, anyone can use these classes. Dependencies are OK when explicit (i.e. in the method or constructor signature), but when they're hidden through the use of static methods they make the code much less modular and much harder to test. Fixing this would be a great use case for a Dependency Injection pattern (i.e. Guice or Spring).

• How should we implement local vs. global attributes?
  • What is the use case for global attributes? If we've decided that nodes and edges are specific to networks and that they won't be re-used, what need will we have for global attributes?
• How should special attributes be implemented? E.g. hidden.

Design Ideas

There are essentially two approaches to linking the Attributes module and the Network module:

1. Attributes depends on Network.
2. Network depends on Attributes.

Approach 1: Attributes depends on Network. Leave things pretty much as they are, but use an SUID instead of a string identifier. Attributes will at once be both global (i.e. accessible in any context) and local since the SUID is specific to a node/edge/network and not reused in multiple networks (as nodes and edges are now). In this case, Attributes depends on a Network modelthat uses SUIDs, so the dependency is much like it currently is, just not with strings.

For this approach the method interfaces would look something like this:

• getAttribute(int SUID, String attrName);
• setAttribute(int SUID, String attrName, Object attrValue);
• containsAttribute(String attrName)

where the SUID is used to identify which object the attribute is bound to.

Advantages:

• Conceptually simple: an SUID accesses attributes.
• Similar to what we have now, so there won't be many conceptual hurdles for plugin developers.
• Would require relatively few changes.
• Still easy for attibute browser and other to see all attributes.

Disadvantages:

• Extra steps are involved for getting the attribute, e.g.
  • attrs.getAttribute( node.getSUID(), ...);
• Saving state might be harder since the mapping from attribute to graph object is ephemeral (SUID).
• ???

Approach 2: Network depends on Attributes. Reverse the dependency so that Networks depend on Attributes and make local Attribute objects part of the CyNetwork/CyNode/CyEdge classes. Instead of getting attributes from one location, attribute objects will become available from individual objects, such as nodes, edges, or networks.

For this approach the method interfaces would look something like this:

• getAttribute(String attrName);
• setAttribute(String attrName, Object attrValue);
• containsAttribute(String attrName)

where the object binding is implicit to the object.

Advantages:

• Conceptually simple: an object has attributes.
• Simple access to attributes.
  • node.getAttribute(...), edge.getAttribute(...)

Disadvantages:

• A big change since this is opposite of how we do things now.
• A conceptual shift for plugin developers.
• Perhaps more difficult to track what attributes currently exist since you'd have to know what objects have attributes.
• ???

Identifiers

• Gary's ID proposal from Dec.15.2007:

1. Graph objects = nodes, edges, groups, hyperedges (these are children of GraphObject)
2. Each graph object has a session unique integer ID (G-SUID) (not globally unique, just unique for a given Cytoscape session)
3. Each attribute row in a table has a SUID (A-SUID - not the same space as the G-SUID)
4. A map exists between graph object SUIDs (G-SUIDs) and attribute table row SUIDs (A-SUIDs)
This is simple and allows a lot of flexibility.  The presence of SUIDs mean you don't have to track IDs in any context, which is the simplest option.  This also allows multiple attribute tables (think relational database tables).  For instance, we can implement user attributes in one table and hidden attributes in another table.  In this case of >1 attribute tables, you need to store table context in the map.  Further, we can have multiple attribute tables in the same space e.g. load up 2 gene expression datasets in 2 different tables.  This gets rid of the need for empty attribute table cells.  I don't think we should really implement this latter option, as the GUI is more complex and we already have an efficient CyAttribute data structure (MultiHashMap), but having it is only a change in how the graph object SUID to attribute SUID map is used.
Also, the presence of a GraphObject superclass will make it easier for more general algorithm code to be written (really important!) and provides a place to track G-SUIDs.  Also, the GraphObject class can have additional children if we need to add more things in the future.  The advantage of this design is that there is no coupling in the model i.e. network doesn't know about groups leaving the model layer to be very flexible, however, composition (bringing different parts of the model together) in the application layer is facilitated.
What about network attributes?  It's just another SUID map.  Networks are separate from other objects that have SUIDs because of the above point about algorithm generality.  You don't want graph algorithms to work on networks as a GraphObject (and semantically, networks should not be network objects, otherwise we introduce a high level of complexity into the model by having hierarchy in there by default - you could be tempted to implement groups like this, but I'm not sure it would be a good idea due to the complexity issue).
5. Graph objects are not shared between graphs.
This is important for reducing complexity.  If you want to have network specific attributes or shared attributes across networks, just update the SUID map.
Challenges: keeping the map up to date is work, unlike in our current model.  It could be implemented either using an event based manager design or building a layer on top of the simple model APIs that handles adding attributes to graph objects and keeping the map current.  This is all application layer work, though, and the application sets the policy of attribute sharing among graph objects.
Notes:
Persistence: The only rule for persistence would be uniqueness within a session or file, so you can write or read IDs however you want, as long as you maintain uniqueness per session.  This would likely involve renumbering the SUIDs of all graphobjects upon reading from a session file.
Network merging: you can't use SUIDs to determine equivalence between graph objects.  This needs to be done at the application layer using additional information, such as attributes of those graph objects.

Open Issues

• Should we implement multiple maps to handle local vs. global vs. hidden attributes?
• Should users be able to use this like a database and just create their own tables? (with Cytoscape having default tables defined for graph object attributes?)
• Should we use an existing database layer to implement this or just use a basic map?
• Need to decide a data sharing policy for nodes e.g. no sharing of attributes (memory intensive in the worst case) vs. sharing by default (current case, breaks in some cases e.g. local attributes). The simplest level of the proposal does not deal with shared graph objects or attributes (1:1 mapping). If you want to have 1:many mapping from graph objects to attributes (shared attributes/node), you have to do extra work (though Sarah had a good point that databases may already do some of that work). You could also have other mapping relationships i.e. many:1 (shared nodes/attribute) or many:many, but I don't think we want those, at least initially, because their complexity doesn't justify their use in terms of our use cases.

Events

• Define a low level event mechanism that can be used by modules to communicate their state changes to other modules that depend on them, but not vice versa.

Open Issues

• Use an inheritance model or Event type model?

Groups

A Group is a concept where multiple nodes and edges get collapsed into a single node in a network view. There are several use cases for groups.

• list them here..
• ...

Open Issue

• Currently, Groups are modeled as Nodes. I believe that this is the wrong abstraction. A Group consists of nodes and edges just like a network, the only difference being that Groups have the concept of Inner and Outer edges. Inner edges connect two nodes which are both within the group whereas Outer edges connect one node that is within the group and one node that is outside of the group.

Design Ideas

• Model Groups as a subclass of CyNetwork with additional methods that return just inner edges and just outer edges.

• Nodes can be associated with Groups using attributes that point to network SUIDs.

Hyperedges

A hyperedge is an edge in a hypergraph that can connect two or more nodes at once. A multigraph is subset of a hypergraph where one edge may connect a maximum of two nodes. The requirement for hyperedges is the ability to render biochemical interaction diagrams where reactions are modeled as edges between nodes and these reactions are modified by connecting another edge to the existing reaction edge. The appearance is roughly that of one edge connecting 3 nodes, which would imply that a hyperedge is needed.

Open Issues

• I think the Hyperedge model is the incorrect abstraction for biochemical interaction diagrams. The problem is that in a hypergraph a hyperedge is a single entity with no distinct parts. In the biochemical interaction diagram example the reaction edge is a distinguishable entity from the modifier edge, meaning that the single hyperedge connecting the three nodes is at least two edges (reaction and modifier). If a true hypergraph were used, the distinction between reaction and modifier would not be possible since a true hyperedge is a single entity. I think the fundamental problem here is that as biochemical interaction diagrams are currently conceptualized, they are not graphs at all!

• An implementation of hyperedge currently exists which models hyperedges using connector nodes. That means a reaction edge would actually be two edges connected to an intermediate connector node. Then, any modifier of the reaction is also connected to the connector node. What this effectively does is convert the non-graph biochemical interaction diagram into a simple multigraph.

Design Ideas

• Instead of implementing a true Hypergraph in Cytoscape, I would advocate a variation of the current Hyperedge plugin. Instead of adding (incorrect) hyperedge semantics to the current network model, I would change the way that we present the plugin. The idea is to think of the plugin of a way of simply transforming a biochemical interaction diagram into a multigraph. The advantage of this approach is that we maintain a simple multigraph network model and should allow us to use much of the code that already exists.