прикреплённый файл:LinuxNetwork2020_gen.py к странице LecturesCMC/LinuxNetwork2020

   1 #!/usr/bin/env python3
   2 # limit: 5000
   3 '''
   4 '''
   5 
   6 import networkx as nx
   7 import matplotlib.pyplot as plt
   8 import copy
   9 from networkx.algorithms.isomorphism import is_isomorphic
  10 
  11 
  12 class Net(nx.DiGraph):
  13     NTypes = {  "P" : (1, 2, "P"),
  14                 "S" : (2, 2, "S"),
  15                 "B" : (1, 1, "B"),
  16                 "V" : (1, 1, "V"),
  17                 "R" : (1, 1, "R"),
  18                 "C" : (2, 1, "R"),
  19                 "I" : (1, 0, ""),
  20                 "H" : (0, 1, "H"),
  21              }
  22 
  23     Once = { "C", "S", "P" }
  24 
  25     def __init__(self, *ap, **an):
  26         super().__init__(*ap, **an)
  27         if len(self.nodes) == 0:
  28             self += "HI"
  29 
  30     def __iadd__(self, E):
  31         A, B = self@E[0], self@E[1]
  32         self.add_edge(A, B, ntype=f"{self%A}{self%B}")
  33         return self
  34 
  35     def __matmul__(self, ntype):
  36         if len(ntype) > 1:
  37             return ntype
  38         if not ntype in self.NTypes:
  39             raise TypeError(f"No {ntype} node type")
  40         idxes = { self.nodes[h]['idx'] for h in self.nodes }
  41         idx = (min(set(range(max(idxes)+2)) - idxes)) if idxes else 0
  42         self.add_node(N := f"{ntype}{idx}", ntype=ntype, idx=idx)
  43         return N
  44 
  45     def replace(self, node, ntype):
  46         if not ntype in self.NTypes:
  47             raise TypeError(f"No {ntype} node type")
  48         if not node in self:
  49             raise KeyError(f"Node {node} is not in the graph")
  50         if self.NTypes[ntype][0] < len(self.in_edges(node)):
  51             raise IndexError(f"Minimum {len(self.in_edges(node))} inbound networks is allowed when replacing {node}, but {self.NTypes[ntype][0]} is given")
  52         if self.NTypes[ntype][1] < len(self.out_edges(node)):
  53             raise IndexError(f"Minimum {len(self.out_edges(node))} outbound networks is allowed when replacing {node}, but {ntype}={self.NTypes[ntype][1]} is given")
  54         nx.relabel_nodes(self, {node: (N:=f"{ntype}{self.nodes[node]['idx']}")}, copy=False)
  55         self.nodes[N]['ntype'] = ntype
  56         for i in range(len(self.in_edges(N)), self.NTypes[ntype][0]):
  57             self += "H", N
  58         for i in range(len(self.out_edges(N)), self.NTypes[ntype][1]):
  59             self += N, "I"
  60         for a, b in set(self.in_edges(N)) | set(self.out_edges(N)):
  61             self[a][b]['ntype'] = f"{self%a}{self%b}"
  62         return self
  63 
  64     def show(self, ax=None, Num=1):
  65 
  66         nodelist = [h for h in self if self%h != "I"]
  67         #labels = {h: (self.NTypes[self%h][2] if self%h != "I" else "") for h in self}
  68         if ax is None:
  69             fig, ax = plt.subplots()
  70 
  71         title = f"{Num}: " + " ".join(f"{a}→{b}" for a, b in sorted(self.edges) if self%b !="I")
  72         print(f" * {title}")
  73         ax.set_title(title)
  74         nx.draw_shell(self, ax=ax, 
  75                 nodelist=nodelist,
  76                 #labels=labels,
  77                 with_labels=True, 
  78                 node_size=600, 
  79                 node_color="white", 
  80                 edgecolors = "green", 
  81                 node_shape="s")
  82 
  83     def __str__(self):
  84         return " ".join(f"{a}→{b}" for a, b in self.edges)+"\n"+\
  85                 " ".join(f"{n}:{self.nodes[n]}" for n in self.nodes)
  86 
  87     def __mod__(self, node):
  88         return self.nodes[node]['ntype']
  89 
  90     def __invert__(self):
  91         return [ self % n for n in self ]
  92 
  93     def __pos__(self):
  94         return len([n for n in self if self%n != "I"])
  95 
  96     def __neg__(self):
  97         return [ f"{self%a}{self%b}" for a, b in self.edges ]
  98 
  99 def gen(N, mx=5):
 100     if +N < mx:
 101         for H in N:
 102             if N%H in "IH":
 103                 for T in list(N.NTypes)[:-2]:
 104                     if T not in N.Once & set(~N):
 105                         yield from gen(copy.deepcopy(N).replace(H, T), mx)
 106     elif +N == mx:
 107         yield N
 108 
 109 def valid(N):
 110     C = ~N
 111     return      ("V" in C or "B" in C) \
 112             and ("S" in C or "P" in C) \
 113             and C.count("P")<2 \
 114             and "VV" not in -N \
 115             and "VI" not in -N
 116 
 117 def like(N, NN):
 118     chk = lambda a, b: a['ntype'] == b['ntype']
 119     return set(~N) == set(~NN) or is_isomorphic(N, NN, chk, chk)
 120 
 121 def makepool(size):
 122     Pool = []
 123     for N in gen(Net(), 5):
 124         if valid(N):
 125             if all(not like(N, NN) for NN in Pool):
 126                 Pool.append(N)
 127     return Pool
 128 
 129 def main():
 130     Pool = makepool(5)
 131     fig, ax = plt.subplots(3, 5)
 132     idx = 0, 12, 3, 8, 1, 5, 13, 2, 10, 9, 4, 7, 6, 11
 133     for n, (i, a) in enumerate(zip(idx, ax.reshape(15))):
 134         Pool[i].show(a, n+1)
 135     plt.show()
 136     return Pool
 137 
 138 if __name__ == "__main__":
 139     main()