Last active
November 3, 2020 14:15
-
-
Save detkov/fc41eec7362354cb04760ed9b033075f to your computer and use it in GitHub Desktop.
These functions allow you to generate random undirected (un)weighted graph without loops with specified number of vertices (nodes) and edges. Also it has a function converting adjacency matrix to adjacency list and adjacency list to edges list. Under the hood it is optimized with the usage of numpy arrays.
This file contains bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
import networkx as nx | |
import numpy as np | |
import matplotlib.pyplot as plt | |
from typing import List, Tuple, Union | |
def create_random_adjacency_matrix(V: int, E: int, weighted: bool = False, | |
min_: float = 1., max_: float = 10.) -> np.ndarray: | |
"""Generates undirected (un)weighted graph without loops (connectivity is not guaranteed). | |
Generation consists of creating upper triangular matrix (with zeros on main diagonal) and mirroring it. | |
Args: | |
V (int): Number of vertices (nodes). | |
E (int): Number of edges between vertices. | |
weighted (bool, optional): Whether graph should be weighted ot not. Defaults to False. | |
min_ (float, optional): Minimal random weight. Defaults to 1.0. | |
max_ (float, optional): Maximal random weight. Defaults to 10.0. | |
Returns: | |
np.ndarray: Random graph. | |
""" | |
up_tr_mat_n = int((V - 1) * V / 2) | |
assert up_tr_mat_n >= E, f'Can\'t choose E={E} random edges from {up_tr_mat_n} possible. Lower E value.' | |
up_tr_mat_list = np.zeros(up_tr_mat_n) | |
adjacency_indices = np.random.choice(range(up_tr_mat_n), E, replace=False) | |
up_tr_mat_list[adjacency_indices] = 1 if not weighted else np.random.randint(min_, max_, E) | |
adjacency_matrix = np.zeros((V, V)) | |
adjacency_matrix[np.triu_indices(V, k=1)] = up_tr_mat_list | |
adjacency_matrix += np.rot90(np.fliplr(adjacency_matrix)) | |
return adjacency_matrix | |
def adjacency_matrix_to_list(adjacency_matrix: Union[List[List[int]], np.ndarray], | |
weighted: bool = False) -> Union[List[List[int]], | |
List[List[Tuple[int, float]]]]: | |
"""Generates adjacency list from adjacency matrix, can be weighted or unweighted. | |
Args: | |
adjacency_matrix (Union[List[List[int]], np.ndarray]): Adjacency matrix. | |
weighted (bool, optional): Whether graph is weighted ot not. Defaults to False. | |
Returns: | |
Union[List[List[int]], List[List[Tuple[int, float]]]]: Adjacency list. | |
""" | |
return [[i if not weighted else (i, el) | |
for i, el in enumerate(row) if el != 0] | |
for row in adjacency_matrix] | |
def adjacency_list_to_edges(adjacency_list: List[List[int]], | |
weighted: bool = False) -> Union[List[Tuple[int, int]], | |
List[Tuple[int, int, float]]]: | |
"""Generates sorted edges list from adjacency list. | |
Each edge is presented with tuple: (FROM, TO[, WEIGHT]). | |
Args: | |
adjacency_list (List[List[int]]): Adjacency list. | |
weighted (bool, optional): Whether graph is weighted ot not. Defaults to False. | |
Returns: | |
Union[List[Tuple[int, int]], List[Tuple[int, int, float]]]: Edges list. | |
""" | |
if weighted: | |
return [(i, *neighbor) for i, neighbors_list in enumerate(adjacency_list) | |
for neighbor in neighbors_list] | |
else: | |
return [(i, neighbor) for i, neighbors_list in enumerate(adjacency_list) | |
for neighbor in neighbors_list] | |
if __name__ == "__main__": | |
# Generate graph | |
V, E, weighted = 6, 10, True | |
adjacency_matrix = create_random_adjacency_matrix(V, E, weighted) | |
print(f'Randomly generated adjacency matrix with {V} nodes and {E} edges: \n{adjacency_matrix}\n') | |
adjacency_list = adjacency_matrix_to_list(adjacency_matrix, weighted) | |
print(f'Adjacency list from afore generated matrix: {adjacency_list}\n') | |
edges_list = adjacency_list_to_edges(adjacency_list, weighted) | |
print(f'Edges list from afore generated matrix: {edges_list}') | |
# Plot obtained graph | |
G = nx.Graph(adjacency_matrix) | |
layout = nx.spring_layout(G) | |
nx.draw(G, layout, with_labels=True, node_color="g", edge_color="k", font_color='w', font_size=12) | |
if weighted: | |
labels = nx.get_edge_attributes(G, "weight") | |
nx.draw_networkx_edge_labels(G, pos=layout, edge_labels=labels) | |
plt.show() |
Sign up for free
to join this conversation on GitHub.
Already have an account?
Sign in to comment