]>
git.proxmox.com Git - mirror_edk2.git/blob - Tools/Source/Prototype/DAG.java
3 // A directed Acyclic Graph class. The main purpose is to provide a set of nodes
4 // and the dependency relations between them. Then ask for a topological sort of
12 children
= new HashMap
<Node
,Set
<Node
>>();
15 public Set
<Node
> nodes() { return children
.keySet(); }
16 public Set
<Node
> children(Node parent
) { return children
.get(parent
); }
18 // Add the relations from a compatible DAG to this one.
19 public void add(DAG
<Node
> newDag
)
21 for(Node parent
: newDag
.children
.keySet())
23 children
.put(parent
, newDag
.children(parent
));
27 // The central data structure is a one-to-many map. Each node is
28 // treated as a parent. It is mapped to a list of its children. Leaf
29 // nodes are also treated as parents and map to an empty list of
31 Map
<Node
,Set
<Node
>> children
;
33 public void remove(Collection
<Node
> nodes
)
35 // Remove it as a parent
36 for(Node node
: nodes
)
38 children
.remove(node
);
41 for(Set
<Node
> childlist
: children
.values())
43 // Remove it as a child
44 childlist
.removeAll(nodes
);
48 // Remove every occurrence of node from the DAG.
49 public void remove(Node node
)
51 // Remove it as a parent
52 children
.remove(node
);
54 for(Set
<Node
> childlist
: children
.values())
56 // Remove it as a child
57 childlist
.remove(node
);
61 // Return true iff parent is a direct parent of child.
62 public boolean directDepends(Node parent
, Node child
)
64 return children
.containsKey(parent
) ?
65 children(parent
).contains(child
) :
69 // Return true iff parent is a direct or indirect parent of child.
70 // This is the transitive closure of the dependency relation.
71 public boolean depends(Node parent
, Node child
)
73 if(!children
.containsKey(parent
))
77 if( directDepends(parent
, child
) )
83 for(Node descendent
: children(parent
) )
85 // Recursively call depends() to compute the transitive closure of
87 if(depends(descendent
, child
))
96 // Add a parent child relation to the dag. Fail if there is already
97 // a dependency from the child to the parent. This implies a cycle.
98 // Our invariant is that the DAG must never contain a cycle. That
99 // way it lives up to its name.
100 public void add(Node parent
, Node child
)
102 if(depends(child
, parent
))
104 System
.out
.format("Error: There is a cycle from %s to %s.\n", parent
, child
);
107 if(children
.containsKey(parent
))
109 children(parent
).add(child
);
113 Set
<Node
> cs
= new HashSet
<Node
>();
115 children
.put(parent
, cs
);
117 if(!children
.containsKey(child
))
119 children
.put(child
,new HashSet
<Node
>());
123 // Perform a topological sort on the DAG.
124 public List
<Node
> sort()
126 // Make an ordered list to hold the topo sort.
127 List
<Node
> sorted
= new LinkedList
<Node
>();
129 // We add the leaves to the beginning of the list until
130 // the sorted list contains all the nodes in the DAG.
131 while(!sorted
.containsAll(nodes()))
133 // Ignoring the ones we have found, what are the leaves of this
135 Set
<Node
> leaves
= leaves(sorted
);
136 // Put the new leaves at the beginning of the list.
137 sorted
.addAll(0, leaves
);
142 // Return the set of nodes that have no children. Pretend
143 // the nodes in the exclude list are not present.
144 public Set
<Node
> leaves(Collection
<Node
> exclude
)
146 Set
<Node
> leaves
=new HashSet
<Node
>();
147 for(Node parent
: children
.keySet())
149 if(exclude
.contains(parent
))
153 // If the children of parent are a subset of the exclude set,
154 // then parent is a leaf.
155 if(exclude
.containsAll(children(parent
)))
163 // Return the set of nodes that have no children.
164 public Set
<Node
> leaves()
166 Set
<Node
> leaves
=new HashSet
<Node
>();
167 for(Node parent
: children
.keySet())
169 if( children(parent
).isEmpty())