Package org.eclipse.emf.compare.internal.utils

## Class Graph<E>

- java.lang.Object
- - org.eclipse.emf.compare.internal.utils.Graph<E>

Type Parameters:
  `E` - Kind of elements used as this graph's nodes.

All Implemented Interfaces:
  `IGraph<E>`

    public class Graph<E>
    extends Object
    implements IGraph<E>

This structure will be used to maintain a undirected graph of elements.

This boils down to maintaining a list of children and parents of each node, updating them in sync with each other.

Take note that the elements of this graph are not necessarily all connected together. This can be used to represent a set of trees, a set of undirected graphs, a set of roots with no children...

This class is not intended to be sub-classed.

### Constructor Summary

Constructors
`Graph()` Constructs an empty graph.

### Method Summary

All Methods Instance Methods Concrete Methods
`boolean` `add​(E element)` Adds a new element to this graph, if it does not exists yet.
`void` `addChildren​(E element, Set<E> newChildren)` Connects the given set of elements to a given parent.
`void` `addParentData​(E element, E parentData)` Set the parent data for the given element.
`PruningIterator<E>` `breadthFirstIterator()` Returns a breadth-first iterator over this whole graph.
`void` `clear()` Clears this graph and goes back to a pristine state.
`boolean` `contains​(E element)` Checks whether this graph already contains the given element.
`Iterator<E>` `depthFirstIterator​(E root)` Returns a depth first iterator created with the given element as root.
`Set<E>` `getDirectParents​(E element)` Returns the direct parents of the given `element`.
`E` `getParentData​(E element)` Get the parent data of the given element.
`Set<E>` `getSubgraphContaining​(E element)` Returns the set of all elements of the subgraph containing the given element.
`Set<E>` `getSubgraphContaining​(E element, Set<E> endPoints)` Returns the set of all elements of the subgraph containing the given element and ending at the given boundaries.
`Set<E>` `getTreeFrom​(E root)` Returns the tree starting from the given root element if it is contained in the graph.
`Set<E>` `getTreeFrom​(E root, Set<E> endPoints)` Returns the tree starting from the given root element and ending at the given boundaries..
`boolean` `hasChild​(E parent, E potentialChild)` Checks if the given element is a parent of the given potential child, directly or not.
`void` `remove​(E element)` Removes the given element's node from this graph.
`void` `removeAll​(Collection<E> elements)` Removes the given elements' nodes from this graph.

### Methods inherited from class java.lang.Object

`clone, equals, finalize, getClass, hashCode, notify, notifyAll, toString, wait, wait, wait`

### Constructor Detail

#### Graph

    public Graph()

Constructs an empty graph.

### Method Detail

#### contains

    public boolean contains​(E element)

Checks whether this graph already contains the given element.

Specified by:
  `contains` in interface `IGraph<E>`
Parameters:
  `element` - Element we need to check.
Returns:
  `true` if this graph already contains the given elment, `false` otherwise.

#### clear

    public void clear()

Clears this graph and goes back to a pristine state.

Specified by:
  `clear` in interface `IGraph<E>`

#### add

    public boolean add​(E element)

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.

Specified by:
  `add` in interface `IGraph<E>`
Parameters:
  `element` - The element to add as a new root to this graph.
Returns:
  `true` if this element did not previously exist in the graph.

#### remove

    public void remove​(E element)

Removes the given element's node from this graph. This will effectively break all connections to that node.

Specified by:
  `remove` in interface `IGraph<E>`
Parameters:
  `element` - The element which is to be removed from this graph.

#### removeAll

    public void removeAll​(Collection<E> elements)

Removes the given elements' nodes from this graph. This will effectively break all connections to these nodes.

Specified by:
  `removeAll` in interface `IGraph<E>`
Parameters:
  `elements` - The elements which are to be removed from this graph.

#### addChildren

    public void addChildren​(E element,
                            Set<E> newChildren)

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.

Specified by:
  `addChildren` in interface `IGraph<E>`
Parameters:
  `element` - The element that is to be connected with new children.
  `newChildren` - The set of elements to connect to the given parent.

