Question

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.

Was it helpful?

Solution

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.

OTHER TIPS

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.

Licensed under: CC-BY-SA with attribution
Not affiliated with StackOverflow
scroll top