class Vertex(object):
 def __init__(self, label=''):
  self.label = label
 def __repr__(self):
  return 'Vertex(%s)' % repr(self.label)
 # __repr__返回表達(dá)式， __str__返回可閱讀信息
 __str__=__repr__ # 使其指向同一個(gè)函數(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)建兩個(gè)頂點(diǎn)一條邊
 v = Vertex('v')
 w = Vertex('w')
 e = Edge(v,w)
#  print e
 # 將頂點(diǎn)和邊放入圖中
 g = Graph([v,w],[e])
#  print g

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

def get_edge(self,v1, v2):
  """ 接收兩個(gè)頂點(diǎn)，若這兩個(gè)頂點(diǎn)之間右邊則返回這條邊，否則返回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):
  """ 返回圖中所有頂點(diǎn)的列表 """
  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):
  """ 接受一個(gè)Vertex并返回鄰近頂點(diǎn)（通過一條邊連接到給定節(jié)點(diǎn)的節(jié)點(diǎn)）的列表 """
  return self[v].keys()
 def out_edges(self,v):
  """ 接受一個(gè)Vertex并返回連接到給定節(jié)點(diǎn)的邊的列表 """
  return self[v].values()
 def add_all_edges(self,vs=None):
  """ 從一個(gè)無邊的圖開始，通過在各個(gè)頂點(diǎn)間添加邊來生成一個(gè)完全圖
   輸入為目標(biāo)頂點(diǎn)的列表，如果為None,則對所有的點(diǎn)進(jìn)行全聯(lián)結(jié) """
  if vs == None:
   vs = self.vertices()
  for v1 in vs:
   for v2 in vs:
    if v1 is v2 : continue  # 假設(shè)不存在單頂點(diǎn)連通
    self.add_edge(Edge(v1,v2))

def add_regular_edges(self,k):
  """ 從一個(gè)無邊的圖開始不斷添加邊，使得每個(gè)頂點(diǎn)都有相同的度k
   一個(gè)節(jié)點(diǎn)的度指的是連接到它的邊的數(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ù)（頂點(diǎn)個(gè)數(shù)）為n
   利用歸納方法生成邊的個(gè)數(shù)
   偶數(shù)度 當(dāng)k=2m,m>=1時(shí)
   遞歸過程：
   0. 假設(shè)n>k+1，因?yàn)楫?dāng)n=k+1時(shí)，只要生成全連接即可，當(dāng)n<k+1，則不能生成正則圖
   1. 當(dāng)n>k+1時(shí)：先從原圖中前k+1個(gè)頂點(diǎn)(v1,v2,...,v2m-1,v2m, v2m+1)生成完全圖
    此時(shí)，該k+1個(gè)頂點(diǎn)的度數(shù)均為k
   2. 現(xiàn)添加一個(gè)頂點(diǎn)vx，x=2m+2該頂點(diǎn)的度為0
   3. 刪除m條不相連的邊，如(v1,v2),(v3,v4),(v5,v6),...,(v2m-1,v2m),這時(shí)頂點(diǎn)v1,v2,...v2m的度為k-1
    記錄下這m條邊的頂點(diǎn)
   4. 聯(lián)結(jié) (v1,vx),(v2,vx),...,(v2m-1,vx),(v2m,vx),使得v1,v2,...,v2m,v2m+2的度=k
   5. 對新加入的點(diǎn)，重復(fù)3,4
   奇數(shù)度 當(dāng)k=2m+1,m>=1時(shí)
   遞歸過程：
   設(shè)圖G是有n個(gè)頂點(diǎn)的k正則圖，且k=2m+1，m>=1,按照下面法則生成新圖G1
   0. 假設(shè)n>k+1，因?yàn)楫?dāng)n=k+1時(shí)，只要生成全連接即可，當(dāng)n<k+1，則不能生成正則圖
   1. 在圖G中任取m條頂點(diǎn)不同的邊(x1,x2),(x3,x4),(x5,x6),...,(x2m-1,x2m) 記為組es1
    再另取m條頂點(diǎn)不同的邊 (y1,y2),(y3,y4),(y5,y6),...,(y2m-1,y2m) 記為組es2
    其中xi和yj可以存在相同，但是兩組中的所有邊都不相同
    此時(shí)，該k+1個(gè)頂點(diǎn)的度數(shù)均為k
   2. 在圖G中去掉m條邊(x1,x2),(x3,x4),(x5,x6),...,(x2m-1,x2m)，增加新的頂點(diǎn)v1，并增加2m條新邊
    (v1,x1),(v1,x2),...,(v1,x2m-1),(v1,x2m)
   3. 在圖G中去掉m條邊(y1,y2),(y3,y4),(y5,y6),...,(y2m-1,y2m)，增加新的頂點(diǎn)v2，并增加2m條新邊
    (v2,y1),(v2,y2),...,(v2,y2m-1),(v2,y2m)
   4. 增加新邊 (v1,v2)
   5. 對新的點(diǎn)v3,v4,重復(fù)1,2,3,4
   增加的頂點(diǎn)和邊保證了v1，v2和x1,x2,...,x2m,y1,y2,...,y2m的度數(shù)為2m+1其余頂點(diǎn)度數(shù)不變
  """
  if k%2==0:
   # 選取前k+1個(gè)點(diǎn),先構(gòu)造完全圖
   vs = self.vertices()
   self.add_all_edges(vs[:k+1])
   for i in range(k+1,n):   # 對之后的點(diǎn)進(jìn)行遍歷 
    vsdel = []     # 記錄刪除過邊的頂點(diǎn)
    for e in self.edges():      
     # 獲得邊的兩個(gè)頂點(diǎn)
     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)
     # 當(dāng)已刪除的邊數(shù)為k/2，即共k個(gè)非鄰近點(diǎn)時(shí)，退出循環(huán)
     if len(vsdel)==k:
      break 
    # 將新的點(diǎn)與記錄的點(diǎn)進(jìn)行連接
    for v in vsdel:
     self.add_edge(Edge(v,vs[i]))
  else:
   if n%2==0 and n>k+1: # 由上述法則可知，n必須為偶數(shù)
    # 選取前k+1個(gè)偶數(shù)點(diǎn),先構(gòu)造完全圖
    vs = self.vertices()
    self.add_all_edges(vs[:k+1])
    for i in range(k+1,n,2): # 之后的點(diǎn)進(jìn)行兩兩遍歷
     vsdel1 = []    # 記錄第1組刪除的點(diǎn)
     edel1 = []    # 記錄第1組刪除的邊
     for e in self.edges():      
      # 獲得邊的兩個(gè)頂點(diǎn)
      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)
      # 當(dāng)已刪除的邊數(shù)為m，即共k-1個(gè)非鄰近點(diǎn)時(shí)，退出循環(huán)
      if len(vsdel1)==k-1:
       break
     vsdel2 = []    # 記錄第2組刪除的點(diǎn)
     edel2 = []    # 記錄第2組刪除的邊
     for e in self.edges():      
      # 獲得邊的兩個(gè)頂點(diǎn)
      v1,v2 = e[0],e[1]  
      # 點(diǎn)可以和第一組相同，但邊不可以
      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)
      # 當(dāng)已刪除的邊數(shù)為m，即共k-1個(gè)非鄰近點(diǎn)時(shí)，退出循環(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):
  """ 判斷一個(gè)圖是否連通的
   從任意頂點(diǎn)開始進(jìn)行一次BFS，將所有到達(dá)的節(jié)點(diǎn)都標(biāo)記上，然后檢查是否所有的節(jié)點(diǎn)都被標(biāo)記上 """
  pass
  vs = self.vertices() # 獲得所有頂點(diǎn)
  q, s = [], set()  # 搜索隊(duì)列，標(biāo)記集合
  q.append(vs[0])   # 從第1個(gè)頂點(diǎn)開始搜索
  while q:    # 當(dāng)隊(duì)列非空
   v = q.pop(0)  # 從隊(duì)列中刪除移一個(gè)頂點(diǎn)
   s.add(v)   # 并標(biāo)記當(dāng)前頂點(diǎn)
   # 搜索當(dāng)前頂點(diǎn)的連接點(diǎn)，如果這些連接點(diǎn)沒有被標(biāo)記
   # 則將其添加到隊(duì)列中
   for w in self.out_vertices(v):
    if w not in s:
     q.append(w)
  # 當(dāng)隊(duì)列為空時(shí)完成搜索，檢查標(biāo)記過的頂點(diǎn)是否等于圖的頂點(diǎn)數(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):
  """ 從一個(gè)·無邊圖開始隨機(jī)生成邊
   使得任意兩個(gè)節(jié)點(diǎn)間存在邊的概率為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)建一個(gè)迭代器
def generate_letters():
 for letter in 'abc':
  yield letter
iter = generate_letters()
import string
# 帶有無限循環(huán)的生成器會(huì)返回一個(gè)不會(huì)終止的迭代器
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()