# Creating a minimal graph representing all combinations of 3-bit binary strings

I have an algorithm that creates a graph that has all representations of 3-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 progressbar import itertools 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]                                       g = nx.Graph() added = []    good = [] index = [] # I create list with 3-bit binary strings # I do not include one of the pairs of binary strings that have a mirror image list_1 = [list(i) for i in itertools.product(tuple(range(2)), repeat=3) if tuple(reversed(i)) >= tuple(i)] count = list(range(len(list_1))) h = 0 while len(added) < len(list_1):       # In each next step I enlarge the list 'good` by the next even and odd number      if h != 0:            for q in range(2):                good.append([i for i in good if i%2 == q][-1] + 2)      # I create a list `c` with string indices from the list` list_1`, that are not yet used.      # Whereas the `index` list stores the numbering of strings from the list` list_1`, whose representations have already been correctly added to the `added` list.                c = [item for item in count if item not in index]      for m in c:      # 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 list_1[m]]          if h == 0:             for w in range(2):                 if len([i for i in good if i%2 == w]) < a.count('v{}'.format(w)):                    for j in range(len([i for i in good if i%2 == w]), a.count('v{}'.format(w))):                        good.insert(j,2*j + w)                                 sources={}          for x in range(2):              sources["v{0}".format(x)] = [n for n in good if n%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):                           # Here, the edges and nodes are added to the graph from the combination of `aaa_binary` and checking whether the combination meets the conditions. If so, it is added to the `added` list. If not, the newly added edges are removed and the next `aaa_binary` combination is taken.                         g.add_nodes_from (aaa_binary)              t1 = (aaa_binary,aaa_binary)              t2 = (aaa_binary,aaa_binary)               added_now = []                                    for edge in (t1,t2):                  if not g.has_edge(*edge):                     g.add_edge(*edge)                     added_now.append(edge)              added.append(aaa_binary)              index.append(m)              for f in range(len(added)):                  if nx.shortest_path(g, aaa_binary, aaa_binary) != aaa_binary or nx.shortest_path(g, added[f], added[f]) != added[f]:                     for edge in added_now:                         g.remove_edge(*edge)                     added.remove(aaa_binary)                     index.remove(m)                     break              # Calling a good combination search interrupt if it was found and the result added to the `added` list, while the index from the list 'list_1` was added to the` index` list                            if m in index:                 break      good.sort()      set(good)      index.sort()       h = h+1 ``

Output paths representing 3-bit binary strings from `added`:

``[[0, 2, 4], [0, 2, 1], [2, 1, 3], [1, 3, 5], [0, 3, 6], [3, 0, 7]] ``

So these are representations of 3-bit binary strings:

``[[0, 0, 0], [0, 0, 1], [0, 1, 1], [1, 1, 1], [0, 1, 0], [1, 0, 1]] ``

Where in the step `h = 0` the first 4 sub-lists were found, and in the step `h = 1` the last two sub-lists were added.

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 above solution creates a minimal graph and with the unique shortest paths. This means that one combination of a binary string has only one representation on the graph in the form of the shortest path. So the choice of a given path is a single-pointing indication of a given binary sequence.

Now I would like to use multiprocessing on the `for m in c` loop, because the order of finding elements does not matter here.

I try to use multiprocessing in this way:

``from multiprocessing import Pool added = [] def foo(i):     added = []        # do something         added.append(x[i])     return added if __name__ == '__main__': h = 0 while len(added)<len(c):     pool = Pool(4)    result = pool.imap_unordered(foo, c)          added.append(result[-1])    pool.close()    pool.join()    h = h + 1 ``

Multiprocessing takes place in the while-loop, and in the `foo` function, the

`added` list is created. In each subsequent step `h` in the loop, the list`added` should be incremented by subsequent values, and the current list `added` should be used in the function`foo`. Is it possible to pass the current contents of the list to the function in each subsequent step of the loop? Because in the above code, the `foo` function creates the new contents of the `added` list from scratch each time. How can this be solved?

Which in consequence gives bad results:

``[[0, 2, 4], [0, 2, 1], [2, 1, 3], [1, 3, 5], [0, 1, 2], [1, 0, 3]] ``

Because for such a graph, nodes and edges, the condition is not met that `nx.shortest_path (graph, i, j) == added[k]` for every final nodes `i, j` from `added[k] for k in added list`.

Where for `h = 0` to the elements `[0, 2, 4], [0, 2, 1], [2, 1, 3], [1, 3, 5]` are good, while elements added in the step`h = 1`, ie `[0, 1, 2], [1, 0, 3]` are evidently found without affecting the elements from the previous step.

How can this be solved?

I realize that this is a type of sequential algorithm, but I am also interested in partial solutions, i.e. parallel processes even on parts of the algorithm. For example, that the steps of `h` while looping run sequentially, but the`for m in c` loop is multiprocessing. Or other partial solutions that will improve the entire algorithm for larger combinations.

I will be grateful for showing and implementing some idea for the use of multiprocessing in my algorithm.