Node degree not updating upon edge removal

[jdmswong]

I'm building a graph which allows edges to be toggled on/off. I need to be able to add and remove them repeatedly. I have noticed this error with node degrees with nodes attached to toggled edges. I've included an example.

My code:

allElements = cy.elements();
....
var allEdges  = allElements.filter('edge');                
var allNodes = allElements.filter('node');
for(var i=0; i<5; i++){
    // DELETE
    var printThis = []; 
    allNodes.filter(function(i,ele){
        printThis.push(ele.degree());
    });
    console.log(printThis);
    cy.remove(allEdges);
    cy.add(allEdges);
}

Returns:

[1, 1, 1, 1, 1, 3, 1, 1, 1, 1, 1, 6, 1, 2, 1, 1, 1, 36, 8, 3, 4, 4, 2, 1, 1, 1, 1, 1, 1, 2]
[1, 1, 1, 1, 1, 3, 1, 1, 1, 1, 1, 6, 1, 2, 1, 1, 1, 36, 8, 3, 4, 4, 2, 1, 1, 1, 1, 1, 1, 2] 
[2, 2, 2, 2, 2, 6, 2, 2, 2, 2, 2, 12, 2, 4, 2, 2, 2, 72, 16, 6, 8, 8, 4, 2, 2, 2, 2, 2, 2, 4] 
[3, 3, 3, 3, 3, 9, 3, 3, 3, 3, 3, 18, 3, 6, 3, 3, 3, 108, 24, 9, 12, 12, 6, 3, 3, 3, 3, 3, 3, 6] 
[4, 4, 4, 4, 4, 12, 4, 4, 4, 4, 4, 24, 4, 8, 4, 4, 4, 144, 32, 12, 16, 16, 8, 4, 4, 4, 4, 4, 4, 8]

Which shows that removing edges after the first time doesn't decrease the degree of the nodes they're attached to.

This is quite important towards our cytoscape application.

[maxkfranz]

Great; I'll make a unit test that reproduces this case like your example, and we'll fix it in the next release (NB if you build from trunk you can get the changes sooner). Thanks! -M

On Fri, Sep 13, 2013 at 1:53 PM, JD Wong notifications@github.com wrote:

'm building a graph which allows edges to be toggled on/off. I need to be able to add and remove them repeatedly. I have noticed this error with node degrees with nodes attached to toggled edges. I've included an example.

My code:

