2

Given a graph where each node may contain arbitrary dependencies or conflicts with other nodes leading to any possible arrangement including circular and contradictory references.

I'm trying to compute a stable result list maximally containing a list of nodes able to respect all of their constraints. I just need to find one possible solution if there is one to be had.

In the examples below "A depends on B" means for A to be true B must be true. "B conflicts with A" means for B to be true A must not be true. There is no precedence both dependencies and conflicts with have equal weight and apply concurrently.

On 3rd example 'A' does not appear because it depends on D which conflicts with B. Since A also requires B .. A cannot exist as D's conflict and A's dependencies forbid it.

A depends on B
B conflicts with A
= B

A depends on B
B depends on A
= A and B

A depends on B
A depends on D
B depends on C
D conflicts with B
D conflicts with C
= B and C or D

A conflicts with B
B conflicts with C
C conflicts with D
D conflicts with A
= A and C or B and D

I've been trying to come up with an algorithm that works but so far my efforts resemble heuristical gobblygook which fail spectacularly on non-trivial graphs. Any insights, pointers to reading material or names of algorithms would be much appreciated.

5
  • To clarify the intended output, could you 1) indicate the precedence of the operators (I think you assuming the precedence of and > or)?, and 2) Explain why A does not appear in the answer for the third example? At present, I'm unsure why one needs the "depends on" lines, except to show which nodes should be considered when assessing the conflicts. Without the "depends on" lines, the problem seems to resolve to a set of boolean statements of the form "if A then NOT B / if B then NOT A" etc. Thanks for the clarifications.
    – Simon
    Jan 28, 2013 at 4:11
  • Hi Simon, I updated the question above to try and answer your questions. Jan 28, 2013 at 5:38
  • Can someone verify this please: "A depends on B" = A implies B. "B conflicts with A" = B implies not A. If this is the case, then there is a simple polynomial time algorithm.
    – Dan
    Jan 31, 2013 at 19:54
  • @Dan: When testing my original answer, I found that your interpretation is necessary to give the example output that the OP provided so I think he/she (and I, since I have a likely future project that might require something like this) would find a pointer to the polynomial time algorithm to be useful. Thanks.
    – Simon
    Feb 1, 2013 at 1:04
  • @Simon: I added an answer to this question.
    – Dan
    Feb 1, 2013 at 7:59

2 Answers 2

2

I assume that

  • "A depends on B" means A implies B and
  • "B conflicts with A" means B implies not A.

Now, you have A implies B = not A or B and B implies not A = not B or not A. This means that the problem boils down to finding a solution for a conjunction of disjunctions (also known as clauses) where each clause has two arguments (A, not A, B, or not B).

This problem is known as 2-satisfiability. You find polynomial time algorithms in the web, e.g., start at http://en.wikipedia.org/wiki/2-satisfiability.

As far as I understand resolution in modern SAT solvers, there is no need to write your own algorithm. A SAT solver should be able to solve such instances automatically in polynomial time.

2
  • Hi Dan, thank you very much. Wikipedia graphs even look eerily like charts I've been drawing out to try and figure this out. Thank you. Feb 3, 2013 at 8:02
  • You're welcome. I'm glad that my CS studies pay out eventually ;)
    – Dan
    Feb 4, 2013 at 8:43
1

Translating the language used in the question into boolean expressions, we have:

"A depends on B" => "(a and b) or (not a)"

and

"B conflicts with A" => "(b and not a) or (not b)"

Thus, a simple way to write this (in Python 3) is by generating the cartesian product (to give all the possible alternatives) and then selecting only the cases for which the constraints are satisfied. For simplicity, I'm using indices instead of letters for the input, so y[0] is equivalent to A, etc. I've translated the output into letters, however.

For n nodes, this approach will generate and test all 2^n possible cases. See below for a more complicated but potentially more efficient approach.

import itertools

bbb = (True,False)

def resolve(n,test):
    return [x for x in itertools.product(bbb,repeat=n) if test(x)]

def dependsOn(a,b):
    return (a and b) or (not a)

def conflictsWith(b,a):
    return (b and not a) or (not b)

letters = 'ABCDEFGHIJKLMNOPQRSTUVWXYZ'

