1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211
212
213
214
215
216
217
218
219
220
221
222
223
224
225
226
227
228
229
230
231
232
233
234
235
236
237
238
239
240
241
242
243
244
245
246
|
/*******************************************************************************
* Copyright (c) 2015 Obeo.
* All rights reserved. This program and the accompanying materials
* are made available under the terms of the Eclipse Public License v1.0
* which accompanies this distribution, and is available at
* http://www.eclipse.org/legal/epl-v10.html
*
* Contributors:
* Obeo - initial API and implementation
*******************************************************************************/
package org.eclipse.emf.compare.graph;
import java.util.Collection;
import java.util.Iterator;
import java.util.Set;
/**
* Interface of a directed graph.
*
* @author <a href="mailto:laurent.delaigue@obeo.fr">Laurent Delaigue</a>
* @param <E>
* The type of the graph nodes
* @since 3.3
*/
public interface IGraph<E> {
/**
* Checks whether this graph already contains the given element.
*
* @param element
* Element we need to check.
* @return <code>true</code> if this graph already contains the given elment, <code>false</code>
* otherwise.
*/
boolean contains(E element);
/** Clears this graph and goes back to a pristine state. */
void clear();
/**
* Adds a new element to this graph, if it does not exists yet. Elements will initially have no connection
* to other elements, and can thus be considered "roots" of the graph.
*
* @param element
* The element to add as a new root to this graph.
* @return <code>true</code> if this element did not previously exist in the graph.
*/
boolean add(E element);
/**
* Removes the given element's node from this graph. This will effectively break all connections to that
* node.
*
* @param element
* The element which is to be removed from this graph.
*/
void remove(E element);
/**
* Removes the given elements' nodes from this graph. This will effectively break all connections to these
* nodes.
*
* @param elements
* The elements which are to be removed from this graph.
*/
void removeAll(Collection<E> elements);
/**
* Connects the given set of elements to a given parent. Note that nodes will be created for all new
* elements if they do not exist yet.
*
* @param element
* The element that is to be connected with new children.
* @param newChildren
* The set of elements to connect to the given parent.
*/
void addChildren(E element, Set<E> newChildren);
/**
* Checks if the given element is a parent of the given potential child, directly or not.
*
* @param parent
* Element that could be a parent of <code>potentialChild</code>.
* @param potentialChild
* The potential child of <code>parent</code>.
* @return <code>true</code> if <code>parent</code> is an ancestor of <code>potentialChild</code>.
*/
boolean hasChild(E parent, E potentialChild);
/**
* Returns the <u>direct</u> parents of the given <code>element</code>.
* <p>
* <b>Note</b> that the returned set is a view over a sub-graph of this graph, and that changes to it will
* not be reflected within the graph itself.
* </p>
*
* @param element
* The element which parents we seek.
* @return The set of <u>direct</u> parents for the given <code>element</code>.
*/
Set<E> getDirectParents(E element);
/**
* Returns the tree starting from the given root element if it is contained in the graph.
* <p>
* Contrarily to {@link #getSubgraphContaining(Object)}, this will only iterate over the children (and
* recursively) of the given node, without ever "going up" to parents of these children.
* </p>
* <p>
* <b>Note</b> that the returned set is a view over a sub-graph of this graph, and that changes to it will
* not be reflected within the graph itself.
* </p>
*
* @param root
* The element we are to consider as the root of a tree.
* @return The tree starting from the given root element if it is contained in this graph, and empty set
* otherwise.
*/
Set<E> getTreeFrom(E root);
/**
* Returns the tree starting from the given root element and ending at the given boundaries..
* <p>
* Contrarily to {@link #getSubgraphContaining(Object, Set)}, this will only iterate over the children
* (and recursively) of the given node, without ever "going up" to parents of these children.
* </p>
* <p>
* <b>Note</b> that the returned set is a view over a sub-graph of this graph, and that changes to it will
* not be reflected within the graph itself.
* </p>
*
* @param root
* The element we are to consider as the root of a tree.
* @param endPoints
* Boundaries of the tree.
* @return The tree starting from the given root element if it is contained in this graph, and empty set
* otherwise.
*/
Set<E> getTreeFrom(E root, Set<E> endPoints);
/**
* Returns the set of all elements of the subgraph containing the given element.
* <p>
* <b>Note</b> that the returned set is a view over a sub-graph of this graph, and that changes to it will
* not be reflected within the graph itself.
* </p>
*
* @param element
* Element we need the subgraph of.
* @return The set of all elements of the subgraph containing the given element, an empty set if that
* element is not present in this graph.
*/
Set<E> getSubgraphContaining(E element);
/**
* Returns the set of all elements of the subgraph containing the given element and ending at the given
* boundaries.
* <p>
* <b>Note</b> that the returned set is a view over a sub-graph of this graph, and that changes to it will
* not be reflected within the graph itself.
* </p>
*
* @param element
* Element we need the subgraph of.
* @param endPoints
* Boundaries of the needed subgraph.
* @return An iterable over all elements of the subgraph containing the given element, an empty set if
* that element is not present in this graph.
*/
Set<E> getSubgraphContaining(E element, Set<E> endPoints);
/**
* Returns a breadth-first iterator over this whole graph. This will begin iteration on this graph's roots
* (whether they are linked together (directly or indirectly) or not), then carry on over each depth
* level. This will never visit the same element twice, nor will it ever visit an element which parents
* haven't all been iterated over yet.
* <p>
* The returned iterator does not support removal, and will fail or return undefined results if this graph
* is modified after the iterator's creation.
* </p>
*
* @return A breadth-first iterator over this whole graph.
*/
PruningIterator<E> breadthFirstIterator();
/**
* Returns a depth first iterator created with the given element as root. If the graph contains cycles,
* the same node won't be returned twice.
* <p>
* The root will be returned first, then the left-most child of that root, then the left-most child of
* that child if any, or the closest sibling to the right of the current element. For example, with the
* following tree:
*
* <pre>
* A
* / \
* B C
* / / \
* D E F
* </pre>
*
* The iteration order will be : A, B, D, C, E, F.
* </p>
* <p>
* The returned iterator does not support removal, and will fail or return undefined results if this graph
* is modified after the iterator's creation.
* </p>
*
* @param root
* The root of the tree over which we need to iterate.
* @return An iterator over the tree starting from the given root.
*/
Iterator<E> depthFirstIterator(E root);
/**
* Get the parent data of the given element.
* <p>
* The parent data, is the URI of the parent resource's object in case of a containment relationship
* between the given element and its parent.
* <p>
*
* @param element
* Element we need the parent data of.
* @return A parent data of type <code>E</code> if this element has a parent data, <code>null</code>
* otherwise.
*/
E getParentData(E element);
/**
* Set the parent data for the given element.
* <p>
* The parent data, is the URI of the parent resource's object in case of a containment relationship
* between the given element and its parent.
* </p>
* If the given element has several parents, then the addition of a new parent data results in delete the
* parent data. If the given element has no parents, then the addition of a new parent data results in
* delete the parent data.
*
* @param element
* Element for which we need to set the parent data.
* @param parentData
* The parent data to set.
*/
void addParentData(E element, E parentData);
}
|
