Как распутать график? - PullRequest
Новая
       8

Как распутать график?

2 голосов
/ 25 января 2020

У меня есть API, который отправляет мне информацию о следующем исходном графе (Вы можете предположить, что у A, B & C есть общий родительский элемент)

Constructed graph

как следующее JSON (игнорировать строковые и числовые значения, чисто репрезентативные; порядок ключей не определен c) 

{
    "f": {
        "childOf": {
            "d": "own"
        },
        "data": 6
    },
    "d": {
        "childOf": {
            "b": "foster"
        },
        "data": 4
    },
    "a": {
        "data": 1
    },
    "h": {
        "childOf": {
            "f": "step"
        },
        "data": 8
    },
    "g": {
        "childOf": {
            "e": "foster",
            "a": "own"
        },
        "data": 7
    },
    "c": {
        "data": 3
    },
    "e": {
        "childOf": {
            "c": "step"
        },
        "data": 5
    },
    "b": {
        "data": 2
    },
    "i": {
        "childOf": {
            "a": "step"
        },
        "data": 9
    }
}

Для построения графического представления из json, я написал функцию, которая дает мне уровни, на которых находится каждый узел, на основе данных, предоставленных свойством childOf. В результате получается что-то вроде 

[
    ["a", "b", "c"],
    ["i", "d", "e"],
    ["g", "f"],
    ["h"]
]

, которое, хотя и является верным по вертикали, не учитывает порядок узлов слева в исходном представлении. Это иногда приводит к следующему (запутанному) графику (см. Красные и синие края)

Tangled Reconstruction

Как бы я мог получить распутанный график из информации в приведенном выше JSON формат? (зная, что исходное представление всегда распутано, и, следовательно, должно существовать распутанное решение)

Идея 1: У меня есть идея для реализации - DFS с приоритетом. Например, если DFS начинается с A и достигает G, ей следует установить приоритет E, а затем C, когда он выбирает братьев и сестер для погружения для следующей ветви.

...