#### hasChild

    public boolean hasChild​(E parent,
                            E potentialChild)

Checks if the given element is a parent of the given potential child, directly or not.

Specified by:
  `hasChild` in interface `IGraph<E>`
Parameters:
  `parent` - Element that could be a parent of `potentialChild`.
  `potentialChild` - The potential child of `parent`.
Returns:
  `true` if `parent` is an ancestor of `potentialChild`.

#### getDirectParents

    public Set<E> getDirectParents​(E element)

Returns the direct parents of the given `element`.

Note 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.

Specified by:
  `getDirectParents` in interface `IGraph<E>`
Parameters:
  `element` - The element which parents we seek.
Returns:
  The set of direct parents for the given `element`.

#### getTreeFrom

    public Set<E> getTreeFrom​(E root)

Returns the tree starting from the given root element if it is contained in the graph.

Contrarily to `getSubgraphContaining(Object)`, this will only iterate over the children (and recursively) of the given node, without ever "going up" to parents of these children.

Note 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.

Specified by:
  `getTreeFrom` in interface `IGraph<E>`
Parameters:
  `root` - The element we are to consider as the root of a tree.
Returns:
  The tree starting from the given root element if it is contained in this graph, and empty set otherwise.

#### getTreeFrom

    public Set<E> getTreeFrom​(E root,
                              Set<E> endPoints)

Returns the tree starting from the given root element and ending at the given boundaries..

Contrarily to `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.

Note 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.

Specified by:
  `getTreeFrom` in interface `IGraph<E>`
Parameters:
  `root` - The element we are to consider as the root of a tree.
  `endPoints` - Boundaries of the tree.
Returns:
  The tree starting from the given root element if it is contained in this graph, and empty set otherwise.

#### getSubgraphContaining

    public Set<E> getSubgraphContaining​(E element)

Returns the set of all elements of the subgraph containing the given element.

Note 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.

Specified by:
  `getSubgraphContaining` in interface `IGraph<E>`
Parameters:
  `element` - Element we need the subgraph of.
Returns:
  The set of all elements of the subgraph containing the given element, an empty set if that element is not present in this graph.

#### getSubgraphContaining

    public Set<E> getSubgraphContaining​(E element,
                                        Set<E> endPoints)

Returns the set of all elements of the subgraph containing the given element and ending at the given boundaries.

Note 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.

Specified by:
  `getSubgraphContaining` in interface `IGraph<E>`
Parameters:
  `element` - Element we need the subgraph of.
  `endPoints` - Boundaries of the needed subgraph.
Returns:
  An iterable over all elements of the subgraph containing the given element, an empty set if that element is not present in this graph.

#### breadthFirstIterator

    public PruningIterator<E> breadthFirstIterator()

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.

The returned iterator does not support removal, and will fail or return undefined results if this graph is modified after the iterator's creation.

Specified by:
  `breadthFirstIterator` in interface `IGraph<E>`
Returns:
  A breadth-first iterator over this whole graph.

#### depthFirstIterator

    public Iterator<E> depthFirstIterator​(E root)

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.

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:

         A
        / \
       B   C
      /   / \
     D   E   F

The iteration order will be : A, B, D, C, E, F.

The returned iterator does not support removal, and will fail or return undefined results if this graph is modified after the iterator's creation.

Specified by:
  `depthFirstIterator` in interface `IGraph<E>`
Parameters:
  `root` - The root of the tree over which we need to iterate.
Returns:
  An iterator over the tree starting from the given root.

#### getParentData

    public E getParentData​(E element)

Get the parent data of the given element.

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.

Specified by:
  `getParentData` in interface `IGraph<E>`
Parameters:
  `element` - Element we need the parent data of.
Returns:
  A parent data of type `E` if this element has a parent data, `null` otherwise.

#### addParentData

    public void addParentData​(E element,
                              E parentData)

Set the parent data for the given element.

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.

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.

Specified by:
  `addParentData` in interface `IGraph<E>`
Parameters:
  `element` - Element for which we need to set the parent data.
  `parentData` - The parent data to set.