|
| 1 | +importnumpyasnp |
| 2 | +fromrandomimportrandint |
| 3 | +importnetworkxasnx |
| 4 | +importmatplotlib.pyplotasplt |
| 5 | + |
| 6 | + |
| 7 | +defdraw_graph(relation,color):#to visualize the graph |
| 8 | +G=nx.Graph() |
| 9 | +G.add_edges_from(relation) |
| 10 | +co= [color[i]foriinG.nodes()] |
| 11 | +nx.draw(G,node_size=1000/(len(relation)/10),node_color=co, |
| 12 | +with_labels=True,font_color='white') |
| 13 | +plt.show() |
| 14 | + |
| 15 | +defgenerateRandomGraph(nodes,a,b):#to generate random graph |
| 16 | +L=np.zeros((node,node),dtype=int) |
| 17 | +foriinrange(nodes): |
| 18 | +forjinrange(nodes): |
| 19 | +ifi!=jandL[i][j]==0: |
| 20 | +v=int(np.random.choice(2,1,p=[a,b])) |
| 21 | +ifv==1 : |
| 22 | +L[i][j]=v |
| 23 | +L[j][i]=v |
| 24 | +returnL |
| 25 | +#-------------------------- main program begin ------------------------- |
| 26 | +defisSafe(co,list_color,n): |
| 27 | +foriinrange(node-1): |
| 28 | +ifadj_mtx[n][i]==1andlist_color[i]==co: |
| 29 | +returnFalse |
| 30 | +returnTrue |
| 31 | + |
| 32 | +deffindSolution(list_color,n): |
| 33 | +if(n==node): |
| 34 | +returnTrue |
| 35 | +forcoinrange(1,mc+1): |
| 36 | +if(isSafe(co,list_color,n)): |
| 37 | +list_color[n]=co |
| 38 | +iffindSolution(list_color,n+1): |
| 39 | +returnTrue |
| 40 | +list_color[n]=0 |
| 41 | +returnFalse |
| 42 | + |
| 43 | +defgraphColoring(mtx,mc): |
| 44 | +list_color=np.zeros(node,dtype=int) |
| 45 | +print('>> Maximum color :',mc) |
| 46 | +ifnot(findSolution(list_color,0)): |
| 47 | +print('>> Solution not found') |
| 48 | +returnFalse |
| 49 | +print('>> Solution Found :',list_color) |
| 50 | +print('>> Minimum color needed :',max(list_color)) |
| 51 | +draw_graph(relation,list_color) |
| 52 | + |
| 53 | +#-------------------------- inti program ends ------------------------------ |
| 54 | + |
| 55 | +node=int(input("Generate Random Graph, numebr of nodes : ")) |
| 56 | +#the greater the probability, the more edges |
| 57 | +p=float(input("probabilitas terbentuk koneksi (0.1 - 0.9): "))#auto matically generates an edges with probabilities |
| 58 | +adj_mtx=generateRandomGraph(node,1-p,p) |
| 59 | +print(adj_mtx) |
| 60 | +#find relation |
| 61 | +relation= [] |
| 62 | +foriinrange(len(adj_mtx)): |
| 63 | +forjinrange(len(adj_mtx[i])): |
| 64 | +ifadj_mtx[i][j]==1and (i,j)notinrelationand (j,i)notinrelation: |
| 65 | +relation.append((i,j)) |
| 66 | + |
| 67 | +mc=node#max color |
| 68 | +graphColoring(adj_mtx,mc) |