ConcreteDGraph.java

package org.thegalactic.dgraph;

/*
 * ConcreteDGraph.java
 *
 * Copyright: 2010-2015 Karell Bertet, France
 * Copyright: 2015-2016 The Galactic Organization, France
 *
 * License: http://www.cecill.info/licences/Licence_CeCILL-B_V1-en.html CeCILL-B license
 *
 * This file is part of java-lattices.
 * You can redistribute it and/or modify it under the terms of the CeCILL-B license.
 */
import java.util.AbstractSet;
import java.util.ArrayList;
import java.util.Collections;
import java.util.Comparator;
import java.util.Iterator;
import java.util.List;
import java.util.Map;
import java.util.NoSuchElementException;
import java.util.Set;
import java.util.SortedSet;
import java.util.TreeMap;
import java.util.TreeSet;

/**
 * This class gives a standard representation for a directed graph by sets of
 * successors and predecessors.
 *
 * A directed graph is composed of
 *
 * - a treeset of node, defined by class {@link Node}; - a treemap of successors
 * that associates to each node a treeset of successors, defined by class
 * {@link Edge}; - a treemap of predecessors that associates to each node a
 * treeset of predecessors, defined by class {@link Edge}.
 *
 * This class provides methods implementing classical operation on a directed
 * graph:
 *
 * - sinks - wells - subgraph - reflexive closure and reduction - transitive
 * closure - strongly connected components - ...
 *
 * This class also provides a static method randomly generating a directed
 * graph.
 *
 * ![ConcreteDGraph](ConcreteDGraph.png)
 *
 * @param <N> Node content type
 * @param <E> Edge content type
 *
 * @uml DGraph.png
 * !include resources/org/thegalactic/dgraph/DGraph.iuml
 * !include resources/org/thegalactic/dgraph/Edge.iuml
 * !include resources/org/thegalactic/dgraph/Node.iuml
 *
 * hide members
 * show DGraph members
 * class DGraph #LightCyan
 * title DGraph UML graph
 */
public class ConcreteDGraph<N, E> extends AbstractDGraph<N, E> implements Cloneable {

    /*
     * ------------- FIELDS ------------------
     */
    /**
     * A set of elements.
     */
    private TreeSet<Node<N>> nodes;

    /**
     * A map to associate a set of successors to each node.
     *
     * @todo use a TreeSet for edges with a specific comparator for predecessors
     */
    private TreeMap<Node<N>, TreeSet<Edge<N, E>>> successors;

    /**
     * A map to associate a set of predecessors to each node.
     */
    private TreeMap<Node<N>, TreeSet<Edge<N, E>>> predecessors;


    /*
     * ------------- CONSTRUCTORS ------------------
     */
    /**
     * Constructs a new directed graph with an empty set of node.
     */
    public ConcreteDGraph() {
        super();
        this.nodes = new TreeSet<Node<N>>();
        this.successors = new TreeMap<Node<N>, TreeSet<Edge<N, E>>>();
        this.predecessors = new TreeMap<Node<N>, TreeSet<Edge<N, E>>>();
    }

    /**
     * Constructs a new directed graph source the specified set of nodes.
     *
     * Successors and predecessors of each nodes are initialised by an empty
     * set.
     *
     * @param set the set of nodes
     */
    public ConcreteDGraph(final SortedSet<Node<N>> set) {
        this();
        this.nodes.addAll(set);
        for (final Node<N> node : this.nodes) {
            this.successors.put(node, new TreeSet<Edge<N, E>>());
            this.predecessors.put(node, new TreeSet<Edge<N, E>>());
        }
    }

    /**
     * Constructs this component as a copy of the specified directed graph.
     *
     * @param graph the directed graph to be copied
     */
    public ConcreteDGraph(final DGraph<N, E> graph) {
        this(graph.getNodes());
        for (final Edge<N, E> edge : graph.getEdges()) {
            this.addEdge(edge);
        }
    }

