CoCalc Public FilesCDS2017.ipynb
Author: Mihai Ninov
Views : 4
Description: Jupyter notebook CDS2017.ipynb
In [ ]:
# # MNinov GMU 2017 # #
import networkx as nx
import matplotlib.pyplot as plt

In [ ]:
Pi=3.14

In [ ]:
Pi*2

In [ ]:
Pi*2**2

In [ ]:
Pi*3**2

In [ ]:
Pi

In [ ]:
a=2
type(a)

In [ ]:
b=2.0
type(b)

In [ ]:
c='2'
type(c)

In [ ]:
a==b

In [ ]:
type(a)==type(b)

In [ ]:
a==c

In [ ]:
L=[a,b,c]

In [ ]:
L[0]

In [ ]:
L[-1]

In [ ]:
L.append('two')

In [ ]:
L[-1]

In [ ]:
L.insert(2,2.)

In [ ]:
L

In [ ]:
L.pop(3)

In [ ]:
L

In [ ]:
L.remove(2.0)

In [ ]:
L

In [ ]:
len(L)

In [ ]:
L[1]=10

In [ ]:
L

In [ ]:
# Dictionary and Key
M={}

In [ ]:
M[2]=L[1]

In [ ]:
M[2]

In [ ]:
M[1]=L[2]

In [ ]:
M

In [ ]:
#Keys of Dictionary don't need to be ordered in any way
#When accecces, one must keep this in mind
M.keys()

In [ ]:
#To determined what is stored for each of those keys
M.values()

In [ ]:
#Obtain a complete listing of what is contained in M
M.items()
#tuples are very similar to lists, but are not mutable,which is to say,
#I could not reassign a value to an element of a tuple, in contrast to list.

In [ ]:
#IF Statement ends with:
if a==b:
e=1
#we have used a Boolean operator to determine whether a and b are equal to one another
#an if statement determining this, will allow the execution to continue to the block of instructions indented below it
#In this case, it simply assign the integer value 1 to e

In [ ]:
e

In [ ]:
#Indentation:
# python requires some sort of cue to tell it that a block of instructions depends on something.

In [ ]:
#If you want to paste code into IPython, try the %paste and %cpastemagic functions
##

In [ ]:
#IF Else statements end with: %autoindent = Magic Word
if a==c:
f=1
else:
g=1

In [ ]:
g

In [ ]:
f
#We know from above that a and c are different, and hence when a==c evaluates to 'False'
#Therefore, the if statement will not evaluate f=1, but rather it will evaluate g=1.

In [ ]:
#For Statement (Define Dictionary s and range
s={}
#range(x) gives a list of numbers of length x, running from 0 to x-1
range(10)

In [ ]:
#For statements end with : and indent
for i in range(100):
s[i] = i+1

In [ ]:
#Choose what you want to call: spaces are used for code||Readability
s[0], s[1], s[5], s[99]

In [ ]:
#For Loop #for (Vvariable) in (a list)
#variable is i, and the list is given by range(100) since Gauss added up to 100
# #count sum of elements s+1 increments of the Keys
sum=0
for i in s.keys():
sum=sum+s[i]
#sum appears both on the left and the right of the equality sign. The way that programming languages work is
# that for an equality sign as in this line, they will make STUFF on the left become equal to STUFF on the right
#Therefore, is sum at some point has a value, say 1, and we evaluate sum=sum+s[i], then sum will take on the new value 1+s[i]

In [ ]:
sum

In [ ]:
#Calculating an average An=Ao*r^n OR well approximated by about 1+n*(r-1)
#calculate an average of 20 terms of a geometric series
#where r = 2, and a o = 10
#First let us create a list Comprehensions containing the elements of the geometric series
#gs=[] must be in the same line in Python 3.6
#gs.append is used and ** denotes exponents in Python, where ^ is used in MATLAB
gs=[]
for i in range(20):
gs.append(10*2**(i+1))

In [ ]:
avg=0
for elem in gs:
avg=avg+elem

In [ ]:
avg=avg/len(gs)
avg

In [ ]:
#Link indicator **using an integer counter such as i or j, links (edges) that connect a node (vertex) as (i,j)
#
#Node Degree aka (incident on the node) may contain large # of links => Ki= number of links connecting to node i
#Important: Many networks have a very wide spread of values of Ki
#Mathematically keep track of whether a link is present or absent (from source to target) Ai,j{1/0 if i,j connected 1, else 0

In [ ]:
#Let's store these link indicators and calculate degrees without the help of python libraries
##So we want to create some data structure (lists or dictionaries)
####So if we were to use a list to store indicators, we would need an ordering of the list elements that is a convention
#so that every time we go looking for a particular node pair, we know exactly where to find it.
##### Other possibility is using a dictionary. This allows us to specify an entry value so that we
##can ask a correctly constructed dictionary whether the link we are supplying it as entry is present or not.

In [ ]:
#Decide What KIND of entry you supply the dictionary ex, tuples
#It turns out that tuples can be a good solution to use as keys to a dictionary
a={}
#first statement defines the dictionary a
a[(1,2)]=1
#defined one element of the dictionary with key (1,2) ~ nodes 1and2 are connected aka (ASW)

##But why use tuples and not a list as the keys of the dictionary?
### ### turns out ### ###
#that one of the few requirements that dictionaries have is that the keys cannot be mutable.
#one of the few requirements that dictionaries have is that the keys cannot be mutable.

