graph/graph_pg_extra.py

   1
   2 import networkx as nx
   3 import numpy as np
   4 import matplotlib.pyplot as plt
   5
   6
   7 def generate_graph_and_matrices(n, p, plot=False):
   8     """
   9     Generates a random graph and computes the Laplacian, Incidence, and Diagonal matrices.
  10
  11     :param n: Number of nodes
  12     :param p: Probability of edges
  13     :return: Laplacian matrix L, Incidence matrix C, Diagonal matrix D, Weight matrix W
  14     """
  15     # Create a random undirected graph
  16     G = nx.erdos_renyi_graph(n, p)
  17
  18     # Ensure the graph is connected
  19     if not nx.is_connected(G):
  20         raise ValueError("The generated graph is not connected. Please try again with a different probability or number of nodes.")
  21
  22     # Assign weights to the edges
  23     for u, v in G.edges():
  24         G[u][v]['weight'] = 1  # Example: Assigning weight 1 to all edges
  25
  26     # Calculate the Laplacian matrix L
  27     L = nx.laplacian_matrix(G).toarray()
  28
  29     # Calculate the Incidence matrix C
  30     C = -nx.incidence_matrix(G, oriented=True).T.toarray()
  31
  32     # Calculate the Weight matrix W as Identity matrix - Laplacian / (2 * max_degree)
  33     max_degree = max(dict(G.degree(weight='weight')).values())
  34     W = np.eye(n) - L / (2 * max_degree)
  35     D = np.diag([np.sqrt(W[i, j]/2) for i, j in G.edges])
  36     V = np.matmul(D,C)
  37
  38     # Get the neighbors of each node including the node itself
  39     neighbors = {node: set([node]) | set(G.neighbors(node)) for node in G.nodes}
  40
  41     # Get the list of edges connected to each node
  42     edges_connected = {node: set(G.edges(node)) for node in G.nodes}
  43
  44
  45     # Print the number of created edges from the total possible number of edges
  46     created_edges = G.number_of_edges()
  47     # total_possible_edges = n * (n - 1) // 2  # For undirected graph
  48     # print(f"Created {created_edges} edges from {total_possible_edges} possible edges.")
  49
  50
  51   # Initialize a dictionary to store the indices of edges connected to each node
  52     edge_indices = {node: [] for node in G.nodes}
  53
  54     # Assign indices to the edges and store them in the dictionary
  55     for index, (u, v) in enumerate(G.edges()):
  56         if v > u:  # Ensure that j > i
  57             edge_indices[u].append(index)
  58         elif u > v:  # Ensure that j > i
  59             edge_indices[v].append(index)
  60
  61
  62     n = len(G.nodes)
  63     H = np.zeros((n, n))  # Initialize Metropolis matrix
  64
  65     for i in G.nodes:
  66         for j in G.neighbors(i):
  67             H[i, j] = 1 / (1 + max(G.degree[i], G.degree[j]))
  68
  69         # Set diagonal elements
  70         H[i, i] = 1 - np.sum(H[i, :])
  71
  72     neighbors = 1*(W>0)
  73     zr = np.eye(n)-W
  74     zc = np.eye(n)-W
  75
  76     # Plot the graph
  77     if plot:
  78         pos = nx.spring_layout(G)
  79         nx.draw(G, pos, with_labels=True, node_color='skyblue', node_size=2000, edge_color='black', linewidths=1, font_size=15, connectionstyle='arc3,rad=0.1')
  80
  81         # Label the edges with their indices
  82         edge_labels = {(u, v): idx for idx, (u, v) in enumerate(G.edges())}
  83         nx.draw_networkx_edge_labels(G, pos, edge_labels=edge_labels, font_color='red')
  84
  85         plt.show()
  86
  87     return L, C, W, D, V, neighbors, edges_connected, edge_indices, created_edges, H, neighbors, zr, zc
  88
  89
  90
  91
  92 ####  Example usage:
  93 # n = 5  # Number of nodes
  94 # p = 0.8  # Probability of edges
  95 # L, C, W, D, V, neighbors, edges_connected, edge_indices, num_edges, H = generate_graph_and_matrices(n, p, plot=False)
  96
  97 # print("Laplacian Matrix L:\n", L)
  98 # print("Incidence Matrix C:\n", C)
  99 # print("Diagonal Matrix D:\n", D)
 100 # print("Weight Matrix W:\n", W)
 101 # print("Metropolis Matrix H:\n", H)
 102 # print("Neighbors of each node including the node itself:\n", neighbors)
 103 # print("List of edges connected to each node:\n", edges_connected)
 104 # print("Indices of edges connected to each node (j > i):\n", edge_indices)