    /*
     * --------------- ACCESSOR AND OVERLAPPING METHODS ------------
     */
    /**
     * Returns a clone of this component composed of a clone of each node and
     * each edge.
     *
     * @return the clone of this
     *
     * @throws java.lang.CloneNotSupportedException
     */
    @Override
    public ConcreteDGraph<N, E> clone() throws CloneNotSupportedException {
        final ConcreteDGraph<N, E> graph = (ConcreteDGraph<N, E>) super.clone();
        graph.nodes = (TreeSet) this.nodes.clone();
        graph.successors = new TreeMap<Node<N>, TreeSet<Edge<N, E>>>();
        graph.predecessors = new TreeMap<Node<N>, TreeSet<Edge<N, E>>>();
        for (final Map.Entry<Node<N>, TreeSet<Edge<N, E>>> entry : this.successors.entrySet()) {
            graph.successors.put(entry.getKey(), (TreeSet<Edge<N, E>>) entry.getValue().clone());
        }
        for (final Map.Entry<Node<N>, TreeSet<Edge<N, E>>> entry : this.predecessors.entrySet()) {
            graph.predecessors.put(entry.getKey(), (TreeSet<Edge<N, E>>) entry.getValue().clone());
        }
        return graph;
    }

    /**
     * Returns the set of nodes of this component.
     *
     * @return the set of nodes
     */
    public final SortedSet<Node<N>> getNodes() {
        return Collections.unmodifiableSortedSet(this.nodes);
    }

    /**
     * Returns the set of edges of this component.
     *
     * @return the set of edges
     */
    public final SortedSet<Edge<N, E>> getEdges() {
        return new Edges(this);
    }

    /**
     * Returns the set of edges successors of the specified node.
     *
     * @param node the node to search for
     *
     * @return the set of edges
     */
    public final SortedSet<Edge<N, E>> getSuccessorEdges(final Node<N> node) {
        return Collections.unmodifiableSortedSet(this.successors.get(node));
    }

    /**
     * Returns the set of edges predecessors of the specified node.
     *
     * @param node the node to search for
     *
     * @return the set of edges
     */
    public final SortedSet<Edge<N, E>> getPredecessorEdges(final Node<N> node) {
        return Collections.unmodifiableSortedSet(this.predecessors.get(node));
    }

    /**
     * Returns the set of nodes successors of the specified node.
     *
     * @param node the node to search for
     *
     * @return the set of nodes
     *
     * @todo use iterator pattern (some changes in ArrowRelation.java and
     * Lattice.java)
     */
    public final SortedSet<Node<N>> getSuccessorNodes(final Node<N> node) {
        final SortedSet<Node<N>> successorsFromNode = new TreeSet<Node<N>>();
        for (final Edge<N, E> edge : this.successors.get(node)) {
            successorsFromNode.add(edge.getTarget());
        }
        return Collections.unmodifiableSortedSet(successorsFromNode);
    }

    /**
     * Returns the set of nodes predecessors of the specified node.
     *
     * @param node the node to search for
     *
     * @return the set of nodes
     *
     * @todo use iterator pattern (some changes in ArrowRelation.java and
     * Lattice.java)
     */
    public final SortedSet<Node<N>> getPredecessorNodes(final Node<N> node) {
        final SortedSet<Node<N>> predecessorsFromNode = new TreeSet<Node<N>>();
        for (final Edge<N, E> edge : this.predecessors.get(node)) {
            predecessorsFromNode.add(edge.getSource());
        }
        return Collections.unmodifiableSortedSet(predecessorsFromNode);
    }

    /**
     * Returns, if it exists, the edge between node source and node to.
     *
     * @param source The origin node
     * @param target The destination node
     *
     * @return the found edge or null
     *
     * @todo see getNode
     */
    public final Edge<N, E> getEdge(final Node<N> source, final Node<N> target) {
        Edge<N, E> edge = null;
        if (source != null && target != null) {
            try {
                final Edge<N, E> search = new Edge<N, E>(source, target);
                edge = this.successors.get(source).subSet(search, true, search, true).first();
            } catch (NoSuchElementException ex) {
            }
        }
        return edge;
    }

