class Vertex(object):
 def __init__(self, label=''):
  self.label = label
 def __repr__(self):
  return 'Vertex(%s)' % repr(self.label)
 # __repr__返回表達式， __str__返回可閱讀信息
 __str__=__repr__ # 使其指向同一個函數(shù)
class Edge(tuple):
 # 繼承自建tuple類型并重寫new方法
 def __new__(cls, e1, e2):
  return tuple.__new__(cls, (e1,e2))
 def __repr__(self):
  return "Edge(%s, %s)" % (repr(self[0]), repr(self[1]))
 __str__ = __repr__

if __name__=="__main__":
 # 創(chuàng)建兩個頂點一條邊
 v = Vertex('v')
 w = Vertex('w')
 e = Edge(v,w)
#  print e
 # 將頂點和邊放入圖中
 g = Graph([v,w],[e])
#  print g

# 通過字典的字典實現(xiàn)圖的結(jié)構(gòu)
class Graph(dict):
 def __init__(self, vs=[], es=[]):
  """ 建立一個新的圖，(vs)為頂點vertices列表，(es)為邊緣edges列表 """
  for v in vs:
   self.add_vertex(v)
  for e in es:
   self.add_edge(e)
 def add_vertex(self,v):
  """ 添加頂點 v: 使用字典結(jié)構(gòu)"""
  self[v] = {}
 def add_edge(self, e):
  """ 添加邊緣 e: e 為一個元組(v,w) 
   在兩個頂點 w 和 v 之間添加成員e ，如果兩個頂點之間已有邊緣，則替換之 """
  v, w = e
  # 由于一條邊會產(chǎn)生兩個項目，因此該實現(xiàn)代表了一個無向圖
  self[v][w] = e
  self[w][v] = e

def get_edge(self,v1, v2):
  """ 接收兩個頂點，若這兩個頂點之間右邊則返回這條邊，否則返回None """
  try:
   return self[v1][v2]
  except:
   return None
 def remove_edge(self,e):
  """ 接受一條邊，并且刪除圖中該邊的所有引用 """
  v, w = e
  self[v].pop(w)
  self[w].pop(v)
 def vertices(self):
  """ 返回圖中所有頂點的列表 """
  return self.keys()
 def edges(self):
  """ 返回圖中邊的列表 """
  es = set()    # 為了避免返回重復(fù)的邊，設(shè)為集合
  for v1 in self.vertices():
   for v2 in self.vertices():
    es.add(self.get_edge(v2, v1))
  es.discard(None)  # 若集合中存在None元素,則刪除 
  return list(es)
  """ 利用圖的字典結(jié)構(gòu)獲得所有邊
  es = []
  for v in self.vertices():
   es.extend(self[v].values())
  es = list(set(es))
  return es
  """
 def out_vertices(self,v):
  """ 接受一個Vertex并返回鄰近頂點（通過一條邊連接到給定節(jié)點的節(jié)點）的列表 """
  return self[v].keys()
 def out_edges(self,v):
  """ 接受一個Vertex并返回連接到給定節(jié)點的邊的列表 """
  return self[v].values()
 def add_all_edges(self,vs=None):
  """ 從一個無邊的圖開始，通過在各個頂點間添加邊來生成一個完全圖
   輸入為目標頂點的列表，如果為None,則對所有的點進行全聯(lián)結(jié) """
  if vs == None:
   vs = self.vertices()
  for v1 in vs:
   for v2 in vs:
    if v1 is v2 : continue  # 假設(shè)不存在單頂點連通
    self.add_edge(Edge(v1,v2))

