Function iarandGraph

Synopse

This function generates a random oriented or non-oriented graph and returns its adjacency matrix.

  • graph = iarandGraph(V = 10, edges_density= 0.5,weighted = 'no', weightrange = array([0,255]))

    • Output

      • graph: Numpy array containing the adjacency matrix of the graph. The convention used is graph[i,j] = 'inf' means theres is no edges between i and j.
    • Input

      • V: Number of vertices;
      • density: Percentual of the maximum number of edges/arcs of the graph;
      • weighted: 'no' means there are no weights in the graph edges, 'yes' means there are.
      • weightrange: If weighted = 'yes', then weight range contains the maxvalue and the minvalues for the weights of the edges.;
      • type: If type = 'graph', then the result is a non-oriented graph. If type = 'digraph', then the result is a oriented graph.
      • gseed: Defines the pseudo random sequence.

Description

This function generates a random non-oriented graph and returns its adjacency matrix. The function doesn't produce self-incident edges.

Function Code

 1 from numpy import*
 2 from numpy.random import rand, seed
 3 from time import time
 4 
 5 def iarandGraph(V  = 10, density= 0.5,weighted = 'no',weightrange = array([0,255]),type = 'graph',gseed=time()):
 6 
 7    seed([gseed])
 8 
 9    temp = rand(V, V)
10 
11    if (type == 'graph'):
12 
13       temp = triu(temp)
14       G = triu(ones((V,V)))
15 
16       temp = (temp<=density)
17       G[~temp] = float('inf')
18 
19       if weighted != 'no':
20          temp2 = (rand(V, V))  # matriz aleatória que será usada para gerar os peso aleatórios
21          temp2  = (weightrange[1]-weightrange[0])*temp2 + weightrange[0]
22          G[temp] = temp2[temp]
23 
24       G = triu(G)
25       G = (G+G.transpose())
26       i = range(V)
27       G[i,i] =  G[i,i]/2
28       G[range(V),range(V)] = float('inf')
29 
30    if (type == 'digraph'):
31 
32       G = ones((V,V))
33       temp = (temp<=density)
34       G[~temp] = float('inf')
35 
36       if weighted != 'no':
37          temp2 = rand(V, V)  # matriz aleatória
38          temp2 = (weightrange[1]-weightrange[0])*temp2 + weightrange[0]
39          G[temp] = temp2[temp]
40 
41 
42    return G

Examples

These examples produces a non-oriented graph (example 1) and a oriented graph(example 2) and display them using GraphViz.

Example 1 - Non-oriented Graph

1 from iaOPF import iarandGraph
2 from courseIA368Q1S2012.wen_lib import adj2Graph
3 from numpy import*
4 
5 
6 graph1 = iarandGraph(5, 0.6,'yes')
7 print('\n Random graph generated: \n "%s"' %graph1)
8 mmgraphviz(adj2Graph(graph1),'Weighted random non-oriented graph with V = 5')
Random graph generated: 
 "[[          Inf  115.47550971  196.88308959  172.56537626  212.34747129]
 [ 115.47550971           Inf   30.04295729           Inf   26.31064988]
 [ 196.88308959   30.04295729           Inf           Inf           Inf]
 [ 172.56537626           Inf           Inf           Inf  139.59008445]
 [ 212.34747129   26.31064988           Inf  139.59008445           Inf]]"
/media/_xsb/iaOPF/rob_iarandgraph/GRVIZ85667_001.png

Weighted random non-oriented graph with V = 5

Example 2- Oriented Graph

1 graph2 = iarandGraph(5, 0.6,'yes',type = 'digraph')
2 print('\n Random graph generated: \n %s' %graph2)
3 mmgraphviz(adj2Graph(graph2),'Weighted random oriented graph with V = 5')
Random graph generated: 
 [[  60.32695834  115.47550971  196.88308959  172.56537626  212.34747129]
 [          Inf           Inf   30.04295729           Inf   26.31064988]
 [ 251.44718154  138.29464665           Inf           Inf           Inf]
 [  82.86035238           Inf   88.47022914  227.93967185  139.59008445]
 [ 253.11430076           Inf   86.39516624           Inf   70.13428239]]
/media/_xsb/iaOPF/rob_iarandgraph/GRVIZ85667_002.png

Weighted random oriented graph with V = 5