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
Комментариев нет:
Отправить комментарий