Как я могу улучшить свой код Python для применения к n узлам ориентированного графа? - PullRequest
Новая
       21

Как я могу улучшить свой код Python для применения к n узлам ориентированного графа?

0 голосов
/ 01 апреля 2019

В графе из четырех узлов (A, B, C, D) имеется 6 потенциальных ребер; AB, AC, AD, BC, BD, CD. Вероятность выбора ребра равна 0,2.

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

Тем не менее, это ручной ввод комбинаций. Поэтому моя проблема в том, что если есть 6 узлов (A, B, C, D, E, F) с 15 возможными ребрами, как я могу изменить свой код, чтобы применить его к n узлам.

При любом количестве узлов выше 4 этот код будет невозможен.

Есть идеи, как решить эту проблему, не вводя все возможные комбинации связного графа? 

def graph_sim(X):    
possible_edges = ['AB', 'AC', 'AD', 'BC', 'BD', 'CD'] 
distinct_connected_graphs = [
      ['AB', 'AC', 'AD', 'BC', 'BD', 'CD'], 
      ['AB', 'AC', 'AD', 'BC', 'BD'], ['AB', 'AC', 'BC', 'BD', 'CD'], ['AB', 'AC', 'AD', 'BD', 'CD'],
      ['AB', 'AC', 'AD', 'BC', 'CD'], ['AC', 'AD', 'BC', 'BD', 'CD'], ['AB', 'AD', 'BC', 'BD', 'CD'],
      ['AB', 'AC', 'AD', 'BC'], ['AB', 'AC', 'AD', 'BD'], ['AB', 'AC', 'AD', 'CD'],
      ['AB', 'AC', 'BC', 'BD'], ['AB', 'AC', 'BC', 'CD'], ['AB', 'AC', 'BD', 'CD'],
      ['AB', 'AD', 'BC', 'BD'], ['AB', 'AD', 'BC', 'CD'], ['AB', 'AD', 'BD', 'CD'],
      ['AB', 'BC', 'BD', 'CD'], ['AC', 'AD', 'BC', 'BD'], ['AC', 'AD', 'BC', 'CD'], 
      ['AC', 'AD', 'BD', 'CD'], ['AC', 'BC', 'BD', 'CD'], ['AD', 'BC', 'BD', 'CD'],
      ['AB', 'AC', 'AD'], ['AB', 'AC', 'BD'], ['AB', 'AC', 'CD'], ['AB', 'AD', 'BC'], 
      ['AB', 'AD', 'CD'], ['AB', 'BC', 'BD'], ['AB', 'BC', 'CD'], ['AB', 'BD', 'CD'],
      ['AC', 'BC', 'BD'], ['AC', 'AD', 'BD'], ['AC', 'BC', 'CD'], ['AC', 'AD', 'BC'],
      ['AC', 'BD', 'CD'], ['AD', 'BC', 'BD'], ['AD', 'BC', 'CD'], ['AD', 'BD', 'CD']
                            ]
directed_graph = [
    [edge for prob, edge in zip(np.random.uniform(low= 0.0, high= 1.0, size=6), possible_edges) if prob < 0.2]
    for i in range(X)]
connected_realisations = [i for i in directed_graph if i in distinct_connected_graphs]

print("-------------------------")
print("* The probability that a graph is connected in", X, "realisations is:", len(connected_realisations)/X)
print("* The number of connected graphs in", X, "realisations is:", len(connected_realisations))
return
graph_sim(2000)
...