Effective Resistance for Graphs

fd0a7a5c-d4ea-4553-8c94-ca5df6fef35f commented 6 years ago

Calculate effective resistances between pairs of nodes in a graph.

Component: graph theory

Keywords: effective resistance, resitance distance, link prediction, sd90

Author: Amanda Francis, Rajat Mittal

Branch: 9648677

Reviewer: David Coudert

Issue created by migration from https://trac.sagemath.org/ticket/24094

fd0a7a5c-d4ea-4553-8c94-ca5df6fef35f commented 6 years ago

Branch: u/afrancis/effective_resistance_for_graphs

7ed8c4ca-6d56-4ae9-953a-41e42b4ed313 commented 6 years ago

Commit: bc41ea1

7ed8c4ca-6d56-4ae9-953a-41e42b4ed313 commented 6 years ago

Branch pushed to git repo; I updated commit sha1. New commits:

bc41ea1 Fixed some documentation errors

7ed8c4ca-6d56-4ae9-953a-41e42b4ed313 commented 6 years ago

Changed commit from bc41ea1 to 054b8ea

7ed8c4ca-6d56-4ae9-953a-41e42b4ed313 commented 6 years ago

Branch pushed to git repo; I updated commit sha1. New commits:

054b8ea Changed indentation authorship line

dcoudert commented 6 years ago

comment:5

Welcome to Sagemath.

I have several comments on your ticket, some on the presentation and some on the algorithms you use.

Let's start with general comments, mostly on the presentation. I give them for the first method, but you should do the same for the other methods.

