Dependency Algorithm - find a minimum set of packages to install


[Dependency Algorithm - find a minimum set of packages to install](http://stackoverflow.com/questions/30429786/dependency-algorithm-find-a-minimum-set-of-packages-to-install/30565843#30565843)

Represent the constraints.

```
X : A&(E|C)
A : E&(Y|N)
E : B&(Z|Y)
C : A|K
```

Prepare two list target and result.
Add the node X to target.

```
target = X, result=[]
```

Add single node X to the result.
Replace node X with its dependent in the target.

```
target = A&(E|C), result=[X]
```

Add single node A to result.
Replace node A with its dependent in the target.

```
target = E&(Y|N)&(E|C), result=[X, A]
```

Single node E must be true.
So (E|C) is always true.
Remove it from the target.

```
target = E&(Y|N), result=[X, A]
```

Add single node E to result.
Replace node E with its dependent in the target.

```
target = B&(Z|Y)&(Y|N), result=[X, A, E]
```

Add single node B to result.
Replace node B with its dependent in the target.

```
target = (Z|Y)&(Y|N), result=[X, A, E, B]
```

There are no single node any more.
Then expand the target expression.

expanded = Z&Y|Z&N|Y&Y|Y&N

Y&Y equals to Y.

```
expanded = Z&Y|Z&N|Y|Y&N
```

Choose the term that has smallest number of nodes.
Add all nodes in the term to the target.

```
target = , result=[X, A, E, B, Y]
```


```java
package stackoverflow.dependency;

import java.util.ArrayList;
import java.util.HashMap;
import java.util.HashSet;
import java.util.Iterator;
import java.util.List;
import java.util.Map;
import java.util.Set;

public class Dependency {

	public static class Node {
		final String name;
		final List<String> and = new ArrayList<>();
		final List<String> or = new ArrayList<>();

		Node(String name) {
			this.name = name;
		}

		public Node and(String... and) {
			for (String e : and)
				this.and.add(e);
			return this;
		}

		public Node or(String... or) {
			for (String e : or)
				this.or.add(e);
			return this;
		}
		
		@Override
		public String toString() {
			return name + " and" + and + " or" + or;
		}
	}

	final Map<String, Node> map = new HashMap<>();
	
	public Node node(String name) {
		Node node = map.get(name);
		if (node == null)
			map.put(name, node = new Node(name));
		return node;
	}
	
	@Override
	public String toString() {
		StringBuilder sb = new StringBuilder();
		for (Node e : map.values())
			sb.append(e).append("\n");
		return sb.toString();
	}

	public Node get(String name) {
		return map.get(name);
	}

	static void expand(List<List<String>> targetOr, int index, List<String> set, List<Set<String>> expanded) {
		int size = targetOr.size();
		if (index >= size)
			expanded.add(new HashSet<>(set));
		else
			for (String s : targetOr.get(index)) {
				set.add(s);
				expand(targetOr, index + 1, set, expanded);
				set.remove(set.size() - 1);
			}
	}

	public List<String> dependents(String start) {
		List<String> targetAnd = new ArrayList<>();
		List<List<String>> targetOr = new ArrayList<>();
		List<String> result = new ArrayList<>();
		targetAnd.add(start);
        while (!targetAnd.isEmpty()) {
            System.out.println("target=AND" + targetAnd + " OR" + targetOr + ", result=" + result);
            String single = targetAnd.remove(0);
            Node singleNode = get(single);
            result.add(single);
            for (Iterator<List<String>> i = targetOr.iterator(); i.hasNext(); )
                if (i.next().contains(single))
                    i.remove();
            System.out.println("target=AND" + targetAnd + " OR" + targetOr + ", result=" + result);
            targetAnd.addAll(singleNode.and);
            if (singleNode.or.size() > 0)
                targetOr.add(singleNode.or);
        }
        if (!targetOr.isEmpty()) {
        	List<Set<String>> expanded = new ArrayList<>();
        	expand(targetOr, 0, new ArrayList<>(), expanded);
        	System.out.println("expanded=OR" + expanded);
        	int min = Integer.MAX_VALUE;
        	Set<String> minSet = null;
        	for (Set<String> set : expanded)
        		if (set.size() < min) {
        			min = set.size();
        			minSet = set;
        		}
        	result.addAll(minSet);
        }
		return result;
	}

	public static void main(String[] args) {
		Dependency d = new Dependency();
		d.node("X").and("A").or("E", "C");
		d.node("E").and("B").or("Y", "Z");
		d.node("A").and("E").or("H", "Y");
		d.node("C").or("A", "K");
		d.node("Z");
		d.node("B");
		d.node("H");
		d.node("K");
		System.out.println(d);
		List<String> result = d.dependents("X");
		System.out.println(result);
	}
}

```