Как создать график, представляющий все возможности с использованием Python - PullRequest
Новая
       13

Как создать график, представляющий все возможности с использованием Python

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

Мне нужно написать код на Python, который позволит мне генерировать дерево возможностей, которые зависят друг от друга. Фактически, если у нас есть два вектора: a=[0, 1] и b=[0, 1], мы можем построить 4 различных варианта:

  • (0, 0)
  • (0, 1)
  • (1, 0)
  • (1, 1)

Если мы возьмем (0,0) в качестве родительского узла, мы можем сгенерировать 3 ребра из (0, 0) для всех других возможностей: (0, 0) -> (0, 1), (1, 0), (1, 1).

Тогда для каждой возможности мы можем сгенерировать 3 ребра для других возможностей, например:

  • (0, 1) -> (0, 0), (1, 0), (1, 1)
  • (1, 0) -> (0, 0), (1, 1), (0, 1)
  • (1, 1) -> (0, 0), (1, 0), (0, 1)

Мне нужно повторить это N раз. Результатом должно быть дерево, где у каждого неконечного узла есть 3 преемника - для каждой возможности, кроме текущей.

1 Ответ

1 голос
/ 10 апреля 2019

Правильное название вашего графика: полный график . Хорошие библиотеки обработки графов для Python - networkx - имеют специальную функцию для генерации таких графов: complete_graph

Редактировать 1: Я создал рабочий процесс для вас, который решит вашу проблему. Вы можете скопировать и вставить его в свой блокнот Jupyter, но учтите, что вам нужно:

  • NetworkX
  • Graphviz
  • pydot

для установки. 

import networkx as nx

# Set main parameters
items = {(0, 0), (0, 1), (1, 0), (1, 1)}
root = (0, 1)
N = 4

# Calculate the number of nodes for our tree
node_count = sum((len(items)-1)**i for i in range(N))

# Construct full r-rary tree
G = nx.full_rary_tree(len(items)-1, node_count, create_using=nx.DiGraph)

# Create LG-topologically sorted array of nodes
# NOTE THAT NODES' IDs AREN'T EQUAL TO YOUR ITEMS
lgts = list(nx.lexicographical_topological_sort(G))

# Get the first element to preset its label
first = lgts[0]

# Preset an empty label for all nodes
nx.set_node_attributes(G, '', 'label')

# Set the label for the root
G.nodes[first]['label'] = root

# For all nodes:
for node in lgts:
    # Get needed names
    s_labels = list(items - {G.nodes[node]['label']})
    # For all childs:
    for s_node in G.successors(node):
        # Set the child's label
        G.nodes[s_node]['label'] = s_labels.pop()

# Create dict for drawing labels
labels = {n: G.nodes[n]['label'] for n in G.nodes}

# And draw the final graph
nx.draw(
    G,
    pos=nx.nx_pydot.graphviz_layout(G, prog='dot'),
    with_labels=True,
    labels=labels
)

Наконец вы получите этот график:

enter image description here

...