Opened 4 years ago

Closed 4 years ago

#18260 closed enhancement (fixed)

DiGraph.centrality_betweeenness

Reported by: ncohen Owned by:
Priority: major Milestone: sage-6.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 ncohen

  • Branch set to public/18260
  • Commit set to e55042e6eae922a7ea483fc1a62ef1694071b38d
  • Status changed from new to needs_review

New commits:

e25a95etrac #18260: Small fix for directed graphs
b83d828trac #18260: Move centrality functions from graph.py to generic_graph.py
e55042etrac #18260: A new doctest

comment:2 Changed 4 years ago by git

  • Commit changed from e55042e6eae922a7ea483fc1a62ef1694071b38d to 731445932eb551241b7f4e0ad10a4d533850c1e7

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

7314459trac #18260: Broken link in the doc

comment:3 follow-up: Changed 4 years ago by dcoudert

  • Status changed from needs_review to needs_work

Hello,

some remarks:

David.

comment:4 Changed 4 years ago by git

  • Commit changed from 731445932eb551241b7f4e0ad10a4d533850c1e7 to 4bc0de8139d72fb4a2c19cd3cb0d2f61e1b7bb60

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

4bc0de8trac #18260: Reviewer's comments

comment:5 in reply to: ↑ 3 Changed 4 years ago by ncohen

Hellooooooooooo,

  • I cannot do ctrl-C. 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 file generic_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.

I added this link.

Nathann


New commits:

4bc0de8trac #18260: Reviewer's comments

comment:6 Changed 4 years ago by ncohen

  • Status changed from needs_work to needs_review

comment:7 Changed 4 years ago by dcoudert

  • 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 ncohen

Thanks !

comment:9 Changed 4 years ago by vbraun

  • Branch changed from public/18260 to 4bc0de8139d72fb4a2c19cd3cb0d2f61e1b7bb60
  • Resolution set to fixed
  • Status changed from positive_review to closed
Note: See TracTickets for help on using tickets.