Mercurial > repos > shellac > sam_consensus_v3
comparison env/lib/python3.9/site-packages/networkx/algorithms/bipartite/__init__.py @ 0:4f3585e2f14b draft default tip
"planemo upload commit 60cee0fc7c0cda8592644e1aad72851dec82c959"
author | shellac |
---|---|
date | Mon, 22 Mar 2021 18:12:50 +0000 |
parents | |
children |
comparison
equal
deleted
inserted
replaced
-1:000000000000 | 0:4f3585e2f14b |
---|---|
1 r""" This module provides functions and operations for bipartite | |
2 graphs. Bipartite graphs `B = (U, V, E)` have two node sets `U,V` and edges in | |
3 `E` that only connect nodes from opposite sets. It is common in the literature | |
4 to use an spatial analogy referring to the two node sets as top and bottom nodes. | |
5 | |
6 The bipartite algorithms are not imported into the networkx namespace | |
7 at the top level so the easiest way to use them is with: | |
8 | |
9 >>> from networkx.algorithms import bipartite | |
10 | |
11 NetworkX does not have a custom bipartite graph class but the Graph() | |
12 or DiGraph() classes can be used to represent bipartite graphs. However, | |
13 you have to keep track of which set each node belongs to, and make | |
14 sure that there is no edge between nodes of the same set. The convention used | |
15 in NetworkX is to use a node attribute named `bipartite` with values 0 or 1 to | |
16 identify the sets each node belongs to. This convention is not enforced in | |
17 the source code of bipartite functions, it's only a recommendation. | |
18 | |
19 For example: | |
20 | |
21 >>> B = nx.Graph() | |
22 >>> # Add nodes with the node attribute "bipartite" | |
23 >>> B.add_nodes_from([1, 2, 3, 4], bipartite=0) | |
24 >>> B.add_nodes_from(["a", "b", "c"], bipartite=1) | |
25 >>> # Add edges only between nodes of opposite node sets | |
26 >>> B.add_edges_from([(1, "a"), (1, "b"), (2, "b"), (2, "c"), (3, "c"), (4, "a")]) | |
27 | |
28 Many algorithms of the bipartite module of NetworkX require, as an argument, a | |
29 container with all the nodes that belong to one set, in addition to the bipartite | |
30 graph `B`. The functions in the bipartite package do not check that the node set | |
31 is actually correct nor that the input graph is actually bipartite. | |
32 If `B` is connected, you can find the two node sets using a two-coloring | |
33 algorithm: | |
34 | |
35 >>> nx.is_connected(B) | |
36 True | |
37 >>> bottom_nodes, top_nodes = bipartite.sets(B) | |
38 | |
39 However, if the input graph is not connected, there are more than one possible | |
40 colorations. This is the reason why we require the user to pass a container | |
41 with all nodes of one bipartite node set as an argument to most bipartite | |
42 functions. In the face of ambiguity, we refuse the temptation to guess and | |
43 raise an :exc:`AmbiguousSolution <networkx.AmbiguousSolution>` | |
44 Exception if the input graph for | |
45 :func:`bipartite.sets <networkx.algorithms.bipartite.basic.sets>` | |
46 is disconnected. | |
47 | |
48 Using the `bipartite` node attribute, you can easily get the two node sets: | |
49 | |
50 >>> top_nodes = {n for n, d in B.nodes(data=True) if d["bipartite"] == 0} | |
51 >>> bottom_nodes = set(B) - top_nodes | |
52 | |
53 So you can easily use the bipartite algorithms that require, as an argument, a | |
54 container with all nodes that belong to one node set: | |
55 | |
56 >>> print(round(bipartite.density(B, bottom_nodes), 2)) | |
57 0.5 | |
58 >>> G = bipartite.projected_graph(B, top_nodes) | |
59 | |
60 All bipartite graph generators in NetworkX build bipartite graphs with the | |
61 `bipartite` node attribute. Thus, you can use the same approach: | |
62 | |
63 >>> RB = bipartite.random_graph(5, 7, 0.2) | |
64 >>> RB_top = {n for n, d in RB.nodes(data=True) if d["bipartite"] == 0} | |
65 >>> RB_bottom = set(RB) - RB_top | |
66 >>> list(RB_top) | |
67 [0, 1, 2, 3, 4] | |
68 >>> list(RB_bottom) | |
69 [5, 6, 7, 8, 9, 10, 11] | |
70 | |
71 For other bipartite graph generators see | |
72 :mod:`Generators <networkx.algorithms.bipartite.generators>`. | |
73 | |
74 """ | |
75 | |
76 from networkx.algorithms.bipartite.basic import * | |
77 from networkx.algorithms.bipartite.centrality import * | |
78 from networkx.algorithms.bipartite.cluster import * | |
79 from networkx.algorithms.bipartite.covering import * | |
80 from networkx.algorithms.bipartite.edgelist import * | |
81 from networkx.algorithms.bipartite.matching import * | |
82 from networkx.algorithms.bipartite.matrix import * | |
83 from networkx.algorithms.bipartite.projection import * | |
84 from networkx.algorithms.bipartite.redundancy import * | |
85 from networkx.algorithms.bipartite.spectral import * | |
86 from networkx.algorithms.bipartite.generators import * |