HyperEdgeUpdating

How Do We Keep HyperEdge Structures Up-To-Date?

The Problem

Using Event callbacks to monitor the hiding of GraphObjects can lead to IllegalStateExceptions. We can cause IllegalStateExceptions in FGraphPerspective by indirectly fully hiding objects we are in the middle of hiding.

For example, assume we have a HyperEdge with ConnectorNode cn1. This HyperEdge has edge e1 to node P and edge e2 to node M (see diagram). Notice that if we hide any edge, the HyperEdge will be hidden causing e1-e2, and cn1 to be hidden.

  e2    e1
M----o---->P
    cn1

Now assume a user selects e1 and does 'Edit->Delete Selected Nodes and Edges'. The call chain looks something like:

...
cytoscape.editor.actions.DeleteAction.actionPerformed()
  fing.model.FGraphPerspective.hideEdges()
    fing.model.FGraphPerspective$GraphWeeder.hideEdges()
       <HyperEdgeManager callback called with e1>
    fing.model.FGraphPerspective$GraphWeeder.actuallyHideEdge()
    ...

The current HyperEdgeManager event callback will take the edge (e1) and carefully remove HyperEdge bookkeeping information about this edge--without deleting it. However, removing e1 from the HyperEdge implies that the whole HyperEdge must be removed. So, e2 and cn1 are hidden. When cn1 is really hidden by FGraphPerspective, it will first hide its edges, namely e1 will be fully hidden. However, notice that we are in the process of hiding e1--we are in the event call back for it being hidden. So, after our event callback completes, FGraphPerspective.actuallyHideEdge() will get an IllegalStateException since e2 is been hidden out from underneath it (for all the gory details, see Details of Simple Example, below).

Rehiding versus Recursively Hiding

Notice that rehiding and recursively hiding a GraphObject are different issues. Rehiding a CyNode or CyEdge is attempting to hide it again after fully hiding it already. Fing is fairly robust here, since it already has to deal with these situations (see Rehiding CyNodes and CyEdges in Fing, below). However, where Fing is inflexible is in recursively hiding a GraphObject.

How to Solve This Problem

Before looking at temporary solutions, notice that this problem goes away if (when) HyperEdge is placed in Cytoscape core. At this time, then event callbacks will no longer be needed to track deletions but instead the real HyperEdge API deletion methods would be invoked directly.

To temporarily solve this problem, we need to follow the rule:

• Never hide any Cytoscape GraphObjects while in a hide-related event callback.

• Save what must be hidden during hide event callback to HyperEdgeManager and reconcile differences at end of a hide operation.

  This requires the addition of one, or possibly two, new events to be fired when we are beginning (HIDING_STARTED) and ending all hide operations (HIDING_ENDED). Because this isn't feasible in the short-term, a limited solution would be to modify cytoscape.editor.actions.DeleteAction.actionPerformed() to fire these events. Here's how this would work:

  1. HyperEdgeManager would listen for HIDING_STARTED and HIDING_ENDED events.

  2. When getting HIDING_STARTED callback, store the set of all GraphObjects to be hidden in a originallyHidden Set. Also clear out a toBeHidden Set tracking HyperEdge-based GraphObjects to be hidden. [It may be possible to dispense with this event and simply store this Set when the hide event callback is performed.]

  3. During hidden nodes and hidden edges callbacks, perform all HyperEdge management bookkeeping to remove the given GraphObjects, but don't actually hide them--including GraphObjects indirectly hidden. Instead, add these objects in toBeHidden Set. Caution: We must be careful about using real info from GraphObjects since this will not batch internal HyperEdge info (nodes and edges will still exist, but not be part of HyperEdge). [Question: What should we do if HIDING_STARTED wasn't called?]

  4. When HIDING_COMPLETED is called, compare originallyHidden set with toBeHidden set. For each GraphObject in toBeHidden that is not in originallyHidden, really hide the GraphObject but treat as internal deletion--do nothing on callback for their hiding. [If Cytoscape is truely robust about rehiding GraphObjects, then the originallyHidden set may not be necessary.]

