forked from networkx/networkx
-
Notifications
You must be signed in to change notification settings - Fork 0
/
example_map.py
85 lines (74 loc) · 1.51 KB
/
example_map.py
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
import numpy as np
import matplotlib.pyplot as plt
import networkx as nx
G = nx.Graph()
G.add_nodes_from(
[
("1"),
("2"),
("3"),
("4"),
("5"),
("6"),
("7"),
("9"),
("10"),
]
)
G.add_edges_from(
[
("1", "2"),
("7", "2"),
("3", "9"),
("3", "2"),
("7", "6"),
("5", "2"),
("1", "5"),
("2", "8"),
("10", "2"),
("1", "7"),
("6", "1"),
("6", "9"),
("8", "4"),
("9", "4"),
]
)
from networkx.algorithms import approximation as apxa
I = apxa.maximum_independent_set(G)
M = apxa.min_maximal_matching(G)
color_map_1 = []
for node in G:
if node in I:
color_map_1.append("red")
else:
color_map_1.append("grey")
color_map_2 = []
for edge in G.edges:
if edge in M:
color_map_2.append("red")
else:
color_map_2.append("grey")
fig, axs = plt.subplots(ncols=2, figsize=(3, 2), gridspec_kw={"width_ratios": [1, 1]})
nx.draw(
G,
with_labels=True,
node_size=50,
font_size=25,
edge_color="grey",
node_color=color_map_1,
ax=axs[0],
)
nx.draw(
G,
with_labels=True,
node_size=50,
font_size=25,
edge_color=color_map_2,
node_color="grey",
ax=axs[1],
)
axs[0].set_title(
"Clique - Maximum Independent Set\nMaximum set of (red) vertices with no edge connecting them"
)
axs[1].set_title("Matching\nMaximal set of pairwise non-adjacent (red) edges")
plt.show()