In [ ]:
##or undirected networks, the link (i,j) is the same as the link (j,i)
#   However, python does not know we are working with links from a network
#       and in python the order of the elements in a tuple matters ##
(1,2)==(2,1)

In [ ]:
b={}
b[[1,2]=1

In [ ]:
(1,2)==(2,1)

In [ ]:
import networkx as nx

In [ ]:
G=nx.graph()

In [ ]:


In [ ]:
G.nodes()

In [ ]:
G.edges()

In [ ]:
G.add_edge(a,b)

In [ ]:
G.nodes()

In [ ]:
G.edges()

In [ ]:
nx.draw(G)
plt.show()
Nx.draw(G)
Plt.show()

In [ ]:
#put all of this together to create and store the full set of link indicators##
##range(1:n+1) creates a list of elements that starts exactly at 1 and ends at n
####(the last element is range is always the last argument inside of range minus 1)#
#’if (i,j) in G:’
##when i and j are linked, then both (i,j) and (j,i) evaluate (output) to ’True’, if not (else)="False"

#n=int(args[1])
input=open(
a={}
for i in range(1,n+1):
for j in range(1,n+1):
if (i,j) in G:
a[(i,j)]=1
else:
a[(i,j)]=0

In [ ]:
#calculate DEGREES for every node
#aij represented by a[(i,j)] are the elements of adjacency matrix A
##dictionary k has a key ’i’ initialized, with value 0
k={}
for i in range(1,n+1):
k[i]=0
for j in range(1,n+1):
k[i]=k[i]+a[(i,j)]
# #Here, it is very important that the code above whichdefined dictionary ’a’
#and this code use consistent definitions

In [2]:
cd
Input=open(
sum_m=0
for i in range(1:n+1):
for j in range(1:n+1):
sum_m=sum_0+a[(i,j)]

import networkx as nx
import matplotlib.pyplot as plt
import scipy as sp
import numpy as
import sys
import math

n=int(input())
npG=(nx)

#Handshake Lemma
#Degree Distribution
#Histogram
G=degree(List)

#R is now 2, does
#Method of a Dictionary
R={}
h.has_key(elem)
h{elem}={elem}+1
Else:
h{elem}=1
#Complete Graph: All nodes are connected to all other nodes
#All nodes have n-1 connections
#How many times? N times for n nodes

###Graph density P = m/n(n-1)/2
#Spanning Trees P = n-1

def BFS(G,s):
front=[s]
d=0
visited=[s]
distance={}
distance[s]=0

def BFS(G,s):
front=[s]
d=0
visited=[s]
distance={}
distance[s]=d
while len(front)>0:
d=d+1
new_front=[]
for i in front:
for j in G.neighbors(i):
if j in visited:
continue
else:
new_front.append(j)
distance[j]=d
visited.append(j)
front=new_front
return(distance)

nx.draw(G)
plt.show()
plot plt(show)

G=nx.Graph()
G.nodes()
G.nodes()
[1,2,3]
G.edges()
[(1,2),(1,3)]
G.degree(1),G.degree(2),G.degree(3)
(2,1,1)

while len(pending)>0:
d=BFS(H,pending[0])
NewComponent=[]
for node in d.keys():
pending.remove(node)
NewComponent.append(node)
components.append(NewComponent)

 File "<ipython-input-2-a39bbf3b2dfa>", line 4 sum_m=0 ^ SyntaxError: invalid syntax 
In [ ]:
#CDS 292 Homework 3
def BFS(G,i):
front=[i]
d=0
visited=[i]
distance={}
distance[i]=d
while len(front)>0:
d=d+1
new_front=[]
for i in front:
for H in G.neighbors(i):
if H in visited:
continue
else:
new_front.append(H)
distance[H]=d
visited.append(h)
front=new_front
return(distance)

New.front=[]
for i in front:
for H in neighbor(i)
if H in visited:
else:
new_front.append(H)

import matplotlib.pyplot as plt

from bfs import BFS
import networkx as nx
import BFS as bfs

components=[]
ToVisit=H.nodes()
while len (ToVisit) >0:
d=BFS(H,ToVisit[0])
NewComponent=[]
for node in d.keys():
ToVisit.remove(node)
NewComponent.append(node)
components.append(NewComponent)
components=[]
pending=H.nodes()

len(Components)
components[1]
len(components[1])
components
nx.is_connected(H)
len(components[H])
nx.number_connected_components(H)
nx.number_connected_components(H,1)
nx.number_connected_components(H,2)
gl=list(nx.connectected_components(G))
gl[0]
gl=list(nx.connectected_component_subgraph(H))
gl[0]
H=nx.Graph()
H.nodes()
H.nodes()
H.edges()
nx.draw(H)
plt.show()
G=nx.path_graph(5)
length=nx.all_pairs_dijkstra_path_length(G)
print(length[1][4])
length[1]

#TRIANGLE COUNTING
def triangle(G,i):
iNeighList=G.neighbors(i)
ki=G.degree(i)
CountTri=0
for n in range(ki):
for m in range(n+1,ki):
a=iNeighList[n]
b=iNeighList[m]
if G.has_edge(a,b):
CountTri=CountTri+1
return(CountTri)

G=nx.graph()
G.nodes()