Как представить странный граф в некоторой структуре данных

Question

Простой способ представления графика - это структура данных в форме:

{1:[2,3],
 2:[1,3],
 3:[1,2]}

Где ключи в этом словаре являются узлами, а ребра представлены списком других узлов, которыми они являютсясоединен с.Эта структура данных также может легко представлять ориентированный граф, если ссылки не симметричны:

{1:[2],
 2:[3],
 3:[1]}

Я не очень разбираюсь в теории графов, поэтому то, что я собираюсь предложить, может уже иметьпростое решение, но я не знаю, что искать.Я столкнулся с ситуацией, когда граф несколько ориентирован, в зависимости от того, на каком узле вы находитесь, и на каком узле вы пришли.Чтобы проиллюстрировать это, у меня есть рисунок:

Представьте, что вы движетесь по краю A в картинге, а в узле 1 вы вешаете налево на ребро B.Вы идете так быстро, когда вы попадаете на узел 3, вы вынуждены продолжать движение по краю F. Однако, если вы шли от края F, вы могли бы перейти либо к краю E, либо к B. Очевидно, чтоузел три связан с 1 и 2, но то, сможете ли вы добраться до них с этого узла, зависит от того, в каком направлении вы пришли.

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

Редактировать: я пытался опубликовать изображение, чтобы согласиться с этим, но я не уверен, еслиэто появляетсяЕсли это не так, вот ссылка на изображение

Редактировать 2: Я должен был быть ясным.Размещенное изображение предназначено для того, чтобы быть частью полного графика, в котором есть больше узлов за пределами экрана от A, D и F.

Answer 1

Это может быть представлено направленным графом .

Узлы в вашем графике могут быть представлены как два узла в графе.Думайте об узлах как о представлении местоположения на определенных сторонах улицы - края подобны входящим и исходящим полосам.

Answer 2

Представьте свой график как отображение строк в сопоставлении строк и множеств.

Чтобы быть более понятным, в python у вас будет:

graph = {
    'A': {
        'B': set(['C', 'D', ...]),
        'E': set(['F']),
    },
    ...
}

Между A и B существует ребро, если ключ B содержится в записи A в отображении graph.

По этому краю можно пройти, если узел, из которого мы пришли, содержится в наборе, сопоставленном graph['A']['B'].

Следующий класс python реализует эту спецификацию (вы можете найти закомментированную версию в this gist ):

class Graph(object):
    def __init__(self):
        self.nodes = {}

    def addEdge(self, (node1, comingFrom1), (node2, comingFrom2)):
        self.nodes.setdefault(node1, {})[node2] = comingFrom1
        self.nodes.setdefault(node2, {})[node1] = comingFrom2

    def isEdge(self, comingFrom, passingBy, goingTo):
        try:
            return comingFrom in self.nodes[passingBy][goingTo]
        except KeyError:
            return False

    def destinations(self, comingFrom, passingBy):
        dests = set()
        try:
            for node, directions in self.nodes[passingBy].iteritems():
                if comingFrom in directions:
                    dests.add(node)
        except KeyError:
            pass

        return dests

    def sources(self, passingBy, goingTo):
        return self.destinations(goingTo, passingBy)

Этот класс можно использовать так:

    >>> graph = Graph()
>>> graph.addEdge(('0', set([        ])), ('1', set(['3', '2'])))
>>> graph.addEdge(('1', set(['0'     ])), ('3', set(['4'     ])))
>>> graph.addEdge(('1', set(['0'     ])), ('2', set(['5'     ])))
>>> graph.addEdge(('3', set(['1', '2'])), ('4', set([        ])))
>>> graph.addEdge(('3', set(['4'     ])), ('2', set(['5'     ])))
>>> graph.addEdge(('2', set(['1', '3'])), ('5', set([        ])))

>>> print graph.isEdge('0', '1', '3')
True
>>> print graph.isEdge('1', '3', '2')
False
>>> print graph.isEdge('1', '2', '5')
True
>>> print graph.isEdge('5', '2', '3')
True
>>> print graph.isEdge('3', '2', '5')
True

>>> print graph.destinations('0', '1')
set(['3', '2'])
>>> print graph.destinations('1', '3')
set(['4'])
>>> print graph.destinations('3', '4')
set([])

>>> print graph.sources('0', '1')
set([])
>>> print graph.sources('1', '3')
set(['0'])
>>> print graph.sources('3', '4')

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

Answer 3

Вы можете реализовать его как базовый граф с узлами и ребрами. В каждом узле хранится список ребер. Для каждого из этих ребер сохраните отображение от этого «входного» ребра до допустимых выходных ребер.

Следует отметить, что размещенное вами изображение не является графиком, поскольку A, F и D не подключаются ни к каким узлам (если только они не находятся вне экрана).