Networkx: найдите все минимальные разрезы, состоящие только из узлов из одного набора в двудольном графе

Ответ 1

Как указано в комментарии, существует пара интерпретаций "всех node разрезов минимального размера, состоящих только из узлов из одного набора в двудольном графе". Это означает, что

• Все node разрезы минимального размера при ограничении разрезов в одном наборе двудольного графика или
• Все node разрезают безусловный смысл (состоящий из узлов из A или B), которые полностью входят в B.

Из вашего примера кода, который вас интересует 2. Согласно документам, есть способ ускорить этот расчет, а из результатов профиля он немного помогает. Для определения минимальных разрезов node построены вспомогательные структуры на каждый граф. Каждый node заменяется двумя узлами, добавляются дополнительные направленные ребра и т.д. В соответствии с алгоритмом 9 в http://www.cse.msu.edu/~cse835/Papers/Graph_connectivity_revised.pdf Мы можем повторно использовать эти структуры, а не восстанавливать их внутри жесткой петли:

Улучшение для случая 2:

from networkx.algorithms.connectivity import (
    build_auxiliary_node_connectivity)
from networkx.algorithms.flow import build_residual_network

from networkx.algorithms.flow import edmonds_karp

def getone_sided_cuts_Case2(G, A, B):
    # build auxiliary networks
    H = build_auxiliary_node_connectivity(G)
    R = build_residual_network(H, 'capacity')


    # get all cutes that consist of nodes exclusively from B which disconnet
    # nodes from A
    one_sided_cuts = []
    seen           = []

    l = list(combinations(A,2))

    for x in l:
        s = x[0]
        t = x[1]

    cut = minimum_st_node_cut(G, s, t, auxiliary=H, residual=R)
    if set(cut).issubset(B):
        if cut not in seen:
            one_sided_cuts.append(cut)
    seen.append(cut)

    # Find minimum cut size
    cur_min = float('inf')
    for i in one_sided_cuts:
        if len(i) < cur_min:
            curr_min = len(i)

    one_sided_cuts = [x for x in one_sided_cuts if len(x) == cur_min]

    return one_sided_cuts

Для целей профилирования вы можете использовать следующее или один из встроенных двудольных генераторов графов в Networkx:

def create_bipartite_graph(size_m, size_n, num_edges):
    G = nx.Graph()

    edge_list_0 = list(range(size_m))
    edge_list_1 = list(range(size_m,size_m+size_n))
    all_edges = []

    G.add_nodes_from(edge_list_0, bipartite=0)
    G.add_nodes_from(edge_list_1, bipartite=1)

    all_edges = list(product(edge_list_0, edge_list_1))
    num_all_edges = len(all_edges)

    edges = [all_edges[i] for i in random.sample(range(num_all_edges), num_edges)]
    G.add_edges_from(edges)

    return G, edge_list_0, edge_list_1

Используя %timeit, вторая версия работает на 5-10% быстрее.

Для случая 1 логика немного более сложна. Нам нужно рассмотреть минимальные сокращения от узлов только внутри B. Это требует изменения на minimum_st_node_cut следующим образом. Затем замените все вхождения от minimum_st_node_cut до rest_minimum_st_node_cut в ваше решение или решение Case 2, указанное выше, отметив, что новая функция также требует спецификации наборов A, B, обязательно:

def rest_build_auxiliary_node_connectivity(G,A,B):
    directed = G.is_directed()

    H = nx.DiGraph()

    for node in A:
        H.add_node('%sA' % node, id=node)
        H.add_node('%sB' % node, id=node)
        H.add_edge('%sA' % node, '%sB' % node, capacity=1)

    for node in B:
        H.add_node('%sA' % node, id=node)
        H.add_node('%sB' % node, id=node)
        H.add_edge('%sA' % node, '%sB' % node, capacity=1)        

    edges = []
    for (source, target) in G.edges():
        edges.append(('%sB' % source, '%sA' % target))
        if not directed:
            edges.append(('%sB' % target, '%sA' % source))
    H.add_edges_from(edges, capacity=1)

    return H

def rest_minimum_st_node_cut(G, A, B, s, t, auxiliary=None, residual=None, flow_func=edmonds_karp):

    if auxiliary is None:
        H = rest_build_auxiliary_node_connectivity(G, A, B)
    else:
        H = auxiliary

    if G.has_edge(s,t) or G.has_edge(t,s):
        return []
    kwargs = dict(flow_func=flow_func, residual=residual, auxiliary=H)

    for node in [x for x in A if x not in [s,t]]:
        edge = ('%sA' % node, '%sB' % node)
        num_in_edges = len(H.in_edges(edge[0]))
        H[edge[0]][edge[1]]['capacity'] = num_in_edges

    edge_cut = minimum_st_edge_cut(H, '%sB' % s, '%sA' % t,**kwargs)

    node_cut = set([n for n in [H.nodes[node]['id'] for edge in edge_cut for node in edge] if n not in A])

    return node_cut - set([s,t])

Тогда мы имеем, например:

In [1]: G = nx.Graph()
        # A = [0,1,2,3], B = [4,5,6,7]
In [2]: G.add_edges_from([(0,4),(0,5),(1,6),(1,7),(4,1),(5,1),(6,3),(7,3)])
In [3]: minimum_st_node_cut(G, 0, 3)
           {1}
In [4]: rest_minimum_st_node_cut(G,A,B,0,3)
           {6, 7}

Наконец, обратите внимание, что функция minimum_st_edge_cut() возвращает [], если два узла смежны. Иногда соглашение заключается в возврате набора узлов n-1 в этом случае, всех узлов, кроме источника или приемника. Во всяком случае, с пустым соглашением о списках, и поскольку ваше исходное решение для Case 2 завершает работу над парами node в A, вы, скорее всего, получите [] как возвращаемое значение для большинства конфигураций, если только узлы в A не будут смежные, скажем.

ИЗМЕНИТЬ

ОП столкнулась с проблемой двудольных графов, для которых множества A, B содержали смесь целых чисел и типов str. Мне кажется, что build_auxiliary_node_connectivity преобразует эти узлы str в целые числа, вызывающие столкновения. Я переписал вещи выше, я думаю, что это позаботится. Я ничего не вижу в документах networkx об этом, поэтому либо используйте все целые узлы, либо используйте над ним rest_build_auxiliary_node_connectivity().