trjhtr

Update: Important notes to understand the problem can be found in the comments under the response of colleague Gareth Rees's.

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] 

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["v0".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)

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 to 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? I ask because I've tried everything but to no avail.

In particular, can I use multiprocessing for the for aaa_binary in groups (sources, a) loop? Because groups (sources, a) contains all the possibilities that represent a given binary string. And here the order of checking and searching for the correct combination would not matter. However, the itself loop add edges to a graph, then tests whether that was a good idea, and takes them back out if not.

1. Summary of the problem

The problem, as described in the post, is to construct an undirected graph with numbered nodes, such that for every $0 le k < 2^n$ there is a pair of nodes in the graph $a, b$ such that one of the shortest routes from $a$ to $b$ is $a=a_1, a_2, ldots, a_n=b$, and $$ a_i equiv leftlfloor k over 2^n-i rightrfloor pmod 2.$$

2. Brute force approach

A graph meeting the constraints in the post can be constructed in time $Theta(n2^n)$ like this:

import itertools
import networkx as nx

def route_parity_graph(n):
 """Return a graph such that every n-bit number is represented by
 the parity of the nodes along the shortest route between two
 nodes.

 """ 
 node_number = itertools.count(step=2)
 g = nx.Graph()
 for i in range(2 ** n):
 old = None
 if i > sum(((i >> j) & 1) << (n - j - 1) for j in range(n)):
 # Reverse of i has already been added to graph.
 continue
 for j in range(n):
 node = next(node_number) + ((i >> j) & 1)
 g.add_node(node)
 if old is not None:
 g.add_edge(old, node)
 old = node
 return g

This generates graphs with $$nleft(2^n-1+2^leftlfloorn-1over2rightrfloorright)$$ nodes, where each shortest path is a separate connected component, for example:

3. Binary digits approach

Here's an alternative approach that runs in $Theta(n)$ and generates the smallest possible graphs meeting the constraints in the post:

def route_parity_graph(n):
 """Return a graph such that the every n-bit number is represented by
 the parity of the nodes along one of the shortest routes between two
 nodes.

 """ 
 g = nx.Graph()
 for i in range(2 * n):
 g.add_node(i)
 for i in range(0, 2 * (n - 1), 2):
 g.add_edge(i, i + 2)
 g.add_edge(i, i + 3)
 g.add_edge(i + 1, i + 2)
 g.add_edge(i + 1, i + 3)
 return g

These graphs have $2n$ vertices, and all the shortest paths run between two of the same four endpoints, like this:

4. De Bruijn sequence approach

Here's an approach based on De Bruijn sequences that produces graphs with $2^n$ vertices.

def de_bruijn(k, n):
 "Return de Bruijn sequence for base k and subsequences of length n."
 a = [0] * k * n
 sequence = 
 def db(t, p):
 if t > n:
 if n % p == 0:
 sequence.extend(a[1:p + 1])
 else:
 a[t] = a[t - p]
 db(t + 1, p)
 for j in range(a[t - p] + 1, k):
 a[t] = j
 db(t + 1, t)
 db(1, 1)
 return sequence

def route_parity_graph(n):
 """Return a graph such that the every n-bit number is represented by
 the parity of the nodes along one of the shortest routes between two
 nodes.

 """ 
 g = nx.Graph()
 sequence = de_bruijn(2, n)
 prev = None
 for i, j in enumerate(sequence):
 cur = 2 * i + j
 g.add_node(cur)
 if prev is not None:
 g.add_edge(prev, cur)
 prev = cur
 g.add_edge(cur, sequence[0])
 return g

These graphs have the additional property that for every $0 le k < 2^n$ there is a pair of nodes in the graph $a, b$ such that there is one shortest route from $a$ to $b$, and this satisfies the parity condition.

5. Conclusion

Are any of these what you were looking for? You never explained what problem you were trying to solve, so I have no idea if these approaches will solve your problem or not. All I can say is that all of them meet the requirements specified in the post and are faster than the original code.