How to make a graph from the produced in python-CodePudding

I have this code, it produces a random matrix of 1s and 0s. I want to create a graph from this matrix where the 1s in the matrix represent a node and each node has a maximum of 3 edges. How can i implement this, please help?

import numpy as np
from random import sample

N = int(input("Enter the number of nodes:"))
my_matrix = np.zeros((N,N), dtype='int8')

CodePudding user response：

If you matrix is just random, probably, you don't need it. Instead, you can create graph from list of edges

import networkx as nx
from random import sample
import numpy as np
from numpy.random import randint


n = 7  # number of nodes in graph
max_connections = int(input("Enter max connections per node:"))  # input: 3

nodes = np.arange(n)
# create graph based on list of edges [(0, 1), (0, 4), ...]
gr = nx.Graph([
    #     for each node      select <= 'max_connections' nodes as connections
    (i, j) for i in range(n) for j in sample(nodes[nodes != i].tolist(), randint(1, max_connections 1))
])

# check number of connections
for n in gr.nodes():
    nei = list(gr.neighbors(n))
    while len(nei) > max_connections:
        gr.remove_edge(n, random.choice(nei))
        nei = list(gr.neighbors(n))

nx.draw_networkx(gr, with_labels=True, node_color='#7d99f5')

Graph:

And you can get adjacency matrix using nx.adjacency_matrix()

nx.adjacency_matrix(gr, nodelist=sorted(gr.nodes())).todense()

matrix([[0, 1, 1, 0, 1, 0, 0],
        [1, 0, 0, 0, 0, 1, 1],
        [1, 0, 0, 1, 0, 1, 0],
        [0, 0, 1, 0, 0, 0, 1],
        [1, 0, 0, 0, 0, 1, 1],
        [0, 1, 1, 0, 1, 0, 0],
        [0, 1, 0, 1, 1, 0, 0]])

CodePudding user response：

complete update :

if bi-directional is not important, then the adjM is tri-diagonal
if not more than 3 edges per node are allowed, then each row and each column of adjM has 3 or less "1"
the code follows the tri-diagnoal structure required
step 1: fill in 3 edges starting from each node (follow the rows of adjM)
step 2: but then some nodes may receive more than 3 edges, so remove some of them until there are 3 left only (follow the columnes of adjM)
step 3: remove the self-adjacencies
yes, it might happen that the graph will not be connected due to the random processes. Then repeat the runs till you are happy with.

The structure of adjM looks reasonable now at least. The graph however presents at node 12 more connections than can be seen in the adjM matrix. (so there is still an improvement necessary....)

import numpy as np
import networkx as nx
import matplotlib.pyplot as plt

Nnodes = 16
Nedges = 3

#---- 0. to initialize: generate a random adjacency matrix 
rng = np.random.default_rng()
adjM = rng.integers(1, size=(Nnodes,Nnodes))  # random adjacency matrix / with upper=1 it is a zero matrix


#---- 1. for eaach node generate randomly Nedges edges ("sending" connections alongs the rows of adjM)
for node in range(Nnodes):
    dd = Nnodes-node
    rand_ind = np.random.choice(np.arange(node,Nnodes), size=min(dd,Nedges), replace=False, p=None) # generate randomly indexes
                                                                                       # you might use replace=False too with different results
    adjM[node, rand_ind] = 1   # insert the connections        

#---- 2. for each node eliminate randomly edges that are more than Nedges ("receiving" connections alongs the columns of adjM)
for node in range(Nnodes):          # run through the columns of adjM
    dd = Nnodes-node
    a = adjM[:,node]                # select a column = receiving connections
    jnz = np.array(a.nonzero())     # indices of the non-zero elements
    Nnz = jnz.shape[1]              # number of  non-zero elements
    
    if Nnz > Nedges:                # ...then randomly select Nedges edges only 
        jchoice = np.random.choice(jnz.ravel(),  size=min(Nedges,Nedges), replace=False, p=None)
        #print('            jchoice', jchoice)
        adjM[:,node] = 0
        adjM[jchoice, node] = 1           
        
 #---- 3. remove self-adjacency
jDiag = np.arange(Nnodes)
adjM[jDiag, jDiag] = 0         # set the diagonals to zero
print(adjM) 
        
#---- grafics
plt.spy(adjM, precision=0, marker=None, markersize=12, aspect='equal', origin='upper')
plt.show()
gr = nx.from_numpy_matrix(adjM)
nx.draw_networkx(gr, with_labels=True, node_size=400, node_color='#7d99f5',  edge_color='orange', width=2, font_weight='bold')
plt.show()

CodePudding user response：

Addition to your code (function check_graph () fix two problems we have discussed). Also, according your way of generation of adjacency matrix, you won't face second problem, so you can comment out second section in function.

def check_graph(graph, max_conn):
    # 1) remove self loops
    graph.remove_edges_from(nx.selfloop_edges(graph))

    # 2) remove random edge(s) if limit of edges per node have been exceeded
    for i in graph.nodes():
        # list of connections - nodes that are connected to the selected node 'i'
        nei = list(graph.neighbors(i))
        if len(nei) > max_conn:
            graph.remove_edges_from(
                # like if len(nei) - max_conn = 5 - 4 = 1, then one random edge will be selected
                np.random.choice(nei, size=(len(nei)-max_conn))
            )

# <-- insert your code here -->  N = 20

gr = nx.from_numpy_matrix(my_matrix)
check_graph(gr, max_conn=N)
nx.draw_networkx(gr, with_labels=True, node_color='#7d99f5')

Result looks a bit strange for me, but I don't know purposes of your graph, probably, it's okay.