alignment constraints cause explosion of internal constraints in vpsc

[gordonwoodhull]

Hi Tim!

I have this page to test dynamic graph layout using dc.graph.js and cola.js:

http://dc-js.github.io/dc.graph.js/index.html?reinit=0&displace=0&linklength=30

I'm trying to draw a graph with displacement and alignment (rank) constraints. Each step I am adding or removing a few nodes and edges, and I feed new nodes, links, and (in this case two) constraints to cola.js as so:

        _d3cola.nodes(nodes1)
            .links(edges1)
            .constraints(constraints)
            .start(10,20,20)

But the two alignment constraints cause cola.js to slow down to a halt (and use 100% CPU) unless I reboot cola.js each step (by constructing cola.d3adaptor()).

Putting a profiler on it, I found most of the time is being consumed in Variable.prototype.visitNeighbours. So I added a log

cola.js:813         console.log(this.cOut.length, this.cIn.length)

and set my looper to just go back and forth between step 6 and 7.

Externally, there are two alignment constraints, with one "rank" having about 9 nodes and the other about 7 nodes.

It looks like the number of internal constraints for the different kinds of variables increase linearly (by 1s, 2s, and 3s), starting out in the dozens and getting up into the thousands, before it completely eats the CPU and is difficult to stop.

For example, two corresponding sections of log near the end:

7481 2493
2493 1
2493 4987
2493 2493
7481 2493
2493 1
2493 4987
4986 4986

7484 2494
2494 1
2494 4989
2494 2494
7484 2494
2494 1
2494 4989
4988 4988

Am I doing something wrong, or should replacing the two alignment constraints each step be okay?

Thanks,
Gordon

[tgdwyer]

Hi Gordon,

I didn't look at your code, but I can think of two possibilities here:

1. the constraints you are specifying constraints that are infeasible (e.g.
   a cycle of inequality separation constraints or conflicting equality
   constraints) - this should still not cause an infinite loop but I don't do
   much to handle such degenerate input gracefully.

2. you are changing the constraints or graph structure without
   reinitializing layout. It is very important that you don't try to change
   the structure of the graph or constraints while the layout is actually
   running. Thus, you should either rerun it statically after each change in
   graph or constraints, by just calling (e.g.) cola.start(50,20,10), where
   the three numbers are numbers of iterations of each phase of constraint
   layout to run (see inline comments for details). Or, if you want to
   animate the layout by listening to tick events, then you should wait for
   the "end" event (notifying of layout convergence) before calling start
   again.

Does that help? Otherwise, we'll dig in a little bit more :-)

Cheers,

Tim

On 18 June 2015 at 07:11, Gordon Woodhull notifications@github.com wrote:

Hi Tim!

I have this page to test dynamic graph layout using dc.graph.js
https://github.com/dc-js/dc.graph.js:

http://dc-js.github.io/dc.graph.js/index.html?reinit=0&displace=0&linklength=20

I'm trying to draw a graph with displacement and alignment (rank)
constraints, but the alignment constraints cause cola.js to slow down to a
halt (and use 100% CPU) unless I reboot cola.js each step (by constructing
cola.d3adaptor()).

Putting a profiler on it, I found most of the time is being consumed in
Variable.prototype.visitNeighbours. So I added a log

cola.js:813 console.log(this.cOut.length, this.cIn.length)

and set my looper to just go back and forth between step 6 and 7.

There are two alignment constraints, with one "rank" having about 9 nodes
and the other about 7 nodes.

It looks like the number of neighbors for the different kinds of variables
increase linearly (by 1s, 2s, and 3s), starting out in the dozens and
getting up into the thousands, before it completely eats the CPU and is
difficult to stop.

For example, two corresponding sections of log near the end:

7481 2493
2493 1
2493 4987
2493 2493
7481 2493
2493 1
2493 4987
4986 4986

7484 2494
2494 1
2494 4989
2494 2494
7484 2494
2494 1
2494 4989
4988 4988

Am I doing something wrong, or should replacing the two alignment
constraints each step be okay?

Thanks,
Gordon

—
Reply to this email directly or view it on GitHub
#117.

Dr Tim Dwyer BSc BCS(Hons) PhD
Senior Lecturer and Larkins Fellow
Caulfield School of Information Technology
Mobile: 0481 240 767
(from overseas: +61 481 240 767)

[gordonwoodhull]

Thanks for your help. This is with just two alignment constraints of this form:

[
  {
    "offsets": [
      {
        "node": 0,
        "offset": 0
      },
      {
        "node": 1,
        "offset": 0
      },
      {
        "node": 2,
        "offset": 0
      }
    ],
    "type": "alignment",
    "axis": "y"
  },
  {
    "offsets": [
      {
        "node": 5,
        "offset": 0
      },
      {
        "node": 6,
        "offset": 0
      },
      {
        "node": 7,
        "offset": 0
      }
    ],
    "type": "alignment",
    "axis": "y"
  }
]

so I don't think there should be any cycles.

That is a helpful tip about watching for the end event. I was calling stop before but now I'm also waiting for the later of one second and the end event. It turns out I was indeed stepping on my own heels, but the performance degradation kicks in before layout gets to a full second. (In fact, the degradation seems to be the cause of layout taking a full second at all.)

Note: the linear increase of 1-3 constraints is per-Descent.prototype.stepAndProject, which runs hundreds of times each layout step! That's why this degrades so fast.

By contrast, if I re-construct cola on each step with cola.d3adaptor(), the number of constraints reported by the above log does not leave the single digits! So I imagine the performance is going to be pretty amazing if I get past this.

[gordonwoodhull]

BTW, I also ran into a case where these alignment constraints cause layout not to converge at all:

It's kind of hard to see the jitter with just a couple of screenshots, but the middle two (blue and purple) nodes are oscillating back and forth together, and layout doesn't terminate because of them.

But this may be because there are hundreds of erroneous constraints by this point.

[gordonwoodhull]

So, it turns out that there are some big differences between constructing a new cola.d3adaptor() each step, and keeping the same object. In particular, layout seems to be much more stable if you keep it around (which is why I wanted to make this work).

On a guess, I decided that since it obviously is keeping some state (including bounds and variable) inside the nodes, I should probably make sure I'm passing the same objects in each time, and this fixed this issue. Starting a Troubleshooting wiki and adding this hint there.

Now I can move along to my layout problems, so that's great!