• Delayed CyNode Deletion

  Notice that all of our problems are because deletion of an edge or node can lead to the deletion of another node that then causes its edges to be deleted. This can lead to an edge being deleted that we are already in the process of deleting. So, if we don't delete ConnectorNodes, then this stops our problems. The strategy here is to place all ConnectorNodes to be deleted on a deletion list. Then, at a later time, a call can be made to "garbage collect" the deleted nodes. Here's how this would work:

  1. Change HyperEdge bookeeping methods to no longer delete CyNodes, but to instead place the CyNodes in a delete Set.

  2. Add the monitoring of Cytoscape.NETWORK_MODIFIED events and call:

                  HyperEdgeFactory.INSTANCE.getHyperEdgeManager().hideConnectorNodes();

     to actually delete the nodes on the node deletion list. Currently, NETWORK_MODIFIED doesn't specify what sort of action has occurred, so we could be deleting the CyNodes after an insertion, but this doesn't seem to matter. Also, the check and deletion are fairly efficient.

  This technique avoids the need for new events to be fired by the CytoscapeEditor and is simplier to implement. Like solution one, this solution only completely works when higher-level hide operations manually call hideConnectorNodes(). However, this approach fails more gracefully in that even when hideConnectorNodes() isn't called, the only failing is to leave orphan CyNodes laying around, as opposed to causing IllegalStateExceptions. This is the approach taken for the 2.6 release of the HyperEdge plugin.

Other Strategies Considered

1. Just catch IllegalStateException checking that error is the 'internal error - couldn't hide xxx' and continue. Besides being an incredible hack and possibly catching other unwanted errors, it isn't clear where the catching could be done so that we could continue. The RootGraph may also be in a corrupted state.

2. When a hiding callback starts, track all items given in the list of items to hide and ensure that HyperEdge operations don't actually hide any of these items. This was attempted, passing in a BookkeepingItem that contains all GraphObjects to ignore as far as hiding. Although this catches potential problems with rehiding objects (which doesn't look like it's a problem anyway), it does not deal with recursive hiding.

Rehiding CyNodes and CyEdges in Fing

!FGraphPerspective.hideEdges() must already be somewhat flexible to handle simple hidings. For example, the code for Edit-->"Delete Selected Nodes and Edges", in cytoscape.editor.actions.DeleteAction.actionPerformed(), performs the following steps:

   ...
   cyNet.hideNodes(nodes);
   cyNet.hideEdges(edges);
   ...

If we select a CyNode and its CyEdges and hide them, then by the time cyNet.hideEdges() is called, 'edges' will be hidden.

More Complex Example

Assume we have two HyperEdges he1 and he2 with ConnectorNodes cn1 and cn2 respectively. he1 has edge e2 to cn2 and edge e1 to node A. he2 has edge e2 to cn1 and edge e3 to B (see diagram). Notice that if we hide any edge or any node, both hyperedges will be deleted causing e1-e3, cn1, and cn2 to be hidden.

  e1
A---->o
      |
      |e2
      |
      v
B---->o
  e3

Now assume a user selects e1,e2,e3 and does 'Edit->Delete Selected Nodes and Edges'. The call chain looks something like:

...
cytoscape.editor.actions.DeleteAction.actionPerformed()
  fing.model.FGraphPerspective.hideEdges()
    fing.model.FGraphPerspective$GraphWeeder.hideEdges()
       <HyperEdgeManager callback called with e1,e2,e3>
    fing.model.FGraphPerspective$GraphWeeder.actuallyHideEdge()
    ...

Details of Simple Example

cytoscape.editor.actions.DeleteAction.actionPerformed()
  fing.model.FGraphPerspective.hideEdges()
    fing.model.FGraphPerspective$GraphWeeder.hideEdges()
       [HyperEdgeManager callback called with e1]
         save e1 on toIgnoreList
         HE.removeEdgeBookkeeping()
           HE.primDestroy() -- not enough egdes remain
             HE.primRemoveNode(M)
               HE.primRemoveEdge(e2)
                 HE.removeUnderlyingEdge (e2)
                   since e2 is not on toIgnoreList, really hide
                   CyNet.removeEdge (e2)
                     [HyperEdgeManager callback with e2--immediate return
                      since we are in an internal operation]
                      E2 REALLY REMOVED BY FGraphPerspective
             HE.primRemoveNode(P)
               HE.primRemoveEdge (e1)
                 HE.removeUnderlyingEdge (e1)
                   since e1 is on the toIgnoreList, NO deletion
             HE.removeConnectorNodeAndAttributes()
               HE.removeUnderlyingNode (cn1)
                 HEM.removeNodeFromNet (cn1)
                   since cn1 is NOT on ignore list-hide
                   CyNet.removeNode (cn1)
                     [HyperEdgeManager callback with cn1--immediate return
                      since we are in an internal operation]
                     [HyperEdgeManager callback with e1--immediate return
                      since we are in an internal operation]
                      E1 REALLY REMOVED By FGraphPerspective
                      We are screwed at this point because E1 was
                      hidden while hiding E1.
    fing.model.FGraphPerspective$GraphWeeder.actuallyHideEdge(e1)
       IllegalStateException--internal error: couldn't hide edge -3.