    /**
     * Returns the node that is equal to the specified one.
     *
     * @param search The node to search for
     *
     * @return the found node or null
     *
     * @todo maybe use try { return this.nodes.subSet(search, true, search,
     * true).first(); } catch (NoSuchElementException e) { return null; }
     *
     */
    public final Node<N> getNode(final Node<N> search) {
        for (final Node<N> node : this.nodes) {
            if (node.equals(search)) {
                return node;
            }
        }
        return null;
    }

    /**
     * Returns the node whose content is equal to the specified one.
     *
     * @param content The content to search for
     *
     * @return the found node or null
     *
     * @todo this method is not efficient. Do we remove it or add an index on
     * DGraph using content field? Verify where it is called for migrating it if
     * necessary.
     */
    public final Node<N> getNodeByContent(final Object content) {
        for (final Node<N> node : this.nodes) {
            if (node.getContent().equals(content)) {
                return node;
            }
        }
        return null;
    }

    /**
     * Returns the node whose ident is equal to the specified one.
     *
     * @param identifier node identifier
     *
     * @return the found node or null
     */
    public final Node<N> getNodeByIdentifier(int identifier) {
        for (final Node<N> node : this.nodes) {
            if (node.getIdentifier() == identifier) {
                return node;
            }
        }
        return null;
    }

    /**
     * Returns the number of nodes of this component.
     *
     * @return the number of nodes
     */
    public final int sizeNodes() {
        return this.nodes.size();
    }

    /**
     * Returns the number of edges of this component.
     *
     * @return the number of edges
     */
    public final int sizeEdges() {
        int size = 0;
        for (final Node<N> node : this.nodes) {
            size += this.successors.get(node).size();
        }
        return size;
    }


    /*
     * --------------- NODES AND EDGES MODIFICATION METHODS ------------
     */
    /**
     * Checks if the specified node belong to this component.
     *
     * @param node the node to insert
     *
     * @return true if the node has been successfully inserted
     */
    public final boolean containsNode(final Node<N> node) {
        return this.nodes.contains(node);
    }

    /**
     * Adds the specified node to the set of node of this component.
     *
     * @param node the node to insert
     *
     * @return true if the node has been successfully inserted
     */
    public final boolean addNode(final Node<N> node) {
        if (!this.containsNode(node)) {
            this.nodes.add(node);
            this.successors.put(node, new TreeSet<Edge<N, E>>());
            this.predecessors.put(node, new TreeSet<Edge<N, E>>());
            return true;
        }
        return false;
    }

    /**
     * Removes the specified node from this component.
     *
     * @param node the node to remove
     *
     * @return true if the node was successfully removed
     */
    public final boolean removeNode(final Node<N> node) {
        if (this.containsNode(node)) {
            // Remove the edges (node,target) with key node in successors, and key target in predecessors
            for (final Edge<N, E> successor : this.successors.get(node)) {
                if (successor.getTarget().compareTo(node) != 0) {
                    for (final Edge<N, E> predecessor : this.predecessors.get(successor.getTarget())) {
                        if (predecessor.getSource().compareTo(node) == 0) {
                            this.predecessors.get(successor.getTarget()).remove(predecessor);
                        }
                    }
                }
                this.successors.remove(node);
            }
            // Remove the edges (source,node) with key node in predecessors, and key source in successors
            for (final Edge<N, E> predecessor : this.predecessors.get(node)) {
                if (predecessor.getSource().compareTo(node) != 0) {
                    for (final Edge<N, E> successor : this.successors.get(predecessor.getSource())) {
                        if (successor.getTarget().compareTo(node) == 0) {
                            this.successors.get(predecessor.getSource()).remove(successor);
                        }
                    }
                }
                this.predecessors.remove(node);
            }
            // Remove node
            this.nodes.remove(node);
            return true;
        }
        return false;
    }

