cómo representar una extraña gráfica de alguna estructura de datos

Question

Una forma sencilla de representar un gráfico es una estructura de datos de la forma:

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

donde las claves en este diccionario son los nodos y los bordes están representados por una lista de otros nodos a los que están conectados. Esta estructura de datos también puede representar fácilmente un grafo dirigido, si los enlaces no son simétricos:

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

no sé mucho sobre el gráfico en teoría, por lo que lo que voy a proponer ya podría tener una solución sencilla , pero no sé qué buscar Me encontré con lo que creo que es una situación en la que un gráfico se dirige de alguna manera, dependiendo del nodo en el que se encuentre y del nodo del que proviene. Para ilustrar esto, tengo un dibujo:

Imagínese que usted está acelerando a lo largo del borde A en un kart y en el nodo 1 que colgar a la izquierda en el borde B. Puesto que vas tan rápido, cuando tocas el nodo 3, te ves forzado a continuar hacia el borde F. Sin embargo, si vienes del borde F, podrías continuar con el borde E o B. Está claro que el nodo tres está conectado a 1 y 2, pero si puedes o no alcanzarlos desde ese nodo depende de la dirección de donde vienes.

Me pregunto si hay un concepto de teoría de grafos que describe esto y/o si hay una estructura de datos simple para describirlo. Mientras escribo mi código en Python, recibiré consejos provenientes de cualquier lenguaje razonablemente aplicable.

Editar: Traté de publicar una imagen para ir junto con esto, pero no estoy seguro de si se está mostrando. Si no está aquí, hay un enlace al image

Editar 2: Debí haber estado libre. La imagen publicada está destinada a ser una parte de un gráfico completo, en el que hay más nodos fuera de la pantalla de A, D y F.

Answer 1

Esto podría estar representado por un directed graph.

Los nodos en su gráfico podrían representarse como dos nodos en el gráfico. Piense en los nodos como representando ubicaciones en lados particulares de una calle, los bordes son como carriles de entrada y salida.

Answer 2

Se puede aplicar como un gráfico básico con nodos y bordes. En cada nodo, almacene una lista de bordes. Para cada uno de esos bordes, almacene una asignación desde ese borde de "entrada" a los bordes de salida válidos.

Debo señalar que la imagen que ha publicado no es un gráfico, ya que A, F y D no se conectan a ningún nodo (a menos que estén fuera de la pantalla).

Answer 3

Represente su gráfico como un mapeo de cadenas para el mapeo de cadenas a conjuntos.

Para ser más claro, en python que tendría que: existe

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

un borde entre A y B si la clave B está contenido por la entrada A en el mapeo.

Este borde se puede recorrer si el nodo del que venimos está incluido en el conjunto asignado por graph['A']['B'].

La siguiente clase de pitón implementa esta especificación (se puede encontrar una versión comentado 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) 

Esta clase se puede utilizar como esto:

>>> 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') 

Las estructuras de datos elegido y su el uso ya permite construir un gráfico dirigido, solo el método addEdge necesitaría ser adaptado.