如何在一些数据结构中表示一个奇怪的图形

A simple way to represent a graph is with a data structure of the form:

表示图形的一种简单方法是使用表单的数据结构:

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

Where the keys in this dictionary are nodes, and the edges are represented by a list of other nodes they are connected to. This data structure could also easily represent a directed graph if the links are not symmetrical:

这个字典中的键是节点，而边是由它们连接到的其他节点的列表表示的。如果链接不对称，这个数据结构也可以很容易地表示一个有向图:

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

I don't know much about the graph-theory, so what I'm about to propose might already have a simple solution, but I don't know what to look for. I've encountered what I think is a situation where a graph is somewhat directed, depending on both the node you're at, and the node you came from. To illustrate, I have a drawing:

我对图形理论不太了解，所以我将要提出的可能已经有了一个简单的解决方案，但我不知道该寻找什么。我遇到过这样的情况，图是有方向的，取决于你所在的节点和你来自的节点。举个例子，我有一幅图:

Imagine you're speeding along edge A in a go-kart and at node 1 you hang a left onto edge B. Since you're going so fast, when you hit node 3, you're forced to continue onto edge F. However, if you were coming from edge F, you would be able to go on to either edge E or B. It is clear that node three is connected to 1 and 2, but whether or not you can reach them from that node depends on which direction you came from.

想象你正在边飞驰一分之一卡丁车在节点1你挂一个左边缘b .既然你跑那么快,当你点击节点3,你不得不继续到边缘F .但是,如果你是来自边缘F,你将能够继续边E或b .很明显,节点三个连接1和2,但是你是否可以从该节点到达取决于你来自哪个方向。

I'm wondering if there is a graph theory concept that describes this and/or if there is a simple data structure to describe it. While I'll be writing my code in python, I'll take advice coming from any reasonably applicable language.

我想知道是否有一个图论概念来描述它，或者是否有一个简单的数据结构来描述它。当我用python编写代码时，我将听取任何合理适用的语言的建议。

Edit: I tried to post an image to go along with this, but I'm not sure if it's showing up. If it isn't here's a link to the image

编辑:我试图发布一个图片来配合这个，但我不确定它是否会出现。如果它不是这里的图像链接。

Edit 2: I should have been clear. The image posted is meant to be a portion of a complete graph, in which there are more nodes off screen from A, D, and F.

编辑2:我应该说清楚的。发布的图像应该是一个完整图形的一部分，在这个图中，从a、D和F中有更多的节点。

3 个解决方案

#1

This could be represented by a directed graph.

这可以用有向图表示。

Nodes in your graph could be represented as two nodes in the graph. Think of the nodes as representing locations on particular sides of a street -- the edges being like inbound and outbound lanes.

图中的节点可以表示为图中的两个节点。可以将节点看作是表示街道特定一侧的位置——边缘就像入站和出站的车道。

#2

You could implement it as a basic graph with nodes and edges. In each node, store a list of edges. For each of those edges, store a mapping from that "entry" edge, to the valid exit edges.

你可以把它作为一个有节点和边的基本图来实现。在每个节点中，存储一个边缘列表。对于每条边，存储从“入口”边到有效出口边的映射。

I should point out that the image you posted isn't a graph, since A, F, and D do not connect to any nodes (unless they're just off-screen).

我要指出的是，您发布的图像不是图形，因为a、F和D不连接任何节点(除非它们只是在屏幕之外)。

#3

Represent your graph as a mapping of strings to mapping of strings to sets.

将图形表示为字符串到字符串到集合的映射。

To be more clear, in python you would have:

更明确地说，在python中，您应该有:

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

An edge exists between A and B if the key B is contained by the entry A in the graph mapping.

如果密钥B由图映射中的条目A包含，则A和B之间存在一条边。

This edge can be walked if the node from which we come from is contained in the set mapped to by graph['A']['B'].

如果我们来自的节点包含在由图['A']['B']映射到的集合中，则可以遍历这条边。

The following python class implements this specification (you can find a commented version on this gist):

下面的python类实现了这个规范(您可以在这个要点上找到一个注释版本):

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)

This class can be used like this:

这个类可以这样使用:

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

The chosen data structures and their usage already allows to build a directed graph, only the addEdge method would need to be adapted.

所选择的数据结构及其使用已经允许构建有向图，只需要修改addEdge方法。