Связные компоненты двудольных графов

Я хотел бы извлечь связанные компоненты (как двудольные графы) из двудольного графа, используя networkx. Но компоненты связности в networkx предназначены не для двудольных графов, а для общих неориентированных и прямых графов. Есть ли пример двудольного графа? Спасибо.


python networkx graph-theory connected-components bipartite
person user1424739    schedule 17.04.2020    source источник
comment
Что вы подразумеваете под связными компонентами двудольного графа, если они не являются связными компонентами базового неориентированного графа?   -  person fuglede    schedule 17.04.2020
comment
Они есть. Но компоненты должны быть представлены в виде двудольных графов. Я не думаю, что общие графики связанных компонентов будут автоматически делать это.   -  person user1424739    schedule 17.04.2020
comment
Не могли бы вы опубликовать свой полный тестовый код в качестве ответа? Спасибо.   -  person user1424739    schedule 17.04.2020

Ответы (1)


arrow_upward
1
arrow_downward

Подграфы, соответствующие связным компонентам двудольных графов (да и вообще любого графа), сами несут все атрибуты узла, так что, в частности, вы можете использовать их для обозначения своих разделов, как в документация:

In [28]: B = nx.Graph()
    ...: B.add_nodes_from([1, 2, 3, 4], bipartite=0)
    ...: B.add_nodes_from(['a', 'b', 'c'], bipartite=1)
    ...: B.add_edges_from([(1, 'a'), (1, 'b'), (2, 'b'), (2, 'a'), (3, 'c'), (4, 'c')])
    ...:
    ...: G = B.subgraph(next(nx.connected_components(B)))

In [30]: G.nodes
Out[30]: NodeView((1, 2, 'a', 'b'))

In [31]: G.nodes[1]
Out[31]: {'bipartite': 0}
person fuglede    schedule 17.04.2020
comment
Как получить узлы из двудольных 0 и 1. `для g в nx.connected_components(B): print([x для x в g, если B.nodes(data=True)[x]['bipartite'] == 0 ]) print([x вместо x в g, если B.nodes(data=True)[x]['bipartite'] == 1]) ` Я использую что-то вроде этого. Я не уверен, что это самый эффективный способ. - person user1424739; 17.04.2020
comment
Это чище: B.nodes[x]['bipartite'], а не B.nodes(data=True)[x]['bipartite']. Я не уверен, что это более эффективно, так как я не уверен, как реализовано B.nodes(data=True), но это может быть немного быстрее. Это точно не медленнее. - person Joel; 18.04.2020
comment
Я предполагаю, что в тот момент, когда вы настраиваете двудольный граф в первом случае, у вас будет какой-то способ индексации разделов, поэтому вам даже не придется искать атрибуты. - person fuglede; 18.04.2020