    /**
     * Removes the specified set of nodes from this component.
     *
     * @param nodes set of nodes
     *
     * @return true if all nodes were removed
     */
    public final boolean removeNodes(final Set<Node<N>> nodes) {
        boolean all = true;
        for (final Node<N> node : nodes) {
            if (!this.removeNode(node)) {
                all = false;
            }
        }
        return all;
    }

    /**
     * Checks if there exists an edge between the two specified nodes.
     *
     * @param source the node origine of the edge
     * @param target the node destination of the edge
     *
     * @return true if the edge is contained by this component
     */
    public final boolean containsEdge(final Node<N> source, final Node<N> target) {
        return this.containsNode(source)
                && this.containsNode(target)
                && this.getSuccessorNodes(source).contains(target)
                && this.getPredecessorNodes(target).contains(source);
    }

    /**
     * Checks if the specified edge belong to this component.
     *
     * @param edge the edge to be checked
     *
     * @return true if the edge is contained by this component
     */
    public final boolean containsEdge(final Edge<N, E> edge) {
        return this.containsEdge(edge.getSource(), edge.getTarget());
    }

    /**
     * Adds an edge between the specified nodes to this component: `to` is added
     * as a successor of `source`.
     *
     * If the case where specified nodes don't belongs to the node set, then the
     * edge will not be added.
     *
     * @param source  the node origin of the edge
     * @param target  the node destination of the edge
     * @param content the edge content
     *
     * @return true if the edge was successfully added
     */
    public final boolean addEdge(final Node<N> source, final Node<N> target, final Object content) {
        if (this.containsNode(source) && this.containsNode(target)) {
            final Edge<N, E> edge = new Edge(source, target, content);
            this.successors.get(source).add(edge);
            this.predecessors.get(target).add(edge);
            return true;
        }
        return false;
    }

    /**
     * Adds an edge between the specified nodes to this component: `to` is added
     * as a successor of `source`.
     *
     * If the case where specified nodes don't belongs to the node set, then the
     * edge will not be added.
     *
     * @param source the node origin of the edge
     * @param target the node destination of the edge
     *
     * @return true if the edge was successfully added
     */
    public final boolean addEdge(final Node<N> source, final Node<N> target) {
        return this.addEdge(source, target, null);
    }

    /**
     * Adds the specified edge to this component in the successors of
     * edge.getSource() and in the predecessors of edge.getTarget().
     *
     * If the case where nodes to and source of this edges don't belongs to the
     * node set, then the edge will not be added.
     *
     * @param edge the edge to be added
     *
     * @return true if the edge was added
     */
    public final boolean addEdge(final Edge<N, E> edge) {
        if (this.containsNode(edge.getSource()) && this.containsNode(edge.getTarget())) {
            this.successors.get(edge.getSource()).add(edge);
            this.predecessors.get(edge.getTarget()).add(edge);
            return true;
        }
        return false;
    }

    /**
     * Removes source this component the edge between the specified node.
     *
     * `to` is removed source the successors of `source` and `to` is removed
     * source
     * the predecessors of `source`.
     *
     * @param source the node origine of the edge
     * @param target the node destination of the edge
     *
     * @return true if the edge was removed
     */
    public final boolean removeEdge(final Node<N> source, final Node<N> target) {
        if (this.containsEdge(source, target)) {
            final Edge<N, E> edge = new Edge(source, target);
            this.successors.get(source).remove(edge);
            this.predecessors.get(target).remove(edge);
            return true;
        }
        return false;
    }

    /**
     * Removes source this component the specified edge source the successors of
     * edge.getSource() and source the predecessors of edge.getTarget().
     *
     * @param edge the edge to be removed.
     *
     * @return true if the edge was removed
     */
    public final boolean removeEdge(final Edge<N, E> edge) {
        if (this.containsEdge(edge)) {
            this.successors.get(edge.getSource()).remove(edge);
            this.predecessors.get(edge.getTarget()).remove(edge);
            return true;
        }
        return false;
    }

