Opened 4 years ago
Closed 4 years ago
#18260 closed enhancement (fixed)
DiGraph.centrality_betweeenness
Reported by:  ncohen  Owned by:  

Priority:  major  Milestone:  sage6.7 
Component:  graph theory  Keywords:  
Cc:  dcoudert, borassi  Merged in:  
Authors:  Nathann Cohen  Reviewers:  David Coudert 
Report Upstream:  N/A  Work issues:  
Branch:  4bc0de8 (Commits)  Commit:  4bc0de8139d72fb4a2c19cd3cb0d2f61e1b7bb60 
Dependencies:  Stopgaps: 
Description
Right now centrality_betweenness is only available for graphs even though both implementations also support digraphs.
This branch moves it where it belongs, fixes a small bug and adds a test.
The temporary digraph is initialized to be the *reverse* of the first, as it is meant to associate to each vertex a list of its predecessors. Thus, each vertex v must be able to store "indegree(v)" possible vertices.
Change History (9)
comment:1 Changed 4 years ago by
 Branch set to public/18260
 Commit set to e55042e6eae922a7ea483fc1a62ef1694071b38d
 Status changed from new to needs_review
comment:2 Changed 4 years ago by
 Commit changed from e55042e6eae922a7ea483fc1a62ef1694071b38d to 731445932eb551241b7f4e0ad10a4d533850c1e7
Branch pushed to git repo; I updated commit sha1. New commits:
7314459  trac #18260: Broken link in the doc

comment:3 followup: ↓ 5 Changed 4 years ago by
 Status changed from needs_review to needs_work
Hello,
some remarks:
 I cannot do ctrlC. It would be useful for large graphs.
 In file
centrality.pyx
you cite Brandes01 and in filegeneric_graph.py
you cite Brandes2003. You could certainly unify.  In fact, I'm unable to find Brandes2003 on Brandes web page: http://www.inf.unikonstanz.de/~brandes/publications/ However, a pdf version of Brandes 2001 is available from Brandes web page: http://www.inf.unikonstanz.de/algo/publications/bfabc01.pdf
David.
comment:4 Changed 4 years ago by
 Commit changed from 731445932eb551241b7f4e0ad10a4d533850c1e7 to 4bc0de8139d72fb4a2c19cd3cb0d2f61e1b7bb60
Branch pushed to git repo; I updated commit sha1. New commits:
4bc0de8  trac #18260: Reviewer's comments

comment:5 in reply to: ↑ 3 Changed 4 years ago by
Hellooooooooooo,
 I cannot do ctrlC. It would be useful for large graphs.
This will be done in another ticket. This one is only about making this computation available for digraphs.
 In file
centrality.pyx
you cite Brandes01 and in filegeneric_graph.py
you cite Brandes2003. You could certainly unify.
Well, I did not write the first docstring, only the second :P
I 'unified' it by removing the first reference.
 In fact, I'm unable to find Brandes2003 on Brandes web page: http://www.inf.unikonstanz.de/~brandes/publications/ However, a pdf version of Brandes 2001 is available from Brandes web page: http://www.inf.unikonstanz.de/algo/publications/bfabc01.pdf
I added this link.
Nathann
New commits:
4bc0de8  trac #18260: Reviewer's comments

comment:6 Changed 4 years ago by
 Status changed from needs_work to needs_review
comment:7 Changed 4 years ago by
 Reviewers set to David Coudert
 Status changed from needs_review to positive_review
For me the patch is good to go.
comment:8 Changed 4 years ago by
Thanks !
comment:9 Changed 4 years ago by
 Branch changed from public/18260 to 4bc0de8139d72fb4a2c19cd3cb0d2f61e1b7bb60
 Resolution set to fixed
 Status changed from positive_review to closed
New commits:
trac #18260: Small fix for directed graphs
trac #18260: Move centrality functions from graph.py to generic_graph.py
trac #18260: A new doctest