Opened 5 years ago

Closed 5 years ago

#18335 closed defect (fixed)

Compute the degree of a vertex without using networkX

Reported by: ncohen Owned by:
Priority: major Milestone: sage-6.7
Component: graph theory Keywords:
Cc: Merged in:
Authors: Nathann Cohen Reviewers: Vincent Delecroix
Report Upstream: N/A Work issues:
Branch: 073e7c5 (Commits) Commit: 073e7c5518d38e74a2d47a2e7cbaabfaf0a23ce5
Dependencies: Stopgaps:

Description

Err. There is a function in Sage which is called .centrality_degree, whose aim is more or less to compute the degree.

Right now, it is done by building a NetworkX copy of the graph, then asking NetworkX to give us the degree (divided by n-1).

Turns out that we can do better.

Change History (13)

comment:1 Changed 5 years ago by ncohen

  • Branch set to public/18335
  • Commit set to a9f34ad605c82f44bb72143a8d45ee1aaf70809f
  • Status changed from new to needs_review

New commits:

a9f34adtrac #18335: Compute the degree of a vertex without using networkX

comment:2 Changed 5 years ago by vdelecroix

What is n?

comment:3 Changed 5 years ago by ncohen

The number of vertices

comment:4 Changed 5 years ago by vdelecroix

Where is it written?

comment:5 Changed 5 years ago by vdelecroix

You could also add SEEALSO between all the *centrality* methods.

comment:6 Changed 5 years ago by ncohen

In Graph theory, n is the number of vertices and m is the number of edges. No exceptions :-P

comment:7 Changed 5 years ago by vdelecroix

Graph
    ...
    -  ``vertex_labels`` - only for implementation == 'c_graph'.
       Whether to allow any object as a vertex (slower), or
       only the integers 0, ..., n-1, where n is the number of vertices.
    ...

def is_overfull(self):
   ...
    A graph `G` on `n` vertices and `m` edges is said to
    be overfull if:
    ...

def clique_polynomial(self):
    ...
    This is the polynomial where the coefficient of `t^n` is the number of
    cliques in the graph with `n` vertices. The constant term of the
    clique polynomial is always taken to be one.
    ...

So even if it is standard, everywhere it is used it seems that there is precision about it. And I like it.

comment:8 Changed 5 years ago by git

  • Commit changed from a9f34ad605c82f44bb72143a8d45ee1aaf70809f to 073e7c5518d38e74a2d47a2e7cbaabfaf0a23ce5

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

073e7c5trac #18335: Review

comment:9 Changed 5 years ago by ncohen

I would like people to have the same kind of strict expectations when they review my patches and when others write theirs. It takes weeks to add a stopgap somewhere but everything gets much more serious when I don't define 'n' in a docstring.

comment:10 Changed 5 years ago by vdelecroix

People always discuss useless things. And when important or technical decisions come, you are alone! That's life.

comment:11 Changed 5 years ago by vdelecroix

  • Reviewers set to Vincent Delecroix
  • Status changed from needs_review to positive_review

comment:12 Changed 5 years ago by ncohen

Thanks !

comment:13 Changed 5 years ago by vbraun

  • Branch changed from public/18335 to 073e7c5518d38e74a2d47a2e7cbaabfaf0a23ce5
  • Resolution set to fixed
  • Status changed from positive_review to closed
Note: See TracTickets for help on using tickets.