def add_regular_edges(self,k):
  """ 從一個無邊的圖開始不斷添加邊，使得每個頂點都有相同的度k
   一個節(jié)點的度指的是連接到它的邊的數(shù)量 """
  n = len(self.vertices())
  assert n > 1
  if k==1:
   vs = self.vertices()
   for i in range(n-1):
    self.add_edge(Edge(vs[i],vs[i+1]))
   return True
  if n < k+1:
   print "Cannot create regular graph"
   return False
  if n == k+1:
   self.add_all_edges()
   return True
  """
   設(shè)度數(shù)為k，圖的階數(shù)（頂點個數(shù)）為n
   利用歸納方法生成邊的個數(shù)
   偶數(shù)度 當k=2m,m>=1時
   遞歸過程：
   0. 假設(shè)n>k+1，因為當n=k+1時，只要生成全連接即可，當n<k+1，則不能生成正則圖
   1. 當n>k+1時：先從原圖中前k+1個頂點(v1,v2,...,v2m-1,v2m, v2m+1)生成完全圖
    此時，該k+1個頂點的度數(shù)均為k
   2. 現(xiàn)添加一個頂點vx，x=2m+2該頂點的度為0
   3. 刪除m條不相連的邊，如(v1,v2),(v3,v4),(v5,v6),...,(v2m-1,v2m),這時頂點v1,v2,...v2m的度為k-1
    記錄下這m條邊的頂點
   4. 聯(lián)結(jié) (v1,vx),(v2,vx),...,(v2m-1,vx),(v2m,vx),使得v1,v2,...,v2m,v2m+2的度=k
   5. 對新加入的點，重復(fù)3,4
   奇數(shù)度 當k=2m+1,m>=1時
   遞歸過程：
   設(shè)圖G是有n個頂點的k正則圖，且k=2m+1，m>=1,按照下面法則生成新圖G1
   0. 假設(shè)n>k+1，因為當n=k+1時，只要生成全連接即可，當n<k+1，則不能生成正則圖
   1. 在圖G中任取m條頂點不同的邊(x1,x2),(x3,x4),(x5,x6),...,(x2m-1,x2m) 記為組es1
    再另取m條頂點不同的邊 (y1,y2),(y3,y4),(y5,y6),...,(y2m-1,y2m) 記為組es2
    其中xi和yj可以存在相同，但是兩組中的所有邊都不相同
    此時，該k+1個頂點的度數(shù)均為k
   2. 在圖G中去掉m條邊(x1,x2),(x3,x4),(x5,x6),...,(x2m-1,x2m)，增加新的頂點v1，并增加2m條新邊
    (v1,x1),(v1,x2),...,(v1,x2m-1),(v1,x2m)
   3. 在圖G中去掉m條邊(y1,y2),(y3,y4),(y5,y6),...,(y2m-1,y2m)，增加新的頂點v2，并增加2m條新邊
    (v2,y1),(v2,y2),...,(v2,y2m-1),(v2,y2m)
   4. 增加新邊 (v1,v2)
   5. 對新的點v3,v4,重復(fù)1,2,3,4
   增加的頂點和邊保證了v1，v2和x1,x2,...,x2m,y1,y2,...,y2m的度數(shù)為2m+1其余頂點度數(shù)不變
  """
  if k%2==0:
   # 選取前k+1個點,先構(gòu)造完全圖
   vs = self.vertices()
   self.add_all_edges(vs[:k+1])
   for i in range(k+1,n):   # 對之后的點進行遍歷 
    vsdel = []     # 記錄刪除過邊的頂點
    for e in self.edges():      
     # 獲得邊的兩個頂點
     v1,v2 = e[0],e[1]  
     if v1 not in vsdel and v2 not in vsdel:
      vsdel.append(v1)
      vsdel.append(v2)
      # 刪除不相連的邊
      self.remove_edge(e)
     # 當已刪除的邊數(shù)為k/2，即共k個非鄰近點時，退出循環(huán)
     if len(vsdel)==k:
      break 
    # 將新的點與記錄的點進行連接
    for v in vsdel:
     self.add_edge(Edge(v,vs[i]))
  else:
   if n%2==0 and n>k+1: # 由上述法則可知，n必須為偶數(shù)
    # 選取前k+1個偶數(shù)點,先構(gòu)造完全圖
    vs = self.vertices()
    self.add_all_edges(vs[:k+1])
    for i in range(k+1,n,2): # 之后的點進行兩兩遍歷
     vsdel1 = []    # 記錄第1組刪除的點
     edel1 = []    # 記錄第1組刪除的邊
     for e in self.edges():      
      # 獲得邊的兩個頂點
      v1,v2 = e[0],e[1]  
      if v1 not in vsdel1 and v2 not in vsdel1:
       vsdel1.append(v1)
       vsdel1.append(v2)
       # 刪除不相連的邊
       edel1.append(e)
       self.remove_edge(e)
      # 當已刪除的邊數(shù)為m，即共k-1個非鄰近點時，退出循環(huán)
      if len(vsdel1)==k-1:
       break
     vsdel2 = []    # 記錄第2組刪除的點
     edel2 = []    # 記錄第2組刪除的邊
     for e in self.edges():      
      # 獲得邊的兩個頂點
      v1,v2 = e[0],e[1]  
      # 點可以和第一組相同，但邊不可以
      if v1 not in vsdel2 and v2 not in vsdel2 and e not in edel1:
       vsdel2.append(v1)
       vsdel2.append(v2)
       # 刪除不相連的邊
       edel2.append(e)
       self.remove_edge(e)
      # 當已刪除的邊數(shù)為m，即共k-1個非鄰近點時，退出循環(huán)
      if len(vsdel2)==k-1:
       break
     # 分別連接兩組邊
     for v in vsdel1:
      self.add_edge(Edge(v,vs[i]))
     for v in vsdel2:
      self.add_edge(Edge(v,vs[i+1]))
     self.add_edge(Edge(vs[i],vs[i+1]))
   else:
    print "Cannot create regular graph"
    return False
  return True