    /*
     * --------------- ACYCLIC CHECKING METHODS ------------
     */
    /**
     * Returns the subgraph of this component induced by the specified set of
     * nodes.
     *
     * The subgraph only contains nodes of the specified set that also are in
     * this component.
     *
     * @param nodes The set of nodes
     *
     * @return The subgraph
     *
     * @todo implement a SubGraph class?
     */
    public ConcreteDGraph<N, E> getSubgraphByNodes(final Set<Node<N>> nodes) {
        ConcreteDGraph<N, E> graph = new ConcreteDGraph<N, E>();
        // addition of nodes in the subgraph
        for (Node<N> node : nodes) {
            if (this.containsNode(node)) {
                graph.addNode(node);
            }
        }
        // addition of edges in the subgraph
        for (Edge<N, E> edge : this.getEdges()) {
            if (graph.containsNode(edge.getTarget())) {
                graph.addEdge(edge);
            }
        }
        return graph;
    }

    /**
     * Returns the subgraph of this component induced by the specified set of
     * edges.
     *
     * The subgraph contains all nodes of this components, and only edges of the
     * specified set that also are in this component.
     *
     * @param edges The set of edges
     *
     * @return The subgraph
     *
     * @todo implement a SubGraph class?
     */
    public ConcreteDGraph<N, E> getSubgraphByEdges(final Set<Edge<N, E>> edges) {
        ConcreteDGraph<N, E> graph = new ConcreteDGraph<N, E>();
        // addition of all nodes in the subgraph
        for (Node<N> node : this.nodes) {
            graph.addNode(node);
        }
        // addition of specified edges in the subgraph
        for (Edge<N, E> edge : edges) {
            if (this.containsEdge(edge)) {
                graph.addEdge(edge);
            }
        }
        return graph;
    }

    /**
     * Replaces this component by its complementary graph.
     *
     * There is an edge between to nodes in the complementary graph when there
     * is no edges between the nodes in this component.
     */
    public void complementary() {
        for (Node<N> source : this.nodes) {
            TreeSet<Node<N>> newSuccessors = new TreeSet<Node<N>>(this.nodes);
            newSuccessors.removeAll(this.getSuccessorNodes(source));
            TreeSet<Node<N>> oldSuccessors = new TreeSet<Node<N>>(this.getSuccessorNodes(source));
            for (Node<N> target : oldSuccessors) {
                this.removeEdge(source, target);
            }
            for (Node<N> target : newSuccessors) {
                this.addEdge(source, target);
            }
        }
    }

    /*
     * --------------- GRAPH TREATMENT METHODS ------------
     */
    /**
     * Computes the reflexive reduction of this component.
     *
     * @return the number of removed edges
     */
    public final int reflexiveReduction() {
        int size = 0;
        for (final Node<N> node : this.nodes) {
            if (this.containsEdge(node, node)) {
                size++;
                this.removeEdge(node, node);
            }
        }
        return size;
    }

    /**
     * Computes the reflexive closure of this component.
     *
     * @return the number of added edges
     */
    public final int reflexiveClosure() {
        int size = 0;
        for (final Node<N> node : this.nodes) {
            if (!this.containsEdge(node, node)) {
                size++;
                this.addEdge(node, node);
            }
        }
        return size;
    }

