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)

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

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/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

• Is fast for writing and reading and is memory efficient. Use case: large gene expression data sets
• Has simple types, which are good for inter-layer communication and core simplification, that can be combined into more complex types by advanced users. Use case: simple communication of data structures between plugins and modules, experience from Cyto1 and Cyto2.
• Ability to optionally backend attributes to a database. Use case: large gene expression data sets

Open issues

• 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?
• How should special attributes be implemented? E.g. hidden.
• What is the largest size of network we should consider in our design (order of magnitude)? Millions of nodes/edges?

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?