def is_connect(self):
  """ 判斷一個圖是否連通的
   從任意頂點開始進行一次BFS，將所有到達的節(jié)點都標記上，然后檢查是否所有的節(jié)點都被標記上 """
  pass
  vs = self.vertices() # 獲得所有頂點
  q, s = [], set()  # 搜索隊列，標記集合
  q.append(vs[0])   # 從第1個頂點開始搜索
  while q:    # 當隊列非空
   v = q.pop(0)  # 從隊列中刪除移一個頂點
   s.add(v)   # 并標記當前頂點
   # 搜索當前頂點的連接點，如果這些連接點沒有被標記
   # 則將其添加到隊列中
   for w in self.out_vertices(v):
    if w not in s:
     q.append(w)
  # 當隊列為空時完成搜索，檢查標記過的頂點是否等于圖的頂點數(shù)
  if len(s)==len(vs):
   return True
  else:
   return False

from GraphWorld import CircleLayout,GraphWorld
from Graph import Graph,Vertex,Edge
import string
def test(n,k):
 # create n Vertices
 labels = string.ascii_lowercase + string.ascii_uppercase
 vs = [Vertex(c) for c in labels[:n]]
 # create a graph and a layout
 g = Graph(vs)
 g.add_regular_edges(k)
 layout = CircleLayout(g)
 # draw the graph
 gw = GraphWorld()
 gw.show_graph(g, layout)
 gw.mainloop()
if __name__ == '__main__':
 test(n=10,k=3)

from Graph import Graph,Vertex,Edge
from random import randint
class RandomGraph(Graph):
 """ 隨即圖 """
 def add_random_edges(self,p):
  """ 從一個·無邊圖開始隨機生成邊
   使得任意兩個節(jié)點間存在邊的概率為p (0<=p<=1) """
  for v1 in self.vertices():
   for v2 in self.vertices():
    if v1 is v2: continue
    if randint(0,100) < p*100 :
     self.add_edge(Edge(v1,v2))

from GraphWorld import CircleLayout,GraphWorld
import string
def test(n,p):
 # create n Vertices
 labels = string.ascii_lowercase + string.ascii_uppercase
 vs = [Vertex(c) for c in labels[:n]]
 # create a graph and a layout
 g = RandomGraph(vs)
 g.add_random_edges(p)
 print "connect?:",g.is_connect()
 layout = CircleLayout(g)
 # draw the graph
 gw = GraphWorld()
 gw.show_graph(g, layout)
 gw.mainloop()
if __name__ == '__main__':
 test(p=0.2,n=5)

# 迭代器
class AllTrue(object):
 def next(self):
  return True
 def __iter__(self):
  return self
# 使用AllTrue之類的迭代器可以表現(xiàn)無限序列
print zip('abc',AllTrue())
# 通過編寫生成器函數(shù)創(chuàng)建一個迭代器
def generate_letters():
 for letter in 'abc':
  yield letter
iter = generate_letters()
import string
# 帶有無限循環(huán)的生成器會返回一個不會終止的迭代器
def alphabet_cycle():
 while True:
  for i in range(1,10):
   for c in string.lowercase:
    yield c+str(i)
iter_ac = alphabet_cycle()
print iter_ac.next()