def pr(d):
    for dd in d:
        s = [letters[i] for i in range(len(dd)) if dd[i] ]
        if (len(s) > 0):
            print(s,end = " ")
    print()

pr(list(resolve(2,lambda y: 
    dependsOn(y[0],y[1]) and 
    conflictsWith(y[1],y[0])
    )))
pr(list(resolve(2,lambda y: 
    dependsOn(y[0],y[1]) and 
    dependsOn(y[1],y[0]) 
    )))
pr(list(resolve(4,lambda y: 
    dependsOn(y[0],y[1]) and 
    dependsOn(y[0],y[3]) and
    dependsOn(y[1],y[2]) and 
    conflictsWith(y[3],y[1]) and 
    conflictsWith(y[3],y[2])
    )))
pr(list(resolve(4,lambda y: 
    conflictsWith(y[0],y[1]) and
    conflictsWith(y[1],y[2]) and
    conflictsWith(y[2],y[3]) and
    conflictsWith(y[3],y[0])
    )))

This gives the results:

['B']
['A', 'B']
['B', 'C'] ['C'] ['D']
['A', 'C'] ['A'] ['B', 'D'] ['B'] ['C'] ['D']

... for the four test cases.

For more information, you could look at the Wikipedia entry on truth tables.

(EDIT)

A more efficient approach for problems with many nodes and many constraints would be to build the list of nodes progressively and then only continue building from each partial list if that partial list complies with the constraints, at least to the extent that it has been populated so far. We could do that by replacing the resolve function above with the following version and by replacing the dependsOn and conflictsWith functions to match:

import queue

# The following constraint functions return True if the constraint is met
# or if one or more of the elements relating to the constraint is None

def dependsOn(a,b):
    if (a != None) and (b != None):
        return (a and b) or (not a)
    else:
        return True

def conflictsWith(b,a):
    if (a != None) and (b != None):
        return (b and not a) or (not b)
    else:
        return True

def resolve(n,test):
    result = []
    testCount = 0
    # initialise the list with all None
    lst = [None] * n
    q = queue.Queue()
    q.put(lst)
    while not q.empty():
        lst = list(q.get())
        testCount += 1
        if test(lst):
            # the list complies with the constraints, at least
            # as far as it is populated
            if lst[-1] != None:
                # we have a fully-populated list
                result.append(lst)
            else:
                i = lst.index(None)
                lst[i] = True
                q.put(list(lst))
                lst[i] = False
                q.put(list(lst))
    print ("testCount = %d" % testCount)
    return result

This gives the same results for the four test cases. However, for the third and fourth test cases, the value of testCount is 21 and 23 respectively. That is more than the total number of tests required for the cartesian product solution (which is 16 for n=4) but, for cases where there are many more nodes and many more constraints, this approach avoids testing subsets of nodes that can't possibly contain a solution and therefore could easily require many fewer tests than the cartesian product solution. Of course, in the worst-case scenario with few or no constraints, this approach can require a maximum of 2^(n+1) - 1 tests. That does, in fact, happen for the first two test cases, for which testCount is 7 using this algorithm.

Note that the implementation shown here is crude and could certainly be optimised for speed.

6
  • @user1887190: Glad to help. I noticed that you'd accepted then unaccepted this answer. If I can help further, please let me know.
    – Simon
    Jan 30, 2013 at 2:49
  • The exponential time requirement makes this scheme impossible to use. I was hoping there was some kind of graph walking algorithm I did not know about that could be used to solve this type of problem. Everything I have been able to find only works if there are no cycles. For all I know this is the only solution in which case I am more than happy to accept your answer. Jan 31, 2013 at 2:46
  • @user1887190: Yes, the exponential time requirement would be a problem for very large cases. I'll think about the alternatives. For example, it might be possible to partition the problem by considering the "Conflicts with" criteria first. In the meantime, do you have an indication of how big the problem might get in your application? Thanks.
    – Simon
    Jan 31, 2013 at 3:10
  • @user1887190: It occurred to me that there are ways to avoid testing subsets of cases that we already know don't contain potential solutions so I've edited my answer to incorporate one way to do that.
    – Simon
    Jan 31, 2013 at 5:45
  • @Dan: Good thought. Stack Overflow has had good questions and answers on sat solvers here.
    – Simon
    Jan 31, 2013 at 21:58

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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