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

Una forma sencilla de representar un gráfico es con una estructura de datos del formulario:

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

Donde las claves en este diccionario son 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 podría representar fácilmente un gráfico dirigido si los enlaces no son simétricos:

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

No sé mucho acerca de la teoría de los gráficos, por lo que lo que voy a proponer podría tener una solución simple, pero no sé qué buscar. Me he encontrado con lo que creo que es una situación en la que un gráfico está algo dirigido, según el nodo en el que se encuentre y el nodo del que proviene. Para ilustrar, tengo un dibujo:

Extrañamente gráfico direccional

Imagina que estás acelerando a lo largo del borde A en un go-kart y en el nodo 1 cuelgas a la izquierda en el borde B. Como vas tan rápido, cuando tocas el nodo 3, estás obligado a continuar al borde F. Sin embargo Si estuviera viniendo del borde F, podría ir al borde E o al B. Está claro que el nodo tres está conectado a 1 y 2, pero si puede alcanzarlos desde ese nodo o no, depende de cuál dirección de donde viniste

Me pregunto si hay un concepto de teoría de grafos que describa esto y / o si hay una estructura de datos simple para describirlo. Mientras escribo mi código en python, tomaré consejos que provengan de cualquier idioma que sea razonablemente aplicable.

Edit: traté de publicar una imagen para estar de acuerdo con esto, pero no estoy seguro de si está apareciendo. Si no es así, aquí hay un enlace a la imagen.

Edit 2: Debería haber sido claro. La imagen publicada debe ser una parte de un gráfico completo, en el que hay más nodos fuera de la pantalla desde A, D y F.

Esto podría ser representado por un gráfico dirigido .

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

introduzca la descripción de la imagen aquí

Podrías implementarlo como un gráfico básico con nodos y aristas. 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 publicaste 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).

Representa tu gráfica como una asignación de cadenas a la asignación de cadenas a conjuntos.

Para ser más claros, en python tendrías que:

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

Existe un borde entre A y B si la clave B está contenida en la entrada A en la asignación del graph .

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

La siguiente clase de python implementa esta especificación (puede encontrar una versión comentada en esta idea ):

 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 así:

  >>> 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 elegidas y su uso ya permiten construir un gráfico dirigido, solo el método addEdge deberá adaptarse.