advanced algorithm (python)

{ "cells": [ { "cell_type": "code", "execution_count": 10, "metadata": {}, "outputs": [ { "name": "stdout", "output_type": "stream", "text": [ "number of nodes in the graph: 800\n", "kindky enter a value for p: 1\n", "kindky enter a value for p: 1\n", "kindky enter a value for p: 1\n", "kindky enter a value for p: 1\n", "kindly enter a value for r: 0.5\n", "kindly enter a value for r: 0.5\n", "kindly enter a value for r: 0.5\n", "kindly enter a value for r: 0.5\n" ] }, { "ename": "NameError", "evalue": "name 'random_network' is not defined", "output_type": "error", "traceback": [ "\u001b[1;31m---------------------------------------------------------------------------\u001b[0m", "\u001b[1;31mNameError\u001b[0m Traceback (most recent call last)", "\u001b[1;32m<ipython-input-10-d4ab3a40b823>\u001b[0m in \u001b[0;36m<module>\u001b[1;34m\u001b[0m\n\u001b[0;32m 273\u001b[0m \u001b[0mplt\u001b[0m\u001b[1;33m.\u001b[0m\u001b[0mshow\u001b[0m\u001b[1;33m(\u001b[0m\u001b[1;33m)\u001b[0m\u001b[1;33m\u001b[0m\u001b[1;33m\u001b[0m\u001b[0m\n\u001b[0;32m 274\u001b[0m \u001b[1;33m\u001b[0m\u001b[0m\n\u001b[1;32m--> 275\u001b[1;33m \u001b[0mmain\u001b[0m\u001b[1;33m(\u001b[0m\u001b[1;33m)\u001b[0m\u001b[1;33m\u001b[0m\u001b[1;33m\u001b[0m\u001b[0m\n\u001b[0m\u001b[0;32m 276\u001b[0m \u001b[1;33m\u001b[0m\u001b[0m\n\u001b[0;32m 277\u001b[0m \u001b[1;33m\u001b[0m\u001b[0m\n", "\u001b[1;32m<ipython-input-10-d4ab3a40b823>\u001b[0m in \u001b[0;36mmain\u001b[1;34m()\u001b[0m\n\u001b[0;32m 161\u001b[0m \u001b[1;33m\u001b[0m\u001b[0m\n\u001b[0;32m 162\u001b[0m \u001b[1;33m\u001b[0m\u001b[0m\n\u001b[1;32m--> 163\u001b[1;33m \u001b[0mg\u001b[0m\u001b[1;33m=\u001b[0m\u001b[0mrandom_network\u001b[0m\u001b[1;33m(\u001b[0m\u001b[1;33m)\u001b[0m\u001b[1;33m\u001b[0m\u001b[1;33m\u001b[0m\u001b[0m\n\u001b[0m\u001b[0;32m 164\u001b[0m \u001b[1;32mfor\u001b[0m \u001b[0my\u001b[0m \u001b[1;32min\u001b[0m \u001b[0mrange\u001b[0m \u001b[1;33m(\u001b[0m\u001b[1;36m4\u001b[0m\u001b[1;33m)\u001b[0m\u001b[1;33m:\u001b[0m\u001b[1;33m\u001b[0m\u001b[1;33m\u001b[0m\u001b[0m\n\u001b[0;32m 165\u001b[0m \u001b[0mred_nodes\u001b[0m\u001b[1;33m=\u001b[0m\u001b[1;33m[\u001b[0m\u001b[0my\u001b[0m\u001b[1;33m,\u001b[0m\u001b[1;34m'r'\u001b[0m\u001b[1;33m]\u001b[0m\u001b[1;33m\u001b[0m\u001b[1;33m\u001b[0m\u001b[0m\n", "\u001b[1;31mNameError\u001b[0m: name 'random_network' is not defined" ] } ], "source": [ "import random\n", "import math\n", "import numpy as np\n", "import matplotlib.pyplot as plt\n", "from collections import Counter\n", "import matplotlib\n", "\n", " \n", " \n", "class graph:\n", " \n", " def vertex_count(graph): \n", " vertex = []\n", " for x in graph.keys():\n", " vertex.append(x)\n", " return len(vertex)\n", "\n", " def vertices(graph): \n", " vertices = []\n", " for x in graph.keys():\n", " vertices.append(x)\n", " return list(graph.keys())\n", "\n", " def edges_count(graph):\n", " edges = []\n", " count = 0\n", " for k,v in graph.items():\n", " if k not in edges:\n", " edges.append(k)\n", " for i in v:\n", " if i not in edges:\n", " count += 1\n", " return count\n", "\n", " def edges(graph):\n", " edges = []\n", " for k,v in graph.items():\n", " for i in v:\n", " edges.append((k,i))\n", " return edges\n", " \n", " def get_vertex(x,graph):\n", " for k in graph.key():\n", " if k[0]==x:\n", " return x\n", " return 'None'\n", " \n", "\n", "\n", " def get_edge(x,y,graph):\n", " for k,v in graph.items():\n", " if x == k and y in v:\n", " return x,y\n", " return \"None\"\n", "\n", " def degree(x,graph):\n", " for k,v in graph.items():\n", " if x == k:\n", " return len(v)\n", "\n", " def incident_edges(x, graph):\n", " for k,v in graph.items():\n", " if x == k:\n", " return graph[v]\n", "\n", " def insert_vertex(x,graph):\n", " if x not in graph.keys():\n", " graph[x] = {}\n", " return graph\n", "\n", " def insert_edge(u,v,graph):\n", " if u in graph.keys():\n", " if v not in graph[u].values():\n", " graph[u]=[v]\n", " for q in graph[u]:\n", " if q==v:\n", " graph[v]=[u]\n", " return graph\n", " else:\n", " return 'does not exist'\n", "\n", " def remove_vertex(v,graph):\n", " del graph[v]\n", " return graph\n", "\n", " def remove_edge(u,v,graph):\n", " test = 0\n", " if u in graph.keys():\n", " for q in graph[u]:\n", " if q==v:\n", " graph[u].remove(q)\n", " return graph\n", " \n", " def binomial_degree_distribution( p, k,graph):\n", " for N in graph.items():\n", " \n", " numerator = math.factorial(N-1)\n", " denominator = math.factorial(k)*math.factorial((N-1-k))\n", " x = numerator/denominator\n", " pk = x*(pow(p, k))*(pow(1-p, N-1-k))\n", " return pk\n", " \n", " \n", " def degree_distribution(graph,initial_nodes):\n", " dd=[]\n", " for i in range (initial_nodes):\n", " dd[i]=0\n", " for j in graph:\n", " x=len(graph[j])\n", " dd[x]=dd[x]+1\n", " \n", " degrees=[]\n", " for i in dd:\n", " degree[i]=(dd[i]/inital_nodes)\n", " return degrees\n", " \n", " def random_network():\n", " g = graph()\n", " \n", " \n", " for i in range (4):\n", " g.insert_vetrex(i,'r')\n", " g.insert_vertex(4+i,'b')\n", " return g\n", "\n", " \n", " \n", " \n", " \n", "def main():\n", " matplotlib.rcParams.update({'figure.autolayout': True})\n", " N=int(input('number of nodes in the graph: '))\n", " m = random.randint(0,4)\n", " k=0\n", " kk=0\n", " p_list=list()\n", " r_list = [] \n", " for i in range(4):\n", " p = float(input(\"kindky enter a value for p: \"))\n", " p_list.append(p)\n", "\n", " for i in range(4):\n", " r = float(input(\"kindly enter a value for r: \"))\n", " r_list.append(r)\n", "\n", " for p in p_list:\n", " j =0\n", " q = 1-p\n", " \n", " for r in r_list:\n", " if k>0 and j>0:\n", " break\n", " \n", " \n", "\n", " \n", "\n", " the_probabilite_nodes_of_same_color=int(round(m*p))\n", " the_probabilite_nodes_of_different_color=int(round(m-the_probabilite_nodes_of_same_color))\n", " \n", " \n", " \n", " g= random_network()\n", " for y in range (4):\n", " red_nodes=[y,'r']\n", " for y in range(4,8):\n", " blue_nodes=[y,'b']\n", " \n", " for u in g.vertices():\n", " for v in g.vertices():\n", " r_u=random_uniform(0.0,1.0)\n", " if ((u!=v) and u[1]==v[1]):\n", " if (r_u < p or p==1.0):\n", " g.insert_edge(u,v)\n", " else:\n", " if ((r_u > p or q==1.0) and (u!=v)):\n", " g.insert_edge(u,v)\n", " \n", " \n", " for i in range(8,N):\n", " \n", " red_size = list()\n", " blue_size = list()\n", " degrees = list()\n", " k_nodes_of_same_color = int(round(p*m))\n", " k_nodes_of_different_color = m-k_nodes_of_same_color\n", " \n", " \n", " for vertex in g.vertices():\n", " degree = g.degree(vertex)\n", " degrees.append(degree)\n", " \n", " for h in range(g.vertex_count()):\n", " t = g.get_vertex(h)\n", " if t[1] == 'r':\n", " red_size.append(degrees[h])\n", " total_of_red_degrees += degrees[h]\n", " else:\n", " blue_size.append(degrees[h])\n", " total_of_blue_degrees += degrees[h]\n", " \n", " sum_r_s = sum( red_size)\n", " sum_b_s = sum( blue_size)\n", " for x in red_nodes[0]:\n", " vec_r = x[0] \n", " for x in blue_nodes[0]:\n", " vec_b = x[0] \n", " for f in red_size ():\n", " P_r = [f/ sum_r_s]\n", " for f in blue_size ():\n", " P_b = [f/ sum_b_s] \n", " \n", " \n", " rand_uf=random_uniform(0.0,1.0)\n", " the_preferential_attachement_of_red_nodes=[]\n", " the_preferential_attachement_of_blue_nodes=[]\n", " generated_node = ()\n", " if ((rand_uf >=r) and len(red_nodes)<int(round(N*r))):\n", " generated_node = (i,'r')\n", " g.insert_vertex(generated_node)\n", " \n", " \n", " choices=np.random.choice(vec_r,size=k_nodes_of_different_color,replace=False, p=P_r)\n", " \n", " \n", " the_preferential_attachement_of_red_nodes=[x for x in red_nodes if x[0] in choices]\n", " \n", " choices=np.random.choice(vec_b,size=k_nodes_of_different_color,replace=False, p=P_b)\n", " \n", " the_preferential_attachement_of_blue_nodes=[x for x in blue_nodes if x[0] in choices]\n", " red_nodes.append(generated_node)\n", " \n", " elif ((rand_uf<r) and N-len(red_nodes)>N-int(round(N*r))):\n", " generated_node = (i,'b')\n", " g.insert_vertex(generated_node)\n", " choices = np.random.choice(vec_r,size=k_nodes_of_different_color,replace=False, p=P_r)\n", " \n", " the_preferential_attachement_of_red_nodes=[x for x in red_nodes if x[0] in choices]\n", " choices = np.random.choice(vec_b,size=k_nodes_of_same_color,replace=False, p=P_b)\n", " \n", " \n", " \n", " \n", " the_preferential_attachement_of_blue_nodes=[x for x in blue_nodes if x[0] in choices]\n", " blue_nodes.append(generated_node)\n", " \n", " \n", " for n in the_preferential_attachement_of_red_nodes:\n", " g.insert_edge(generated_node,n)\n", " for n in bthe_preferential_attachement_of_blue_nodes:\n", " g.insert_edge(generated_node,n)\n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " degs_count = g.degree_distribution()\n", " x, y = zip(*degs_count.items())\n", " degs = x\n", " counts = y\n", " plt.subplot(int(str(24)+str(kk+1)))\n", " plt.bar(degs, counts,width=.5)\n", " plt.xlabel('degrees')\n", " plt.ylabel('counts')\n", " plt.title('r = '+str(r)+', p = '+str(p))\n", " kk+=1\n", " j+=1\n", " k+=1\n", "\n", " plt.show()\n", "\n", "main()\n", " \n", " \n", " \n", " \n", "\n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", "\n", "\n" ] }, { "cell_type": "code", "execution_count": 9, "metadata": {}, "outputs": [ { "ename": "NameError", "evalue": "name 'plt' is not defined", "output_type": "error", "traceback": [ "\u001b[1;31m---------------------------------------------------------------------------\u001b[0m", "\u001b[1;31mNameError\u001b[0m Traceback (most recent call last)", "\u001b[1;32m<ipython-input-9-496de1a540db>\u001b[0m in \u001b[0;36m<module>\u001b[1;34m\u001b[0m\n\u001b[1;32m----> 1\u001b[1;33m \u001b[0mplt\u001b[0m\u001b[1;33m.\u001b[0m\u001b[0mloglog\u001b[0m\u001b[1;33m(\u001b[0m\u001b[0mlist\u001b[0m\u001b[1;33m(\u001b[0m\u001b[0mdeg\u001b[0m\u001b[1;33m.\u001b[0m\u001b[0mkeys\u001b[0m\u001b[1;33m(\u001b[0m\u001b[1;33m)\u001b[0m\u001b[1;33m)\u001b[0m\u001b[1;33m,\u001b[0m\u001b[0mlist\u001b[0m\u001b[1;33m(\u001b[0m\u001b[0mdeg\u001b[0m\u001b[1;33m.\u001b[0m\u001b[0mvalues\u001b[0m\u001b[1;33m(\u001b[0m\u001b[1;33m)\u001b[0m\u001b[1;33m)\u001b[0m\u001b[1;33m)\u001b[0m\u001b[1;33m\u001b[0m\u001b[1;33m\u001b[0m\u001b[0m\n\u001b[0m\u001b[0;32m 2\u001b[0m \u001b[0mplt\u001b[0m\u001b[1;33m.\u001b[0m\u001b[0mxlabel\u001b[0m\u001b[1;33m(\u001b[0m\u001b[1;34m'k'\u001b[0m\u001b[1;33m)\u001b[0m\u001b[1;33m\u001b[0m\u001b[1;33m\u001b[0m\u001b[0m\n\u001b[0;32m 3\u001b[0m \u001b[0mplt\u001b[0m\u001b[1;33m.\u001b[0m\u001b[0mylabel\u001b[0m\u001b[1;33m(\u001b[0m\u001b[1;34m'pk'\u001b[0m\u001b[1;33m)\u001b[0m\u001b[1;33m\u001b[0m\u001b[1;33m\u001b[0m\u001b[0m\n\u001b[0;32m 4\u001b[0m \u001b[0mplt\u001b[0m\u001b[1;33m.\u001b[0m\u001b[0msavefig\u001b[0m\u001b[1;33m(\u001b[0m\u001b[1;34m'Degree distribution.png'\u001b[0m\u001b[1;33m)\u001b[0m\u001b[1;33m\u001b[0m\u001b[1;33m\u001b[0m\u001b[0m\n", "\u001b[1;31mNameError\u001b[0m: name 'plt' is not defined" ] } ], "source": [] }, { "cell_type": "code", "execution_count": null, "metadata": {}, "outputs": [], "source": [] }, { "cell_type": "code", "execution_count": null, "metadata": {}, "outputs": [], "source": [] }, { "cell_type": "code", "execution_count": null, "metadata": {}, "outputs": [], "source": [] }, { "cell_type": "code", "execution_count": null, "metadata": {}, "outputs": [], "source": [] }, { "cell_type": "code", "execution_count": null, "metadata": {}, "outputs": [], "source": [] } ], "metadata": { "kernelspec": { "display_name": "Python 3", "language": "python", "name": "python3" }, "language_info": { "codemirror_mode": { "name": "ipython", "version": 3 }, "file_extension": ".py", "mimetype": "text/x-python", "name": "python", "nbconvert_exporter": "python", "pygments_lexer": "ipython3", "version": "3.7.3" } }, "nbformat": 4, "nbformat_minor": 2 }