What is the best way to get the closest neighbors on the chart?

Question

I need to compute something whose value is given by the following inappropriate pseudo-python code:

def foo(a,b): tmp = 0 for i in graph.nodes(): for j in graph.nodes(): tmp += c if (i and j are neighbors): tmp += a - c elif (i and j are next-neighbors): tmp += b - c return tmp 

In other words, given all pairs of nodes, foo = a * (E = the number of edges) + b * (EE = the number of pairs that are not neighbors but have a common neighbor) + c * (N (N-1) / 2- EE-E).

I tried to think about some kind of broad first search, but could not.

EDIT: more info

• the graph is not static. I constantly add and remove edges, so I cannot calculate this only once. I have to constantly update the "list of next neighbors."
• I keep the graph as an adjacency matrix.

Answer 1

Here is a rough idea. But, firstly, some assumptions: 1. undirected graph 2. constant graph graph

Your schedule is constantly changing. Therefore, you need to effectively update the number of neighbors (edges) and second neighbors. The first is trivial, so let's look at the second neighbors.

In @Patrick's suggestion, let's work with A^2 , and see how it can be updated efficiently without digesting it from scratch every time. A^2_ij is the number of paths of length - from i to j , just keep in mind that it will also have diagonal entries, because there is always a path of length two from the top to itself. If you have A^2 , you can easily count the number of second neighbors, so let the entire contents of A^2 updated in memory when the graph changes.

How to effectively update A^2 :

When you add / remove an edge, you change A to matrix B , which has only two entries. Suppose we add (without removing) an edge. Then (A+B)^2 = A^2 + AB + BA + B^2 .

Suppose the added edge was (i,j) .

• B^2 is trivial: (B^2)_ii = (B^2)_jj = 1 , the rest is 0.
• AB = transpose(BA) , so we only need to calculate one of the two, say BA . It turns out that line i of BA is line j of A , and line j of BA is line i of A , the rest is zero. Thus, it is quickly calculated.

Removing edges will be similar.

You only need the number of second neighbors, so instead of counting the number of non-zero off-diagonal entries A^2 at each step, with some additional work, you can calculate how many non-zero changes the records have in A^2 when adding AB + BA .

EDIT

All this is explained in another language:

Let the number of paths of length be tracked — two between any two vertices in the matrix M When we add (remove) an edge between i and j , the number of paths of length and length will increase (decrease) by one between i and all neighbors j , as well as j and all neighbors i , so M easily updated to O(n) after each schedule changes.

Answer 2

If you store the graph in Adjacency Matrix A , you can find all the lengths of the 2 paths by multiplying the matrix by yourself ( A^2 ), if that is what you are asking for.

It takes O (n ^ 3) time for preprocessing, but then you can search for neighbors and "neighboring neighbors" at a constant time.

Answer 3

Get a list of neighbors on your node (node_main). Visit every neighbor. Add each of your neighbors to the list of neighbor neighbors, unless it is one of the nodes node_main (or node_main itself). Did I miss something?