четверг, 30 июня 2016 г.
среда, 29 июня 2016 г.
вторник, 28 июня 2016 г.
понедельник, 27 июня 2016 г.
Intro to Algorithms Lesson 4: It's Who You KnowNotes
https://classroom.udacity.com/courses/cs215/lessons/48739297/concepts/487342830923
LESSON 4
# animal speed weight lifespan brain
# (mph) (kg) (years) mass (g)
animals = [("dog", 46, 35, 13, 280 ),
("elephant", 30, 3500, 50, 6250 ),
("frog", 5, 0.5, 8, 3 ),
("hippopotamus", 45, 1600, 45, 573 ),
("horse", 40, 385, 30, 642 ),
("human", 27, 80, 78, 2000 ),
("lion", 50, 250, 30, 454 ),
("mouse", 8, 0.025, 2, 0.625),
("rabbit", 25, 4, 12, 40 ),
("shark", 26, 230, 20, 92 ),
("sparrow", 16, 0.024, 7, 2 )]
def importance_rank(items, weights):
names = [item[0] for item in items] # get the list of animal names
scores = [sum([a*b for (a,b) in zip(item[1:], weights)]) for item in items] # get the list of overall scores for each animal
results = zip(scores,names) # make a list of tuple
res2 = sorted(results) # sort the tuple based on the score
return res2
answer = importance_rank(animals, (2,3,7,1))
for i in range(len(answer)):
print i, answer[i][1], "(", answer[i][0], ")"
0 mouse ( 30.7 )
1 frog ( 70.5 )
2 sparrow ( 83.072 )
3 rabbit ( 186 )
4 dog ( 568 )
5 shark ( 974 )
6 lion ( 1514 )
7 horse ( 2087 )
8 human ( 2840 )
9 hippopotamus ( 5778 )
10 elephant ( 17160 )
In graph theory and network analysis, indicators of centrality identify the most important vertices within a graph. Applications include identifying the most influential person(s) in a social network, key infrastructure nodes in the Internet or urban networks, and super-spreaders of disease. Centrality concepts were first developed in social network analysis, and many of the terms used to measure centrality reflect their sociological origin.
Degree (node) centrality:
"An important node is involved in large number of interactions"
Historically first and conceptually simplest is degree centrality, which is defined as the number of links incident upon a node (i.e., the number of ties that a node has). The degree can be interpreted in terms of the immediate risk of a node for catching whatever is flowing through the network (such as a virus, or some information). In the case of a directed network (where ties have direction), we usually define two separate measures of degree centrality, namely indegree and outdegree.
Closeness centrality
In connected graphs there is a natural distance metric between all pairs of nodes, defined by the length of their shortest paths.
The information centrality of Stephenson and Zelen (1989) is another closeness measure, which computes the harmonic mean of the resistance distances towards a vertex x, which is smaller if x has many paths of small resistance connecting it to other vertices.
Betweenness is a centrality measure of a vertex within a graph. It quantifies the number of times a node acts as a bridge along the shortest path between two other nodes. It was introduced as a measure for quantifying the control of a human on the communication between other humans in a social network by Linton Freeman. In his conception, vertices that have a high probability to occur on a randomly chosen shortest path between two randomly chosen vertices have a high betweenness.
Eigenvector centrality (also called eigencentrality) is a measure of the influence of a node in a network. It assigns relative scores to all nodes in the network based on the concept that connections to high-scoring nodes contribute more to the score of the node in question than equal connections to low-scoring nodes. Google's PageRank is a variant of the eigenvector centrality measure.
###################################################################
21 57 midpoint
43 51 median
48 54 mean C1&C2
49
50
51
75
77
79
87
93
The Sorter: http://www.youtube.com/watch?v=2HjspVV0jK4
def max(L):
maxL = L[0]
for i in range(1, len(L)):
if L[i] >= maxL:
maxL = L[i]
return maxL
def test():
L = [1, 2, 3, 4]
assert 4 == max(L)
L = [3, 6, 10, 9, 3]
assert 10 == max(L)
print test()
#############################################################################
f = open("yob1995.txt", "r")
def find_count_f(a):
max_count = 0
for line in a:
name,sex,count = line.split(",")
count = int(count)
if sex == "F" and max_count < count:
max_count = count
fmost_popular = name
return fmost_popular, max_count
print find_count_f(f)
Python 2.7.11 (v2.7.11:6d1b6a68f775, Dec 5 2015, 12:54:16)
[GCC 4.2.1 (Apple Inc. build 5666) (dot 3)] on darwin
Type "copyright", "credits" or "license()" for more information.
>>>
======= RESTART: /Users/olgabelitskaya/Desktop/course7/hello world.py =======
('Jessica', 27931)
>>>
f = open("yob1995.txt", "r")
def second_count_f(a):
first_count = 0
second_count = 0
first_name = None
second_name = None
for line in a:
name,sex,count = line.split(",")
count = int(count)
if sex == "F":
if first_count < count:
second_count = first_count
second_name = first_name
first_count = count
first_name = name
return second_name
print second_count_f(f)
Python 2.7.11 (v2.7.11:6d1b6a68f775, Dec 5 2015, 12:54:16)
[GCC 4.2.1 (Apple Inc. build 5666) (dot 3)] on darwin
Type "copyright", "credits" or "license()" for more information.
>>> WARNING: The version of Tcl/Tk (8.5.9) in use may be unstable.
Visit http://www.python.org/download/mac/tcltk/ for current information.
======= RESTART: /Users/olgabelitskaya/Desktop/course7/hello world.py =======
Ashley
>>>
#
# Write partition to return a new array with
# all values less then `v` to the left
# and all values greater then `v` to the right
#
def partition(L, v):
p1 = []
p2 = []
for element in L:
if element < v:
p1.append(element)
elif element > v:
p2.append(element)
p1.append(v)
# your code here
return p1 + p2
L = [12, 24, 98, 35, 73, 76, 18, 65]
print partition(L,65)
In computer science, a heap is a specialized tree-based data structure that satisfies the heap property: If A is a parent node of B then the key (the value) of node A is ordered with respect to the key of node B with the same ordering applying across the heap. A heap can be classified further as either a "max heap" or a "min heap". In a max heap, the keys of parent nodes are always greater than or equal to those of the children and the highest key is in the root node. In a min heap, the keys of parent nodes are less than or equal to those of the children and the lowest key is in the root node. Heaps are crucial in several efficient graph algorithms such as Dijkstra's algorithm, and in the sorting algorithm heapsort. A common implementation of a heap is the binary heap, in which the tree is a complete binary tree (see figure).
In a heap, the highest (or lowest) priority element is always stored at the root. A heap is not a sorted structure and can be regarded as partially ordered. As visible from the heap-diagram, there is no particular relationship among nodes on any given level, even among the siblings. When a heap is a complete binary tree, it has a smallest possible height—a heap with N nodes always has log N height. A heap is a useful data structure when you need to remove the object with the highest (or lowest) priority.
A binary heap is a heap data structure created using a binary tree. It can be seen as a binary tree with two additional constraints:
Shape property
A binary heap is a complete binary tree; that is, all levels of the tree, except possibly the last one (deepest) are fully filled, and, if the last level of the tree is not complete, the nodes of that level are filled from left to right.
Heap property
All nodes are either greater than or equal to or less than or equal to each of their children, according to a comparison predicate defined for the heap.
Heaps with a mathematical "greater than or equal to" (≥) comparison predicate are called max-heaps; those with a mathematical "less than or equal to" (≤) comparison predicate are called min-heaps. Min-heaps are often used to implement priority queues.
#
# Implement remove_min
#
def remove_min(L):
if len(L) == 1:
return []
L[0] = L.pop()
down_heapify(L, 0)
# your code here
return L
def parent(i):
return (i-1)/2
def left_child(i):
return 2*i+1
def right_child(i):
return 2*i+2
def is_leaf(L,i):
return (left_child(i) >= len(L)) and (right_child(i) >= len(L))
def one_child(L,i):
return (left_child(i) < len(L)) and (right_child(i) >= len(L))
# Call this routine if the heap rooted at i satisfies the heap property
# *except* perhaps i to its immediate children
def down_heapify(L, i):
# If i is a leaf, heap property holds
if is_leaf(L, i):
return
# If i has one child...
if one_child(L, i):
# check heap property
if L[i] > L[left_child(i)]:
# If it fails, swap, fixing i and its child (a leaf)
(L[i], L[left_child(i)]) = (L[left_child(i)], L[i])
return
# If i has two children...
# check heap property
if min(L[left_child(i)], L[right_child(i)]) >= L[i]:
return
# If it fails, see which child is the smaller
# and swap i's value into that child
# Afterwards, recurse into that child, which might violate
if L[left_child(i)] < L[right_child(i)]:
# Swap into left child
(L[i], L[left_child(i)]) = (L[left_child(i)], L[i])
down_heapify(L, left_child(i))
return
else:
(L[i], L[right_child(i)]) = (L[right_child(i)], L[i])
down_heapify(L, right_child(i))
return
#########
# Testing Code
#
# build_heap
def build_heap(L):
for i in range(len(L)-1, -1, -1):
down_heapify(L, i)
return L
def test():
L = range(10)
build_heap(L)
remove_min(L)
# now, the new minimum should be 1
assert L[0] == 1
print test()
olgabelitskaya (master) ~ $ cd version-control
olgabelitskaya (master *) version-control $ git status
On branch master
Your branch is up-to-date with 'exercises/master'.
Changes not staged for commit:
(use "git add <file>..." to update what will be committed)
(use "git checkout -- <file>..." to discard changes in working directory)
modified: reflections-cs215/lesson3_reflections_ob.txt
Untracked files:
(use "git add <file>..." to include in what will be committed)
reflections-cs215/lesson4_reflections_ob.txt
no changes added to commit (use "git add" and/or "git commit -a")
olgabelitskaya (master *) version-control $ git add 'reflections-cs215/lesson3_reflections_ob.txt'
olgabelitskaya (master +) version-control $ git commit -m "Update lesson3_reflections_ob.txt"
[master 1a4653b] Update lesson3_reflections_ob.txt
1 file changed, 45 insertions(+)
olgabelitskaya (master) version-control $ git add 'reflections-cs215/lesson4_reflections_ob.txt'
olgabelitskaya (master +) version-control $ git commit -m "Add reflections lesson 4"
[master 3814483] Add reflections lesson 4
1 file changed, 251 insertions(+)
create mode 100644 reflections-cs215/lesson4_reflections_ob.txt
olgabelitskaya (master) version-control $ git status
On branch master
Your branch is ahead of 'exercises/master' by 2 commits.
(use "git push" to publish your local commits)
nothing to commit, working directory clean
olgabelitskaya (master) version-control $ git push exercises master
Counting objects: 8, done.
Delta compression using up to 4 threads.
Compressing objects: 100% (8/8), done.
Writing objects: 100% (8/8), 5.27 KiB | 0 bytes/s, done.
Total 8 (delta 5), reused 0 (delta 0)
To https://github.com/OlgaBelitskaya/my-exercises.git
4443845..3814483 master -> master
PROBLEM SET 4
#1
heap = []
for v in vals:
insert_heap(heap,v)
Θ(n*log(n))
#2
#
# Given a list of numbers, L, find a number, x, that
# minimizes the sum of the absolute value of the difference
# between each element in L and x: SUM_{i=0}^{n-1} |L[i] - x|
#
# Your code should run in Theta(n) time
#
L = [12,83,15,27,35,7,64]
def minimize_absolute(L):
S = []
for element in L:
se = 0
for i in range(len(L)):
se = se + abs(L[i] - element)
S.append(se)
print S
k = min(S)
print k
ik = S.index(k)
# your code here
return L[ik]
print minimize_absolute(L)
#3
#
# Given a list of numbers, L, find a number, x, that
# minimizes the sum of the square of the difference
# between each element in L and x: SUM_{i=0}^{n-1} (L[i] - x)^2
#
# Your code should run in Theta(n) time
#
L = [2,2,3,4]
def minimize_square(L):
S = []
for element in L:
sq = 0
for j in range(len(L)):
se = element - L[j]
sq = sq + se*se
S.append(sq)
print S
k = min(S)
print k
ik = S.index(k)
# your code here
return L[ik]
print minimize_square(L)
#################################################################
L = [2,2,3,4]
def minimize_square(L):
S = {}
print L
for element in L:
sq = 0
for j in range(len(L)):
se = element - L[j]
sq = sq + se*se
S[element] = sq
print S
for key, value in S.iteritems():
if value == min(S.values()):
return key
print minimize_square(L)
#4
4.1
#
# Given a list L of n numbers, find the mode
# (the number that appears the most times).
# Your algorithm should run in Theta(n).
# If there are ties - just pick one value to return
#
from operator import itemgetter
def mode(L):
counts = {}
maxelement = None
maxn = 0
for element in L:
if element not in counts:
counts[element] = 1
else:
counts[element] += 1
if counts[element] > maxn:
maxelement = element
maxn = counts[element]
return maxelement
# your code here
####
# Test
#
import time
from random import randint
def test():
assert 5 == mode([1, 5, 2, 5, 3, 5])
iterations = (10, 20, 30, 100, 200, 300, 1000, 5000, 10000, 20000, 30000)
times = []
for i in iterations:
L = []
for j in range(i):
L.append(randint(1, 10))
start = time.clock()
for j in range(500):
mode(L)
end = time.clock()
print start, end
times.append(float(end - start))
slopes = []
for (x1, x2), (y1, y2) in zip(zip(iterations[:-1], iterations[1:]), zip(times[:-1], times[1:])):
print (x1, x2), (y1, y2)
slopes.append((y2 - y1) / (x2 - x1))
# if mode runs in linear time,
# these factors should be close (kind of)
print slopes
print test()
RESET TEST RUN SUBMIT
0.013615 0.014496
0.014539 0.016172
0.016212 0.018655
0.01876 0.027141
0.027386 0.04383
0.044145 0.068484
0.069518 0.150515
0.15572 0.553299
0.563656 1.339508
1.360104 2.902613
2.933505 5.293337
(10, 20) (0.0008809999999999998, 0.001632999999999999)
(20, 30) (0.001632999999999999, 0.0024430000000000007)
(30, 100) (0.0024430000000000007, 0.008381)
(100, 200) (0.008381, 0.016444)
(200, 300) (0.016444, 0.024339000000000006)
(300, 1000) (0.024339000000000006, 0.08099700000000001)
(1000, 5000) (0.08099700000000001, 0.397579)
(5000, 10000) (0.397579, 0.7758519999999999)
(10000, 20000) (0.7758519999999999, 1.5425090000000001)
(20000, 30000) (1.5425090000000001, 2.3598320000000004)
[7.519999999999992e-05, 8.100000000000017e-05, 8.482857142857141e-05, 8.063e-05, 7.895000000000006e-05, 8.094000000000001e-05, 7.914550000000001e-05, 7.565459999999997e-05, 7.666570000000002e-05, 8.173230000000003e-05]
None
##########################################################
4.2
from operator import itemgetter
from collections import defaultdict
def mode(L):
counts = defaultdict(int)
mode = None
maxn = 0
for e in L:
counts[e] += 1
current = counts[e]
if current > maxn:
mode = e
maxn = current
return mode
0.01416 0.01542
0.015468 0.017476
0.017512 0.020281
0.020391 0.027656
0.027869 0.041363
0.041676 0.061522
0.062561 0.12634
0.131508 0.457904
0.468202 1.123113
1.143701 2.454703
2.485846 4.46365
(10, 20) (0.001259999999999999, 0.0020079999999999976)
(20, 30) (0.0020079999999999976, 0.0027690000000000006)
(30, 100) (0.0027690000000000006, 0.007265000000000001)
(100, 200) (0.007265000000000001, 0.013493999999999996)
(200, 300) (0.013493999999999996, 0.019846000000000003)
(300, 1000) (0.019846000000000003, 0.063779)
(1000, 5000) (0.063779, 0.32639599999999996)
(5000, 10000) (0.32639599999999996, 0.654911)
(10000, 20000) (0.654911, 1.3110019999999998)
(20000, 30000) (1.3110019999999998, 1.9778040000000003)
[7.479999999999987e-05, 7.61000000000003e-05, 6.422857142857144e-05, 6.228999999999995e-05, 6.352000000000007e-05, 6.276142857142857e-05, 6.565425e-05, 6.570300000000002e-05, 6.560909999999998e-05, 6.668020000000006e-05]
None
#######################################################################
4.3
from operator import itemgetter
from collections import defaultdict
def mode(L):
amounts = defaultdict(int)
for v in L:
amounts[v] +=1
return max(amounts, key = lambda x: amounts[x])
0.014366 0.016016
0.016062 0.018403
0.018443 0.021367
0.021478 0.026966
0.027181 0.036292
0.036608 0.049343
0.050382 0.088166
0.093351 0.281401
0.297654 0.713603
0.734345 1.498868
1.529933 2.681095
(10, 20) (0.0016499999999999987, 0.0023409999999999993)
(20, 30) (0.0023409999999999993, 0.0029239999999999995)
(30, 100) (0.0029239999999999995, 0.005488)
(100, 200) (0.005488, 0.009110999999999998)
(200, 300) (0.009110999999999998, 0.012734999999999996)
(300, 1000) (0.012734999999999996, 0.03778399999999999)
(1000, 5000) (0.03778399999999999, 0.18805)
(5000, 10000) (0.18805, 0.415949)
(10000, 20000) (0.415949, 0.7645230000000001)
(20000, 30000) (0.7645230000000001, 1.151162)
[6.910000000000007e-05, 5.830000000000002e-05, 3.6628571428571435e-05, 3.622999999999998e-05, 3.6239999999999985e-05, 3.578428571428571e-05, 3.75665e-05, 4.557980000000001e-05, 3.48574e-05, 3.8663899999999994e-05]
None
##########################################################################
4.4
from operator import itemgetter
def mode(L):
values = set(L)
return max(values, key = lambda x: L.count(x))
0.013503 0.014766
0.014812 0.016569
0.016608 0.019108
0.019215 0.024997
0.025211 0.035604
0.035921 0.050884
0.051921 0.099694
0.104897 0.342236
0.352604 0.82273
0.843408 1.783683
1.814736 3.228627
(10, 20) (0.0012630000000000002, 0.0017569999999999999)
(20, 30) (0.0017569999999999999, 0.0024999999999999988)
(30, 100) (0.0024999999999999988, 0.005781999999999999)
(100, 200) (0.005781999999999999, 0.010392999999999996)
(200, 300) (0.010392999999999996, 0.014962999999999997)
(300, 1000) (0.014962999999999997, 0.047773)
(1000, 5000) (0.047773, 0.23733899999999997)
(5000, 10000) (0.23733899999999997, 0.470126)
(10000, 20000) (0.470126, 0.9402749999999999)
(20000, 30000) (0.9402749999999999, 1.413891)
[4.939999999999997e-05, 7.429999999999988e-05, 4.688571428571429e-05, 4.610999999999997e-05, 4.570000000000001e-05, 4.687142857142858e-05, 4.739149999999999e-05, 4.65574e-05, 4.701489999999999e-05, 4.736160000000002e-05]
None
###########################################################################
4.5
from operator import itemgetter
def mode(L):
return max(set(L), key = lambda x: L.count(x))
TEST RUN
0.013792 0.014963
0.015015 0.016845
0.016882 0.019399
0.019513 0.025268
0.025498 0.035938
0.036287 0.051412
0.052471 0.100546
0.105764 0.344642
0.355091 0.830679
0.851587 1.797449
1.828574 3.2462
(10, 20) (0.0011710000000000002, 0.0018299999999999983)
(20, 30) (0.0018299999999999983, 0.0025169999999999984)
(30, 100) (0.0025169999999999984, 0.005755)
(100, 200) (0.005755, 0.010439999999999998)
(200, 300) (0.010439999999999998, 0.015125)
(300, 1000) (0.015125, 0.048075)
(1000, 5000) (0.048075, 0.238878)
(5000, 10000) (0.238878, 0.47558799999999996)
(10000, 20000) (0.47558799999999996, 0.9458620000000001)
(20000, 30000) (0.9458620000000001, 1.417626)
[6.589999999999981e-05, 6.870000000000002e-05, 4.625714285714288e-05, 4.684999999999998e-05, 4.6850000000000014e-05, 4.707142857142857e-05, 4.770075e-05, 4.734199999999999e-05, 4.702740000000002e-05, 4.71764e-05]
None
#########################################################################
#5
#
# write up_heapify, an algorithm that checks if
# node i and its parent satisfy the heap
# property, swapping and recursing if they don't
#
# L should be a heap when up_heapify is done
#
def parent(i):
return (i-1)/2
def left_child(i):
return 2*i+1
def right_child(i):
return 2*i+2
def is_leaf(L,i):
return (left_child(i) >= len(L)) and (right_child(i) >= len(L))
def one_child(L,i):
return (left_child(i) < len(L)) and (right_child(i) >= len(L))
def up_heapify(L, i):
while L[i] < L[parent(i)] and parent(i) != -1:
print L
print i, L[i]
print parent(i), L[parent(i)]
(L[parent(i)], L[i]) = (L[i], L[parent(i)])
i = parent(i)
# your code here
return L
def test():
L = [2, 4, 3, 5, 9, 7, 7]
L.append(1)
up_heapify(L, 7)
assert 1 == L[0]
assert 2 == L[1]
print test()
TEST RUN
[2, 4, 3, 5, 9, 7, 7, 1]
7 1
3 5
[2, 4, 3, 1, 9, 7, 7, 5]
3 1
1 4
[2, 1, 3, 4, 9, 7, 7, 5]
1 1
0 2
None
#######################################################################
#6
import random
import csv
def make_link(G, node1, node2):
if node1 not in G:
G[node1] = {}
(G[node1])[node2] = 1
if node2 not in G:
G[node2] = {}
(G[node2])[node1] = 1
return G
def make_data(file_name):
data = scv.reader(open(file_name), delimiter='\t')
G = {}
actors = {}
movies = {}
for (actor, movie, year) in data:
movie_year = str(movie) + "," + str(year)
actors[actor] = 1
movies[movie_year] = 1
make_link(G, actor, movie_year)
return (G,actors,movies)
def centrality(G, v):
distance_from_start = {}
open_list = [v]
distance_from_start[v] = 0
while len(open_list) > 0:
current = open_list.pop(0)
for neighbor in G[current].keys():
if neighbor not in distance_from_start:
distance_from_start[neighbor] = distance_from_start[current] + 1
open_list.append(neighbor)
return (float(sum(distance_from_start.values())))/len(distance_from_start)
def rank(L,v):
rank = 0
for element in L:
if element < v:
rank += 1
return rank
def find_rank(L, t):
less_t = {}
equal_t = {}
greater_t = {}
v = random.choice(L.keys())
for t in L.keys():
if L[l] < L[v]:
less_t[t] = L[t]
elif L[t] == L[v]:
equal_t[t] = L[t]
elif L[t] > L[v]:
greater_t[t] = L[t]
if len(less_t) >= t: return find_rank(less_t,t)
elif len(less_t) + len(equal_t) >= t: return v
else: return find_rank(greater_t, t - len(less_t) - len(equal_t))
(G, actors, movies) = make_data(actors.tsv)
centralities = {}
for actor in actors.key():
centralities[actor] = centrality(G, actor)
actor_rank = firn_rank(centralities, 20)
print actor_rank
print centralities[actor_rank]
#######################################################################
Last login: Tue Jun 21 09:16:40 on console
olgabelitskaya (master) ~ $ cd version-control
olgabelitskaya (master *) version-control $ git status
On branch master
Your branch is up-to-date with 'exercises/master'.
Changes not staged for commit:
(use "git add <file>..." to update what will be committed)
(use "git checkout -- <file>..." to discard changes in working directory)
modified: reflections-cs215/lesson4_reflections_ob.txt
Untracked files:
(use "git add <file>..." to include in what will be committed)
reflections-cs215/lesson5_reflections_ob.rtf
no changes added to commit (use "git add" and/or "git commit -a")
olgabelitskaya (master *) version-control $ git add 'reflections-cs215/lesson4_reflections_ob.txt'
olgabelitskaya (master +) version-control $ git commit -m "Update lesson4_reflections_ob.txt"
[master b1ee03c] Update lesson4_reflections_ob.txt
1 file changed, 411 insertions(+), 1 deletion(-)
olgabelitskaya (master) version-control $ git add 'reflections-cs215/lesson5_reflections_ob.rtf'
olgabelitskaya (master +) version-control $ git commit -m "Create lesson5_reflections_ob.rtf"
[master 2ebe71b] Create lesson5_reflections_ob.rtf
1 file changed, 13 insertions(+)
create mode 100644 reflections-cs215/lesson5_reflections_ob.rtf
olgabelitskaya (master) version-control $ git push exercises master
Counting objects: 8, done.
Delta compression using up to 4 threads.
Compressing objects: 100% (8/8), done.
Writing objects: 100% (8/8), 8.07 KiB | 0 bytes/s, done.
Total 8 (delta 4), reused 0 (delta 0)
To https://github.com/OlgaBelitskaya/my-exercises.git
3814483..2ebe71b master -> master
Last login: Tue Jun 21 17:24:48 on ttys000
olgabelitskaya (master) ~ $ cd version-control
olgabelitskaya (master *) version-control $ git status
On branch master
Your branch is up-to-date with 'exercises/master'.
Changes not staged for commit:
(use "git add <file>..." to update what will be committed)
(use "git checkout -- <file>..." to discard changes in working directory)
modified: reflections-cs215/lesson3_reflections_ob.txt
modified: reflections-cs215/lesson4_reflections_ob.txt
no changes added to commit (use "git add" and/or "git commit -a")
olgabelitskaya (master *) version-control $ git add 'reflections-cs215/lesson3_reflections_ob.txt'
olgabelitskaya (master *+) version-control $ git add 'reflections-cs215/lesson4_reflections_ob.txt'
olgabelitskaya (master +) version-control $ git status
On branch master
Your branch is up-to-date with 'exercises/master'.
Changes to be committed:
(use "git reset HEAD <file>..." to unstage)
modified: reflections-cs215/lesson3_reflections_ob.txt
modified: reflections-cs215/lesson4_reflections_ob.txt
olgabelitskaya (master +) version-control $ git commit -m "Update lesson3_reflections_ob.txt and lesson4_reflections_ob.txt"
[master cfaa476] Update lesson3_reflections_ob.txt and lesson4_reflections_ob.txt
2 files changed, 120 insertions(+)
olgabelitskaya (master) version-control $ git push exercises master
Counting objects: 5, done.
Delta compression using up to 4 threads.
Compressing objects: 100% (5/5), done.
Writing objects: 100% (5/5), 8.32 KiB | 0 bytes/s, done.
Total 5 (delta 3), reused 0 (delta 0)
To https://github.com/OlgaBelitskaya/my-exercises.git
2ebe71b..cfaa476 master -> master
LESSON 4
# animal speed weight lifespan brain
# (mph) (kg) (years) mass (g)
animals = [("dog", 46, 35, 13, 280 ),
("elephant", 30, 3500, 50, 6250 ),
("frog", 5, 0.5, 8, 3 ),
("hippopotamus", 45, 1600, 45, 573 ),
("horse", 40, 385, 30, 642 ),
("human", 27, 80, 78, 2000 ),
("lion", 50, 250, 30, 454 ),
("mouse", 8, 0.025, 2, 0.625),
("rabbit", 25, 4, 12, 40 ),
("shark", 26, 230, 20, 92 ),
("sparrow", 16, 0.024, 7, 2 )]
def importance_rank(items, weights):
names = [item[0] for item in items] # get the list of animal names
scores = [sum([a*b for (a,b) in zip(item[1:], weights)]) for item in items] # get the list of overall scores for each animal
results = zip(scores,names) # make a list of tuple
res2 = sorted(results) # sort the tuple based on the score
return res2
answer = importance_rank(animals, (2,3,7,1))
for i in range(len(answer)):
print i, answer[i][1], "(", answer[i][0], ")"
0 mouse ( 30.7 )
1 frog ( 70.5 )
2 sparrow ( 83.072 )
3 rabbit ( 186 )
4 dog ( 568 )
5 shark ( 974 )
6 lion ( 1514 )
7 horse ( 2087 )
8 human ( 2840 )
9 hippopotamus ( 5778 )
10 elephant ( 17160 )
In graph theory and network analysis, indicators of centrality identify the most important vertices within a graph. Applications include identifying the most influential person(s) in a social network, key infrastructure nodes in the Internet or urban networks, and super-spreaders of disease. Centrality concepts were first developed in social network analysis, and many of the terms used to measure centrality reflect their sociological origin.
Degree (node) centrality:
"An important node is involved in large number of interactions"
Historically first and conceptually simplest is degree centrality, which is defined as the number of links incident upon a node (i.e., the number of ties that a node has). The degree can be interpreted in terms of the immediate risk of a node for catching whatever is flowing through the network (such as a virus, or some information). In the case of a directed network (where ties have direction), we usually define two separate measures of degree centrality, namely indegree and outdegree.
Closeness centrality
In connected graphs there is a natural distance metric between all pairs of nodes, defined by the length of their shortest paths.
The information centrality of Stephenson and Zelen (1989) is another closeness measure, which computes the harmonic mean of the resistance distances towards a vertex x, which is smaller if x has many paths of small resistance connecting it to other vertices.
Betweenness is a centrality measure of a vertex within a graph. It quantifies the number of times a node acts as a bridge along the shortest path between two other nodes. It was introduced as a measure for quantifying the control of a human on the communication between other humans in a social network by Linton Freeman. In his conception, vertices that have a high probability to occur on a randomly chosen shortest path between two randomly chosen vertices have a high betweenness.
Eigenvector centrality (also called eigencentrality) is a measure of the influence of a node in a network. It assigns relative scores to all nodes in the network based on the concept that connections to high-scoring nodes contribute more to the score of the node in question than equal connections to low-scoring nodes. Google's PageRank is a variant of the eigenvector centrality measure.
###################################################################
21 57 midpoint
43 51 median
48 54 mean C1&C2
49
50
51
75
77
79
87
93
The Sorter: http://www.youtube.com/watch?v=2HjspVV0jK4
def max(L):
maxL = L[0]
for i in range(1, len(L)):
if L[i] >= maxL:
maxL = L[i]
return maxL
def test():
L = [1, 2, 3, 4]
assert 4 == max(L)
L = [3, 6, 10, 9, 3]
assert 10 == max(L)
print test()
#############################################################################
f = open("yob1995.txt", "r")
def find_count_f(a):
max_count = 0
for line in a:
name,sex,count = line.split(",")
count = int(count)
if sex == "F" and max_count < count:
max_count = count
fmost_popular = name
return fmost_popular, max_count
print find_count_f(f)
Python 2.7.11 (v2.7.11:6d1b6a68f775, Dec 5 2015, 12:54:16)
[GCC 4.2.1 (Apple Inc. build 5666) (dot 3)] on darwin
Type "copyright", "credits" or "license()" for more information.
>>>
======= RESTART: /Users/olgabelitskaya/Desktop/course7/hello world.py =======
('Jessica', 27931)
>>>
f = open("yob1995.txt", "r")
def second_count_f(a):
first_count = 0
second_count = 0
first_name = None
second_name = None
for line in a:
name,sex,count = line.split(",")
count = int(count)
if sex == "F":
if first_count < count:
second_count = first_count
second_name = first_name
first_count = count
first_name = name
return second_name
print second_count_f(f)
Python 2.7.11 (v2.7.11:6d1b6a68f775, Dec 5 2015, 12:54:16)
[GCC 4.2.1 (Apple Inc. build 5666) (dot 3)] on darwin
Type "copyright", "credits" or "license()" for more information.
>>> WARNING: The version of Tcl/Tk (8.5.9) in use may be unstable.
Visit http://www.python.org/download/mac/tcltk/ for current information.
======= RESTART: /Users/olgabelitskaya/Desktop/course7/hello world.py =======
Ashley
>>>
#
# Write partition to return a new array with
# all values less then `v` to the left
# and all values greater then `v` to the right
#
def partition(L, v):
p1 = []
p2 = []
for element in L:
if element < v:
p1.append(element)
elif element > v:
p2.append(element)
p1.append(v)
# your code here
return p1 + p2
L = [12, 24, 98, 35, 73, 76, 18, 65]
print partition(L,65)
In computer science, a heap is a specialized tree-based data structure that satisfies the heap property: If A is a parent node of B then the key (the value) of node A is ordered with respect to the key of node B with the same ordering applying across the heap. A heap can be classified further as either a "max heap" or a "min heap". In a max heap, the keys of parent nodes are always greater than or equal to those of the children and the highest key is in the root node. In a min heap, the keys of parent nodes are less than or equal to those of the children and the lowest key is in the root node. Heaps are crucial in several efficient graph algorithms such as Dijkstra's algorithm, and in the sorting algorithm heapsort. A common implementation of a heap is the binary heap, in which the tree is a complete binary tree (see figure).
In a heap, the highest (or lowest) priority element is always stored at the root. A heap is not a sorted structure and can be regarded as partially ordered. As visible from the heap-diagram, there is no particular relationship among nodes on any given level, even among the siblings. When a heap is a complete binary tree, it has a smallest possible height—a heap with N nodes always has log N height. A heap is a useful data structure when you need to remove the object with the highest (or lowest) priority.
A binary heap is a heap data structure created using a binary tree. It can be seen as a binary tree with two additional constraints:
Shape property
A binary heap is a complete binary tree; that is, all levels of the tree, except possibly the last one (deepest) are fully filled, and, if the last level of the tree is not complete, the nodes of that level are filled from left to right.
Heap property
All nodes are either greater than or equal to or less than or equal to each of their children, according to a comparison predicate defined for the heap.
Heaps with a mathematical "greater than or equal to" (≥) comparison predicate are called max-heaps; those with a mathematical "less than or equal to" (≤) comparison predicate are called min-heaps. Min-heaps are often used to implement priority queues.
#
# Implement remove_min
#
def remove_min(L):
if len(L) == 1:
return []
L[0] = L.pop()
down_heapify(L, 0)
# your code here
return L
def parent(i):
return (i-1)/2
def left_child(i):
return 2*i+1
def right_child(i):
return 2*i+2
def is_leaf(L,i):
return (left_child(i) >= len(L)) and (right_child(i) >= len(L))
def one_child(L,i):
return (left_child(i) < len(L)) and (right_child(i) >= len(L))
# Call this routine if the heap rooted at i satisfies the heap property
# *except* perhaps i to its immediate children
def down_heapify(L, i):
# If i is a leaf, heap property holds
if is_leaf(L, i):
return
# If i has one child...
if one_child(L, i):
# check heap property
if L[i] > L[left_child(i)]:
# If it fails, swap, fixing i and its child (a leaf)
(L[i], L[left_child(i)]) = (L[left_child(i)], L[i])
return
# If i has two children...
# check heap property
if min(L[left_child(i)], L[right_child(i)]) >= L[i]:
return
# If it fails, see which child is the smaller
# and swap i's value into that child
# Afterwards, recurse into that child, which might violate
if L[left_child(i)] < L[right_child(i)]:
# Swap into left child
(L[i], L[left_child(i)]) = (L[left_child(i)], L[i])
down_heapify(L, left_child(i))
return
else:
(L[i], L[right_child(i)]) = (L[right_child(i)], L[i])
down_heapify(L, right_child(i))
return
#########
# Testing Code
#
# build_heap
def build_heap(L):
for i in range(len(L)-1, -1, -1):
down_heapify(L, i)
return L
def test():
L = range(10)
build_heap(L)
remove_min(L)
# now, the new minimum should be 1
assert L[0] == 1
print test()
olgabelitskaya (master) ~ $ cd version-control
olgabelitskaya (master *) version-control $ git status
On branch master
Your branch is up-to-date with 'exercises/master'.
Changes not staged for commit:
(use "git add <file>..." to update what will be committed)
(use "git checkout -- <file>..." to discard changes in working directory)
modified: reflections-cs215/lesson3_reflections_ob.txt
Untracked files:
(use "git add <file>..." to include in what will be committed)
reflections-cs215/lesson4_reflections_ob.txt
no changes added to commit (use "git add" and/or "git commit -a")
olgabelitskaya (master *) version-control $ git add 'reflections-cs215/lesson3_reflections_ob.txt'
olgabelitskaya (master +) version-control $ git commit -m "Update lesson3_reflections_ob.txt"
[master 1a4653b] Update lesson3_reflections_ob.txt
1 file changed, 45 insertions(+)
olgabelitskaya (master) version-control $ git add 'reflections-cs215/lesson4_reflections_ob.txt'
olgabelitskaya (master +) version-control $ git commit -m "Add reflections lesson 4"
[master 3814483] Add reflections lesson 4
1 file changed, 251 insertions(+)
create mode 100644 reflections-cs215/lesson4_reflections_ob.txt
olgabelitskaya (master) version-control $ git status
On branch master
Your branch is ahead of 'exercises/master' by 2 commits.
(use "git push" to publish your local commits)
nothing to commit, working directory clean
olgabelitskaya (master) version-control $ git push exercises master
Counting objects: 8, done.
Delta compression using up to 4 threads.
Compressing objects: 100% (8/8), done.
Writing objects: 100% (8/8), 5.27 KiB | 0 bytes/s, done.
Total 8 (delta 5), reused 0 (delta 0)
To https://github.com/OlgaBelitskaya/my-exercises.git
4443845..3814483 master -> master
PROBLEM SET 4
#1
heap = []
for v in vals:
insert_heap(heap,v)
Θ(n*log(n))
#2
#
# Given a list of numbers, L, find a number, x, that
# minimizes the sum of the absolute value of the difference
# between each element in L and x: SUM_{i=0}^{n-1} |L[i] - x|
#
# Your code should run in Theta(n) time
#
L = [12,83,15,27,35,7,64]
def minimize_absolute(L):
S = []
for element in L:
se = 0
for i in range(len(L)):
se = se + abs(L[i] - element)
S.append(se)
print S
k = min(S)
print k
ik = S.index(k)
# your code here
return L[ik]
print minimize_absolute(L)
#3
#
# Given a list of numbers, L, find a number, x, that
# minimizes the sum of the square of the difference
# between each element in L and x: SUM_{i=0}^{n-1} (L[i] - x)^2
#
# Your code should run in Theta(n) time
#
L = [2,2,3,4]
def minimize_square(L):
S = []
for element in L:
sq = 0
for j in range(len(L)):
se = element - L[j]
sq = sq + se*se
S.append(sq)
print S
k = min(S)
print k
ik = S.index(k)
# your code here
return L[ik]
print minimize_square(L)
#################################################################
L = [2,2,3,4]
def minimize_square(L):
S = {}
print L
for element in L:
sq = 0
for j in range(len(L)):
se = element - L[j]
sq = sq + se*se
S[element] = sq
print S
for key, value in S.iteritems():
if value == min(S.values()):
return key
print minimize_square(L)
#4
4.1
#
# Given a list L of n numbers, find the mode
# (the number that appears the most times).
# Your algorithm should run in Theta(n).
# If there are ties - just pick one value to return
#
from operator import itemgetter
def mode(L):
counts = {}
maxelement = None
maxn = 0
for element in L:
if element not in counts:
counts[element] = 1
else:
counts[element] += 1
if counts[element] > maxn:
maxelement = element
maxn = counts[element]
return maxelement
# your code here
####
# Test
#
import time
from random import randint
def test():
assert 5 == mode([1, 5, 2, 5, 3, 5])
iterations = (10, 20, 30, 100, 200, 300, 1000, 5000, 10000, 20000, 30000)
times = []
for i in iterations:
L = []
for j in range(i):
L.append(randint(1, 10))
start = time.clock()
for j in range(500):
mode(L)
end = time.clock()
print start, end
times.append(float(end - start))
slopes = []
for (x1, x2), (y1, y2) in zip(zip(iterations[:-1], iterations[1:]), zip(times[:-1], times[1:])):
print (x1, x2), (y1, y2)
slopes.append((y2 - y1) / (x2 - x1))
# if mode runs in linear time,
# these factors should be close (kind of)
print slopes
print test()
RESET TEST RUN SUBMIT
0.013615 0.014496
0.014539 0.016172
0.016212 0.018655
0.01876 0.027141
0.027386 0.04383
0.044145 0.068484
0.069518 0.150515
0.15572 0.553299
0.563656 1.339508
1.360104 2.902613
2.933505 5.293337
(10, 20) (0.0008809999999999998, 0.001632999999999999)
(20, 30) (0.001632999999999999, 0.0024430000000000007)
(30, 100) (0.0024430000000000007, 0.008381)
(100, 200) (0.008381, 0.016444)
(200, 300) (0.016444, 0.024339000000000006)
(300, 1000) (0.024339000000000006, 0.08099700000000001)
(1000, 5000) (0.08099700000000001, 0.397579)
(5000, 10000) (0.397579, 0.7758519999999999)
(10000, 20000) (0.7758519999999999, 1.5425090000000001)
(20000, 30000) (1.5425090000000001, 2.3598320000000004)
[7.519999999999992e-05, 8.100000000000017e-05, 8.482857142857141e-05, 8.063e-05, 7.895000000000006e-05, 8.094000000000001e-05, 7.914550000000001e-05, 7.565459999999997e-05, 7.666570000000002e-05, 8.173230000000003e-05]
None
##########################################################
4.2
from operator import itemgetter
from collections import defaultdict
def mode(L):
counts = defaultdict(int)
mode = None
maxn = 0
for e in L:
counts[e] += 1
current = counts[e]
if current > maxn:
mode = e
maxn = current
return mode
0.01416 0.01542
0.015468 0.017476
0.017512 0.020281
0.020391 0.027656
0.027869 0.041363
0.041676 0.061522
0.062561 0.12634
0.131508 0.457904
0.468202 1.123113
1.143701 2.454703
2.485846 4.46365
(10, 20) (0.001259999999999999, 0.0020079999999999976)
(20, 30) (0.0020079999999999976, 0.0027690000000000006)
(30, 100) (0.0027690000000000006, 0.007265000000000001)
(100, 200) (0.007265000000000001, 0.013493999999999996)
(200, 300) (0.013493999999999996, 0.019846000000000003)
(300, 1000) (0.019846000000000003, 0.063779)
(1000, 5000) (0.063779, 0.32639599999999996)
(5000, 10000) (0.32639599999999996, 0.654911)
(10000, 20000) (0.654911, 1.3110019999999998)
(20000, 30000) (1.3110019999999998, 1.9778040000000003)
[7.479999999999987e-05, 7.61000000000003e-05, 6.422857142857144e-05, 6.228999999999995e-05, 6.352000000000007e-05, 6.276142857142857e-05, 6.565425e-05, 6.570300000000002e-05, 6.560909999999998e-05, 6.668020000000006e-05]
None
#######################################################################
4.3
from operator import itemgetter
from collections import defaultdict
def mode(L):
amounts = defaultdict(int)
for v in L:
amounts[v] +=1
return max(amounts, key = lambda x: amounts[x])
0.014366 0.016016
0.016062 0.018403
0.018443 0.021367
0.021478 0.026966
0.027181 0.036292
0.036608 0.049343
0.050382 0.088166
0.093351 0.281401
0.297654 0.713603
0.734345 1.498868
1.529933 2.681095
(10, 20) (0.0016499999999999987, 0.0023409999999999993)
(20, 30) (0.0023409999999999993, 0.0029239999999999995)
(30, 100) (0.0029239999999999995, 0.005488)
(100, 200) (0.005488, 0.009110999999999998)
(200, 300) (0.009110999999999998, 0.012734999999999996)
(300, 1000) (0.012734999999999996, 0.03778399999999999)
(1000, 5000) (0.03778399999999999, 0.18805)
(5000, 10000) (0.18805, 0.415949)
(10000, 20000) (0.415949, 0.7645230000000001)
(20000, 30000) (0.7645230000000001, 1.151162)
[6.910000000000007e-05, 5.830000000000002e-05, 3.6628571428571435e-05, 3.622999999999998e-05, 3.6239999999999985e-05, 3.578428571428571e-05, 3.75665e-05, 4.557980000000001e-05, 3.48574e-05, 3.8663899999999994e-05]
None
##########################################################################
4.4
from operator import itemgetter
def mode(L):
values = set(L)
return max(values, key = lambda x: L.count(x))
0.013503 0.014766
0.014812 0.016569
0.016608 0.019108
0.019215 0.024997
0.025211 0.035604
0.035921 0.050884
0.051921 0.099694
0.104897 0.342236
0.352604 0.82273
0.843408 1.783683
1.814736 3.228627
(10, 20) (0.0012630000000000002, 0.0017569999999999999)
(20, 30) (0.0017569999999999999, 0.0024999999999999988)
(30, 100) (0.0024999999999999988, 0.005781999999999999)
(100, 200) (0.005781999999999999, 0.010392999999999996)
(200, 300) (0.010392999999999996, 0.014962999999999997)
(300, 1000) (0.014962999999999997, 0.047773)
(1000, 5000) (0.047773, 0.23733899999999997)
(5000, 10000) (0.23733899999999997, 0.470126)
(10000, 20000) (0.470126, 0.9402749999999999)
(20000, 30000) (0.9402749999999999, 1.413891)
[4.939999999999997e-05, 7.429999999999988e-05, 4.688571428571429e-05, 4.610999999999997e-05, 4.570000000000001e-05, 4.687142857142858e-05, 4.739149999999999e-05, 4.65574e-05, 4.701489999999999e-05, 4.736160000000002e-05]
None
###########################################################################
4.5
from operator import itemgetter
def mode(L):
return max(set(L), key = lambda x: L.count(x))
TEST RUN
0.013792 0.014963
0.015015 0.016845
0.016882 0.019399
0.019513 0.025268
0.025498 0.035938
0.036287 0.051412
0.052471 0.100546
0.105764 0.344642
0.355091 0.830679
0.851587 1.797449
1.828574 3.2462
(10, 20) (0.0011710000000000002, 0.0018299999999999983)
(20, 30) (0.0018299999999999983, 0.0025169999999999984)
(30, 100) (0.0025169999999999984, 0.005755)
(100, 200) (0.005755, 0.010439999999999998)
(200, 300) (0.010439999999999998, 0.015125)
(300, 1000) (0.015125, 0.048075)
(1000, 5000) (0.048075, 0.238878)
(5000, 10000) (0.238878, 0.47558799999999996)
(10000, 20000) (0.47558799999999996, 0.9458620000000001)
(20000, 30000) (0.9458620000000001, 1.417626)
[6.589999999999981e-05, 6.870000000000002e-05, 4.625714285714288e-05, 4.684999999999998e-05, 4.6850000000000014e-05, 4.707142857142857e-05, 4.770075e-05, 4.734199999999999e-05, 4.702740000000002e-05, 4.71764e-05]
None
#########################################################################
#5
#
# write up_heapify, an algorithm that checks if
# node i and its parent satisfy the heap
# property, swapping and recursing if they don't
#
# L should be a heap when up_heapify is done
#
def parent(i):
return (i-1)/2
def left_child(i):
return 2*i+1
def right_child(i):
return 2*i+2
def is_leaf(L,i):
return (left_child(i) >= len(L)) and (right_child(i) >= len(L))
def one_child(L,i):
return (left_child(i) < len(L)) and (right_child(i) >= len(L))
def up_heapify(L, i):
while L[i] < L[parent(i)] and parent(i) != -1:
print L
print i, L[i]
print parent(i), L[parent(i)]
(L[parent(i)], L[i]) = (L[i], L[parent(i)])
i = parent(i)
# your code here
return L
def test():
L = [2, 4, 3, 5, 9, 7, 7]
L.append(1)
up_heapify(L, 7)
assert 1 == L[0]
assert 2 == L[1]
print test()
TEST RUN
[2, 4, 3, 5, 9, 7, 7, 1]
7 1
3 5
[2, 4, 3, 1, 9, 7, 7, 5]
3 1
1 4
[2, 1, 3, 4, 9, 7, 7, 5]
1 1
0 2
None
#######################################################################
#6
import random
import csv
def make_link(G, node1, node2):
if node1 not in G:
G[node1] = {}
(G[node1])[node2] = 1
if node2 not in G:
G[node2] = {}
(G[node2])[node1] = 1
return G
def make_data(file_name):
data = scv.reader(open(file_name), delimiter='\t')
G = {}
actors = {}
movies = {}
for (actor, movie, year) in data:
movie_year = str(movie) + "," + str(year)
actors[actor] = 1
movies[movie_year] = 1
make_link(G, actor, movie_year)
return (G,actors,movies)
def centrality(G, v):
distance_from_start = {}
open_list = [v]
distance_from_start[v] = 0
while len(open_list) > 0:
current = open_list.pop(0)
for neighbor in G[current].keys():
if neighbor not in distance_from_start:
distance_from_start[neighbor] = distance_from_start[current] + 1
open_list.append(neighbor)
return (float(sum(distance_from_start.values())))/len(distance_from_start)
def rank(L,v):
rank = 0
for element in L:
if element < v:
rank += 1
return rank
def find_rank(L, t):
less_t = {}
equal_t = {}
greater_t = {}
v = random.choice(L.keys())
for t in L.keys():
if L[l] < L[v]:
less_t[t] = L[t]
elif L[t] == L[v]:
equal_t[t] = L[t]
elif L[t] > L[v]:
greater_t[t] = L[t]
if len(less_t) >= t: return find_rank(less_t,t)
elif len(less_t) + len(equal_t) >= t: return v
else: return find_rank(greater_t, t - len(less_t) - len(equal_t))
(G, actors, movies) = make_data(actors.tsv)
centralities = {}
for actor in actors.key():
centralities[actor] = centrality(G, actor)
actor_rank = firn_rank(centralities, 20)
print actor_rank
print centralities[actor_rank]
#######################################################################
Last login: Tue Jun 21 09:16:40 on console
olgabelitskaya (master) ~ $ cd version-control
olgabelitskaya (master *) version-control $ git status
On branch master
Your branch is up-to-date with 'exercises/master'.
Changes not staged for commit:
(use "git add <file>..." to update what will be committed)
(use "git checkout -- <file>..." to discard changes in working directory)
modified: reflections-cs215/lesson4_reflections_ob.txt
Untracked files:
(use "git add <file>..." to include in what will be committed)
reflections-cs215/lesson5_reflections_ob.rtf
no changes added to commit (use "git add" and/or "git commit -a")
olgabelitskaya (master *) version-control $ git add 'reflections-cs215/lesson4_reflections_ob.txt'
olgabelitskaya (master +) version-control $ git commit -m "Update lesson4_reflections_ob.txt"
[master b1ee03c] Update lesson4_reflections_ob.txt
1 file changed, 411 insertions(+), 1 deletion(-)
olgabelitskaya (master) version-control $ git add 'reflections-cs215/lesson5_reflections_ob.rtf'
olgabelitskaya (master +) version-control $ git commit -m "Create lesson5_reflections_ob.rtf"
[master 2ebe71b] Create lesson5_reflections_ob.rtf
1 file changed, 13 insertions(+)
create mode 100644 reflections-cs215/lesson5_reflections_ob.rtf
olgabelitskaya (master) version-control $ git push exercises master
Counting objects: 8, done.
Delta compression using up to 4 threads.
Compressing objects: 100% (8/8), done.
Writing objects: 100% (8/8), 8.07 KiB | 0 bytes/s, done.
Total 8 (delta 4), reused 0 (delta 0)
To https://github.com/OlgaBelitskaya/my-exercises.git
3814483..2ebe71b master -> master
Last login: Tue Jun 21 17:24:48 on ttys000
olgabelitskaya (master) ~ $ cd version-control
olgabelitskaya (master *) version-control $ git status
On branch master
Your branch is up-to-date with 'exercises/master'.
Changes not staged for commit:
(use "git add <file>..." to update what will be committed)
(use "git checkout -- <file>..." to discard changes in working directory)
modified: reflections-cs215/lesson3_reflections_ob.txt
modified: reflections-cs215/lesson4_reflections_ob.txt
no changes added to commit (use "git add" and/or "git commit -a")
olgabelitskaya (master *) version-control $ git add 'reflections-cs215/lesson3_reflections_ob.txt'
olgabelitskaya (master *+) version-control $ git add 'reflections-cs215/lesson4_reflections_ob.txt'
olgabelitskaya (master +) version-control $ git status
On branch master
Your branch is up-to-date with 'exercises/master'.
Changes to be committed:
(use "git reset HEAD <file>..." to unstage)
modified: reflections-cs215/lesson3_reflections_ob.txt
modified: reflections-cs215/lesson4_reflections_ob.txt
olgabelitskaya (master +) version-control $ git commit -m "Update lesson3_reflections_ob.txt and lesson4_reflections_ob.txt"
[master cfaa476] Update lesson3_reflections_ob.txt and lesson4_reflections_ob.txt
2 files changed, 120 insertions(+)
olgabelitskaya (master) version-control $ git push exercises master
Counting objects: 5, done.
Delta compression using up to 4 threads.
Compressing objects: 100% (5/5), done.
Writing objects: 100% (5/5), 8.32 KiB | 0 bytes/s, done.
Total 5 (delta 3), reused 0 (delta 0)
To https://github.com/OlgaBelitskaya/my-exercises.git
2ebe71b..cfaa476 master -> master
воскресенье, 26 июня 2016 г.
Intro to Algorithms 3: Basic Graph Algorithms Notes
https://www.udacity.com/course/viewer#!/c-cs215/l-48723544
LESSON 3
Clustering coefficient
In undirected networks, the clustering coefficient Cn of a node n is defined as Cn = 2en/(kn(kn-1)), where kn is the number of neighbors of n and en is the number of connected pairs between all neighbors of n. In directed networks, the definition is slightly different: Cn = en/(kn(kn-1)).
In both cases, the clustering coefficient is a ratio N / M, where N is the number of edges between the neighbors of n, and M is the maximum number of edges that could possibly exist between the neighbors of n. The clustering coefficient of a node is always a number between 0 and 1.
The network clustering coefficient is the average of the clustering coefficients for all nodes in the network. Here, nodes with less than two neighbors are assumed to have a clustering coefficient of 0.
Quiz: Clustering Coefficient Quiz
def make_link(G, node1, node2):
if node1 not in G:
G[node1] = {}
(G[node1])[node2] = 1
if node2 not in G:
G[node2] = {}
(G[node2])[node1] = 1
return G
flights = [("ORD", "SEA"), ("ORD", "LAX"), ('ORD', 'DFW'), ('ORD', 'PIT'),
('SEA', 'LAX'), ('LAX', 'DFW'), ('ATL', 'PIT'), ('ATL', 'RDU'),
('RDU', 'PHL'), ('PIT', 'PHL'), ('PHL', 'PVD')]
G = {}
for (x,y) in flights: make_link(G,x,y)
def clustering_coefficient(G,v):
neighbors = G[v].keys()
if len(neighbors) == 1: return -1.0
links = 0
for w in neighbors:
for u in neighbors:
if u in G[w]: links += 0.5
return 2.0*links/(len(neighbors)*(len(neighbors)-1))
print clustering_coefficient(G,"ORD")
total = 0
for v in G.keys():
total += clustering_coefficient(G,v)
print total/len(G)
http://stackoverflow.com/questions/10301000/python-connected-components
А function get_connected_components for a class Graph:
def get_connected_components(self):
path=[]
for i in self.graph.keys():
q=self.graph[i]
while q:
print(q)
v=q.pop(0)
if not v in path:
path=path+[v]
return path
the function returning a dictionary whose keys are the roots and whose values are the connected components:
def getRoots(aNeigh):
def findRoot(aNode,aRoot):
while aNode != aRoot[aNode][0]:
aNode = aRoot[aNode][0]
return (aNode,aRoot[aNode][1])
myRoot = {}
for myNode in aNeigh.keys():
myRoot[myNode] = (myNode,0)
for myI in aNeigh:
for myJ in aNeigh[myI]:
(myRoot_myI,myDepthMyI) = findRoot(myI,myRoot)
(myRoot_myJ,myDepthMyJ) = findRoot(myJ,myRoot)
if myRoot_myI != myRoot_myJ:
myMin = myRoot_myI
myMax = myRoot_myJ
if myDepthMyI > myDepthMyJ:
myMin = myRoot_myJ
myMax = myRoot_myI
myRoot[myMax] = (myMax,max(myRoot[myMin][1]+1,myRoot[myMax][1]))
myRoot[myMin] = (myRoot[myMax][0],-1)
myToRet = {}
for myI in aNeigh:
if myRoot[myI][0] == myI:
myToRet[myI] = []
for myI in aNeigh:
myToRet[findRoot(myI,myRoot)[0]].append(myI)
return myToRet
https://breakingcode.wordpress.com/2013/04/08/finding-connected-components-in-a-graph/
example-connected-components.py
#!/usr/bin/env python
# Finding connected components in a bidirectional graph.
# By Mario Vilas (mvilas at gmail dot com)
# The graph nodes.
class Data(object):
def __init__(self, name):
self.__name = name
self.__links = set()
@property
def name(self):
return self.__name
@property
def links(self):
return set(self.__links)
def add_link(self, other):
self.__links.add(other)
other.__links.add(self)
# The function to look for connected components.
def connected_components(nodes):
# List of connected components found. The order is random.
result = []
# Make a copy of the set, so we can modify it.
nodes = set(nodes)
# Iterate while we still have nodes to process.
while nodes:
# Get a random node and remove it from the global set.
n = nodes.pop()
# This set will contain the next group of nodes connected to each other.
group = {n}
# Build a queue with this node in it.
queue = [n]
# Iterate the queue.
# When it's empty, we finished visiting a group of connected nodes.
while queue:
# Consume the next item from the queue.
n = queue.pop(0)
# Fetch the neighbors.
neighbors = n.links
# Remove the neighbors we already visited.
neighbors.difference_update(group)
# Remove the remaining nodes from the global set.
nodes.difference_update(neighbors)
# Add them to the group of connected nodes.
group.update(neighbors)
# Add them to the queue, so we visit them in the next iterations.
queue.extend(neighbors)
# Add the group to the list of groups.
result.append(group)
# Return the list of groups.
return result
##################################################################
# Traversal...
# Call this routine on nodes being visited for the first time
def mark_component(G, node, marked):
marked[node] = True
total_marked = 1
for neighbor in G[node]:
if neighbor not in marked:
total_marked += mark_component(G, neighbor, marked)
return total_marked
def check_connection(G, v1, v2):
marked = {}
mark_component(G, v1, marked)
print mark_component(G, v1, marked)
print marked
if v2 not in marked:
return False
# Return True if v1 is connected to v2 in G
# or False if otherwise
return True
def make_link(G, node1, node2):
if node1 not in G:
G[node1] = {}
(G[node1])[node2] = 1
if node2 not in G:
G[node2] = {}
(G[node2])[node1] = 1
return G
def test():
edges = [('a', 'g'), ('a', 'd'), ('g', 'c'), ('g', 'd'),
('b', 'f'), ('f', 'e'), ('e', 'h')]
G = {}
for v1, v2 in edges:
make_link(G, v1, v2)
assert check_connection(G, "a", "c") == True
assert check_connection(G, 'a', 'b') == False
print test()
def dfs(graph, start):
visited, stack = set(), [start]
while stack:
vertex = stack.pop()
if vertex not in visited:
visited.add(vertex)
stack.extend(graph[vertex] - visited)
return visited
def dfs(graph, start, visited=None):
if visited is None:
visited = set()
visited.add(start)
for next in graph[start] - visited:
dfs(graph, next, visited)
return visited
def dfs_paths(graph, start, goal):
stack = [(start, [start])]
while stack:
(vertex, path) = stack.pop()
for next in graph[vertex] - set(path):
if next == goal:
yield path + [next]
else:
stack.append((next, path + [next]))
def dfs_paths(graph, start, goal, path=None):
if path is None:
path = [start]
if start == goal:
yield path
for next in graph[start] - set(path):
yield from dfs_paths(graph, next, goal, path + [next])
list(dfs_paths(graph, 'C', 'F')) # [['C', 'F'], ['C', 'A', 'B', 'E', 'F']]
###########################################################################
from pythonds.graphs import Graph
class DFSGraph(Graph):
def __init__(self):
super().__init__()
self.time = 0
def dfs(self):
for aVertex in self:
aVertex.setColor('white')
aVertex.setPred(-1)
for aVertex in self:
if aVertex.getColor() == 'white':
self.dfsvisit(aVertex)
def dfsvisit(self,startVertex):
startVertex.setColor('gray')
self.time += 1
startVertex.setDiscovery(self.time)
for nextVertex in startVertex.getConnections():
if nextVertex.getColor() == 'white':
nextVertex.setPred(startVertex)
self.dfsvisit(nextVertex)
startVertex.setColor('black')
self.time += 1
startVertex.setFinish(self.time)
###########################################################################
def bfs(graph, start):
visited, queue = set(), [start]
while queue:
vertex = queue.pop(0)
if vertex not in visited:
visited.add(vertex)
queue.extend(graph[vertex] - visited)
return visited
def bfs_paths(graph, start, goal):
queue = [(start, [start])]
while queue:
(vertex, path) = queue.pop(0)
for next in graph[vertex] - set(path):
if next == goal:
yield path + [next]
else:
queue.append((next, path + [next]))
list(bfs_paths(graph, 'A', 'F')) # [['A', 'C', 'F'], ['A', 'B', 'E', 'F']]
def shortest_path(graph, start, goal):
try:
return next(bfs_paths(graph, start, goal))
except StopIteration:
return None
shortest_path(graph, 'A', 'F') # ['A', 'C','F']
#########################################################################
from pythonds.graphs import Graph, Vertex
from pythonds.basic import Queue
def bfs(g,start):
start.setDistance(0)
start.setPred(None)
vertQueue = Queue()
vertQueue.enqueue(start)
while (vertQueue.size() > 0):
currentVert = vertQueue.dequeue()
for nbr in currentVert.getConnections():
if (nbr.getColor() == 'white'):
nbr.setColor('gray')
nbr.setDistance(currentVert.getDistance() + 1)
nbr.setPred(currentVert)
vertQueue.enqueue(nbr)
currentVert.setColor('black')
#########################################################################
In graph theory, the shortest path problem is the problem of finding a path between two vertices (or nodes) in a graph such that the sum of the weights of its constituent edges is minimized.
The problem of finding the shortest path between two intersections on a road map (the graph's vertices correspond to intersections and the edges correspond to road segments, each weighted by the length of its road segment) may be modeled by a special case of the shortest path problem in graphs.
An algorithm for finding a graph geodesic, i.e., the shortest path between two graph vertices in a graph. It functions by constructing a shortest-path tree from the initial vertex to every other vertex in the graph. The algorithm is implemented as Dijkstra[g] in the Wolfram Language package Combinatorica` .
The worst-case running time for the Dijkstra algorithm on a graph with n nodes and m edges is O(n^2) because it allows for directed cycles. It even finds the shortest paths from a source node s to all other nodes in the graph. This is basically O(n^2) for node selection and O(m) for distance updates. While O(n^2) is the best possible complexity for dense graphs, the complexity can be improved significantly for sparse graphs.
With slight modifications, Dijkstra's algorithm can be used as a reverse algorithm that maintains minimum spanning trees for the sink node. With further modifications, it can be extended to become bidirectional.
The bottleneck in Dijkstra's algorithm is node selection. However, using Dial's implementation, this can be significantly improved for sparse graphs.
A bridge of a connected graph is a graph edge whose removal disconnects the graph (Chartrand 1985, p. 45; Skiena 1990, p. 177). More generally, a bridge is an edge of a graph G whose removal increases the number of components of G (Harary 1994, p. 26). An edge of a connected graph is a bridge iff it does not lie on any cycle.
A bridge is also known as an isthmus, cut-edge, or cut arc.
A graph containing one or more bridges is said to be a bridged graph, while a graph containing no bridges is called a bridgeless graph.
The bridges of a graph can be found using Bridges[g] in the Wolfram Language package Combinatorica` . Precomputed bridges for many named graphs can be obtained using GraphData[graph, "Bridges"].
Every edge of a tree is a bridge.
A connected cubic graph contains a bridge iff it contains an articulation vertex (Skiena 1990, p. 177), i.e., if it is not a biconnected graph.
PROBLEM SET 3
#1
c 5 0 0
b 7 2 0.09523809524
f 5 2 0.2
e 7 7 0.3333333333
a 5 5 0.5
d 4 6 1
kv nv ccv
#2
A bipartite graph (or bigraph) is a graph whose vertices can be divided into two disjoint sets U and V (that is, U and V are each independent sets) such that every edge connects a vertex in U to one in V. Vertex sets U and V are usually called the parts of the graph. Equivalently, a bipartite graph is a graph that does not contain any odd-length cycles.
Every tree is bipartite.
Cycle graphs with an even number of vertices are bipartite.
Every planar graph whose faces all have even length is bipartite. Special cases of this are grid graphs and squaregraphs, in which every inner face consists of 4 edges and every inner vertex has four or more neighbors.
The complete bipartite graph on m and n vertices, denoted by Kn,m is the bipartite graph G = (U, V, E), where U and V are disjoint sets of size m and n, respectively, and E connects every vertex in U with all vertices in V. It follows that Km,n has mn edges. Closely related to the complete bipartite graphs are the crown graphs, formed from complete bipartite graphs by removing the edges of a perfect matching.
Hypercube graphs, partial cubes, and median graphs are bipartite. In these graphs, the vertices may be labeled by bitvectors, in such a way that two vertices are adjacent if and only if the corresponding bitvectors differ in a single position. A bipartition may be formed by separating the vertices whose bitvectors have an even number of ones from the vertices with an odd number of ones. Trees and squaregraphs form examples of median graphs, and every median graph is a partial cube.
################################################################
Consider a bipartite graph, that has 5 nodes in one group and 3 in the other:
- what is the smallest number of edges to make the graph have a single reachable component consisting of all the nodes?
7
#3
- whites the maximum number of edges the graph can have?
5*3 = 15
#4
- what is the maximum possible path length in the graph?
6
#5
- what is the maximum possible clustering coefficient for a node in the graph (nodes degree >=2)?
2*0/Kv = 0
#6
# Rewrite `mark_component` to not use recursion
# and instead use the `open_list` data structure
# discussed in lecture
#
def mark_component(G, node, marked):
marked[node] = True
total_marked = 1
for neighbor in G[node]:
if neighbor not in marked:
total_marked = total_marked + 1
marked[neighbor] = True
for element in G[neighbor]:
if element not in marked:
total_marked = total_marked + 1
marked[element] = True
return total_marked
#########
# Code for testing
#
def make_link(G, node1, node2):
if node1 not in G:
G[node1] = {}
(G[node1])[node2] = 1
if node2 not in G:
G[node2] = {}
(G[node2])[node1] = 1
return G
def test():
test_edges = [(1, 2), (2, 3), (4, 5), (5, 6)]
G = {}
for n1, n2 in test_edges:
make_link(G, n1, n2)
marked = {}
assert mark_component(G, 1, marked) == 3
assert 1 in marked
assert 2 in marked
assert 3 in marked
assert 4 not in marked
assert 5 not in marked
assert 6 not in marked
print test()
#7
The Maximum Betweenness Centrality problem (MBC)can be defined as follows. Given a graph find a k-element node set C that maximizes the probability of detecting communication between a pair of nodes s and t chosen uniformly at random. It is assumed that the communication between s and t is realized along a shortest s–t path which is, again, selected uniformly at random. The communication is detected if the communication path contains a node of C.
#
# Write centrality_max to return the maximum distance
# from a node to all the other nodes it can reach
#
def centrality_max(G, v):
distance_from_start = {}
open_list = [v]
distance_from_start[v] = 0
while len(open_list) >0:
current = open_list[0]
del open_list[0]
for neighbor in G[current].keys():
if neighbor not in distance_from_start:
distance_from_start[neighbor] = distance_from_start[current] + 1
open_list.append(neighbor)
print distance_from_start
return max(distance_from_start.values())
# your code here
#################
# Testing code
#
def make_link(G, node1, node2):
if node1 not in G:
G[node1] = {}
(G[node1])[node2] = 1
if node2 not in G:
G[node2] = {}
(G[node2])[node1] = 1
return G
def test():
chain = ((1,2), (2,3), (3,4), (4,5), (5,6))
G = {}
for n1, n2 in chain:
make_link(G, n1, n2)
assert centrality_max(G, 1) == 5
assert centrality_max(G, 3) == 3
tree = ((1, 2), (1, 3),
(2, 4), (2, 5),
(3, 6), (3, 7),
(4, 8), (4, 9),
(6, 10), (6, 11))
G = {}
for n1, n2 in tree:
make_link(G, n1, n2)
assert centrality_max(G, 1) == 3
assert centrality_max(G, 11) == 6
print test()
#8
#########################################################################
for checking
############################################################################
# Bridge Edges v4
#
# Find the bridge edges in a graph given the
# algorithm in lecture.
# Complete the intermediate steps
# - create_rooted_spanning_tree
# - post_order
# - number_of_descendants
# - lowest_post_order
# - highest_post_order
#
# And then combine them together in
# `bridge_edges`
# So far, we've represented graphs
# as a dictionary where G[n1][n2] == 1
# meant there was an edge between n1 and n2
#
# In order to represent a spanning tree
# we need to create two classes of edges
# we'll refer to them as "green" and "red"
# for the green and red edges as specified in lecture
#
# So, for example, the graph given in lecture
# G = {'a': {'c': 1, 'b': 1},
# 'b': {'a': 1, 'd': 1},
# 'c': {'a': 1, 'd': 1},
# 'd': {'c': 1, 'b': 1, 'e': 1},
# 'e': {'d': 1, 'g': 1, 'f': 1},
# 'f': {'e': 1, 'g': 1},
# 'g': {'e': 1, 'f': 1}
# }
# would be written as a spanning tree
# S = {'a': {'c': 'green', 'b': 'green'},
# 'b': {'a': 'green', 'd': 'red'},
# 'c': {'a': 'green', 'd': 'green'},
# 'd': {'c': 'green', 'b': 'red', 'e': 'green'},
# 'e': {'d': 'green', 'g': 'green', 'f': 'green'},
# 'f': {'e': 'green', 'g': 'red'},
# 'g': {'e': 'green', 'f': 'red'}
# }
#
def make_link_color(G, node1, node2, red_green):
if node1 not in G:
G[node1] = {}
(G[node1])[node2] = red_green
if node2 not in G:
G[node2] = {}
(G[node2])[node1] = red_green
return G
def get_children(S, root, parent):
return [n for n, e in S[root].items() if ((not n == parent) and (e == 'green'))]
def get_children_all(S, root, parent):
green = []
red = []
for n, e in S[root].items():
if n == parent:
continue
if e == 'green':
green.append(n)
if e == 'red':
red.append(n)
return green, red
def create_rooted_spanning_tree(G, root):
open_list = [root]
S = {}
S[root] = {}
while len(open_list) > 0:
node = open_list.pop()
neighbors = G[node]
for n in neighbors:
if n not in S:
make_link_color(S, node, n, 'green')
open_list.append(n)
else:
if node not in S[n]:
make_link_color(S, node, n, 'red')
# your code here
return S
# This is just one possible solution
# There are other ways to create a
# spanning tree, and the grader will
# accept any valid result
# feel free to edit the test to
# match the solution your program produces
def test_create_rooted_spanning_tree():
G = {'a': {'c': 1, 'b': 1},
'b': {'a': 1, 'd': 1},
'c': {'a': 1, 'd': 1},
'd': {'c': 1, 'b': 1, 'e': 1},
'e': {'d': 1, 'g': 1, 'f': 1},
'f': {'e': 1, 'g': 1},
'g': {'e': 1, 'f': 1}
}
S = create_rooted_spanning_tree(G, "a")
assert S == {'a': {'c': 'green', 'b': 'green'},
'b': {'a': 'green', 'd': 'red'},
'c': {'a': 'green', 'd': 'green'},
'd': {'c': 'green', 'b': 'red', 'e': 'green'},
'e': {'d': 'green', 'g': 'green', 'f': 'green'},
'f': {'e': 'green', 'g': 'red'},
'g': {'e': 'green', 'f': 'red'}
}
print test_create_rooted_spanning_tree()
###########
def _post_order(S, root, parent, val, po):
children = get_children(S, root, parent)
for c in children:
val = _post_order(S, c, root, val, po)
po[root] = val
return val + 1
def post_order(S, root):
# return mapping between nodes of S and the post-order value
# of that node
po = {}
_post_order(S, root, None, 1, po)
return po
# This is just one possible solution
# There are other ways to create a
# spanning tree, and the grader will
# accept any valid result.
# feel free to edit the test to
# match the solution your program produces
def test_post_order():
S = {'a': {'c': 'green', 'b': 'green'},
'b': {'a': 'green', 'd': 'red'},
'c': {'a': 'green', 'd': 'green'},
'd': {'c': 'green', 'b': 'red', 'e': 'green'},
'e': {'d': 'green', 'g': 'green', 'f': 'green'},
'f': {'e': 'green', 'g': 'red'},
'g': {'e': 'green', 'f': 'red'}
}
po = post_order(S, 'a')
assert po == {'a':7, 'b':1, 'c':6, 'd':5, 'e':4, 'f':2, 'g':3}
##############
def pre_number_descendants(S, root, parent, nd):
children = get_children(S, root, parent)
nd_val = 1
for c in children:
nd_val += pre_number_descendants(S, c, root, nd)
nd[root] = nd_val
return nd_val
def number_of_descendants(S, root):
nd = {}
pre_number_descendants(S, root, None, nd)
return nd
# return mapping between nodes of S and the number of descendants
# of that node
def test_number_of_descendants():
S = {'a': {'c': 'green', 'b': 'green'},
'b': {'a': 'green', 'd': 'red'},
'c': {'a': 'green', 'd': 'green'},
'd': {'c': 'green', 'b': 'red', 'e': 'green'},
'e': {'d': 'green', 'g': 'green', 'f': 'green'},
'f': {'e': 'green', 'g': 'red'},
'g': {'e': 'green', 'f': 'red'}
}
nd = number_of_descendants(S, 'a')
assert nd == {'a':7, 'b':1, 'c':5, 'd':4, 'e':3, 'f':1, 'g':1}
###############
def general_post_order(S, root, parent, po, gpo, comp):
green, red = get_children_all(S, root, parent)
val = po[root]
for c in green:
test = general_post_order(S, c, root, po, gpo, comp)
if comp(val, test):
val = test
for c in red:
test = po[c]
if comp(val, test):
val = test
gpo[root] = val
return val
def lowest_post_order(S, root, po):
lpo = {}
general_post_order(S, root, None, po, lpo, lambda x, y: x > y)
return lpo
def highest_post_order(S, root, po):
hpo = {}
general_post_order(S, root, None, po, hpo, lambda x, y: x < y)
return hpo
def test_lowest_post_order():
S = {'a': {'c': 'green', 'b': 'green'},
'b': {'a': 'green', 'd': 'red'},
'c': {'a': 'green', 'd': 'green'},
'd': {'c': 'green', 'b': 'red', 'e': 'green'},
'e': {'d': 'green', 'g': 'green', 'f': 'green'},
'f': {'e': 'green', 'g': 'red'},
'g': {'e': 'green', 'f': 'red'}
}
po = post_order(S, 'a')
l = lowest_post_order(S, 'a', po)
assert l == {'a':1, 'b':1, 'c':1, 'd':1, 'e':2, 'f':2, 'g':2}
def test_highest_post_order():
S = {'a': {'c': 'green', 'b': 'green'},
'b': {'a': 'green', 'd': 'red'},
'c': {'a': 'green', 'd': 'green'},
'd': {'c': 'green', 'b': 'red', 'e': 'green'},
'e': {'d': 'green', 'g': 'green', 'f': 'green'},
'f': {'e': 'green', 'g': 'red'},
'g': {'e': 'green', 'f': 'red'}
}
po = post_order(S, 'a')
h = highest_post_order(S, 'a', po)
assert h == {'a':7, 'b':5, 'c':6, 'd':5, 'e':4, 'f':3, 'g':3}
#################
def bridge_edges(G, root):
# use the four functions above
# and then determine which edges in G are bridge edges
# return them as a list of tuples ie: [(n1, n2), (n4, n5)]
S = create_rooted_spanning_tree(G, root)
po = post_order(S, root)
nd = number_of_descendants(S, root)
lpo = lowest_post_order(S, root, po)
hpo = highest_post_order(S, root, po)
bridges = []
open_list = [(root, None)]
while len(open_list) > 0:
node, parent = open_list.pop()
for child in get_children(S, node, parent):
if hpo[child] <= po[child] and lpo[child] > (po[child] - nd[child]):
bridges.append((node, child))
open_list.append((child, node))
return bridges
def test_bridge_edges():
G = {'a': {'c': 1, 'b': 1},
'b': {'a': 1, 'd': 1},
'c': {'a': 1, 'd': 1},
'd': {'c': 1, 'b': 1, 'e': 1},
'e': {'d': 1, 'g': 1, 'f': 1},
'f': {'e': 1, 'g': 1},
'g': {'e': 1, 'f': 1}
}
bridges = bridge_edges(G, 'a')
assert bridges == [('d', 'e')]
print test_post_order()
print test_number_of_descendants()
print test_lowest_post_order()
print test_highest_post_order()
print test_bridge_edges()
#############################################
the right decision
#############################################
# Bridge Edges v4
#
# Find the bridge edges in a graph given the
# algorithm in lecture.
# Complete the intermediate steps
# - create_rooted_spanning_tree
# - post_order
# - number_of_descendants
# - lowest_post_order
# - highest_post_order
#
# And then combine them together in
# `bridge_edges`
# So far, we've represented graphs
# as a dictionary where G[n1][n2] == 1
# meant there was an edge between n1 and n2
#
# In order to represent a spanning tree
# we need to create two classes of edges
# we'll refer to them as "green" and "red"
# for the green and red edges as specified in lecture
#
# So, for example, the graph given in lecture
# G = {'a': {'c': 1, 'b': 1},
# 'b': {'a': 1, 'd': 1},
# 'c': {'a': 1, 'd': 1},
# 'd': {'c': 1, 'b': 1, 'e': 1},
# 'e': {'d': 1, 'g': 1, 'f': 1},
# 'f': {'e': 1, 'g': 1},
# 'g': {'e': 1, 'f': 1}
# }
# would be written as a spanning tree
# S = {'a': {'c': 'green', 'b': 'green'},
# 'b': {'a': 'green', 'd': 'red'},
# 'c': {'a': 'green', 'd': 'green'},
# 'd': {'c': 'green', 'b': 'red', 'e': 'green'},
# 'e': {'d': 'green', 'g': 'green', 'f': 'green'},
# 'f': {'e': 'green', 'g': 'red'},
# 'g': {'e': 'green', 'f': 'red'}
# }
#
#
# First some utility functions
#
def make_link(G, node1, node2, r_or_g):
# modified make_link to apply
# a color to the edge instead of just 1
if node1 not in G:
G[node1] = {}
(G[node1])[node2] = r_or_g
if node2 not in G:
G[node2] = {}
(G[node2])[node1] = r_or_g
return G
def get_children(S, root, parent):
"""returns the children from following the
green edges"""
return [n for n, e in S[root].items()
if ((not n == parent) and
(e == 'green'))]
def get_children_all(S, root, parent):
"""returns the children from following
green edges and the children from following
red edges"""
green = []
red = []
for n, e in S[root].items():
if n == parent:
continue
if e == 'green':
green.append(n)
if e == 'red':
red.append(n)
return green, red
#################
def create_rooted_spanning_tree(G, root):
# use DFS from the root to add edges and nodes
# to the tree. The first time we see a node
# the edge is green, but after that its red
open_list = [root]
S = {root:{}}
while len(open_list) > 0:
node = open_list.pop()
neighbors = G[node]
for n in neighbors:
if n not in S:
# we haven't seen this node, so
# need to use a green edge to connect
# it
make_link(S, node, n, 'green')
open_list.append(n)
else:
# we have seen this node,
# but, first make sure that
# don't already have the edge
# in S
if node not in S[n]:
make_link(S, node, n, 'red')
return S
##################
def _post_order(S, root, parent, val, po):
children = get_children(S, root, parent)
for c in children:
val = _post_order(S, c, root, val, po)
po[root] = val
return val + 1
def post_order(S, root):
po = {}
_post_order(S, root, None, 1, po)
return po
##################
def _number_descendants(S, root, parent, nd):
# number of descendants is the
# sum of the number of descendants of a nodes
# children plus one
children = get_children(S, root, parent)
nd_val = 1
for c in children:
# recursively calculate the number of descendants
# for the children
nd_val += _number_descendants(S, c, root, nd)
nd[root] = nd_val
return nd_val
def number_of_descendants(S, root):
nd = {}
_number_descendants(S, root, None, nd)
return nd
#
# Since highest and lowest post order will follow
# a similar method, I only wrote one method
# that can be used for both
#
def _general_post_order(S, root, parent, po, gpo, comp):
green, red = get_children_all(S, root, parent)
val = po[root]
for c in green:
# recursively find the low/high post order value of the children
test = _general_post_order(S, c, root, po, gpo, comp)
# and save the low/highest one
if comp(val, test):
val = test
for c in red:
test = po[c]
# and also look at the direct children
# from following red edges
# and save the low/highest one if needed
if comp(val, test):
val = test
gpo[root] = val
return val
def lowest_post_order(S, root, po):
lpo = {}
_general_post_order(S, root, None, po, lpo, lambda x, y: x > y)
return lpo
def highest_post_order(S, root, po):
hpo = {}
_general_post_order(S, root, None, po, hpo, lambda x, y: x < y)
return hpo
#
# Now put everything together
#
def bridge_edges(G, root):
S = create_rooted_spanning_tree(G, root)
po = post_order(S, root)
nd = number_of_descendants(S, root)
lpo = lowest_post_order(S, root, po)
hpo = highest_post_order(S, root, po)
bridges = []
open_list = [(root, None)]
# walk down the tree and see which edges are
# tree edges
while len(open_list) > 0:
node, parent = open_list.pop()
for child in get_children(S, node, parent):
# all of these edges are automatically green (get_children only
# follows green edges)
# so only need to check the other two conditions
if hpo[child] <= po[child] and lpo[child] > (po[child] - nd[child]):
bridges.append((node, child))
open_list.append((child, node))
return bridges
def test_create_rooted_spanning_tree():
G = {'a': {'c': 1, 'b': 1},
'b': {'a': 1, 'd': 1},
'c': {'a': 1, 'd': 1},
'd': {'c': 1, 'b': 1, 'e': 1},
'e': {'d': 1, 'g': 1, 'f': 1},
'f': {'e': 1, 'g': 1},
'g': {'e': 1, 'f': 1}
}
S = create_rooted_spanning_tree(G, "a")
assert S == {'a': {'c': 'green', 'b': 'green'},
'b': {'a': 'green', 'd': 'red'},
'c': {'a': 'green', 'd': 'green'},
'd': {'c': 'green', 'b': 'red', 'e': 'green'},
'e': {'d': 'green', 'g': 'green', 'f': 'green'},
'f': {'e': 'green', 'g': 'red'},
'g': {'e': 'green', 'f': 'red'}
}
def test_post_order():
S = {'a': {'c': 'green', 'b': 'green'},
'b': {'a': 'green', 'd': 'red'},
'c': {'a': 'green', 'd': 'green'},
'd': {'c': 'green', 'b': 'red', 'e': 'green'},
'e': {'d': 'green', 'g': 'green', 'f': 'green'},
'f': {'e': 'green', 'g': 'red'},
'g': {'e': 'green', 'f': 'red'}
}
po = post_order(S, 'a')
assert po == {'a':7, 'b':1, 'c':6, 'd':5, 'e':4, 'f':2, 'g':3}
def test_lowest_post_order():
S = {'a': {'c': 'green', 'b': 'green'},
'b': {'a': 'green', 'd': 'red'},
'c': {'a': 'green', 'd': 'green'},
'd': {'c': 'green', 'b': 'red', 'e': 'green'},
'e': {'d': 'green', 'g': 'green', 'f': 'green'},
'f': {'e': 'green', 'g': 'red'},
'g': {'e': 'green', 'f': 'red'}
}
po = post_order(S, 'a')
l = lowest_post_order(S, 'a', po)
assert l == {'a':1, 'b':1, 'c':1, 'd':1, 'e':2, 'f':2, 'g':2}
def test_highest_post_order():
S = {'a': {'c': 'green', 'b': 'green'},
'b': {'a': 'green', 'd': 'red'},
'c': {'a': 'green', 'd': 'green'},
'd': {'c': 'green', 'b': 'red', 'e': 'green'},
'e': {'d': 'green', 'g': 'green', 'f': 'green'},
'f': {'e': 'green', 'g': 'red'},
'g': {'e': 'green', 'f': 'red'}
}
po = post_order(S, 'a')
h = highest_post_order(S, 'a', po)
assert h == {'a':7, 'b':5, 'c':6, 'd':5, 'e':4, 'f':3, 'g':3}
def test_bridge_edges():
G = {'a': {'c': 1, 'b': 1},
'b': {'a': 1, 'd': 1},
'c': {'a': 1, 'd': 1},
'd': {'c': 1, 'b': 1, 'e': 1},
'e': {'d': 1, 'g': 1, 'f': 1},
'f': {'e': 1, 'g': 1},
'g': {'e': 1, 'f': 1}
}
bridges = bridge_edges(G, 'a')
assert bridges == [('d', 'e')]
Last login: Sun Jun 19 21:42:20 on ttys000
olgabelitskaya (master) ~ $ cd version-control
olgabelitskaya (master *) version-control $ git status
On branch master
Your branch is up-to-date with 'exercises/master'.
Changes not staged for commit:
(use "git add <file>..." to update what will be committed)
(use "git checkout -- <file>..." to discard changes in working directory)
modified: reflections-cs215/lesson1_reflections_ob.txt
modified: reflections-cs215/lesson2_reflections_ob.txt
Untracked files:
(use "git add <file>..." to include in what will be committed)
reflections-cs215/lesson3_reflections_ob.txt
no changes added to commit (use "git add" and/or "git commit -a")
olgabelitskaya (master *) version-control $ git add 'reflections-cs215/lesson1_reflections_ob.txt'
olgabelitskaya (master *+) version-control $ git commit -m "Update lesson1_reflections_ob.txt"
[master fc7da20] Update lesson1_reflections_ob.txt
1 file changed, 42 insertions(+)
olgabelitskaya (master *) version-control $ git add 'reflections-cs215/lesson2_reflections_ob.txt'
olgabelitskaya (master +) version-control $ git commit -m "Update reflections-cs215/lesson2_reflections_ob.txt"
[master 2d84b30] Update reflections-cs215/lesson2_reflections_ob.txt
1 file changed, 40 insertions(+), 1 deletion(-)
olgabelitskaya (master) version-control $ git add 'reflections-cs215/lesson3_reflections_ob.txt'
olgabelitskaya (master +) version-control $ git commit -m "Add reflections for lesson 3"
[master 4443845] Add reflections for lesson 3
1 file changed, 1040 insertions(+)
create mode 100644 reflections-cs215/lesson3_reflections_ob.txt
olgabelitskaya (master) version-control $ git status
On branch master
Your branch is ahead of 'exercises/master' by 3 commits.
(use "git push" to publish your local commits)
nothing to commit, working directory clean
olgabelitskaya (master) version-control $ git push exercises master
Counting objects: 12, done.
Delta compression using up to 4 threads.
Compressing objects: 100% (12/12), done.
Writing objects: 100% (12/12), 13.32 KiB | 0 bytes/s, done.
Total 12 (delta 6), reused 0 (delta 0)
To https://github.com/OlgaBelitskaya/my-exercises.git
1777e02..4443845 master -> master
LESSON 3
Clustering coefficient
In undirected networks, the clustering coefficient Cn of a node n is defined as Cn = 2en/(kn(kn-1)), where kn is the number of neighbors of n and en is the number of connected pairs between all neighbors of n. In directed networks, the definition is slightly different: Cn = en/(kn(kn-1)).
In both cases, the clustering coefficient is a ratio N / M, where N is the number of edges between the neighbors of n, and M is the maximum number of edges that could possibly exist between the neighbors of n. The clustering coefficient of a node is always a number between 0 and 1.
The network clustering coefficient is the average of the clustering coefficients for all nodes in the network. Here, nodes with less than two neighbors are assumed to have a clustering coefficient of 0.
Quiz: Clustering Coefficient Quiz
def make_link(G, node1, node2):
if node1 not in G:
G[node1] = {}
(G[node1])[node2] = 1
if node2 not in G:
G[node2] = {}
(G[node2])[node1] = 1
return G
flights = [("ORD", "SEA"), ("ORD", "LAX"), ('ORD', 'DFW'), ('ORD', 'PIT'),
('SEA', 'LAX'), ('LAX', 'DFW'), ('ATL', 'PIT'), ('ATL', 'RDU'),
('RDU', 'PHL'), ('PIT', 'PHL'), ('PHL', 'PVD')]
G = {}
for (x,y) in flights: make_link(G,x,y)
def clustering_coefficient(G,v):
neighbors = G[v].keys()
if len(neighbors) == 1: return -1.0
links = 0
for w in neighbors:
for u in neighbors:
if u in G[w]: links += 0.5
return 2.0*links/(len(neighbors)*(len(neighbors)-1))
print clustering_coefficient(G,"ORD")
total = 0
for v in G.keys():
total += clustering_coefficient(G,v)
print total/len(G)
http://stackoverflow.com/questions/10301000/python-connected-components
А function get_connected_components for a class Graph:
def get_connected_components(self):
path=[]
for i in self.graph.keys():
q=self.graph[i]
while q:
print(q)
v=q.pop(0)
if not v in path:
path=path+[v]
return path
the function returning a dictionary whose keys are the roots and whose values are the connected components:
def getRoots(aNeigh):
def findRoot(aNode,aRoot):
while aNode != aRoot[aNode][0]:
aNode = aRoot[aNode][0]
return (aNode,aRoot[aNode][1])
myRoot = {}
for myNode in aNeigh.keys():
myRoot[myNode] = (myNode,0)
for myI in aNeigh:
for myJ in aNeigh[myI]:
(myRoot_myI,myDepthMyI) = findRoot(myI,myRoot)
(myRoot_myJ,myDepthMyJ) = findRoot(myJ,myRoot)
if myRoot_myI != myRoot_myJ:
myMin = myRoot_myI
myMax = myRoot_myJ
if myDepthMyI > myDepthMyJ:
myMin = myRoot_myJ
myMax = myRoot_myI
myRoot[myMax] = (myMax,max(myRoot[myMin][1]+1,myRoot[myMax][1]))
myRoot[myMin] = (myRoot[myMax][0],-1)
myToRet = {}
for myI in aNeigh:
if myRoot[myI][0] == myI:
myToRet[myI] = []
for myI in aNeigh:
myToRet[findRoot(myI,myRoot)[0]].append(myI)
return myToRet
https://breakingcode.wordpress.com/2013/04/08/finding-connected-components-in-a-graph/
example-connected-components.py
#!/usr/bin/env python
# Finding connected components in a bidirectional graph.
# By Mario Vilas (mvilas at gmail dot com)
# The graph nodes.
class Data(object):
def __init__(self, name):
self.__name = name
self.__links = set()
@property
def name(self):
return self.__name
@property
def links(self):
return set(self.__links)
def add_link(self, other):
self.__links.add(other)
other.__links.add(self)
# The function to look for connected components.
def connected_components(nodes):
# List of connected components found. The order is random.
result = []
# Make a copy of the set, so we can modify it.
nodes = set(nodes)
# Iterate while we still have nodes to process.
while nodes:
# Get a random node and remove it from the global set.
n = nodes.pop()
# This set will contain the next group of nodes connected to each other.
group = {n}
# Build a queue with this node in it.
queue = [n]
# Iterate the queue.
# When it's empty, we finished visiting a group of connected nodes.
while queue:
# Consume the next item from the queue.
n = queue.pop(0)
# Fetch the neighbors.
neighbors = n.links
# Remove the neighbors we already visited.
neighbors.difference_update(group)
# Remove the remaining nodes from the global set.
nodes.difference_update(neighbors)
# Add them to the group of connected nodes.
group.update(neighbors)
# Add them to the queue, so we visit them in the next iterations.
queue.extend(neighbors)
# Add the group to the list of groups.
result.append(group)
# Return the list of groups.
return result
##################################################################
# Traversal...
# Call this routine on nodes being visited for the first time
def mark_component(G, node, marked):
marked[node] = True
total_marked = 1
for neighbor in G[node]:
if neighbor not in marked:
total_marked += mark_component(G, neighbor, marked)
return total_marked
def check_connection(G, v1, v2):
marked = {}
mark_component(G, v1, marked)
print mark_component(G, v1, marked)
print marked
if v2 not in marked:
return False
# Return True if v1 is connected to v2 in G
# or False if otherwise
return True
def make_link(G, node1, node2):
if node1 not in G:
G[node1] = {}
(G[node1])[node2] = 1
if node2 not in G:
G[node2] = {}
(G[node2])[node1] = 1
return G
def test():
edges = [('a', 'g'), ('a', 'd'), ('g', 'c'), ('g', 'd'),
('b', 'f'), ('f', 'e'), ('e', 'h')]
G = {}
for v1, v2 in edges:
make_link(G, v1, v2)
assert check_connection(G, "a", "c") == True
assert check_connection(G, 'a', 'b') == False
print test()
def dfs(graph, start):
visited, stack = set(), [start]
while stack:
vertex = stack.pop()
if vertex not in visited:
visited.add(vertex)
stack.extend(graph[vertex] - visited)
return visited
def dfs(graph, start, visited=None):
if visited is None:
visited = set()
visited.add(start)
for next in graph[start] - visited:
dfs(graph, next, visited)
return visited
def dfs_paths(graph, start, goal):
stack = [(start, [start])]
while stack:
(vertex, path) = stack.pop()
for next in graph[vertex] - set(path):
if next == goal:
yield path + [next]
else:
stack.append((next, path + [next]))
def dfs_paths(graph, start, goal, path=None):
if path is None:
path = [start]
if start == goal:
yield path
for next in graph[start] - set(path):
yield from dfs_paths(graph, next, goal, path + [next])
list(dfs_paths(graph, 'C', 'F')) # [['C', 'F'], ['C', 'A', 'B', 'E', 'F']]
###########################################################################
from pythonds.graphs import Graph
class DFSGraph(Graph):
def __init__(self):
super().__init__()
self.time = 0
def dfs(self):
for aVertex in self:
aVertex.setColor('white')
aVertex.setPred(-1)
for aVertex in self:
if aVertex.getColor() == 'white':
self.dfsvisit(aVertex)
def dfsvisit(self,startVertex):
startVertex.setColor('gray')
self.time += 1
startVertex.setDiscovery(self.time)
for nextVertex in startVertex.getConnections():
if nextVertex.getColor() == 'white':
nextVertex.setPred(startVertex)
self.dfsvisit(nextVertex)
startVertex.setColor('black')
self.time += 1
startVertex.setFinish(self.time)
###########################################################################
def bfs(graph, start):
visited, queue = set(), [start]
while queue:
vertex = queue.pop(0)
if vertex not in visited:
visited.add(vertex)
queue.extend(graph[vertex] - visited)
return visited
def bfs_paths(graph, start, goal):
queue = [(start, [start])]
while queue:
(vertex, path) = queue.pop(0)
for next in graph[vertex] - set(path):
if next == goal:
yield path + [next]
else:
queue.append((next, path + [next]))
list(bfs_paths(graph, 'A', 'F')) # [['A', 'C', 'F'], ['A', 'B', 'E', 'F']]
def shortest_path(graph, start, goal):
try:
return next(bfs_paths(graph, start, goal))
except StopIteration:
return None
shortest_path(graph, 'A', 'F') # ['A', 'C','F']
#########################################################################
from pythonds.graphs import Graph, Vertex
from pythonds.basic import Queue
def bfs(g,start):
start.setDistance(0)
start.setPred(None)
vertQueue = Queue()
vertQueue.enqueue(start)
while (vertQueue.size() > 0):
currentVert = vertQueue.dequeue()
for nbr in currentVert.getConnections():
if (nbr.getColor() == 'white'):
nbr.setColor('gray')
nbr.setDistance(currentVert.getDistance() + 1)
nbr.setPred(currentVert)
vertQueue.enqueue(nbr)
currentVert.setColor('black')
#########################################################################
In graph theory, the shortest path problem is the problem of finding a path between two vertices (or nodes) in a graph such that the sum of the weights of its constituent edges is minimized.
The problem of finding the shortest path between two intersections on a road map (the graph's vertices correspond to intersections and the edges correspond to road segments, each weighted by the length of its road segment) may be modeled by a special case of the shortest path problem in graphs.
An algorithm for finding a graph geodesic, i.e., the shortest path between two graph vertices in a graph. It functions by constructing a shortest-path tree from the initial vertex to every other vertex in the graph. The algorithm is implemented as Dijkstra[g] in the Wolfram Language package Combinatorica` .
The worst-case running time for the Dijkstra algorithm on a graph with n nodes and m edges is O(n^2) because it allows for directed cycles. It even finds the shortest paths from a source node s to all other nodes in the graph. This is basically O(n^2) for node selection and O(m) for distance updates. While O(n^2) is the best possible complexity for dense graphs, the complexity can be improved significantly for sparse graphs.
With slight modifications, Dijkstra's algorithm can be used as a reverse algorithm that maintains minimum spanning trees for the sink node. With further modifications, it can be extended to become bidirectional.
The bottleneck in Dijkstra's algorithm is node selection. However, using Dial's implementation, this can be significantly improved for sparse graphs.
A bridge of a connected graph is a graph edge whose removal disconnects the graph (Chartrand 1985, p. 45; Skiena 1990, p. 177). More generally, a bridge is an edge of a graph G whose removal increases the number of components of G (Harary 1994, p. 26). An edge of a connected graph is a bridge iff it does not lie on any cycle.
A bridge is also known as an isthmus, cut-edge, or cut arc.
A graph containing one or more bridges is said to be a bridged graph, while a graph containing no bridges is called a bridgeless graph.
The bridges of a graph can be found using Bridges[g] in the Wolfram Language package Combinatorica` . Precomputed bridges for many named graphs can be obtained using GraphData[graph, "Bridges"].
Every edge of a tree is a bridge.
A connected cubic graph contains a bridge iff it contains an articulation vertex (Skiena 1990, p. 177), i.e., if it is not a biconnected graph.
PROBLEM SET 3
#1
c 5 0 0
b 7 2 0.09523809524
f 5 2 0.2
e 7 7 0.3333333333
a 5 5 0.5
d 4 6 1
kv nv ccv
#2
A bipartite graph (or bigraph) is a graph whose vertices can be divided into two disjoint sets U and V (that is, U and V are each independent sets) such that every edge connects a vertex in U to one in V. Vertex sets U and V are usually called the parts of the graph. Equivalently, a bipartite graph is a graph that does not contain any odd-length cycles.
Every tree is bipartite.
Cycle graphs with an even number of vertices are bipartite.
Every planar graph whose faces all have even length is bipartite. Special cases of this are grid graphs and squaregraphs, in which every inner face consists of 4 edges and every inner vertex has four or more neighbors.
The complete bipartite graph on m and n vertices, denoted by Kn,m is the bipartite graph G = (U, V, E), where U and V are disjoint sets of size m and n, respectively, and E connects every vertex in U with all vertices in V. It follows that Km,n has mn edges. Closely related to the complete bipartite graphs are the crown graphs, formed from complete bipartite graphs by removing the edges of a perfect matching.
Hypercube graphs, partial cubes, and median graphs are bipartite. In these graphs, the vertices may be labeled by bitvectors, in such a way that two vertices are adjacent if and only if the corresponding bitvectors differ in a single position. A bipartition may be formed by separating the vertices whose bitvectors have an even number of ones from the vertices with an odd number of ones. Trees and squaregraphs form examples of median graphs, and every median graph is a partial cube.
################################################################
Consider a bipartite graph, that has 5 nodes in one group and 3 in the other:
- what is the smallest number of edges to make the graph have a single reachable component consisting of all the nodes?
7
#3
- whites the maximum number of edges the graph can have?
5*3 = 15
#4
- what is the maximum possible path length in the graph?
6
#5
- what is the maximum possible clustering coefficient for a node in the graph (nodes degree >=2)?
2*0/Kv = 0
#6
# Rewrite `mark_component` to not use recursion
# and instead use the `open_list` data structure
# discussed in lecture
#
def mark_component(G, node, marked):
marked[node] = True
total_marked = 1
for neighbor in G[node]:
if neighbor not in marked:
total_marked = total_marked + 1
marked[neighbor] = True
for element in G[neighbor]:
if element not in marked:
total_marked = total_marked + 1
marked[element] = True
return total_marked
#########
# Code for testing
#
def make_link(G, node1, node2):
if node1 not in G:
G[node1] = {}
(G[node1])[node2] = 1
if node2 not in G:
G[node2] = {}
(G[node2])[node1] = 1
return G
def test():
test_edges = [(1, 2), (2, 3), (4, 5), (5, 6)]
G = {}
for n1, n2 in test_edges:
make_link(G, n1, n2)
marked = {}
assert mark_component(G, 1, marked) == 3
assert 1 in marked
assert 2 in marked
assert 3 in marked
assert 4 not in marked
assert 5 not in marked
assert 6 not in marked
print test()
#7
The Maximum Betweenness Centrality problem (MBC)can be defined as follows. Given a graph find a k-element node set C that maximizes the probability of detecting communication between a pair of nodes s and t chosen uniformly at random. It is assumed that the communication between s and t is realized along a shortest s–t path which is, again, selected uniformly at random. The communication is detected if the communication path contains a node of C.
#
# Write centrality_max to return the maximum distance
# from a node to all the other nodes it can reach
#
def centrality_max(G, v):
distance_from_start = {}
open_list = [v]
distance_from_start[v] = 0
while len(open_list) >0:
current = open_list[0]
del open_list[0]
for neighbor in G[current].keys():
if neighbor not in distance_from_start:
distance_from_start[neighbor] = distance_from_start[current] + 1
open_list.append(neighbor)
print distance_from_start
return max(distance_from_start.values())
# your code here
#################
# Testing code
#
def make_link(G, node1, node2):
if node1 not in G:
G[node1] = {}
(G[node1])[node2] = 1
if node2 not in G:
G[node2] = {}
(G[node2])[node1] = 1
return G
def test():
chain = ((1,2), (2,3), (3,4), (4,5), (5,6))
G = {}
for n1, n2 in chain:
make_link(G, n1, n2)
assert centrality_max(G, 1) == 5
assert centrality_max(G, 3) == 3
tree = ((1, 2), (1, 3),
(2, 4), (2, 5),
(3, 6), (3, 7),
(4, 8), (4, 9),
(6, 10), (6, 11))
G = {}
for n1, n2 in tree:
make_link(G, n1, n2)
assert centrality_max(G, 1) == 3
assert centrality_max(G, 11) == 6
print test()
#8
#########################################################################
for checking
############################################################################
# Bridge Edges v4
#
# Find the bridge edges in a graph given the
# algorithm in lecture.
# Complete the intermediate steps
# - create_rooted_spanning_tree
# - post_order
# - number_of_descendants
# - lowest_post_order
# - highest_post_order
#
# And then combine them together in
# `bridge_edges`
# So far, we've represented graphs
# as a dictionary where G[n1][n2] == 1
# meant there was an edge between n1 and n2
#
# In order to represent a spanning tree
# we need to create two classes of edges
# we'll refer to them as "green" and "red"
# for the green and red edges as specified in lecture
#
# So, for example, the graph given in lecture
# G = {'a': {'c': 1, 'b': 1},
# 'b': {'a': 1, 'd': 1},
# 'c': {'a': 1, 'd': 1},
# 'd': {'c': 1, 'b': 1, 'e': 1},
# 'e': {'d': 1, 'g': 1, 'f': 1},
# 'f': {'e': 1, 'g': 1},
# 'g': {'e': 1, 'f': 1}
# }
# would be written as a spanning tree
# S = {'a': {'c': 'green', 'b': 'green'},
# 'b': {'a': 'green', 'd': 'red'},
# 'c': {'a': 'green', 'd': 'green'},
# 'd': {'c': 'green', 'b': 'red', 'e': 'green'},
# 'e': {'d': 'green', 'g': 'green', 'f': 'green'},
# 'f': {'e': 'green', 'g': 'red'},
# 'g': {'e': 'green', 'f': 'red'}
# }
#
def make_link_color(G, node1, node2, red_green):
if node1 not in G:
G[node1] = {}
(G[node1])[node2] = red_green
if node2 not in G:
G[node2] = {}
(G[node2])[node1] = red_green
return G
def get_children(S, root, parent):
return [n for n, e in S[root].items() if ((not n == parent) and (e == 'green'))]
def get_children_all(S, root, parent):
green = []
red = []
for n, e in S[root].items():
if n == parent:
continue
if e == 'green':
green.append(n)
if e == 'red':
red.append(n)
return green, red
def create_rooted_spanning_tree(G, root):
open_list = [root]
S = {}
S[root] = {}
while len(open_list) > 0:
node = open_list.pop()
neighbors = G[node]
for n in neighbors:
if n not in S:
make_link_color(S, node, n, 'green')
open_list.append(n)
else:
if node not in S[n]:
make_link_color(S, node, n, 'red')
# your code here
return S
# This is just one possible solution
# There are other ways to create a
# spanning tree, and the grader will
# accept any valid result
# feel free to edit the test to
# match the solution your program produces
def test_create_rooted_spanning_tree():
G = {'a': {'c': 1, 'b': 1},
'b': {'a': 1, 'd': 1},
'c': {'a': 1, 'd': 1},
'd': {'c': 1, 'b': 1, 'e': 1},
'e': {'d': 1, 'g': 1, 'f': 1},
'f': {'e': 1, 'g': 1},
'g': {'e': 1, 'f': 1}
}
S = create_rooted_spanning_tree(G, "a")
assert S == {'a': {'c': 'green', 'b': 'green'},
'b': {'a': 'green', 'd': 'red'},
'c': {'a': 'green', 'd': 'green'},
'd': {'c': 'green', 'b': 'red', 'e': 'green'},
'e': {'d': 'green', 'g': 'green', 'f': 'green'},
'f': {'e': 'green', 'g': 'red'},
'g': {'e': 'green', 'f': 'red'}
}
print test_create_rooted_spanning_tree()
###########
def _post_order(S, root, parent, val, po):
children = get_children(S, root, parent)
for c in children:
val = _post_order(S, c, root, val, po)
po[root] = val
return val + 1
def post_order(S, root):
# return mapping between nodes of S and the post-order value
# of that node
po = {}
_post_order(S, root, None, 1, po)
return po
# This is just one possible solution
# There are other ways to create a
# spanning tree, and the grader will
# accept any valid result.
# feel free to edit the test to
# match the solution your program produces
def test_post_order():
S = {'a': {'c': 'green', 'b': 'green'},
'b': {'a': 'green', 'd': 'red'},
'c': {'a': 'green', 'd': 'green'},
'd': {'c': 'green', 'b': 'red', 'e': 'green'},
'e': {'d': 'green', 'g': 'green', 'f': 'green'},
'f': {'e': 'green', 'g': 'red'},
'g': {'e': 'green', 'f': 'red'}
}
po = post_order(S, 'a')
assert po == {'a':7, 'b':1, 'c':6, 'd':5, 'e':4, 'f':2, 'g':3}
##############
def pre_number_descendants(S, root, parent, nd):
children = get_children(S, root, parent)
nd_val = 1
for c in children:
nd_val += pre_number_descendants(S, c, root, nd)
nd[root] = nd_val
return nd_val
def number_of_descendants(S, root):
nd = {}
pre_number_descendants(S, root, None, nd)
return nd
# return mapping between nodes of S and the number of descendants
# of that node
def test_number_of_descendants():
S = {'a': {'c': 'green', 'b': 'green'},
'b': {'a': 'green', 'd': 'red'},
'c': {'a': 'green', 'd': 'green'},
'd': {'c': 'green', 'b': 'red', 'e': 'green'},
'e': {'d': 'green', 'g': 'green', 'f': 'green'},
'f': {'e': 'green', 'g': 'red'},
'g': {'e': 'green', 'f': 'red'}
}
nd = number_of_descendants(S, 'a')
assert nd == {'a':7, 'b':1, 'c':5, 'd':4, 'e':3, 'f':1, 'g':1}
###############
def general_post_order(S, root, parent, po, gpo, comp):
green, red = get_children_all(S, root, parent)
val = po[root]
for c in green:
test = general_post_order(S, c, root, po, gpo, comp)
if comp(val, test):
val = test
for c in red:
test = po[c]
if comp(val, test):
val = test
gpo[root] = val
return val
def lowest_post_order(S, root, po):
lpo = {}
general_post_order(S, root, None, po, lpo, lambda x, y: x > y)
return lpo
def highest_post_order(S, root, po):
hpo = {}
general_post_order(S, root, None, po, hpo, lambda x, y: x < y)
return hpo
def test_lowest_post_order():
S = {'a': {'c': 'green', 'b': 'green'},
'b': {'a': 'green', 'd': 'red'},
'c': {'a': 'green', 'd': 'green'},
'd': {'c': 'green', 'b': 'red', 'e': 'green'},
'e': {'d': 'green', 'g': 'green', 'f': 'green'},
'f': {'e': 'green', 'g': 'red'},
'g': {'e': 'green', 'f': 'red'}
}
po = post_order(S, 'a')
l = lowest_post_order(S, 'a', po)
assert l == {'a':1, 'b':1, 'c':1, 'd':1, 'e':2, 'f':2, 'g':2}
def test_highest_post_order():
S = {'a': {'c': 'green', 'b': 'green'},
'b': {'a': 'green', 'd': 'red'},
'c': {'a': 'green', 'd': 'green'},
'd': {'c': 'green', 'b': 'red', 'e': 'green'},
'e': {'d': 'green', 'g': 'green', 'f': 'green'},
'f': {'e': 'green', 'g': 'red'},
'g': {'e': 'green', 'f': 'red'}
}
po = post_order(S, 'a')
h = highest_post_order(S, 'a', po)
assert h == {'a':7, 'b':5, 'c':6, 'd':5, 'e':4, 'f':3, 'g':3}
#################
def bridge_edges(G, root):
# use the four functions above
# and then determine which edges in G are bridge edges
# return them as a list of tuples ie: [(n1, n2), (n4, n5)]
S = create_rooted_spanning_tree(G, root)
po = post_order(S, root)
nd = number_of_descendants(S, root)
lpo = lowest_post_order(S, root, po)
hpo = highest_post_order(S, root, po)
bridges = []
open_list = [(root, None)]
while len(open_list) > 0:
node, parent = open_list.pop()
for child in get_children(S, node, parent):
if hpo[child] <= po[child] and lpo[child] > (po[child] - nd[child]):
bridges.append((node, child))
open_list.append((child, node))
return bridges
def test_bridge_edges():
G = {'a': {'c': 1, 'b': 1},
'b': {'a': 1, 'd': 1},
'c': {'a': 1, 'd': 1},
'd': {'c': 1, 'b': 1, 'e': 1},
'e': {'d': 1, 'g': 1, 'f': 1},
'f': {'e': 1, 'g': 1},
'g': {'e': 1, 'f': 1}
}
bridges = bridge_edges(G, 'a')
assert bridges == [('d', 'e')]
print test_post_order()
print test_number_of_descendants()
print test_lowest_post_order()
print test_highest_post_order()
print test_bridge_edges()
#############################################
the right decision
#############################################
# Bridge Edges v4
#
# Find the bridge edges in a graph given the
# algorithm in lecture.
# Complete the intermediate steps
# - create_rooted_spanning_tree
# - post_order
# - number_of_descendants
# - lowest_post_order
# - highest_post_order
#
# And then combine them together in
# `bridge_edges`
# So far, we've represented graphs
# as a dictionary where G[n1][n2] == 1
# meant there was an edge between n1 and n2
#
# In order to represent a spanning tree
# we need to create two classes of edges
# we'll refer to them as "green" and "red"
# for the green and red edges as specified in lecture
#
# So, for example, the graph given in lecture
# G = {'a': {'c': 1, 'b': 1},
# 'b': {'a': 1, 'd': 1},
# 'c': {'a': 1, 'd': 1},
# 'd': {'c': 1, 'b': 1, 'e': 1},
# 'e': {'d': 1, 'g': 1, 'f': 1},
# 'f': {'e': 1, 'g': 1},
# 'g': {'e': 1, 'f': 1}
# }
# would be written as a spanning tree
# S = {'a': {'c': 'green', 'b': 'green'},
# 'b': {'a': 'green', 'd': 'red'},
# 'c': {'a': 'green', 'd': 'green'},
# 'd': {'c': 'green', 'b': 'red', 'e': 'green'},
# 'e': {'d': 'green', 'g': 'green', 'f': 'green'},
# 'f': {'e': 'green', 'g': 'red'},
# 'g': {'e': 'green', 'f': 'red'}
# }
#
#
# First some utility functions
#
def make_link(G, node1, node2, r_or_g):
# modified make_link to apply
# a color to the edge instead of just 1
if node1 not in G:
G[node1] = {}
(G[node1])[node2] = r_or_g
if node2 not in G:
G[node2] = {}
(G[node2])[node1] = r_or_g
return G
def get_children(S, root, parent):
"""returns the children from following the
green edges"""
return [n for n, e in S[root].items()
if ((not n == parent) and
(e == 'green'))]
def get_children_all(S, root, parent):
"""returns the children from following
green edges and the children from following
red edges"""
green = []
red = []
for n, e in S[root].items():
if n == parent:
continue
if e == 'green':
green.append(n)
if e == 'red':
red.append(n)
return green, red
#################
def create_rooted_spanning_tree(G, root):
# use DFS from the root to add edges and nodes
# to the tree. The first time we see a node
# the edge is green, but after that its red
open_list = [root]
S = {root:{}}
while len(open_list) > 0:
node = open_list.pop()
neighbors = G[node]
for n in neighbors:
if n not in S:
# we haven't seen this node, so
# need to use a green edge to connect
# it
make_link(S, node, n, 'green')
open_list.append(n)
else:
# we have seen this node,
# but, first make sure that
# don't already have the edge
# in S
if node not in S[n]:
make_link(S, node, n, 'red')
return S
##################
def _post_order(S, root, parent, val, po):
children = get_children(S, root, parent)
for c in children:
val = _post_order(S, c, root, val, po)
po[root] = val
return val + 1
def post_order(S, root):
po = {}
_post_order(S, root, None, 1, po)
return po
##################
def _number_descendants(S, root, parent, nd):
# number of descendants is the
# sum of the number of descendants of a nodes
# children plus one
children = get_children(S, root, parent)
nd_val = 1
for c in children:
# recursively calculate the number of descendants
# for the children
nd_val += _number_descendants(S, c, root, nd)
nd[root] = nd_val
return nd_val
def number_of_descendants(S, root):
nd = {}
_number_descendants(S, root, None, nd)
return nd
#
# Since highest and lowest post order will follow
# a similar method, I only wrote one method
# that can be used for both
#
def _general_post_order(S, root, parent, po, gpo, comp):
green, red = get_children_all(S, root, parent)
val = po[root]
for c in green:
# recursively find the low/high post order value of the children
test = _general_post_order(S, c, root, po, gpo, comp)
# and save the low/highest one
if comp(val, test):
val = test
for c in red:
test = po[c]
# and also look at the direct children
# from following red edges
# and save the low/highest one if needed
if comp(val, test):
val = test
gpo[root] = val
return val
def lowest_post_order(S, root, po):
lpo = {}
_general_post_order(S, root, None, po, lpo, lambda x, y: x > y)
return lpo
def highest_post_order(S, root, po):
hpo = {}
_general_post_order(S, root, None, po, hpo, lambda x, y: x < y)
return hpo
#
# Now put everything together
#
def bridge_edges(G, root):
S = create_rooted_spanning_tree(G, root)
po = post_order(S, root)
nd = number_of_descendants(S, root)
lpo = lowest_post_order(S, root, po)
hpo = highest_post_order(S, root, po)
bridges = []
open_list = [(root, None)]
# walk down the tree and see which edges are
# tree edges
while len(open_list) > 0:
node, parent = open_list.pop()
for child in get_children(S, node, parent):
# all of these edges are automatically green (get_children only
# follows green edges)
# so only need to check the other two conditions
if hpo[child] <= po[child] and lpo[child] > (po[child] - nd[child]):
bridges.append((node, child))
open_list.append((child, node))
return bridges
def test_create_rooted_spanning_tree():
G = {'a': {'c': 1, 'b': 1},
'b': {'a': 1, 'd': 1},
'c': {'a': 1, 'd': 1},
'd': {'c': 1, 'b': 1, 'e': 1},
'e': {'d': 1, 'g': 1, 'f': 1},
'f': {'e': 1, 'g': 1},
'g': {'e': 1, 'f': 1}
}
S = create_rooted_spanning_tree(G, "a")
assert S == {'a': {'c': 'green', 'b': 'green'},
'b': {'a': 'green', 'd': 'red'},
'c': {'a': 'green', 'd': 'green'},
'd': {'c': 'green', 'b': 'red', 'e': 'green'},
'e': {'d': 'green', 'g': 'green', 'f': 'green'},
'f': {'e': 'green', 'g': 'red'},
'g': {'e': 'green', 'f': 'red'}
}
def test_post_order():
S = {'a': {'c': 'green', 'b': 'green'},
'b': {'a': 'green', 'd': 'red'},
'c': {'a': 'green', 'd': 'green'},
'd': {'c': 'green', 'b': 'red', 'e': 'green'},
'e': {'d': 'green', 'g': 'green', 'f': 'green'},
'f': {'e': 'green', 'g': 'red'},
'g': {'e': 'green', 'f': 'red'}
}
po = post_order(S, 'a')
assert po == {'a':7, 'b':1, 'c':6, 'd':5, 'e':4, 'f':2, 'g':3}
def test_lowest_post_order():
S = {'a': {'c': 'green', 'b': 'green'},
'b': {'a': 'green', 'd': 'red'},
'c': {'a': 'green', 'd': 'green'},
'd': {'c': 'green', 'b': 'red', 'e': 'green'},
'e': {'d': 'green', 'g': 'green', 'f': 'green'},
'f': {'e': 'green', 'g': 'red'},
'g': {'e': 'green', 'f': 'red'}
}
po = post_order(S, 'a')
l = lowest_post_order(S, 'a', po)
assert l == {'a':1, 'b':1, 'c':1, 'd':1, 'e':2, 'f':2, 'g':2}
def test_highest_post_order():
S = {'a': {'c': 'green', 'b': 'green'},
'b': {'a': 'green', 'd': 'red'},
'c': {'a': 'green', 'd': 'green'},
'd': {'c': 'green', 'b': 'red', 'e': 'green'},
'e': {'d': 'green', 'g': 'green', 'f': 'green'},
'f': {'e': 'green', 'g': 'red'},
'g': {'e': 'green', 'f': 'red'}
}
po = post_order(S, 'a')
h = highest_post_order(S, 'a', po)
assert h == {'a':7, 'b':5, 'c':6, 'd':5, 'e':4, 'f':3, 'g':3}
def test_bridge_edges():
G = {'a': {'c': 1, 'b': 1},
'b': {'a': 1, 'd': 1},
'c': {'a': 1, 'd': 1},
'd': {'c': 1, 'b': 1, 'e': 1},
'e': {'d': 1, 'g': 1, 'f': 1},
'f': {'e': 1, 'g': 1},
'g': {'e': 1, 'f': 1}
}
bridges = bridge_edges(G, 'a')
assert bridges == [('d', 'e')]
Last login: Sun Jun 19 21:42:20 on ttys000
olgabelitskaya (master) ~ $ cd version-control
olgabelitskaya (master *) version-control $ git status
On branch master
Your branch is up-to-date with 'exercises/master'.
Changes not staged for commit:
(use "git add <file>..." to update what will be committed)
(use "git checkout -- <file>..." to discard changes in working directory)
modified: reflections-cs215/lesson1_reflections_ob.txt
modified: reflections-cs215/lesson2_reflections_ob.txt
Untracked files:
(use "git add <file>..." to include in what will be committed)
reflections-cs215/lesson3_reflections_ob.txt
no changes added to commit (use "git add" and/or "git commit -a")
olgabelitskaya (master *) version-control $ git add 'reflections-cs215/lesson1_reflections_ob.txt'
olgabelitskaya (master *+) version-control $ git commit -m "Update lesson1_reflections_ob.txt"
[master fc7da20] Update lesson1_reflections_ob.txt
1 file changed, 42 insertions(+)
olgabelitskaya (master *) version-control $ git add 'reflections-cs215/lesson2_reflections_ob.txt'
olgabelitskaya (master +) version-control $ git commit -m "Update reflections-cs215/lesson2_reflections_ob.txt"
[master 2d84b30] Update reflections-cs215/lesson2_reflections_ob.txt
1 file changed, 40 insertions(+), 1 deletion(-)
olgabelitskaya (master) version-control $ git add 'reflections-cs215/lesson3_reflections_ob.txt'
olgabelitskaya (master +) version-control $ git commit -m "Add reflections for lesson 3"
[master 4443845] Add reflections for lesson 3
1 file changed, 1040 insertions(+)
create mode 100644 reflections-cs215/lesson3_reflections_ob.txt
olgabelitskaya (master) version-control $ git status
On branch master
Your branch is ahead of 'exercises/master' by 3 commits.
(use "git push" to publish your local commits)
nothing to commit, working directory clean
olgabelitskaya (master) version-control $ git push exercises master
Counting objects: 12, done.
Delta compression using up to 4 threads.
Compressing objects: 100% (12/12), done.
Writing objects: 100% (12/12), 13.32 KiB | 0 bytes/s, done.
Total 12 (delta 6), reused 0 (delta 0)
To https://github.com/OlgaBelitskaya/my-exercises.git
1777e02..4443845 master -> master
Подписаться на:
Комментарии (Atom)