CODEWITHSUNDEEP
javascriptcytoscape.js
Jim
Jim

Reputation: 3684

Why does Cytoscape go into an "infinite" loop in this specific situation?

If I clone a layout configuration with Object.assign and try to use that layout, cytoscape quickly causes an out of memory error. I can work around this by just defining a second layout mostly identical to the first and not cloning, but I am interested to know the reason behind the problem, or if it's a possible bug in cytoscape.

With this example code, click add and layout 2 right after loading the page and it will hang/run out of memory. (Have your task manager handy to kill your tab or browser.) Different combinations of adding nodes and running the cloned layout will mostly hang, but not always.

let cy
const layout1 = {
  name: 'euler',
  springLength: edge => 80,
  mass: node => 4,
  randomize: true,
  animate: false,
  gravity: -1.2,
  maxIterations: 1000,
  maxSimulationTime: 4000,
}

const layout2 = Object.assign({}, layout1, {
  fit: false,
  animate: true,
  randomize: false,
})

document.addEventListener('DOMContentLoaded', function() {
  cy = cytoscape({
    container: document.getElementById('cy'),
    layout: layout1,
    style: [
      {
        selector: 'node',
        style: {
          label: 'data(id)',
        },
      },
    ],
    elements: [
      { data: { id: 'a' } },
      { data: { id: 'b' } },
      { data: { id: 'a_b', source: 'a', target: 'b' } },
    ],
  })
})

function add() {
  cy.add([
    { data: { id: 'c' } },
    { data: { id: 'd' } },
    { data: { id: 'c_d', source: 'c', target: 'd' } },
  ])
  // cy.layout(layout2).run()
}

function doLayout1() {
  cy.layout(layout1).run()
}

function doLayout2() {
  cy.layout(layout2).run()
}

function addAndLayout2() {
  add()
  doLayout2()
}
<!DOCTYPE html>
    <html>
      <head>
        <script src="https://cdnjs.cloudflare.com/ajax/libs/cytoscape/3.5.0/cytoscape.min.js"></script>
        <script src="https://cdn.jsdelivr.net/npm/[email protected]/cytoscape-euler.min.js"></script>
      </head>
    
      <style>
        body {
          height: 100%;
        }
        #cy {
          height: 100%;
          flex-grow: 1;
        }
        .main {
          height: 100vh;
          display: flex;
          flex: 1;
        }
      </style>
    
      <body>
        <button onclick="add()">add nodes</button>
        <button onclick="doLayout1()">layout 1</button>
        <button onclick="doLayout2()">layout 2</button>
        <button onclick="addAndLayout2()">add and layout 2</button>
        <div class="main">
          <div id="cy"></div>
        </div>
      </body>
    </html>

Upvotes: 0

Views: 613

Answers (1)

user3140972
user3140972

Reputation: 1065

This has nothing to do with Ojbect.assign (even if you did not copy the object properly, it should not hang).

The reason is the randomize option. For this particular graph, when the randomize option is set to false, the layout never ends. Just remove randomize: false from the second layout, or after adding the new nodes and before running layout2, run the random layout (or just randomize the nodes manually) -- the layout2 will terminate.

The problem is that: the layout must terminate at some point (in the worst case when the umber of max iterations is reached). But this particular layout never terminates.

The interesting thing is that this simple graph turns out to be one of the worst cases for some other layout algorithms as well (for randomized: false). I tried cose-bilkent. It also takes a little bit longer and terminates when the maximum number of iterations is reached (setting numIter option to lower number will result in early termination, worse quality) -- but the result is really bad.

Upvotes: 1

Related Questions