effective_resistance(self,i,j) -> effective_resistance(self, i, j)
Returns the effective resistance between nodes i and j -> Return the effective resistance between nodes `i` and `j`.
Please add a description of the notion of effective resistance. What is it?
You could add a link to the wikipedia page (e.g., in the seealso block). Should be See :wikipedia:`Resistance_distance` for more details
Text lines (comments, definition, etc. must be in 80 columns format. Some code editors like emacs help you to do that without effort
a straight linear 2-tree on 6 vertices. Well, I assume it's a Path graph of order 6, no?
then you can use: G1 = graphs.PathGraph(6)
replace G1 with G since you don't have G2
in the test with the complete graph, you check only 1 edge. I assume you want to should that the resistance of each edge is 1/2, right? so you could do instead:

sage: G = graphs.CompleteGraph(4)
sage: all(G.effective_resistance(u, v) == 1/2 for u,v in G.edge_iterator(labels=0))
True

Since I'm not familiar with this definition, it is not easy to tell which tests are important or not.
Could you tell us what is the expected behavior if the graph has loops, multiple edges, is empty, is not connected ?

We will get to the algorithmic part latter. I need to understand the definition first. I have the feeling that we can do something faster, may be in another ticket.

7ed8c4ca-6d56-4ae9-953a-41e42b4ed313 commented 6 years ago

Branch pushed to git repo; I updated commit sha1. New commits:

391271a Documentation changes in response to ticket review

7ed8c4ca-6d56-4ae9-953a-41e42b4ed313 commented 6 years ago

Changed commit from 054b8ea to 391271a

fd0a7a5c-d4ea-4553-8c94-ca5df6fef35f commented 6 years ago

comment:7

Thanks for your very helpful comments! I think I made all the presentation changes you submitted

a straight linear 2-tree on 6 vertices. Well, I assume it's a Path graph of order 6, no? then you can use: G1 = graphs.PathGraph(6)

No, a straight linear 2-tree is like a ladder made out of triangles, not a path.

Since I'm not familiar with this definition, it is not easy to tell which tests are important or not. Could you tell us what is the expected behavior if the graph has loops, multiple edges, is empty, is not connected ?

Multiple edges should lower the effective resistance between pairs of nodes. A 'parallel' network transformation demonstrates how this works, but this is another method we are working on implementing at this Sagedays!

An empty graph has no node pairs, so an error should be returned for effective_resistance, and an empty matrix for effective_resistance_matrix.

I hadn't thought about connected graphs. Effective resistance between edges in different components should be infinity or return an error. I'll work on that. Also, loops should not be allowed. I'll fix that as well.

We will get to the algorithmic part latter. I need to understand the definition first. I have the feeling that we can do something faster, may be in another ticket.

Interesting, I would be happy to find out that this is true!

dcoudert commented 6 years ago

comment:8

In the description of the method, use `i` instead of just i. This indicates that this is math code. It will be handled when generating the html documentation and so well displayed. You can also put latex equations if you like (e.g., \sqrt{x^3+1} \leq 2).

For wikipedia links, the _ in :wikipedia:`Resistance_Distance` is needed. If corresponds to the name of the page you see in the url https://en.wikipedia.org/wiki/Resistance_distance

When you have parameters with default value, don't put spaces. So def effective_resistance_matrix(self, nonedgesonly = True): -> def effective_resistance_matrix(self, nonedgesonly=True):. The same when you call the method.

if ``True`` eliminate pairs of adjacent vertices. Well, you don't eliminate pairs, you assign them value 0. It's different, no?

I prefer self.order() to self.num_verts().

For least_effective_resistance, you should rewrite like that (should be much faster).

    self._scream_if_not_simple()
    if nonedgesonly and self.is_clique():
        return []
    S = self.effective_resistance_matrix(nonedgesonly=nonedgesonly)
    if nonedgesonly:
        edges = self.complement().edges(labels=0)
    else:
        edges = [(i,j) for i in range(n) for j in range(i+1,n)]
    rmin = min(S[e] for e in edges)
    return [e for e in edges if S[e] == rmin]

The self._scream_if_not_simple() will raise an error if the graph has loops or multiple edges. You don't need to add specific tests for that.

For effective_resistance(self, i, j):, you have to decide of what to do when i == j and you should check if not i in self or not j in self:.

The case of non connected should be treated at some point.

method 1: if not in same component return +oo or 0. Otherwise, do computation only on that component
method 2: you can certainly build the matrix from the results on each connected components
method 3: You can do computations independently on each components and collect the result (faster than working on a big matrix)

dcoudert commented 6 years ago

comment:9

you can also decide that the graph must be connected. I don't know what is best.

2460b664-5ecd-43fc-9bbe-d0f333762988 commented 5 years ago

comment:10

According to wikipedia definition: In graph theory, the resistance distance between two vertices of a simple connected graph, G, is equal to the resistance between two equivalent points on an electrical network, constructed so as to correspond to G, with each edge being replaced by a 1 ohm resistance. It is a metric on graphs.

It assumes graph to be simple and connected, so I guess we can do the same here.

Can I work further on this ticket, if nobody else is working based on the proposed changes in the review above?

dcoudert commented 5 years ago

comment:11

Yes, you can.

2460b664-5ecd-43fc-9bbe-d0f333762988 commented 5 years ago

Changed commit from 391271a to none

2460b664-5ecd-43fc-9bbe-d0f333762988 commented 5 years ago

Changed branch from u/afrancis/effective_resistance_for_graphs to u/gh-rajat1433/24094_effective_resistance_for_graphs

2460b664-5ecd-43fc-9bbe-d0f333762988 commented 5 years ago

comment:14

I had a small doubt regarding should I be continue working on these functions in graph.py file or migrate them to generic_graph.py file. I guess these functions might be more suitable in latter module.

dcoudert commented 5 years ago

comment:15

Is the method valid for both Graph and DiGraph ?

2460b664-5ecd-43fc-9bbe-d0f333762988 commented 5 years ago

comment:16

Replying to @dcoudert:

Is the method valid for both Graph and DiGraph ?

It makes sense for Graph. Thanks for clearing the confusion.

7ed8c4ca-6d56-4ae9-953a-41e42b4ed313 commented 5 years ago

Branch pushed to git repo; I updated commit sha1. New commits:

8c4714c Improved the resistance methods.

7ed8c4ca-6d56-4ae9-953a-41e42b4ed313 commented 5 years ago

Commit: 8c4714c

7ed8c4ca-6d56-4ae9-953a-41e42b4ed313 commented 5 years ago

Branch pushed to git repo; I updated commit sha1. New commits:

e164fa3 fixed bugs for documenting

7ed8c4ca-6d56-4ae9-953a-41e42b4ed313 commented 5 years ago

Changed commit from 8c4714c to e164fa3

2460b664-5ecd-43fc-9bbe-d0f333762988 commented 5 years ago

Reviewer: David Coudert

2460b664-5ecd-43fc-9bbe-d0f333762988 commented 5 years ago

comment:20

I have pushed the modified code and passed all the tests and corner cases and also tested the documentation build.

7ed8c4ca-6d56-4ae9-953a-41e42b4ed313 commented 5 years ago

Branch pushed to git repo; I updated commit sha1. New commits:

37d171b fixed indentation and 80 column format

7ed8c4ca-6d56-4ae9-953a-41e42b4ed313 commented 5 years ago

Changed commit from e164fa3 to 37d171b

dcoudert commented 5 years ago

comment:22

Another round of comments. Certainly more to come :P The goal is to obtain the best possible code. It's always easier to read, so contains less errors and is way easier to maintain.

Ensure that all comments are in 80 columns mode. For instace

-- Amanda Francis, Caitlin Lienkaemper, Kate Collins, Rajat Mittal (2019-03-10): methods for computing effective resistance
+- Amanda Francis, Caitlin Lienkaemper, Kate Collins, Rajat Mittal (2019-03-10):
+   methods for computing effective resistance

You can use latex mode

-        OUTPUT: rational number denoting resistance between nodes i and j
+        OUTPUT: rational number denoting resistance between nodes `i` and `j`

Although labels=0 is currently accepted, it is better to write labels=False

-            sage: all(G.effective_resistance(u, v) == 1/2 for u,v in G.edge_iterator(labels=0))
+            sage: all(G.effective_resistance(u, v) == 1/2 for u,v in G.edge_iterator(labels=False))

not i in self: -> i not in self.
some pep8 (I know it's impossible to be aware of all these rules. We try to do our best)

-            raise ValueError('The Graph is not a connected graph.')
+            raise ValueError('the Graph is not a connected graph')

It is better to give the order of the vertices to laplacian_matrix. Furthermore, .vertices() currently sort vertices by default, but you don't need that. So use either list(self) or self.vertices(sort=False)

-        vert = self.vertices()
+        vert = list(self)
         i1 = vert.index(i)
         i2 = vert.index(j)
         n = self.order()
-        L = self.laplacian_matrix()
+        L = self.laplacian_matrix(vertices=vert)

-        sigma = matrix(Id[i1]-Id[i2])
-        diff = sigma* M * sigma.transpose()
+        sigma = matrix(Id[i1] - Id[i2])
+        diff = sigma * M * sigma.transpose()

diff[0,0] -> diff[0, 0]
Improve other methods the same way
Add parameter vertices to least_effective_resistance

7ed8c4ca-6d56-4ae9-953a-41e42b4ed313 commented 5 years ago

Changed commit from 37d171b to 0cbfdbd

7ed8c4ca-6d56-4ae9-953a-41e42b4ed313 commented 5 years ago

Branch pushed to git repo; I updated commit sha1. New commits:

0cbfdbd fixed the coding style bugs

2460b664-5ecd-43fc-9bbe-d0f333762988 commented 5 years ago

comment:24

Thanks for the review.

I don't think least_effective_resistance requires vertices as a perimeter as the user is generally interested in finding the least resistance wrt the whole graph. Still if it is required I can add that. Although I did add this

        verts = list(self)
        verttoidx = {u: i for i, u in enumerate(verts)}
        S = self.effective_resistance_matrix(vertices=verts, nonedgesonly=nonedgesonly)

dcoudert commented 5 years ago

comment:25

Right, I forgot the method returns vertices with least resistance.

This is not needed

-        verttoidx = {}

Also, please improve the code as much as you can according pep8 rules.

7ed8c4ca-6d56-4ae9-953a-41e42b4ed313 commented 5 years ago

Changed commit from 0cbfdbd to 5510cba

7ed8c4ca-6d56-4ae9-953a-41e42b4ed313 commented 5 years ago

Branch pushed to git repo; I updated commit sha1. New commits:

5510cba minor fix

2460b664-5ecd-43fc-9bbe-d0f333762988 commented 5 years ago

comment:27

This is not needed

verttoidx = {}

Yes I did that locally but forgot to commit :)

7ed8c4ca-6d56-4ae9-953a-41e42b4ed313 commented 5 years ago

Changed commit from 5510cba to c8032e7

7ed8c4ca-6d56-4ae9-953a-41e42b4ed313 commented 5 years ago

Branch pushed to git repo; I updated commit sha1. New commits:

c8032e7 pep8 style

dcoudert commented 5 years ago

comment:30

In method effective_resistance:

I prefer this definition:

-        This is the resistance between two equivalent points of a simple connected graph
-        replacing each edge by a 1 ohm resistance.
+        The resistance distance between vertices `i` and `j` of a simple
+        connected graph `G` is defined as the effective resistance between the
+        two vertices on an electrical network constructed from `G` replacing
+        each edge of the graph by a unit (1 ohm) resistor.

-              a similar method giving a matrix full of all effective resistances between all nodes
+              a similar method giving a matrix full of all effective
+              resistances between all nodes

remove the '.' at the end of raise ValueError('the Graph is not a connected graph.')

In method effective_resistance_matrix

add similar definition than above
a ; is missing

-        - ``nonedgesonly`` -- boolean (default: ``True``); if ``True`` assign 
+        - ``nonedgesonly`` -- boolean (default: ``True``) if ``True`` assign

remove . at the end of raise ValueError('the Graph is not a connected graph.')

-        S = d*onesvec.transpose() + onesvec*d.transpose() - 2* M
+        S = d * onesvec.transpose() + onesvec * d.transpose() - 2 * M

In least_effective_resistance

add similar definition than above
may be simpler message

-            raise ValueError('unable to compute least resistance for an empty Graph object')
+            raise ValueError('unable to compute least resistance on empty Graph')

remove . at the end of raise ValueError('the Graph is not a connected graph.')

-            edges = [(verts[i],verts[j]) for i in range(n) for j in range(i+1,n)]
+            edges = [(verts[i], verts[j]) for i in range(n) for j in range(i + 1, n)]

2460b664-5ecd-43fc-9bbe-d0f333762988 commented 5 years ago

comment:31


-        S = d*onesvec.transpose() + onesvec*d.transpose() - 2* M
+        S = d * onesvec.transpose() + onesvec * d.transpose() - 2 * M

But according to pep8

Yes:

x = x*2 - 1

hypot2 = xx + yy

c = (a+b) * (a-b)

No:

x = x * 2 - 1

hypot2 = x x + y y

c = (a + b) * (a - b)

first one seems to be more right

Am I missing something?

7ed8c4ca-6d56-4ae9-953a-41e42b4ed313 commented 5 years ago

Changed commit from c8032e7 to 4db2fda

7ed8c4ca-6d56-4ae9-953a-41e42b4ed313 commented 5 years ago

Branch pushed to git repo; I updated commit sha1. New commits:

4db2fda fixed

dcoudert commented 5 years ago

comment:33

still missing ;

-        - ``nonedgesonly`` -- boolean (default: ``True``) if ``True`` assign 
+        - ``nonedgesonly`` -- boolean (default: ``True``); if ``True`` assign

Remove trailing white spaces. For instance the line above contains a useless space at the end
instead of if n == 0:, we usually use if not n:
please unify the conditions

+        if i not in self:
+            raise ValueError("vertex ({0}) is not a vertex of the graph".format(repr(i)))
+        elif not j in self:

7ed8c4ca-6d56-4ae9-953a-41e42b4ed313 commented 5 years ago

Changed commit from 4db2fda to 9648677

7ed8c4ca-6d56-4ae9-953a-41e42b4ed313 commented 5 years ago

Branch pushed to git repo; I updated commit sha1. New commits:

9648677 fixed

2460b664-5ecd-43fc-9bbe-d0f333762988 commented 5 years ago

comment:35

I couldn't find a suitable way to unify

+        if i not in self:
+            raise ValueError("vertex ({0}) is not a vertex of the graph".format(repr(i)))
+        elif j not in self:

without printing the vertices values. If you have any suggestion I would like to know.

Even in the shortest path between u and v function

        if not self.has_vertex(u):
            raise ValueError("vertex '{}' is not in the (di)graph".format(u))
        if not self.has_vertex(v):
            raise ValueError("vertex '{}' is not in the (di)graph".format(v))

this practice was followed.

dcoudert commented 5 years ago

comment:36

it was just about the use of both forms: if i not in self: and if not j in self:. Now it's better.

dcoudert commented 5 years ago

Changed author from Amanda Francis to Amanda Francis, Rajat Mittal

dcoudert commented 5 years ago

comment:37

For me this patch is not good to go.

2460b664-5ecd-43fc-9bbe-d0f333762988 commented 5 years ago

comment:38

I guess you made a typo above regarding not good to go. (maybe?) :)

dcoudert commented 5 years ago

comment:39

Oups !

This patch is NOW good to go.

vbraun commented 5 years ago

Changed branch from u/gh-rajat1433/24094_effective_resistance_for_graphs to 9648677

sagemath / sage

Effective Resistance for Graphs #24094