allElements = cy.elements(); .... var allEdges = allElements.filter('edge'); var allNodes = allElements.filter('node'); for(var i=0; i<5; i++){ // DELETE var printThis = []; allNodes.filter(function(i,ele){ printThis.push(ele.degree()); }); console.log(printThis); cy.remove(allEdges); cy.add(allEdges); }

Returns:

[1, 1, 1, 1, 1, 3, 1, 1, 1, 1, 1, 6, 1, 2, 1, 1, 1, 36, 8, 3, 4, 4, 2, 1, 1, 1, 1, 1, 1, 2] [1, 1, 1, 1, 1, 3, 1, 1, 1, 1, 1, 6, 1, 2, 1, 1, 1, 36, 8, 3, 4, 4, 2, 1, 1, 1, 1, 1, 1, 2] [2, 2, 2, 2, 2, 6, 2, 2, 2, 2, 2, 12, 2, 4, 2, 2, 2, 72, 16, 6, 8, 8, 4, 2, 2, 2, 2, 2, 2, 4] [3, 3, 3, 3, 3, 9, 3, 3, 3, 3, 3, 18, 3, 6, 3, 3, 3, 108, 24, 9, 12, 12, 6, 3, 3, 3, 3, 3, 3, 6] [4, 4, 4, 4, 4, 12, 4, 4, 4, 4, 4, 24, 4, 8, 4, 4, 4, 144, 32, 12, 16, 16, 8, 4, 4, 4, 4, 4, 4, 8]

Which shows that removing edges after the first time doesn't decrease the degree of the nodes they're attached to.

This is quite important towards our cytoscape application.

— Reply to this email directly or view it on GitHubhttps://github.com/cytoscape/cytoscape.js/issues/347 .

[jdmswong]

Appreciate it, thanks!

[maxkfranz]

I can't reproduce your issue. Looking at your sample, you may be using the API incorrectly. cy.add() is for new elements from JSON (old elements are copied from JSON). You should be using eles.restore() for performance and consistency reasons. Perhaps support for elements as parameters to cy.add() should be removed completely.

[jdmswong]

Ok, I'm curious as to why it seems to work the first time, after which it just starts adding. The elements are new, right, because I removed them? Did you mean never-before-seen elements?

[maxkfranz]

To support multiple instances of cy.js, it is important to allow for transferring elements from one instance to another. To support this:

• Each element has a core owner.
• The core owner is always the instance that created the element from JSON.
• When adding via cy.add(), all elements are treated as new ones. Each element is copied, and a new element is created in the second instance.

What you are seeing is the cy.add() behaviour, which is similar to cy.load(). Each time you call cy.add(), you're just making new copies.

We could support your usecase better if we automatically restored if the creating instance is the same as the one the element is being added to. Another improvement would be to rename the function -- still supporting the old, shorter alias -- to something like cy.addNew() so it's a bit more clear from the getgo.

[maxkfranz]

Please try out the trunk and let me know whether the change makes the API work more like you expect.

[maxkfranz]

Another thing to consider in general is that adding, removing, and restoring elements can be expensive. If you're just toggling, you could try toggling the visibility visual style.

[jdmswong]

@maxkfranz I think the issue is with remove not removing nodes, so cy.add() keeps adding copies over and over.

How do I use the trunk code? I just have the cytoscape.min.js from the provided download links.

[maxkfranz]

If you make all, you'll get everything made for you like a release in the /build directory.

Once an element is removed, it is semi-orphaned: It no longer really belongs to its core instance owner. Any element in this state is in a sort of limbo -- floating around in memory outside of the core but ready to be restored back if need be. If it's not really in the graph, graph metrics don't make sense anymore and neither may the actual results of calling those metric functions, like ele.degree().

[jdmswong]

Thanks, is it still possible to have ele.degree() accurately reflect removed nodes? I would just like nodes to be removed cleanly, so they can be added again if need be.

[maxkfranz]

Short answer: If you want a guarantee that functions behave correctly for an element, then that element must not be removed.

Explanation:

Any removed element should not be used other than to hold onto for restoring later. There are many functions that just will not work when an element is orphaned unless large assumptions are made, such as that the element is simply disconnected somehow from the graph. The degree case seems simple, but it opens a can of worms by creating the client dev expectation that functions should work on removed elements.

However, there are too many inconsistencies that arise from assumptions like this. One simple example (of many you could think of): What about edges? They are defined as a connection between nodes in the graph. Does this mean ele.source() works, or does it not? Does it work if the source node is in the graph? Does it work if it's not? Nothing really makes sense anymore once an element has been removed from the context of a graph -- it's a matter of definition.

It was by design that the behaviour of those sorts of functions is undefined for removed elements. It would overcomplicate the API. It would introduce inconsistencies in the model. It would have issues in terms of maintainability of the codebase. It would likely impact overall performance.

It sounds like you're just hiding elements, anyway, and in that case it makes more sense to use visual styles to hide elements in the appropriate state. If you want to continue with the way that you're doing things, it would make sense to add a removed check if you want to process removed elements. Essentially you would use an intermediary variable for degree rather than just directly reading the function return value.

[jdmswong]

I need to add and remove elements because hidden edges will affect the curvature of visible ones, creating an undesirable looking graph.

[maxkfranz]

How about you use the visibility property for now and we try to support something along the lines of display:none for 2.1 so that display:none elements don't take up space (i.e. display none edges look as though they have been removed)?

[maxkfranz]

@jdmswong You can now use the display visual property. It takes on the value element (shown) or none (hidden). The eles.show() and eles.hide() functions now use the display property, so you can alternatively use those functions for your purposes.

You'll have to make all to get these changes in the trunk.