прикреплённый файл:2013-02-08.graph-gen.py к странице LecturesVMSH/Python/2013-02-08

   1 #!/usr/bin/env python
   2 # coding: utf
   3 '''
   4 Сгенерировать и представить в виде списка рёбер
   5 
   6     Какой-то граф
   7     Заведомо неориентированный граф
   8     Заведомо ориентированный граф
   9     Граф с K несвязными областями
  10     Сеть с одним истоком в первой и одним стоком в последней вершинах
  11     Произвольную сеть
  12     Ориентированный граф с циклами
  13 
  14 Вывод представляется в виде списка рёбер
  15 
  16 Внимание: соответствие количества рёбер числу вершин не проверяется!
  17 '''
  18 
  19 import sys, itertools
  20 from random import randrange, sample, random
  21 
  22 def Any(Peaks, Edges):
  23     '''Какой-то граф'''
  24     # в данном варианте ответ — это просто последовательность
  25     # пар случайных чисел в диапазоне [0…Edges[ .
  26     # Воспользуемся случаем и потренируемся в функциональном программировании.
  27     # Как в математике: формул пишется изнутри
  28     # 0. Последовательность 2*Edges вершин:
  29     #    (randrange(Peaks) for i in xrange(2*Edges))
  30     # 1. Две последовательности, вычисленные из одной
  31     #    itertools.tee(…,2)
  32     # 2. Последовательность пар из двух пос
  33     #    zip(*itertools.tee(…,2))
  34     # Итого:
  35     return zip(*itertools.tee(randrange(Peaks) for i in xrange(2*Edges)))
  36 
  37 def Oriented(Peaks, Edges):
  38     '''Хороший, годный граф без петель (A,A), двойных рёбер (A,B),…,(A,B)
  39     Может считаться заведомо ориентированным,
  40     т. к. никаких других условий на хороший, годный орграф не накладывается.
  41     Правда, вершин в нём может получиться меньше Peaks, если случится так,
  42     что хотя бы одна вершина не встретится ни в одном ребре.'''
  43     # Опять получилось почти что функциональное программирование
  44     return sample([(i,j) for i in xrange(Peaks) for j in xrange(Peaks) if i!=j], Edges)
  45 
  46 def Net(Peaks, Edges):
  47     '''Хороший, годный граф без петель, двойных рёбер и повторений (A,B),…,(B,A)
  48     Может считаться заведомо неориентированным,
  49     т. к. любую пару вершин соединяет не более одного ребра.
  50     Более того, будучи ориентированным он является сетью!
  51     '''
  52     # И снова…
  53     return sample([(i,j) for i in xrange(Peaks-1) for j in xrange(i+1,Peaks)], Edges)
  54 
  55 def Net1(Peaks, Edges):
  56     '''Сеть с одним истоком и одним стоком.
  57     Проще всего изготовить произвольную сеть, а затем налепить на все истоки
  58     общий вход, а на все стоки — общий выход.
  59     Правда, рёбер тогда будет слегка побольше… но что за беда?
  60     '''
  61     # Подсеть
  62     net=Net(Peaks-2,Edges-2)
  63     # Начала и концы всех рёбер
  64     I,O=zip(*net)
  65     # Всего вершин (вдруг некоторые «повисли»?)
  66     IO=set(I)|set(O)
  67     # Истоки и стоки
  68     Ins, Outs = set(I)-set(O), set(O)-set(I)
  69     # 0 — общий исток, Peaks-1 — общий сток (добавим 1 к номерам вершин подсети)
  70     return [(0,i+1) for i in Ins]+[(i+1,j+1) for i,j in net]+[(j+1,Peaks-1) for j in Outs]
  71 
  72 def Coherent(Peaks, Edges):
  73     '''Связный граф.
  74     В принципе, Net1() выдаёт заведомо связный граф.
  75     Но так неинтересно :)'''
  76     # Минимальный связный граф: не менее Peaks-1 рёбер
  77     L=[(randrange(i),i) for i in xrange(1,Peaks)]
  78     # плюс все остальные рёбра, лишь бы их не было в L
  79     for k in xrange(Edges-Peaks-1):
  80         i=j=0
  81         while i==j or (i,j) in L:
  82             i,j=randrange(Peaks),randrange(Peaks)
  83         L.append((i,j))
  84     return L
  85 
  86 def Bush(Peaks, Edges):
  87     '''Произвольное дерево.
  88     Количество рёбер не имеет значения, т. к. оно равно Peaks-1'''
  89     # Так из корня частенько ведёт максимальное число рёбер:
  90     # return [(randrange(i),i) for i in xrange(1,Peaks)]
  91     # попробуем уменьшить масштаб ущерба
  92     return [(randrange(i/4,i),i) for i in xrange(1,Peaks)]
  93 
  94 def Circled(Peaks, Edges):
  95     '''Орграф с циклами.'''
  96     # Это совсем не случайный ограф с циклами :(
  97     # Сгенерируем несколько циклов
  98     nc=randrange(1,Peaks/4)
  99     # сколько вершин в каждом цикле
 100     mc=[randrange(3,Peaks/(nc+1)) for i in xrange(nc)]
 101     L,m=[],0
 102     for n in mc:
 103         L.append([(m+i,m+(i+1)%n) for i in xrange(n)])
 104         m+=n
 105     # Начнём строить решение с "разворачивания" списка циклов
 106     R=list(itertools.chain(*L))
 107     # Добавим рёбра, связываюшие первые вершины графов
 108     s=[g[0][0] for g in L]
 109     R.extend(zip(s,s[1:]))
 110     # Добавим все остальные вершины
 111     R.extend([(randrange(j),j) for j in xrange(m,Peaks)])
 112     # Напихаем ещё рёбер
 113     while len(R)<min(Edges,(Peaks-1)*Peaks/2):
 114         i,j=randrange(Peaks),randrange(Peaks)
 115         if (i,j) not in R and (j,i) not in R:
 116             R.append((i,j))
 117     return R
 118 
 119 def summand(M,n):
 120     '''Представить M в виде n случайных слагаемых'''
 121     # Сгенерируем случайную линейку
 122     L=[random() for i in xrange(n)]
 123     ret=[]
 124     for i in xrange(n):
 125         # длина оставшейся линейки
 126         s=sum(L)
 127         # отделим от оставшегося M очередную долю
 128         ret.append(int(round(M*L.pop()/s)))
 129         # Уменьшим M
 130         M-=ret[-1]
 131     return ret
 132 
 133 def randhole(N,hole):
 134     '''Сгенерировать случайное число в диапазоне [0..N[,
 135     не входящее в hole (или (hole,), если holoe — это один элемент)'''
 136     if not hasattr(hole,"__iter__"):
 137         hole=(hole,)
 138     return choice(tuple(set(xrange(N))-set(hole)))
 139 
 140 def genGraph(Function=Net1, Peaks=None, PEdges=1.5, N=1):
 141     '''Сгенерировать граф функцией Function()
 142     с числом вершин Peaks (или случайным),
 143     с числом рёбер Peaks*PEdges
 144     с минимальным количеством связных областей N
 145     '''
 146     Peaks=Peaks or randrange(max(N*2,10),max(N*4,20))
 147     Edges=int(Peaks*PEdges)
 148     if N==1:
 149         ret=Function(Peaks, Edges)
 150     else: 
 151         # Минимум N несвязных областей
 152         # Для простоты будем считать, что количество вершин в каждой не менее 3
 153         # Сколько вершин будет в каждом подграфе?
 154         P=[3+i for i in summand(Peaks-N*3,N)]
 155         s,ret=0,[]
 156         for p in P:
 157             # Рёбер в подграфе не может быть больше (p-1)*p/2
 158             E=min(Edges*p/Peaks,p*(p-1)/2)
 159             # вершины очередного подграфа начинаются с первой незанятой
 160             ret+=[(i+s,j+s) for i,j in Function(p,E)]
 161             s+=p
 162     # переименуем вершины и перемешаем рёбра ради вящей случайности
 163     code=sample(xrange(Peaks),Peaks)
 164     return sample([(code[i],code[j]) for i,j in ret],len(ret))
 165 
 166 if __name__ == "__main__":
 167   try:
 168     Funct=len(sys.argv)>1 and eval(sys.argv[1]) or Bush
 169     Peaks=len(sys.argv)>2 and int(sys.argv[2]) or 40
 170     PEdges=len(sys.argv)>3 and float(sys.argv[3]) or 1.5
 171     NSep=len(sys.argv)>3 and int(sys.argv[3]) or 1
 172     Funct.__call__
 173   except:
 174     print >> sys.stderr, "Usage:\n\t", sys.argv[0], "Type Peaks PEdges Grapgs"
 175     print >> sys.stderr, "Types: ",", ".join(f for f in dir() if f[0].isupper())
 176     sys.exit(1)
 177   print genGraph(Funct, Peaks, PEdges, NSep)