DAG.java

package org.codehaus.plexus.util.dag;

/*
 * Copyright The Codehaus Foundation.
 *
 * Licensed under the Apache License, Version 2.0 (the "License");
 * you may not use this file except in compliance with the License.
 * You may obtain a copy of the License at
 *
 *     http://www.apache.org/licenses/LICENSE-2.0
 *
 * Unless required by applicable law or agreed to in writing, software
 * distributed under the License is distributed on an "AS IS" BASIS,
 * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
 * See the License for the specific language governing permissions and
 * limitations under the License.
 */

import java.io.Serializable;
import java.util.ArrayList;
import java.util.HashMap;
import java.util.List;
import java.util.Map;
import java.util.Set;

/**
 * DAG = Directed Acyclic Graph
 *
 * @author <a href="michal.maczka@dimatics.com">Michal Maczka</a>
 *
 * TODO this class should be renamed from DAG to Dag
 */
public class DAG implements Cloneable, Serializable {
    // ------------------------------------------------------------
    // Fields
    // ------------------------------------------------------------
    /**
     * Nodes will be kept in two data structures at the same time for faster processing
     */
    /**
     * Maps vertex's label to vertex
     */
    private Map<String, Vertex> vertexMap = new HashMap<>();

    /**
     * Conatin list of all vertices
     */
    private List<Vertex> vertexList = new ArrayList<>();

    // ------------------------------------------------------------
    // Constructors
    // ------------------------------------------------------------

    /**
     *
     */
    public DAG() {
        super();
    }

    // ------------------------------------------------------------
    // Accessors
    // ------------------------------------------------------------

    /**
     * @return the vertices
     */
    public List<Vertex> getVertices() {
        return vertexList;
    }

    /**
     * @deprecated instead use {@link #getVertices()}
     * @return the vertices
     */
    @Deprecated
    public List<Vertex> getVerticies() {
        return getVertices();
    }

    public Set<String> getLabels() {
        return vertexMap.keySet();
    }

    // ------------------------------------------------------------
    // Implementation
    // ------------------------------------------------------------

    /**
     * Adds vertex to DAG. If vertex of given label already exist in DAG no vertex is added
     *
     * @param label The label of the Vertex
     * @return New vertex if vertex of given label was not present in the DAG or existing vertex if vertex of given
     *         label was already added to DAG
     */
    public Vertex addVertex(final String label) {
        Vertex retValue = null;

        // check if vertex is already in DAG
        if (vertexMap.containsKey(label)) {
            retValue = vertexMap.get(label);
        } else {
            retValue = new Vertex(label);

            vertexMap.put(label, retValue);

            vertexList.add(retValue);
        }

        return retValue;
    }

    public void addEdge(final String from, final String to) throws CycleDetectedException {
        final Vertex v1 = addVertex(from);

        final Vertex v2 = addVertex(to);

        addEdge(v1, v2);
    }

    public void addEdge(final Vertex from, final Vertex to) throws CycleDetectedException {

        from.addEdgeTo(to);

        to.addEdgeFrom(from);

        final List<String> cycle = CycleDetector.introducesCycle(to);

        if (cycle != null) {
            // remove edge which introduced cycle

            removeEdge(from, to);

            final String msg = "Edge between '" + from + "' and '" + to + "' introduces to cycle in the graph";

            throw new CycleDetectedException(msg, cycle);
        }
    }

    public void removeEdge(final String from, final String to) {
        final Vertex v1 = addVertex(from);

        final Vertex v2 = addVertex(to);

        removeEdge(v1, v2);
    }

    public void removeEdge(final Vertex from, final Vertex to) {
        from.removeEdgeTo(to);

        to.removeEdgeFrom(from);
    }

    public Vertex getVertex(final String label) {
        final Vertex retValue = vertexMap.get(label);

        return retValue;
    }

    public boolean hasEdge(final String label1, final String label2) {
        final Vertex v1 = getVertex(label1);

        final Vertex v2 = getVertex(label2);

        final boolean retValue = v1.getChildren().contains(v2);

        return retValue;
    }

    /**
     * @param label see name
     * @return the childs
     */
    public List<String> getChildLabels(final String label) {
        final Vertex vertex = getVertex(label);

        return vertex.getChildLabels();
    }

    /**
     * @param label see name
     * @return the parents
     */
    public List<String> getParentLabels(final String label) {
        final Vertex vertex = getVertex(label);

        return vertex.getParentLabels();
    }

    /**
     * @see java.lang.Object#clone()
     */
    @Override
    public Object clone() throws CloneNotSupportedException {
        // this is what's failing..
        final Object retValue = super.clone();

        return retValue;
    }

    /**
     * Indicates if there is at least one edge leading to or from vertex of given label
     * @param label the label
     * @return <code>true</code> if this vertex is connected with other vertex,<code>false</code> otherwise
     */
    public boolean isConnected(final String label) {
        final Vertex vertex = getVertex(label);

        final boolean retValue = vertex.isConnected();

        return retValue;
    }

    /**
     * Return the list of labels of successor in order decided by topological sort
     *
     * @param label The label of the vertex whose predecessors are searched
     * @return The list of labels. Returned list contains also the label passed as parameter to this method. This label
     *         should always be the last item in the list.
     */
    public List<String> getSuccessorLabels(final String label) {
        final Vertex vertex = getVertex(label);

        final List<String> retValue;

        // optimization.
        if (vertex.isLeaf()) {
            retValue = new ArrayList<>(1);

            retValue.add(label);
        } else {
            retValue = TopologicalSorter.sort(vertex);
        }

        return retValue;
    }
}