Opened 4 years ago
Closed 3 years ago
#24094 closed enhancement (fixed)
Effective Resistance for Graphs
Reported by:  afrancis  Owned by:  ghrajat1433 

Priority:  major  Milestone:  sage8.7 
Component:  graph theory  Keywords:  effective resistance, resitance distance, graphs, link prediction, sd90 
Cc:  Merged in:  
Authors:  Amanda Francis, Rajat Mittal  Reviewers:  David Coudert 
Report Upstream:  N/A  Work issues:  
Branch:  9648677 (Commits, GitHub, GitLab)  Commit:  96486772b7f30f0171434050eb4a50c55a03c941 
Dependencies:  Stopgaps: 
Description
Calculate effective resistances between pairs of nodes in a graph.
Change History (40)
comment:1 Changed 4 years ago by
 Branch set to u/afrancis/effective_resistance_for_graphs
comment:2 Changed 4 years ago by
 Commit set to bc41ea18d585cffbe4311aa8c8a0a2fb80d85136
comment:3 Changed 4 years ago by
 Commit changed from bc41ea18d585cffbe4311aa8c8a0a2fb80d85136 to 054b8ea360a9380b71477daf8778131bde50c15d
Branch pushed to git repo; I updated commit sha1. New commits:
054b8ea  Changed indentation authorship line

comment:4 Changed 4 years ago by
 Status changed from new to needs_review
comment:5 Changed 4 years ago by
 Status changed from needs_review to needs_work
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 2tree 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
withG
since you don't haveG2
 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.
comment:6 Changed 4 years ago by
 Commit changed from 054b8ea360a9380b71477daf8778131bde50c15d to 391271aa1e1e2f506bff13dff21512832ad395bb
Branch pushed to git repo; I updated commit sha1. New commits:
391271a  Documentation changes in response to ticket review

comment:7 Changed 4 years ago by
Thanks for your very helpful comments! I think I made all the presentation changes you submitted
a straight linear 2tree 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 2tree 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!
comment:8 Changed 4 years ago by
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)
comment:9 Changed 4 years ago by
you can also decide that the graph must be connected. I don't know what is best.
comment:10 Changed 3 years ago by
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?
comment:11 Changed 3 years ago by
Yes, you can.
comment:12 Changed 3 years ago by
 Owner changed from (none) to ghrajat1433
comment:13 Changed 3 years ago by
 Branch changed from u/afrancis/effective_resistance_for_graphs to u/ghrajat1433/24094_effective_resistance_for_graphs
 Commit 391271aa1e1e2f506bff13dff21512832ad395bb deleted
 Milestone changed from sage8.1 to sage8.7
comment:14 Changed 3 years ago by
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.
comment:15 followup: ↓ 16 Changed 3 years ago by
Is the method valid for both Graph
and DiGraph
?
comment:16 in reply to: ↑ 15 Changed 3 years ago by
Replying to dcoudert:
Is the method valid for both
Graph
andDiGraph
?
It makes sense for Graph. Thanks for clearing the confusion.
comment:17 Changed 3 years ago by
 Commit set to 8c4714cc21ffdc09682f69139dc0d26d1658f055
Branch pushed to git repo; I updated commit sha1. New commits:
8c4714c  Improved the resistance methods.

comment:18 Changed 3 years ago by
 Status changed from needs_work to needs_review
comment:19 Changed 3 years ago by
 Commit changed from 8c4714cc21ffdc09682f69139dc0d26d1658f055 to e164fa3808c8bb5bd2225dd0085919f9fe486cbc
Branch pushed to git repo; I updated commit sha1. New commits:
e164fa3  fixed bugs for documenting

comment:20 Changed 3 years ago by
 Reviewers set to David Coudert
I have pushed the modified code and passed all the tests and corner cases and also tested the documentation build.
comment:21 Changed 3 years ago by
 Commit changed from e164fa3808c8bb5bd2225dd0085919f9fe486cbc to 37d171b006ad75566ed771c6c07a39cf3346a024
Branch pushed to git repo; I updated commit sha1. New commits:
37d171b  fixed indentation and 80 column format

comment:22 Changed 3 years ago by
 Status changed from needs_review to needs_work
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 (20190310): methods for computing effective resistance + Amanda Francis, Caitlin Lienkaemper, Kate Collins, Rajat Mittal (20190310): + 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 writelabels=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 eitherlist(self)
orself.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
toleast_effective_resistance
comment:23 Changed 3 years ago by
 Commit changed from 37d171b006ad75566ed771c6c07a39cf3346a024 to 0cbfdbd8a38ed67a7e1297da1c6a746c1a70bc33
Branch pushed to git repo; I updated commit sha1. New commits:
0cbfdbd  fixed the coding style bugs

comment:24 Changed 3 years ago by
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)
comment:25 Changed 3 years ago by
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.
comment:26 Changed 3 years ago by
 Commit changed from 0cbfdbd8a38ed67a7e1297da1c6a746c1a70bc33 to 5510cba70ba434f89e223a82e1cc47fc1ccb85ea
Branch pushed to git repo; I updated commit sha1. New commits:
5510cba  minor fix

comment:27 Changed 3 years ago by
This is not needed
 verttoidx = {}
Yes I did that locally but forgot to commit :)
comment:28 Changed 3 years ago by
 Commit changed from 5510cba70ba434f89e223a82e1cc47fc1ccb85ea to c8032e76acb6f6122f7a9b9d9ba05643357532b4
Branch pushed to git repo; I updated commit sha1. New commits:
c8032e7  pep8 style

comment:29 Changed 3 years ago by
 Status changed from needs_work to needs_review
comment:30 Changed 3 years ago by
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 ofraise 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 ofraise 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)]
comment:31 Changed 3 years ago by
 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 = x*x + y*y
c = (a+b) * (ab)
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?
comment:32 Changed 3 years ago by
 Commit changed from c8032e76acb6f6122f7a9b9d9ba05643357532b4 to 4db2fdaeb65d5bf103db4da0b6b63306b728fda9
Branch pushed to git repo; I updated commit sha1. New commits:
4db2fda  fixed

comment:33 Changed 3 years ago by
 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 useif 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:
comment:34 Changed 3 years ago by
 Commit changed from 4db2fdaeb65d5bf103db4da0b6b63306b728fda9 to 96486772b7f30f0171434050eb4a50c55a03c941
Branch pushed to git repo; I updated commit sha1. New commits:
9648677  fixed

comment:35 Changed 3 years ago by
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.
comment:36 Changed 3 years ago by
it was just about the use of both forms: if i not in self:
and if not j in self:
. Now it's better.
comment:37 Changed 3 years ago by
 Status changed from needs_review to positive_review
For me this patch is not good to go.
comment:38 Changed 3 years ago by
I guess you made a typo above regarding not good to go. (maybe?) :)
comment:39 Changed 3 years ago by
Oups !
This patch is NOW good to go.
comment:40 Changed 3 years ago by
 Branch changed from u/ghrajat1433/24094_effective_resistance_for_graphs to 96486772b7f30f0171434050eb4a50c55a03c941
 Resolution set to fixed
 Status changed from positive_review to closed
Branch pushed to git repo; I updated commit sha1. New commits:
Fixed some documentation errors