python генерировать случайный график сетки - PullRequest
Новая
       26

python генерировать случайный график сетки

0 голосов
/ 14 января 2020

Я хочу сгенерировать граф сетки (также называемый решетчатым графом) в python, как показано ниже. Он должен иметь размер nxn и учитывать значение p, которое определяет вероятность, с которой один узел (красный) связан с другим.

Например, когда p равно 0,5, узел x будет связан с узлом y с помощью вероятность 50%.

grid graph У меня есть следующий код: 

class Node:
  def __init__(self, name):
    self._name = name
    self._neighbor = set()

  def newneighbor(self, n):
    self._neighbor.add(n)

  def neighbors(self):
    return self._neighbor 

  def __str__(self):
    return self._name


class Graph:

  def __init__(self, data=''):
    self._node = set()
    self._nodenames = dict()
    if not data=='':
       self._read(data)

  def _read(self, data):
    for row in open(data, 'r'):
       node = str.split(row)
       if len(node)==0: continue
       if not node[0] in self._nodenames: self.newnode(node[0])
       if not node[1] in self._nodenames: self.newnode(node[1])
       self.newedge(node[0], node[1])       

  def newnode(self, name):
    neu = Node(name)
    self._node.add(neu)
    self._nodenames[name] = neu

  def newedge(self, name1, name2):
    self[name1].newneighbor(self[name2])
    self[name2].newneighbor(self[name1])

  def __getitem__(self, name):
    return self._nodenames[name]

  def __contains__(self, name):
    return name in self._nodenames

  def __str__(self):
    s = ''
    for i in self._node:
      s += str(i) + ': '
      for n in i.neighbors():
        s += str(n) + ' '
      s += '\n'
    return s

Как я могу создать сетку nxn, как показано выше, вместо чтения в каком-нибудь файле данных?

РЕДАКТИРОВАТЬ:

Со следующими данными 

FRA TXL
**FRA AMS**
**AMS CDG**
CDG LCY
**LCY AMS**
TXL WMI
WMI XYG
CDG MRS
MRS GVA
MRS FCO
GVA XYG
FCO XYG
FRA GVA
FRA XYG

вышеупомянутый .py генерирует этот вывод: 

**AMS: LCY CDG FRA** 
GVA: MRS FRA XYG 
LCY: CDG AMS 
FCO: MRS XYG 
XYG: FRA FCO GVA WMI 
FRA: AMS GVA TXL XYG 
TXL: FRA WMI 
WMI: TXL XYG 
CDG: LCY MRS AMS 
MRS: CDG FCO GVA

Итак Предполагается, что программа генерирует сеть из заданной информации и соединяет узлы, когда между ними есть связь.

EDIT2:

Теперь я добавил следующий код: 

def _neighbours(self, m, i, j):
    return [m[x][y] for x in [i-1,i,i+1] for y in [j-1,j,j+1] if x in range(0,len(m))
            and y in range(0,len(m[x])) and (x,y) != (i,j) and (x,y) != (i+1,j+1) and (x,y) != (i-1,j-1)
            and (x,y) != (i+1,j-1) and (x,y) != (i-1,j+1)]

  def _make_matrix(self, n):
    g = list(range(1, (n * n) + 1))
    return [g[i:i+n] for i in range(0, len(g), n)]

  def _create(self, n):
    g = self._make_matrix(n)

    for i in range(0,4):
      for j in range(0,4):
          node = self._neighbours(g, i, j)
          print(node)
          #if len(node)==0: continue
          for k in range(0, len(node)):
            if not node[k] in self._nodenames: self.newnode(str(node[k])) 

          try:
              self.newedge(str(node[0]), str(node[1]), str(node[2]), str(node[3]))
          except:
            try:
                self.newedge(str(node[0]), str(node[1]), str(node[2]))
            except:
                self.newedge(str(node[0]), str(node[1]))
          else: pass

Когда я вызываю _create (), вызывается _make_matrix (self, n), который создает массив от 1 до n * n (для экспорта, когда n = 4, чем от 1 до 16) и изменяет форму массива до матрица nxn.

После этого я определяю всех прямых соседей для каждой координаты i, j inate. Это будет 2 и 5 для i = 0, j = 0.

Для каждого соседа, которого нет в _nodenames, я создаю новый узел. Но чем я застрял. Я пытался создать новое ребро между каждым соседом, но это не работает, и все, что я хочу.

Мне нужен вывод вроде: 

2: 1, 3, 6

То, что я получаю: 

2: 5
...