I have an algorithm that creates a graph that has all representations of 4-bit binary strings encoded in the form of the shortest graph paths, where an even number in the path means 0, while an odd number means 1:
from itertools import permutations, product import networkx as nx import matplotlib.pyplot as plt import progressbar import itertools g = nx.Graph() dodane_pary=[] def groups(sources, template): func = permutations keys = sources.keys() combos = [func(sources[k], template.count(k)) for k in keys] for t in product(*combos): d = {k: iter(n) for k, n in zip(keys, t)} yield [next(d[k]) for k in template] def main(): bar = progressbar.ProgressBar(maxval=len(list(itertools.product(tuple(range(2)), repeat=4)))).start() count=1 dobre2=[] # I create 4-bit binary strings for y,i in enumerate(itertools.product(tuple(range(2)), repeat=4)): # I do not include one of the pairs of binary strings that have a mirror image if tuple(reversed(i)) >= tuple(i): # I create representations of binary strings, where 0 is 'v0' and 1 is 'v1'. For example, the '001' combination is now 'v0v0v1' a = ['v{}'.format(x%2) for x in i] if len(dodane_pary)!=count+1: # I add an even number if it was not or an odd number if it was not in the 'dobre2' list for p in range(2): if len([i for i in dobre2 if i%2 == p ])==0: dobre2.insert(p,p) h=0 while len(dodane_pary)<count: if h!=0: # extends the list 'dobre2' by subsequent even and odd numbers if the step 'h = 0' did not give the desired effects for q in range(2): g.add_node([i for i in dobre2 if i%2 == q][-1] + 2) dobre2.append([i for i in dobre2 if i%2 == q][-1] + 2) sources={} for x in range(2): sources["v{0}".format(x)] = [i for i in dobre2 if i%2 == x] # for each representation in the form 'v0v0v1' for example, I examine all combinations of strings where 'v0' is an even number 'a' v1 'is an odd number, choosing values from the' dobre2 'list and checking the following conditions. for aaa_binary in groups(sources, a): if len(dodane_pary)!=count: # adding new nodes and edges if they did not exist g.add_nodes_from (aaa_binary) t1 = (aaa_binary[0],aaa_binary[1]) t2 = (aaa_binary[1],aaa_binary[2]) t3 = (aaa_binary[2],aaa_binary[3]) added_now = [] for edge in (t1,t2,t3): if not g.has_edge(*edge): g.add_edge(*edge) added_now.append(edge) dodane_pary.append(aaa_binary) # checking the condition whether the shortest path condition on the existing graph is met after the added edges. if not, newly removed edges remove. for j in range(len(dodane_pary)): if nx.shortest_path(g, aaa_binary[0], aaa_binary[3])!=aaa_binary or nx.shortest_path(g, dodane_pary[j][0], dodane_pary[j][3])!=dodane_pary[j]: for edge in added_now: g.remove_edge(*edge) dodane_pary.remove(aaa_binary) break if len(dodane_pary)==count: break h=h+1 count +=1 bar.update(y) main() g.remove_nodes_from(nx.isolates(g)) pos=nx.circular_layout(g) plt.figure(3,figsize=(8,8)) nx.draw_networkx_edges(g,pos) nx.draw(g,pos) nx.draw_networkx_labels(g,pos) print (dodane_pary) plt.show()
Output paths representing 4-bit binary strings from dodane_pary
:
[[0, 2, 4, 6], [0, 2, 4, 1], [0, 2, 3, 8], [0, 2, 3, 5], [2, 3, 8, 7], [6, 1, 3, 8], [2, 3, 5, 9], [11, 0, 2, 3], [11, 4, 1, 5], [7, 1, 5, 9]]
So these are representations of 4-bit binary strings:
[0000, 0001, 0010, 0011, 0101, 0110, 0111, 1001, 1011, 1111]
Of course, as you can see, there are no reflections of the mirrored strings, because there is no such need in an undirected graph.
Graph:
The time the code works is the biggest problem. Because in this quite simple example at the end of the algorithm’s operation, the dobre2
list has 12 values:[0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11]
, from which the tested there are all four-element sub-lists. However, for example, I would like to build a graph with all representations of 8-bit strings. It’s easy to imagine what size the dobre2
list will grow at some stage.
And unfortunately I do not see any other way to check step by step, because I have not found any mathematical theory matching my problem. For example, the Hamilton cube is built a little differently.
Can multiprocessing be used in the code constructed in this way? Because I’ve tried everything but to no avail.
Trying to speed up the operation of the code, I also tried to reject the combinations written to an additional list, but unfortunately such a list quickly grows to very large sizes and placing a condition checking whether a given combination exists on the list, which further extends the algorithm’s working time.
Or maybe you can somehow optimize the code? I will be grateful for every clue.