Python: проверить зависимости словарей массивов и проверить, является ли он круговым - PullRequest
Новая
       7

Python: проверить зависимости словарей массивов и проверить, является ли он круговым

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

У меня сложная задача. У меня есть массив словарей, структура выглядит так: 

update_logics = [
    {
        "dependency_fields": [
            "population",
            "field_1",
        ],
        "update_logic": "{return CurrentState['population'] / CurrentState['area_km2'];}",
        "updated_field": "field_2",
    },
    {
        "dependency_fields": [
            "leader",
            "fields_2",
        ],
        "update_logic": "{return 'capital is: '+ CurrentState['capital'];}",
        "updated_field": "field_3",
    },
    {
        "dependency_fields": [
            "leader",
            "fields_3",
        ],
        "update_logic": "{return 'capital is: '+ CurrentState['capital'];}",
        "updated_field": "field_1",
    },
]

Я хотел бы проверить каждый updated_field в массиве. updated_field зависит от зависимых полей

Если у меня круговая зависимость, я хотел бы вернуть False или любую отметку. Если он не циклический, я бы хотел получить глубину зависимостей.

Я думаю, рекурсия здесь полезна, но я не понимаю, как работать с массивами: 

def check(arr, parent, el):
    for item in arr:
        item["updated_field"] ==el
        for child in item["dependency_fields"]:
            if child == el or child == parent:
                # circular
                return False
            else:
                # arr_for_check.append(child)
                check(arr, child, el)

Так что здесь рекурсия будет работать для первого элемента в списке всегда.

1 Ответ

1 голос
/ 14 апреля 2020

Чтобы расширить мой комментарий - просто используйте networkx вместо того, чтобы заново изобретать колесо ? 

import networkx as nx

update_logics = [
    {"dependency_fields": ["population", "field_1"], "updated_field": "field_2"},
    {"dependency_fields": ["leader", "field_2"], "updated_field": "field_3"},
    {"dependency_fields": ["leader", "field_3"], "updated_field": "field_1"},
]

g = nx.DiGraph()
for l in update_logics:
    g.add_node(l["updated_field"])
    for dep in l["dependency_fields"]:
        g.add_edge(l["updated_field"], dep)

for f in g:
    all_deps = set()
    for depth, (node, edges) in enumerate(nx.bfs_successors(g, f)):
        all_deps.update(set(edges))
    print(f, "->", depth, all_deps)

print("===")
for cycle in nx.simple_cycles(g):
    print("CYCLE:", cycle)

выводит например 

field_2 -> 1 {'population', 'leader', 'field_3', 'field_1'}
population -> 0 set()
field_1 -> 2 {'field_3', 'field_2', 'population', 'leader'}
field_3 -> 1 {'population', 'field_2', 'field_1', 'leader'}
leader -> 0 set()
===
CYCLE: ['field_3', 'field_2', 'field_1']
...