    /**
     * Computes the transitive closure of this component.
     *
     * This treatment is performed in $O(nm+m_c)$, where $n$ corresponds to the
     * number of nodes, $m$ to the number of edges, and $m_c$ to the number of edges
     * in the closure. This treatment improves the Roy-Warshall algorithm that
     * directly implements the definition in $O(log(m) n^3)$.
     *
     * This treatment is overridden in class {@link DAGraph} with a more
     * efficient algorithm dedicated to directed acyclic graph.
     *
     * @return the number of added edges
     */
    public int transitiveClosure() {
        int size = 0;
        // mark each node to false
        final TreeMap<Node<N>, Boolean> mark = new TreeMap<Node<N>, Boolean>();
        for (final Node<N> node : this.nodes) {
            mark.put(node, Boolean.FALSE);
        }
        // treatment of nodes
        final List<Node<N>> list = new ArrayList<Node<N>>();
        for (final Node<N> source : this.nodes) {
            list.clear();
            list.add(source);
            while (!list.isEmpty()) {
                // Remove the first node
                final Node<N> source2 = list.remove(0);
                for (final Node<N> target : this.getSuccessorNodes(source2)) {
                    // treatment of target when not marked
                    if (!mark.get(target)) {
                        mark.put(target, Boolean.TRUE);
                        this.addEdge(source, target);
                        list.add(target);
                        size++;
                    }
                }
            }
            for (final Node<N> target : this.getSuccessorNodes(source)) {
                mark.put(target, Boolean.FALSE);
            }
        }
        return size;
    }

    /**
     * Transposes this component by replacing for each node its successor set by
     * its predecessor set, and its predecessor set by its successor set.
     */
    public final void transpose() {
        ConcreteDGraph<N, E> tmp = new ConcreteDGraph<N, E>(this);
        for (Edge<N, E> edge : tmp.getEdges()) {
            this.removeEdge(edge);
            this.addEdge(new Edge(edge.getTarget(), edge.getSource(), edge.getContent()));
        }
    }

    /**
     * Returns the directed acyclic graph where each node corresponds to a
     * strongly connected component (SCC) of this component stored in a TreeSet
     * of nodes.
     *
     * When two nodes in two different SCC are in relation, the same is for the
     * SCC they belongs to.
     *
     * @return The directed acyclic graph
     */
    public DAGraph<SortedSet<Node<N>>, Object> getStronglyConnectedComponent() {
        DAGraph<SortedSet<Node<N>>, Object> cc = new DAGraph<SortedSet<Node<N>>, Object>();
        // first depth first search
        ConcreteDGraph<N, E> tmp = new ConcreteDGraph<N, E>(this);
        tmp.transitiveClosure();
        ArrayList<Node<N>> last = tmp.depthFirstSearch()[1];
        // transposition of the graph
        ConcreteDGraph<N, E> transposedGraph = new ConcreteDGraph<N, E>(this);
        transposedGraph.transpose();
        // sort nodes according to the reverse last sort
        ArrayList<Node<N>> sort = new ArrayList<Node<N>>();
        Object[] array = last.toArray();
        for (int i = array.length - 1; i >= 0; i--) {
            sort.add((Node<N>) array[i]);
        }
        // second depth first search according to sort
        TreeSet<Node<N>> visited = new TreeSet<Node<N>>();
        for (Node<N> node : sort) {
            if (!visited.contains(node)) {
                last = transposedGraph.depthFirstSearch(node, visited, sort)[1];
                visited.addAll(last);
                TreeSet<Node<N>> sCC = new TreeSet<Node<N>>(last);
                // a strongly connected component is generated
                cc.addNode(new Node<SortedSet<Node<N>>>(sCC));    // addition of
            }
        }
        // edges between strongly connected component
        for (Node<SortedSet<Node<N>>> ccSource : cc.getNodes()) {
            for (Node<SortedSet<Node<N>>> ccTarget : cc.getNodes()) {
                for (Node<N> source : ccSource.getContent()) {
                    for (Node<N> target : ccTarget.getContent()) {
                        if (tmp.getSuccessorNodes(source).contains(target)) {
                            cc.addEdge(ccSource, ccTarget);
                        }
                    }
                }
            }
        }
        cc.reflexiveReduction();
        return cc;
    }

    /**
     * Set the set of nodes of this component.
     *
     * @param nodes The nodes
     *
     * @return this for chaining
     */
    protected ConcreteDGraph<N, E> setNodes(final TreeSet<Node<N>> nodes) {
        this.nodes = nodes;
        return this;
    }

    /**
     * Returns the successors of this component.
     *
     * @return the map
     */
    protected TreeMap<Node<N>, TreeSet<Edge<N, E>>> getSuccessors() {
        return this.successors;
    }

