Performance problems with digraph structure

Hello, I need to add and remove nodes to a directional graph structure in real-time. Unfortunately i've encountered massive performance problems using the digraph structure from Matlab - especially when adding or removing nodes/edges. Are there any alternatives or more adequate ways to archive my goles. I'm thankful for any help!

    nClosest = 16;
    numFrames = 30;

    idx = knnsearch(featureTree, features, 'K', nClosest).';
    data = frameData(idx,:);

%%420 frames per second
    nodes = table(data, 'VariableNames', {'Data'});

%%350 frames per second

      % Node 1 is START, node 2 is END
      if counter < numFrames
          lastIdx = counter*nClosest+2;
          graph = addnode(graph, nodes);
      else
          lastIdx = numFrames*nClosest+2;
          graph = addnode(graph, nodes);
          graph = rmnode(graph, 3:nClosest+2); % never remove START or END
      end

      myNodes = graph.Nodes;

%%180 frames per second
    if lastIdx == numFrames*nClosest+2
        firstRowIdx = lastIdx-nClosest+1 : lastIdx;
        secondRowIdx = lastIdx-nClosest*2+1 : lastIdx-nClosest;

          firstRow = myNodes(firstRowIdx,:).Data;
          secondRow = myNodes(secondRowIdx,:).Data;

          [t,knnW] = knnsearch(firstRow, secondRow);
          edge = secondRowIdx(t);
          startNodeIdx = 1;
          endNodeIdx = 2;

          w = zeros(1,nClosest*3);
          w(nClosest*2+1:end) = knnW;

          from = 3:nClosest*3+2; %last row
          from(nClosest+1:nClosest*2) = ones(1,nClosest)*startNodeIdx; % start
          from(nClosest*2+1:end) = firstRowIdx; % first row

          to = ones(1,nClosest*3)*endNodeIdx; %end
          to(nClosest+1:nClosest*2) = firstRowIdx; % first row
          to(nClosest*2+1:end) = edge; % second row

          graph = addedge(graph, from, to, w);
      end
  %%108 frames per second

Answer 1

[Christine Tobler]

Generally speaking, it's much cheaper to construct a graph once, given all the nodes and edges, than incrementally using addnode/addedge. From your description, I assume that you need to update the graph as shown above, then call some methods on the graph, then update it again. Otherwise, computing all nodes and edges before constructing the graph would be the way to go.

Could you run the profiler to find out where the bottleneck is - is it in addedge itself, or in addnode, or in constructing the inputs to these functions?

If the bottleneck is addedge, one thing to consider would be to use the adjacency graph constructor instead of updating the graph using addedge. You would be carrying around a sparse matrix M, where M(i,j) has the value of the weight of the edge (i, j), and constructing the graph from M whenever you update it. I'm not sure this would be faster, but it's something to try.

[Tobias Manroth]

Thank you very much! I tried your suggestion and I managed to improve the performance significantly by creating a adjacency matrix on the fly and generating a digraph from that matrix. The bottleneck was adding and removing nodes and edges. However I would really like to improve the performance even more... I need to create an acyclic directional graph where each node can be connected to one or zero other nodes. The graph needs to be updated and every few milliseconds by adding and deleting a certain amount of nodes.

[Christine Tobler]

What methods of graph/digraph are you calling in between the updates? I don't see an obvious way of speeding up the graph constructor, but for some methods there might be a workaround to updating the graph so often.

[Tobias Manroth]

I solved the problem by implementing my own graph class, thank you very much!