4
\$\begingroup\$

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

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:

enter image description here

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.

\$\endgroup\$
  • 4
    \$\begingroup\$ I read the first paragraph like 10 times now and am still clueless about what the graph is supposed to represent. Can you elaborate a bit more, please? \$\endgroup\$ – 409_Conflict Jan 15 '18 at 13:16
  • \$\begingroup\$ It does not help for understanding the code that all the functionality is within a function that has no parameters and does not return anything. (The comments on your post on SO didn't enlighten me either.) Also, the code is quite hard to read due to very inconsistent layout – sometimes 1 space is used for indentation, sometimes 3, 4 or even 13. \$\endgroup\$ – mkrieger1 Jan 15 '18 at 21:19
  • \$\begingroup\$ I improved readability;) and I removed def main () because I used it earlier for a different purpose. \$\endgroup\$ – Tomasz Przemski Jan 15 '18 at 21:42
  • \$\begingroup\$ There are also syntactically incorrect indentations (when trying to run the code I get IndentationError: unexpected indent at line 66). \$\endgroup\$ – mkrieger1 Jan 15 '18 at 21:45
  • \$\begingroup\$ thanks, I did not notice. already corrected and everything works :) \$\endgroup\$ – Tomasz Przemski Jan 15 '18 at 21:53
7
+100
\$\begingroup\$

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 \left\lfloor {k \over 2^{n-i}} \right\rfloor \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 $$n\left(2^{n-1}+2^{\left\lfloor{n-1\over2}\right\rfloor}\right)$$ nodes, where each shortest path is a separate connected component, for example:

enter image description here

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:

enter image description here

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.

enter image description here

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.

\$\endgroup\$
  • \$\begingroup\$ Hi. The first case meets all the conditions for unambiguous search of paths corresponding to 4-binary sequences. But it does not meet the condition that it is the graph as the most economical, minimal. I only needed 19 knots, you need as much as 40. It's faster, but I can not accept it. In the second case, on the other hand, I will not get all cases of 4-bit binary strings giving only the first and last node in the shortest-path function. \$\endgroup\$ – Tomasz Przemski Jan 18 '18 at 12:22
  • \$\begingroup\$ Because, for example, nx.shortest_path (g, 0, 7) == [0,2,4,7], which corresponds to the binary string 0001. And I will not get any other results based on 0 and 7. And for example, nx.shortest_path (g, 0, 1) == [0,2,1], i.e. i will not even get a 4-element representation. Therefore, on this type of graph I will not get all cases of 4-bit binary strings based on giving only the first and last number from the path. And that's what I care about. That's why it's not yet what I expected. But thank you for the effort so far. \$\endgroup\$ – Tomasz Przemski Jan 18 '18 at 12:22
  • 2
    \$\begingroup\$ @TomaszPrzemski: Now you are adding conditions to the problem that were not mentioned in the original post. The original post says nothing about needing the "most economical" graph, nor about having a unique pair of endpoints for each value of \$k\$. How were we supposed to intuit these conditions? This was why I asked you to explain the motivation for the problem — if you told us why you needed these graphs, we might have been able to deduce the conditions. But since you did not tell us, we could only go on what you actually wrote. \$\endgroup\$ – Gareth Rees Jan 18 '18 at 12:33
  • \$\begingroup\$ actually. my mistake! and in my case I did not need 19, only 11 nodes, i made a mistake. So it's a little less than 40 of you :) \$\endgroup\$ – Tomasz Przemski Jan 18 '18 at 12:37
  • \$\begingroup\$ I understand, but I have been here for a short time, and my language is not very good either and sometimes I can not explain everything well ... \$\endgroup\$ – Tomasz Przemski Jan 18 '18 at 12:39

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.