    /**
     * Set the successors of this component.
     *
     * @param successors The successors
     *
     * @return this for chaining
     */
    protected ConcreteDGraph<N, E> setSuccessors(final TreeMap<Node<N>, TreeSet<Edge<N, E>>> successors) {
        this.successors = successors;
        return this;
    }

    /**
     * Returns the predecessors of this component.
     *
     * @return the map
     */
    protected TreeMap<Node<N>, TreeSet<Edge<N, E>>> getPredecessors() {
        return this.predecessors;
    }

    /**
     * Set the predecessors of this component.
     *
     * @param predecessors The predecessors
     *
     * @return this for chaining
     */
    protected ConcreteDGraph<N, E> setPredecessors(final TreeMap<Node<N>, TreeSet<Edge<N, E>>> predecessors) {
        this.predecessors = predecessors;
        return this;
    }

    /**
     * Returns a two cells array containing the first visited sort on the nodes,
     * and the last visited sort on the nodes, by a depth first traverse issued
     * source the specified node.
     *
     * @param source  The source node
     * @param visited The visited nodes
     * @param sort    The sort parameter
     *
     * @return The array
     *
     * @todo Do we change that to iterators? Change to private and add a method
     * that return an iterator
     */
    private ArrayList<Node<N>>[] depthFirstSearch(Node<N> source, TreeSet<Node<N>> visited, ArrayList<Node<N>> sort) {
        ArrayList<Node<N>> first = new ArrayList<Node<N>>();
        ArrayList<Node<N>> last = new ArrayList<Node<N>>();
        first.add(source);
        visited.add(source);
        ArrayList<Node<N>>[] arrayVisited = new ArrayList[2];
        if (sort != null) {
            // search according to a sort
            for (Node<N> node : sort) {
                if (this.getSuccessorNodes(source).contains(node) && !visited.contains(node)) {
                    arrayVisited = this.depthFirstSearch(node, visited, sort);
                    visited.addAll(arrayVisited[0]);
                    first.addAll(arrayVisited[0]);
                    last.addAll(arrayVisited[1]);
                }
            }
        } else {
            // classical search
            for (Node<N> node : this.getSuccessorNodes(source)) {
                if (!visited.contains(node)) {
                    arrayVisited = this.depthFirstSearch(node, visited, sort);
                    visited.addAll(arrayVisited[0]);
                    first.addAll(arrayVisited[0]);
                    last.addAll(arrayVisited[1]);
                }
            }
        }
        last.add(source);
        arrayVisited[0] = first;
        arrayVisited[1] = last;
        return arrayVisited;
    }

    /**
     * Returns a two cells array containing the first visited sort on the nodes,
     * and the last visited sort on the nodes, by a depth first search.
     *
     * @return The array
     */
    private ArrayList<Node<N>>[] depthFirstSearch() {
        TreeSet<Node<N>> visited = new TreeSet<Node<N>>();
        ArrayList<Node<N>>[] arrayVisited = new ArrayList[2];
        ArrayList<Node<N>> first = new ArrayList<Node<N>>();
        ArrayList<Node<N>> last = new ArrayList<Node<N>>();
        for (Node<N> node : this.nodes) {
            if (!visited.contains(node)) {
                arrayVisited = this.depthFirstSearch(node, visited, null);
                visited.addAll(arrayVisited[0]);
                first.addAll(arrayVisited[0]);
                last.addAll(arrayVisited[1]);
            }
        }
        arrayVisited[0] = first;
        arrayVisited[1] = last;
        return arrayVisited;
    }

    /**
     * This class implements a sorted set of the edges.
     *
     * @param <N> Node content type
     * @param <E> Edge content type
     */
    private class Edges<N, E> extends AbstractSet<Edge<N, E>> implements SortedSet<Edge<N, E>> {

        /**
         * The underlying graph.
         */
        private final ConcreteDGraph<N, E> graph;

