Прикреплённый файл «2013-02-08.graph-gen.py»
Загрузка 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)
Прикреплённые файлы
Для ссылки на прикреплённый файл в тексте страницы напишите attachment:имяфайла, как показано ниже в списке файлов. Не используйте URL из ссылки «[получить]», так как он чисто внутренний и может измениться.- [получить | показать] (2013-02-15 15:23:11, 1.9 KB) [[attachment:2013-02-08.drawgraph-dumb.py]]
- [получить | показать] (2013-02-15 15:22:48, 8.8 KB) [[attachment:2013-02-08.graph-gen.py]]
- [получить | показать] (2013-02-15 15:22:25, 1.2 KB) [[attachment:2013-02-08.printtree.py]]
Вам нельзя прикреплять файлы к этой странице.