|
| 1 | +""" |
| 2 | +* Author: Manuel Di Lullo (https://github.com/manueldilullo) |
| 3 | +* Description: Random graphs generator. |
| 4 | + Uses graphs represented with an adjacency list. |
| 5 | +
|
| 6 | +URL: https://en.wikipedia.org/wiki/Random_graph |
| 7 | +""" |
| 8 | + |
| 9 | +import random |
| 10 | + |
| 11 | + |
| 12 | +def random_graph( |
| 13 | + vertices_number: int, probability: float, directed: bool = False |
| 14 | +) -> dict: |
| 15 | + """ |
| 16 | + Generate a random graph |
| 17 | + @input: vertices_number (number of vertices), |
| 18 | + probability (probability that a generic edge (u,v) exists), |
| 19 | + directed (if True: graph will be a directed graph, |
| 20 | + otherwise it will be an undirected graph) |
| 21 | + @examples: |
| 22 | + >>> random.seed(1) |
| 23 | + >>> random_graph(4, 0.5) |
| 24 | + {0: [1], 1: [0, 2, 3], 2: [1, 3], 3: [1, 2]} |
| 25 | + >>> random.seed(1) |
| 26 | + >>> random_graph(4, 0.5, True) |
| 27 | + {0: [1], 1: [2, 3], 2: [3], 3: []} |
| 28 | + """ |
| 29 | + graph = {i: [] for i in range(vertices_number)} |
| 30 | + |
| 31 | + # if probability is greater or equal than 1, then generate a complete graph |
| 32 | + if probability >= 1: |
| 33 | + return complete_graph(vertices_number) |
| 34 | + # if probability is lower or equal than 0, then return a graph without edges |
| 35 | + if probability <= 0: |
| 36 | + return graph |
| 37 | + |
| 38 | + # for each couple of nodes, add an edge from u to v |
| 39 | + # if the number randomly generated is greater than probability probability |
| 40 | + for i in range(vertices_number): |
| 41 | + for j in range(i + 1, vertices_number): |
| 42 | + if random.random() < probability: |
| 43 | + graph[i].append(j) |
| 44 | + if not directed: |
| 45 | + # if the graph is undirected, add an edge in from j to i, either |
| 46 | + graph[j].append(i) |
| 47 | + return graph |
| 48 | + |
| 49 | + |
| 50 | +def complete_graph(vertices_number: int) -> dict: |
| 51 | + """ |
| 52 | + Generate a complete graph with vertices_number vertices. |
| 53 | + @input: vertices_number (number of vertices), |
| 54 | + directed (False if the graph is undirected, True otherwise) |
| 55 | + @example: |
| 56 | + >>> print(complete_graph(3)) |
| 57 | + {0: [1, 2], 1: [0, 2], 2: [0, 1]} |
| 58 | + """ |
| 59 | + return { |
| 60 | + i: [j for j in range(vertices_number) if i != j] for i in range(vertices_number) |
| 61 | + } |
| 62 | + |
| 63 | + |
| 64 | +if __name__ == "__main__": |
| 65 | + import doctest |
| 66 | + |
| 67 | + doctest.testmod() |
0 commit comments