        /**
         * Constructs a sorted set of the edges source a graph.
         *
         * @param graph A ConcreteDGraph
         */
        Edges(final ConcreteDGraph<N, E> graph) {
            this.graph = graph;
        }

        /**
         * Get the underlying graph.
         *
         * @return the graph
         */
        protected final ConcreteDGraph<N, E> getGraph() {
            return this.graph;
        }

        /**
         * Implements the SortedSet interface.
         *
         * @return the first edge
         */
        public final Edge<N, E> first() {
            throw new UnsupportedOperationException();
        }

        /**
         * Implements the SortedSet interface.
         *
         * @return the last edge
         */
        public final Edge<N, E> last() {
            throw new UnsupportedOperationException();
        }

        /**
         * Implements the SortedSet interface.
         *
         * @param edge the to edge
         *
         * @return The head set
         *
         * @throws UnsupportedOperationException
         */
        public final SortedSet<Edge<N, E>> headSet(final Edge<N, E> edge) {
            throw new UnsupportedOperationException();
        }

        /**
         * Implements the SortedSet interface.
         *
         * @param edge the source edge
         *
         * @return The tail set
         *
         * @throws UnsupportedOperationException
         */
        public final SortedSet<Edge<N, E>> tailSet(final Edge<N, E> edge) {
            throw new UnsupportedOperationException();
        }

        /**
         * Implements the SortedSet interface.
         *
         * @param fromEdge the source edge
         * @param toEdge   the to edge
         *
         * @return The sub set
         *
         * @throws UnsupportedOperationException
         */
        public final SortedSet<Edge<N, E>> subSet(final Edge<N, E> fromEdge, final Edge<N, E> toEdge) {
            throw new UnsupportedOperationException();
        }

        /**
         * Implements the SortedSet interface.
         *
         * @return null
         */
        public final Comparator<? super Edge<N, E>> comparator() {
            return null;
        }

        /**
         * Implements the AbstractCollection class.
         *
         * @return the size of the collection
         */
        public final int size() {
            return this.graph.sizeEdges();
        }

        /**
         * Implements the AbstractCollection class.
         *
         * @return a new edges iterator
         */
        public final EdgesIterator iterator() {
            return new EdgesIterator(this);
        }

        /**
         * This class implements an iterator over the edges of a graph.
         */
        private class EdgesIterator implements Iterator<Edge<N, E>> {

            /**
             * The nodes iterator.
             */
            private final Iterator<Node<N>> nodesIterator;

            /**
             * The edges iterator for the current node.
             */
            private Iterator<Edge<N, E>> edgesIterator;

            /**
             * The edges object.
             */
            private final Edges<N, E> edges;

            /**
             * The hasNext flag.
             */
            private boolean hasNext;

            /**
             * Constructs the iterator source a set of edges.
             *
             * @param edges The edges.
             */
            EdgesIterator(final Edges<N, E> edges) {
                this.edges = edges;
                this.nodesIterator = edges.graph.nodes.iterator();
                this.prepareNext();
            }

            /**
             * Prepare the next edge and the hasNext flag.
             */
            private void prepareNext() {
                this.hasNext = false;
                while (!this.hasNext && this.nodesIterator.hasNext()) {
                    this.edgesIterator = this.edges.getGraph().successors.get(this.nodesIterator.next()).iterator();
                    this.hasNext = this.edgesIterator.hasNext();
                }
            }

            /**
             * The remove operation is not supported.
             *
             * @throws UnsupportedOperationException
             */
            @Override
            public void remove() {
                throw new UnsupportedOperationException();
            }

            /**
             * The next method returns the next edge.
             *
             * @return The next edge
             */
            public Edge<N, E> next() {
                Edge<N, E> edge = this.edgesIterator.next();
                if (!this.edgesIterator.hasNext()) {
                    this.prepareNext();
                }
                return edge;
            }

            /**
             * The hasNext method return true if the iterator has a next edge.
             *
             * @return true if the iterator has a next edge
             */
            public boolean hasNext() {
                return this.hasNext;
            }
        }
    }
}