python - 使用 NetworkX 在从 shapefile 导入的 MultiDiGraph 中查找循环

Question

我正在编写一个 QGIS 插件，它将使用 NetworkX 库来操作和分析流网络。我的数据来自代表流网络的形状文件。

(箭头代表水流方向)

在此流网络内有 braids这是我需要保留的重要特征。我将编织特征分为“简单”(共享两个节点的两条边)和“复杂”(两条以上的边，具有两个以上的节点)。

简单的辫子示例

复杂的辫子示例

通常，我只会使用 NetworkX 内置函数 read_shp 将 shapefile 作为有向图导入。从示例中可以明显看出，“简单”辫子将被视为 NetworkX 有向图中的平行边，因为这两条边(共享相同的 to 和 from 节点) )将被折叠成一条边。为了保留这些多条边，我们编写了一个函数，将 shapefile 导入为 MultiDiGraph。通过使用边缘对象中的唯一键来保留简单的辫子(即平行边缘)(这是嵌入在类中的):

def _shp_to_nx(self, in_network_lyr, simplify=True, geom_attrs=True):
    """
    This is a re-purposed version of read_shp from the NetworkX library.
    :param shapelayer:
    :param simplify:
    :param geom_attrs:
    :return:
    """
    self.G = nx.MultiDiGraph()


    for f in in_network_lyr.getFeatures():

        flddata = f.attributes()
        fields = [str(fi.name()) for fi in f.fields()]

        geo = f.geometry()
        # We don't care about M or Z
        geo.geometry().dropMValue()
        geo.geometry().dropZValue()

        attributes = dict(zip(fields, flddata))
        # Add a new _FID_ field
        fid = int(f.id())
        attributes[self.id_field] = fid
        attributes['_calc_len_'] = geo.length()

        # Note:  Using layer level geometry type
        if geo.wkbType() in (QgsWKBTypes.LineString, QgsWKBTypes.MultiLineString):
            for edge in self.edges_from_line(geo, attributes, simplify, geom_attrs):
                e1, e2, attr = edge
                self.features[fid] = attr
                self.G.add_edge(tuple(e1), tuple(e2), key=attr[self.id_field], attr_dict=attr)
            self.cols = self.features[self.features.keys()[0]].keys()
        else:
            raise ImportError("GeometryType {} not supported. For now we only support LineString types.".
                              format(QgsWKBTypes.displayString(int(geo.wkbType()))))

我已经编写了一个函数来查找“简单”编织特征(我只是迭代 MultiDiGraphs 节点，并查找具有多个键的边)。但我还需要找到“复杂”的辫子。通常，在图表中，我可以使用cycle_basis来查找所有“复杂”辫子(即循环)，但是，cycle_basis方法仅适用于无向图，而不是方向图。但我不想将我的 MultiDiGraph 转换为无向图，因为可能会出现与该转换相关的意外结果(更不用说丢失我的边缘键值)。

我怎样才能以一种相对省时的方式找到由多个边组成的循环？我真正使用的河流网络可能非常庞大且复杂，代表着大的流域。

谢谢!

Answer 1

所以我想出了一个解决方案，可以找到“简单”和“复杂”的辫子。

def get_complex_braids(self, G, attrb_field, attrb_name):
    """
    Create graph with the braid edges attributed
    :param attrb_field: name of the attribute field
    :return braid_G: graph with new attribute
    """
    if nx.is_directed(G):
        UG = nx.Graph(G)
        braid_G = nx.MultiDiGraph()
        for edge in G.edges(data=True, keys=True):
            is_edge = self.get_edge_in_cycle(edge, UG)
            if is_edge == True:
                braid_G.add_edge(*edge)
        self.update_attribute(braid_G, attrb_field, attrb_name)
        return braid_G
    else:
        print "ERROR: Graph is not directed."
        braid_complex_G = nx.null_graph()
        return braid_complex_G

def get_simple_braids(self, G, attrb_field, attrb_name):
    """
    Create graph with the simple braid edges attributed
    :param attrb_field: name of the attribute field
    :return braid_G: graph with new attribute
    """
    braid_simple_G = nx.MultiDiGraph()
    parallel_edges = []
    for e in G.edges_iter():
        keys = G.get_edge_data(*e).keys()
        if keys not in parallel_edges:
            if len(keys) == 2:
                for k in keys:
                    data = G.get_edge_data(*e, key=k)
                    braid_simple_G.add_edge(e[0], e[1], key=k, attr_dict=data)
        parallel_edges.append(keys)
    self.update_attribute(braid_simple_G, attrb_field, attrb_name)
    return braid_simple_G