r"""Returns the density of a graph. The density for undirected graphs is .. math:: d = \frac{2m}{n(n-1)}, and for directed graphs is .. math:: d = \frac{m}{n(n-1)}, where `n` is the number of nodes and `m` is the number of edges in `G`. Notes -----
(G)
| 413 | |
| 414 | @hybrid("cpp_density") |
| 415 | def density(G): |
| 416 | r"""Returns the density of a graph. |
| 417 | |
| 418 | The density for undirected graphs is |
| 419 | |
| 420 | .. math:: |
| 421 | |
| 422 | d = \frac{2m}{n(n-1)}, |
| 423 | |
| 424 | and for directed graphs is |
| 425 | |
| 426 | .. math:: |
| 427 | |
| 428 | d = \frac{m}{n(n-1)}, |
| 429 | |
| 430 | where `n` is the number of nodes and `m` is the number of edges in `G`. |
| 431 | |
| 432 | Notes |
| 433 | ----- |
| 434 | The density is 0 for a graph without edges and 1 for a complete graph. |
| 435 | The density of multigraphs can be higher than 1. |
| 436 | |
| 437 | Self loops are counted in the total number of edges so graphs with self |
| 438 | loops can have density higher than 1. |
| 439 | """ |
| 440 | n = G.number_of_nodes() |
| 441 | m = G.number_of_edges() |
| 442 | if m == 0 or n <= 1: |
| 443 | return 0 |
| 444 | d = m / (n * (n - 1)) |
| 445 | if not G.is_directed(): |
| 446 | d *= 2 |
| 447 | return d |
nothing calls this directly
no test coverage detected