/*
    * Zemucan: A Syntax Assistant for DB2
    * Copyright (C) 2009, 2010 Andres Gomez Casanova
    *
    * This file is part of Zemucan.
    *
    * Zemucan is free software: you can redistribute it and/or modify
    * it under the terms of the GNU Lesser General Public License as published by
    * the Free Software Foundation; either version 3 of the License, or
   * (at your option) any later version.
   *
   * Zemucan is distributed in the hope that it will be useful,
   * but WITHOUT ANY WARRANTY; without even the implied warranty of
   * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
   * GNU Lesser General Public License for more details.
   *
   * You should have received a copy of the GNU Lesser General Public License
   * along with this library; if not, see <http://www.gnu.org/licenses/>.
   *
   * Contact:
   * a n g o c a  at  y a h o o  dot  c o m
   * Cra. 45 No 61 - 31, Bogota, Colombia.
   *
   * Author:   $LastChangedBy: angoca $:
   * Date:     $LastChangedDate: 2011-03-06 10:15:32 -0500 (dom, 06 mar 2011) $:
   * Revision: $LastChangedRevision: 1913 $:
   * URL:      $HeadURL: https://zemucan.svn.sourceforge.net/svnroot/zemucan/branches/zemucan_v1/source-code/graph/src/main/java/name/angoca/zemucan/core/graph/model/Graph.java $:
   */
  package name.angoca.zemucan.core.graph.model;
  
  import java.util.ArrayList;
  import java.util.Collections;
  import java.util.HashMap;
  import java.util.Iterator;
  import java.util.List;
  import java.util.Map;
  
  import name.angoca.zemucan.AbstractZemucanException;
  import name.angoca.zemucan.ParameterNullException;
  import name.angoca.zemucan.tools.Constants;
  import name.angoca.zemucan.tools.configurator.Configurator;
  
  import org.slf4j.Logger;
  import org.slf4j.LoggerFactory;
  
  /**
   * This class models the graph that represents the read grammar. The
   * construction of the graph is done in two phases: add nodes, and associate
   * node.
   * <p>
   * The first phase only permits to add nodes to the graph. This is done with the
   * method addNode. Try to establish a relation between nodes is not permitted in
   * this phase.
   * <p>
   * The second phase permits to establish relation between nodes, once they have
   * been defined. In this phase is not possible to add more nodes.
   * <p>
   * In order to change the phase, the method 'firstPhaseFinished' has to be
   * called. Once this method is called, is not possible to go back.
   * <p>
   * The method 'secondPhaseFinished' before to return the StartingNode, it checks
   * the graph if it is stable and there are not inconsistencies. Also, at this
   * phase, the extra nodes are added. The extra nodes include the help node and
   * the about node.
   * <p>
   * This object is immutable, once it is created, their properties cannot be
   * changed. This is the reason because there are not setter methods. The getters
   * methods are for tests purposes and have a default visibility.
   * <p>
   * <b>Control Version</b>
   * <p>
   * <ul>
   * <li>1.0.0 Class creation.</li>
   * <li>1.0.1 The name attribute is used for logging.</li>
   * <li>1.1.0 GraphState.</li>
   * <li>1.2.0 Merge and simplify graph.</li>
   * <li>1.2.1 Extra nodes as part of first phase.</li>
   * <li>1.3.0 GetNodes.</li>
   * <li>1.3.1 Extra nodes addition fixed.</li>
   * <li>1.4.0 Some methods were changed to static.</li>
   * <li>1.4.1 Exception deleted.</li>
   * <li>1.4.2 About and license tokens.</li>
   * <li>1.5.0 GraphNode hierarchy.</li>
   * <li>1.6.0 Next Node: Create / Remove relation from nodes. Simplify graph, add
   * node returning the created one.</li>
   * </ul>
   *
   * @author Andres Gomez Casanova <a
   *         href="mailto:a n g o c a at y a h o o dot c o m" >(AngocA)</a>
   * @version 1.6.0 2010-09-15
   */
  public class Graph {
  
      /**
       * Logger.
       */
      private static final Logger LOGGER = LoggerFactory.getLogger(Graph.class);
  
      /**
      * Change the ascendancy associations of a pair of nodes, to the other one.
      * <p>
      * The nodes are not the same.
      *
      * @param n1
      *            Node to add the other node's associations.
      * @param n2
      *            The associations of this node will be taken out. After this
      *            process it will be deleted.
      * @param node
      *            Node to relocate the associations.
      * @throws AbstractGraphException
      *             If one node is null or there is a problem with the
      *             associations.
      */
     private static void changeAscendancyNodeRelations(
             final AbstractGraphNode/* ! */n1, final AbstractGraphNode/* ! */n2,
             final AbstractGraphNode /* ! */node) throws AbstractGraphException {
         assert n1 != null;
         assert n2 != null;
         assert node != null;
         assert n1 != n2;
         assert n2 != node;
 
         // First removes (If it's Starting or Ending Node)
         node.removeChild(n2);
         n2.removeParent(node);
         // Then, adds relations.
         n1.addParent(node);
         node.addChild(n1);
     }
 
     /**
      * Change the descendancy associations of a pair of nodes, to the other one.
      * <p>
      * The nodes are not the same.
      *
      * @param n1
      *            Node to add the other node's associations.
      * @param n2
      *            The associations of this node will be taken out. After this
      *            process this node will be deleted.
      * @param node
      *            Node to relocate the associations.
      * @throws AbstractGraphException
      *             If one node is null or there is a problem with the
      *             associations.
      */
     private static void changeDescendancyNodeRelations(
             final AbstractGraphNode/* ! */n1, final AbstractGraphNode/* ! */n2,
             final AbstractGraphNode /* ! */node) throws AbstractGraphException {
         assert n1 != null;
         assert n2 != null;
         assert node != null;
         assert n1 != n2;
         assert n2 != node;
 
         // First adds the parent relation.
         node.addParent(n1);
         
         // Then removes the relation.
         node.removeParent(n2);
         n2.removeChild(node);
         
         // Finally add the child relation.
         n1.addChild(node);
     }
 
     /**
      * Checks the children of a given node to see if there are two children that
      * represents the same word.
      *
      * @param node
      *            Node to check its children.
      * @return true if there are two children representing the same word.
      * @throws AbstractZemucanException
      */
     static boolean checkChildren(final AbstractGraphNode/* ! */node)
             throws AbstractZemucanException {
         assert node != null;
 
         boolean ret = false;
         // Checks the names of the nodes in a sorted way.
         if (node.getChildren().size() > 1) {
             Graph.LOGGER.debug("Fusioning children in {}", node.getId()); //$NON-NLS-1$
             // Sort the children
             final List<AbstractGraphNode> children = new ArrayList<AbstractGraphNode>();
             children.addAll(node.getChildren());
             Collections.sort(children);
             AbstractGraphNode n1 = children.get(0);
             Graph.LOGGER.debug("Analyzing to fusion: {}", n1.getId()); //$NON-NLS-1$
             // This condition changes dynamically, so it is calculated
             // for each iteration.
             for (int i = 1; i < children.size(); i += 1) {
                 final AbstractGraphNode n2 = children.get(i);
                 if ((n2 != null)
                         && (n1 instanceof TextualGraphNode)
                         && (n2 instanceof TextualGraphNode)
                         && ((TextualGraphNode) n1).getName().equals(
                                 ((TextualGraphNode) n2).getName())) {
                     // Fusion the nodes.
                     Graph.LOGGER.debug("Fusionning nodes {} and {}",
                             n1.getId(), n2.getId());
                     Graph.nodeFusion(n1, n2);
                     ret = true;
                 } else if (n2 != null) {
                     // Second token, becomes first token.
                     n1 = n2;
                 } else {
                     // Error.
                     assert false;
                 }
             }
         } else {
             Graph.LOGGER.debug("No children to fusion in {}", node.getId()); //$NON-NLS-1$
         }
         return ret;
     }
 
     /**
      * Recursive method to check that all the ways of a graph goes to
      * EndingNode.
      *
      * @param node
      *            Node to tests its ways.
      */
     private static void goBackward(final AbstractGraphNode /* ! */node) {
         assert node != null;
 
         if (!node.isGoToEndingNode()) {
             node.setGoToEndingNode(true);
             final List<AbstractGraphNode> parents = node.getParents();
             for (final AbstractGraphNode graphNode : parents) {
                 Graph.goBackward(graphNode);
             }
         }
     }
 
     /**
      * Recursive method to check that all the ways of a graph comes from
      * StartingNode.
      *
      * @param node
      *            Node to tests its ways.
      */
     private static void goForward(final AbstractGraphNode /* ! */node) {
         assert node != null;
 
         if (!node.isComeFromStartingNode()) {
             node.setComeFromStartingNode(true);
             final List<AbstractGraphNode> children = node.getChildren();
             for (final AbstractGraphNode graphNode : children) {
                 Graph.goForward(graphNode);
             }
         }
     }
 
     /**
      * Fusion two nodes into one.
      * <p>
      * The nodes are not the same.
      *
      * @param n1
      *            First node to merge, and resulting node.
      * @param n2
      *            Second node to merge. It will be deleted.
      * @throws AbstractGraphException
      *             If there is a problem changing the associations.
      */
     static void nodeFusion(final AbstractGraphNode/* ! */n1,
             final AbstractGraphNode/* ! */n2)
             throws AbstractZemucanException {
         assert n1 != null;
         assert n2 != null;
         assert n1 != n2;
 
         // Fusion of children. The size decrease in each iteration.
         while (n2.getChildren().size() >= 1) {
             final AbstractGraphNode node = n2.getChildren().get(0);
             Graph.changeDescendancyNodeRelations(n1, n2, node);
         }
         // Fusion of parents.
         while (n2.getParents().size() >= 1) {
             final AbstractGraphNode node = n2.getParents().get(0);
             Graph.changeAscendancyNodeRelations(n1, n2, node);
         }
     }
 
     /**
      * Ending node of the graph.
      */
     private EndingNode endingNode;
 
     /**
      * Determines if the graph has to include the extra nodes.
      */
     private final boolean extraNodes;
 
     /**
      * This parameter permits to determine the state of the graph. If the graph
      * has all the nodes, and it waits for the second phase when the relations
      * are established. Or if the graph has a valid structure.
      */
     private GraphState graphState;
 
     /**
      * The name of the graph. This aids to identify the graph when merging
      * graphs.
      */
     private String name;
 
     /**
      * Set of nodes. In this array, at the first phase only reads the nodes but
      * they do not have relations. The second phase associates the nodes.
      */
     private Map<String, AbstractGraphNode> nodes;
 
     /**
      * Starting node of the graph.
      */
     private StartingNode startingNode;
 
     /**
      * Creates a graph with a given name. The name works as identifier when
      * dealing with several graphs.
      *
      * @param graphName
      *            Name of this graph.
      * @param addExtraNodes
      *            Determines if the graph has to include some extra predefined
      *            nodes.
      * @throws ParameterNullException
      *             If the graph name is not given.
      */
     public Graph(final String/* ! */graphName, final boolean addExtraNodes)
             throws ParameterNullException {
         if (graphName == null) {
             throw new ParameterNullException("name"); //$NON-NLS-1$
         }
 
         this.name = graphName;
 
         this.nodes = new HashMap<String, AbstractGraphNode>();
         this.graphState = GraphState.FirstPhase;
 
         this.extraNodes = addExtraNodes;
 
         Graph.LOGGER.info("'{}' graph started.", graphName); //$NON-NLS-1$
     }
 
     /**
      * Adds the about information, license and help node to the graph. It can be
      * called several times, but it will add the nodes just once.
      *
      * @throws AbstractZemucanException
      *             If there is a problem adding the associations.
      */
     private void addExtraNodes() throws AbstractGraphException {
         if ((this.startingNode != null) && (this.endingNode != null)) {
             // About node
             final GraphNode aboutCaller;
             final String aboutNode = Configurator.getInstance().getProperty(
                     Constants.ABOUT_TOKEN_PROPERTY);
             if (aboutNode == null) {
                 aboutCaller = new GraphNode(Constants.ABOUT_TOKEN_ID,
                         Constants.ABOUT_TOKEN_VALUE, this);
             } else {
                 aboutCaller = new GraphNode(Constants.ABOUT_TOKEN_ID,
                         aboutNode, this);
             }
             final AboutNode about = new AboutNode(this);
 
             // Adds the nodes to the list.
             this.nodes.put(this.name + ':' + Constants.ABOUT_TOKEN_ID,
                     aboutCaller);
             this.nodes.put(this.name + ':' + Constants.ABOUT_CONTENT_TOKEN_ID,
                     about);
 
             // Adds double relations
             this.startingNode.addChild(aboutCaller);
             aboutCaller.addParent(this.startingNode);
             aboutCaller.addChild(about);
             about.addParent(aboutCaller);
             about.addChild(this.endingNode);
             this.endingNode.addParent(about);
 
             // Help node
             final GraphNode helpCaller;
             final String helpNode = Configurator.getInstance().getProperty(
                     Constants.HELP_TOKEN_PROPERTY);
             if (helpNode == null) {
                 helpCaller = new GraphNode(Constants.HELP_TOKEN_ID,
                         Constants.HELP_TOKEN_VALUE, this);
             } else {
                 helpCaller = new GraphNode(Constants.HELP_TOKEN_ID, helpNode,
                         this);
             }
             final HelpNode help = new HelpNode(this);
 
             // Adds the nodes to the list.
             this.nodes.put(this.name + ':' + Constants.HELP_TOKEN_ID,
                     helpCaller);
             this.nodes.put(this.name + ':' + Constants.HELP_CONTENT_TOKEN_ID,
                     help);
 
             // Adds double relations
             this.startingNode.addChild(helpCaller);
             helpCaller.addParent(this.startingNode);
             helpCaller.addChild(help);
             help.addParent(helpCaller);
             help.addChild(this.endingNode);
             this.endingNode.addParent(help);
 
             // License node
             final GraphNode licenseCaller;
             final String licenseNode = Configurator.getInstance().getProperty(
                     Constants.LICENSE_TOKEN_PROPERTY);
             if (licenseNode == null) {
                 licenseCaller = new GraphNode(Constants.LICENSE_TOKEN_ID,
                         Constants.LICENSE_TOKEN_VALUE, this);
             } else {
                 licenseCaller = new GraphNode(Constants.LICENSE_TOKEN_ID,
                         licenseNode, this);
             }
             final LicenseNode license = new LicenseNode(this);
 
             // Adds the nodes to the list.
             this.nodes.put(this.name + ':' + Constants.LICENSE_TOKEN_ID,
                     licenseCaller);
             this.nodes.put(
                     this.name + ':' + Constants.LICENSE_CONTENT_TOKEN_ID,
                     license);
 
             // Adds double relations
             this.startingNode.addChild(licenseCaller);
             licenseCaller.addParent(this.startingNode);
             licenseCaller.addChild(license);
             license.addParent(licenseCaller);
             license.addChild(this.endingNode);
             this.endingNode.addParent(license);
         } else {
             Graph.LOGGER
                     .info("Extra nodes could not be added, there were not " + //$NON-NLS-1$
                             "StartingNode or EndingNode."); //$NON-NLS-1$
         }
     }
 
     /**
      * Adds a new node in the graph. The given parameters permit to build the
      * node before to add it. This method does not establishes associations.
      *
      * @param nodeId
      *            Id of the node.
      * @param nodeName
      *            Name of the node.
      * @param reserved
      *            if the node represents a reserved word.
      * @return The created node.
      * @throws AbstractGraphException
      *             If the graph state is invalid, or if the graph name is
      *             invalid, or if the node id already exists in the graph.
      */
     public final AbstractGraphNode addNode(final String/* ! */nodeId,
             final String/* ! */nodeName, final boolean reserved)
             throws AbstractGraphException {
         if (!this.graphState.equals(GraphState.FirstPhase)) {
             throw new InvalidGraphStateException(this.graphState,
                     GraphState.FirstPhase);
         }
 
         Graph.LOGGER.debug("Adding node '{}' ({}, {}) in '{}' graph", //$NON-NLS-1$
                 new String[] { nodeId, nodeName, Boolean.toString(reserved),
                         this.name });
 
         // Creates a new node with its parameters
         AbstractGraphNode node = null;
 
         if (nodeId.equals(Constants.STARTING_NODE)) {
             if (nodeName.equals(Constants.STARTING_NODE) && reserved) {
                 // It's the starting node
                 node = new StartingNode(this);
                 this.startingNode = (StartingNode) node;
             } else {
                 throw new InvalidStartingNodeException();
             }
         } else if (nodeId.equals(Constants.ENDING_NODE)) {
             if (nodeName.equals(Constants.ENDING_NODE) && reserved) {
                 // It's the ending node
                 node = new EndingNode(this);
                 this.endingNode = (EndingNode) node;
             } else {
                 throw new InvalidEndingNodeException();
             }
         } else if (nodeId.startsWith(Constants.NEXT_NODE) && reserved) {
             // It's a next node.
             node = new NextNode(nodeName, this);
         } else {
             // It's a normal node
             if (reserved) {
                 node = new GraphNode(nodeId, nodeName, this);
             } else {
                 node = new NonReservedGraphNode(nodeId, nodeName, this);
             }
 
         }
 
         // Adds the node to list
         if (this.nodes.containsKey(this.name + ':' + nodeId)) {
             throw new DuplicatedNodeException(nodeId);
         }
         this.nodes.put(this.name + ':' + nodeId, node);
 
         Graph.LOGGER.debug("Addition {}", this);
 
         assert node != null;
 
         return node;
     }
 
     /**
      * Creates a relation between two nodes. It calls implicitly the method that
      * creates a relation between two node ids.
      *
      * @param parentNode
      *            Origin of the relation.
      * @param childNode
      *            Target of the relation.
      * @throws AbstractZemucanException
      *             If there is a problem while creating the relation.
      */
     public void addRelation(final AbstractGraphNode parentNode,
             final AbstractGraphNode childNode)
             throws AbstractZemucanException {
         final int size = this.name.length() + 1;
         String parentId = parentNode.getId();
         String childId = childNode.getId();
         if (parentId.startsWith(this.name)) {
             parentId = parentId.substring(size);
         }
         if (childId.startsWith(this.name)) {
             childId = childId.substring(size);
         }
         this.addRelation(parentId, childId);
         Graph.LOGGER.debug("Relation {}", parentNode);
     }
 
     /**
      * Adds a relation between two nodes, giving the members of the relation,
      * the parent and the child.
      *
      * @param parentId
      *            Id of the parent node.
      * @param childId
      *            Id of the child node.
      * @throws AbstractZemucanException
      *             if the parent or the child does not exist in the set of
      *             nodes. Or if the state of the graph is invalid. Or when
      *             trying to make an invalid relation between two nodes. If a
      *             parameter is null.
      */
     public final void addRelation(final String/* ! */parentId,
             final String/* ! */childId) throws AbstractZemucanException {
         Graph.LOGGER.debug(
                 "Adding relation in graph '{}' between '{}' and '{}'", //$NON-NLS-1$
                 new String[] { this.name, parentId, childId });
 
         if (parentId == null) {
             throw new ParameterNullException("parentId"); //$NON-NLS-1$
         }
         if (childId == null) {
             throw new ParameterNullException("childId"); //$NON-NLS-1$
         }
         if (this.graphState.equals(GraphState.FirstPhase)) {
             throw new InvalidGraphStateException(this.graphState,
                     GraphState.SecondPhase);
         }
         if (this.graphState.equals(GraphState.Validated)) {
             this.graphState = GraphState.SecondPhase;
         }
         // XXX dumpGraphKeys();
         final String key = this.name + ':' + parentId;
         final AbstractGraphNode parent = this.nodes.get(key);
         if (parent == null) {
             throw new NotExistingNodeException(parentId);
         }
 
         // Retrieves the child and established the relation.
         final AbstractGraphNode childNode = this.nodes.get(this.name + ':'
                 + childId);
         if (childNode == null) {
             throw new NotExistingChildNodeException(parentId, childId);
         }
 
         parent.addChild(childNode);
         childNode.addParent(parent);
     }
 
     /**
      * Checks the graph searching nodes that represents the same word for a
      * common parent.
      *
      * @throws DuplicatedNodeNameException
      *             If a double node is found.
      */
     public final void checkDuplicates() throws DuplicatedNodeNameException {
         final Iterator<AbstractGraphNode> it = this.nodes.values().iterator();
         while (it.hasNext()) {
             final AbstractGraphNode node = it.next();
             final int size = node.getChildren().size();
             if (size >= 2) {
                 final List<AbstractGraphNode> children = new ArrayList<AbstractGraphNode>();
                 children.addAll(node.getChildren());
                 Collections.sort(children);
                 AbstractGraphNode n0 = children.get(0);
                 for (int i = 1; i < size; i += 1) {
                     final AbstractGraphNode n1 = children.get(i);
                     if ((n0 instanceof TextualGraphNode)
                             && (n1 instanceof TextualGraphNode)) {
                         final TextualGraphNode textualn0 = (TextualGraphNode) n0;
                         final TextualGraphNode textualn1 = (TextualGraphNode) n1;
                         if (textualn0.getName().equals(textualn1.getName())) {
                             throw new DuplicatedNodeNameException(node.getId(),
                                     textualn0.getName(), n0.getId(), n1.getId());
                         }
                     }
                     n0 = n1;
                 }
             }
         }
     }
 
     /**
      * Scans the set of nodes searching if someone has StartingNode as Child.
      *
      * @return Always returns true because is used when assertions are
      *         activated.
      * @throws AbstractZemucanException
      *             When a node is detected that references the StartingNode.
      *             When a node is detected that if referenced by the EndingNode.
      */
     private boolean checkNoParentsForStartingNode()
             throws AbstractZemucanException {
         for (final AbstractGraphNode node : this.nodes.values()) {
             // Redundant check that cannot be tested.
             final List<AbstractGraphNode> ways = node.getChildren();
             for (final AbstractGraphNode graphNode : ways) {
                 if (graphNode instanceof StartingNode) {
                     // It cannot be tested, because GraphNode checks
                     // the child node when adding relation
                     throw new ReferencingStartingNodeException(node.getId());
                 }
             }
 
             // Redundant check that cannot be tested.
             final List<AbstractGraphNode> parents = node.getParents();
             for (final AbstractGraphNode graphNode : parents) {
                 if (graphNode instanceof EndingNode) {
                     // It cannot be tested, because EndingNode always
                     // throws an exception when trying to add a child.
                     throw new ReferencingEndingNodeException(node.getId());
                 }
             }
         }
         return true;
     }
 
     /*
      * (non-Javadoc)
      * @see java.lang.Object#equals(java.lang.Object)
      */
     @Override
     public final boolean equals(final Object obj) {
         boolean result = false;
         if (obj instanceof Graph) {
             final Graph graph = (Graph) obj;
             if (this.name.equals(graph.name)
                     && (this.extraNodes == graph.extraNodes)
                     && (this.graphState == graph.graphState)
                     && (this.startingNode != null)
                     && (graph.startingNode != null)
                     && this.startingNode.equals(graph.startingNode)
                     && (this.endingNode != null) && (graph.endingNode != null)
                     && this.endingNode.equals(graph.endingNode)
                     && (this.nodes.size() == graph.nodes.size())) {
                 result = true;
                 for (final String key : this.nodes.keySet()) {
                     final AbstractGraphNode node = graph.nodes.get(key);
                     if (!this.exist(key, node)) {
                         result = false;
                     }
                 }
             }
         }
         return result;
     }
 
     /**
      * Checks if a given key and a node, exist in the current set of nodes.
      *
      * @param key
      *            key of the graph in the set of nodes.
      * @param node
      *            Node.
      * @return If the node exists in the set of nodes.
      */
     private boolean exist(final String/* ! */key,
             final AbstractGraphNode/* ? */node) {
         assert key != null;
         assert !key.equals(""); //$NON-NLS-1$
 
         boolean result = false;
         final AbstractGraphNode graphNode = this.nodes.get(key);
         if ((graphNode != null) && graphNode.equals(node)) {
             result = true;
         }
         return result;
     }
 
     /**
      * This parameter change the state of the graph. The first phase permits to
      * add nodes but it does not permit to establish relation between them. The
      * second phase permits to create associations between nodes when all the
      * nodes are defined in the graph.
      *
      * @throws AbstractZemucanException
      *             If there is a problem adding the extra associations.
      */
     public final void firstPhaseFinished() throws AbstractZemucanException {
         if (!this.graphState.equals(GraphState.FirstPhase)) {
             throw new InvalidGraphStateException(this.graphState,
                     GraphState.FirstPhase);
         }
 
         // Adding extra nodes.
         if (this.extraNodes) {
             this.addExtraNodes();
         }
 
         this.graphState = GraphState.SecondPhase;
 
         Graph.LOGGER.info("'{}' - First Phase finished.", this.name); //$NON-NLS-1$
     }
 
     /**
      * Returns the EndingNode. This method can be called only when the graph has
      * a state of validated; it means that the graph is after the SecondPhase.
      *
      * @return EndingNode if the graph is validated.
      * @throws InvalidGraphStateException
      *             If the graph is not in Validated state.
      */
     final EndingNode/* ! */getEndingNode() throws InvalidGraphStateException {
         if (!this.graphState.equals(GraphState.Validated)) {
             throw new InvalidGraphStateException(this.graphState,
                     GraphState.Validated);
         }
         return this.endingNode;
     }
 
     /**
      * Retrieves the graph state: FirstPhase, SecondPhase or validated.
      *
      * @return Returns the state of the graph.
      */
     final GraphState/* ! */getGraphState() {
         return this.graphState;
     }
 
     /**
      * Returns the name of the graph.
      *
      * @return Graph's name.
      */
     public final String/* ! */getName() {
         return this.name;
     }
 
     /**
      * Returns the set of nodes that compose the graph.
      *
      * @return Set of nodes.
      */
     final Map<String, AbstractGraphNode> /* <!,!>! */getNodes() {
         return this.nodes;
     }
 
     /**
      * Returns the StartingNode. This method can be executed only after the
      * second phase has been finished (The graph has to be in Validated state.)
      *
      * @return StartingNode if the graph is validated..
      * @throws InvalidGraphStateException
      *             If the graph is in an invalid state to call this method.
      */
     public final StartingNode getStartingNode()
             throws InvalidGraphStateException {
         if (!this.graphState.equals(GraphState.Validated)) {
             throw new InvalidGraphStateException(this.graphState,
                     GraphState.Validated);
         }
         return this.startingNode;
     }
 
     /*
      * (non-Javadoc)
      * @see java.lang.Object#hashCode()
      */
     @Override
     public final int hashCode() {
         int result = this.name.hashCode() - GraphState.FirstPhase.hashCode();
         if (this.extraNodes) {
             result *= 2;
         }
         if (this.startingNode != null) {
             result -= this.startingNode.hashCode();
         } else {
             result += 1;
         }
         if (this.endingNode != null) {
             result -= this.endingNode.hashCode();
         } else {
             result += 2;
         }
         if (this.nodes.size() != 0) {
             result /= this.nodes.size();
         }
 
         return result;
     }
 
     /**
      * Merge the current graph in the given graph. The current one will be
      * emptied.
      * <p>
      * Both graphs (this and the given one) have to be validated.
      * <p>
      * The given graph can't be the same.
      *
      * @param graph
      *            Graph that will have all the information of the current graph.
      * @throws AbstractZemucanException
      *             If there is a problem making the fusion between nodes.
      */
     public final void merge(final Graph graph)
             throws AbstractZemucanException {
         assert graph != this;
         assert !this.name.equals(graph.name);
         assert this.graphState == GraphState.Validated;
         assert graph.graphState == GraphState.Validated;
 
         // Fusion Starting and Ending nodes.
         Graph.nodeFusion(graph.startingNode, this.startingNode);
         this.nodes.remove(this.startingNode.getId());
         Graph.nodeFusion(graph.endingNode, this.endingNode);
         this.nodes.remove(this.endingNode.getId());
 
 
         Object[] keys = this.nodes.keySet().toArray();
         int i = 0;
         int len = keys.length;
         while (i < len) {
             final String id = (String) keys[i];
             AbstractGraphNode node = this.nodes.remove(id);
             graph.nodes.put(id, node);
             i += 1;
         }
 
         graph.name = "merged:{" + graph.name + ',' + this.name + '}'; //$NON-NLS-1$
 
         // Rename the keys for all nodes
         final Map<String, AbstractGraphNode> newNodes = new HashMap<String, AbstractGraphNode>();
         keys = graph.nodes.keySet().toArray();
         i = 0;
         len = keys.length;
         while (i < len) {
             final String id = (String) keys[i];
             AbstractGraphNode node = graph.nodes.remove(id);
             node.addGraphName(graph.name);
             newNodes.put(node.getId(), node);
             i += 1;
         }
         graph.nodes = newNodes;
     }
 
     /**
      * Removes a relation between two nodes. It calls implicitly the method that
      * removes a relation between two node ids.
      *
      * @param parentNode
      *            Origin of the relation.
      * @param childNode
      *            Target of the relation.
      * @throws AbstractZemucanException
      *             If there is a problem while removing the relation.
      */
     public void removeRelation(final AbstractGraphNode parentNode,
             final AbstractGraphNode childNode)
             throws AbstractZemucanException {
         final int size = this.name.length() + 1;
         String parentId = parentNode.getId();
         String childId = childNode.getId();
         if (parentId.startsWith(this.name)) {
             parentId = parentId.substring(size);
         }
         if (childId.startsWith(this.name)) {
             childId = childId.substring(size);
         }
         this.removeRelation(parentId, childId);
         Graph.LOGGER.debug("Relation {}", parentNode);
     }
 
     /**
      * Removes a relation between two nodes, giving the members of the relation,
      * the parent and the child.
      *
      * @param parentId
      *            Id of the parent node.
      * @param childId
      *            Id of the child node.
      * @throws AbstractZemucanException
      *             if the parent or the child does not exist in the set of
      *             nodes. Or if the state of the graph is invalid. Or when
      *             trying to remove an invalid relation between two nodes. If a
      *             parameter is null.
      */
     private void removeRelation(final String parentId, final String childId)
             throws AbstractZemucanException {
         Graph.LOGGER.debug(
                 "Removing relation in graph '{}' between '{}' and '{}'", //$NON-NLS-1$
                 new String[] { this.name, parentId, childId });
 
         if (parentId == null) {
             throw new ParameterNullException("parentId"); //$NON-NLS-1$
         }
         if (childId == null) {
             throw new ParameterNullException("childId"); //$NON-NLS-1$
         }
         if (this.graphState.equals(GraphState.FirstPhase)) {
             throw new InvalidGraphStateException(this.graphState,
                     GraphState.SecondPhase);
         }
         if (this.graphState.equals(GraphState.Validated)) {
             this.graphState = GraphState.SecondPhase;
         }
 
         final AbstractGraphNode parent = this.nodes.get(this.name + ':'
                 + parentId);
         if (parent == null) {
             throw new NotExistingNodeException(parentId);
         }
 
         // Retrieves the child and established the relation.
         final AbstractGraphNode childNode = this.nodes.get(this.name + ':'
                 + childId);
         if (childNode == null) {
             throw new NotExistingChildNodeException(parentId, childId);
         }
 
         parent.removeChild(childNode);
         childNode.removeParent(parent);
     }
 
     /**
      * Process the graph. Checks the graph structure as part of the finalization
      * of the second phase. Optionally, it adds the extra nodes, depending on
      * the parameter when creating the graph, and finally it returns the
      * startingNode.
      * <p>
      * Checks that there is not nodes that references to StartingNode. Also,
      * that EndingNode does not reference any node.
      *
      * @return The startingNode of the graph.
      * @throws AbstractZemucanException
      *             When a node is detected that references the StartingNode. Or
      *             when a node is detected that if referenced by the EndingNode.
      *             Or if a node does not come from StartingNode. Or if a node
      *             does not go to EndingNode. Or if the first phase has not
      *             finished. Or if the graph is in an invalid state.
      */
     public final StartingNode/* ! */secondPhaseFinished()
             throws AbstractZemucanException {
         if (this.graphState.equals(GraphState.FirstPhase)) {
             throw new InvalidGraphStateException(this.graphState,
                     GraphState.SecondPhase);
         }
 
         // Reset value of nodes.
         for (final AbstractGraphNode node : this.nodes.values()) {
             node.setComeFromStartingNode(false);
             node.setGoToEndingNode(false);
         }
 
         assert this.checkNoParentsForStartingNode();
 
         if (this.startingNode == null) {
             throw new StartingNodeNotDefinedException();
         }
         Graph.goForward(this.startingNode);
 
         if (this.endingNode == null) {
             throw new EndingNodeNotDefinedException();
         }
         Graph.goBackward(this.endingNode);
 
         for (final AbstractGraphNode node : this.nodes.values()) {
             if (!node.isComeFromStartingNode()) {
                 throw new NodeNotComesFromStartingNodeException(node.getId());
             } else if (!node.isGoToEndingNode()) {
                 throw new NodeNotGoesToEndingNodeException(node.getId());
             }
         }
 
         this.checkDuplicates();
 
         if ((this.startingNode.getChildren().size() == 1)
                 && this.startingNode.getChildren().get(0) instanceof EndingNode) {
             throw new EmptyGrammarException();
         }
 
         Graph.LOGGER.info("'{}' - Second phase finished.", this.name); //$NON-NLS-1$
 
         this.graphState = GraphState.Validated;
 
         assert this.startingNode != null;
         return this.startingNode;
     }
 
     /**
      * Simplify the graph, by merging nodes that represents the same tokens and
      * replacing the next nodes.
      *
      * @throws AbstractZemucanException
      *             If there is a problem add when merging the nodes or replacing
      *             the next nodes.
      */
     public final void simplifyGraph() throws AbstractZemucanException {
         Graph.LOGGER.debug("-> Simplyfing graph");
 
         // Replaces the NextNode nodes.
         Graph.LOGGER.debug("-> Remplacing next nodes");
         Iterator<AbstractGraphNode> ite = this.nodes.values().iterator();
         while (ite.hasNext()) {
             final AbstractGraphNode parentNode = ite.next();
             Graph.LOGGER.debug("parent {}", parentNode.getId());
             final List<AbstractGraphNode> children = parentNode.getChildren();
 
             if (!(parentNode instanceof EndingNode) && children.size() == 0) {
                 // ERROR
                 throw new RuntimeException("Node without children.");
             }
             int size = children.size();
             for (int i = 0; i < size; i++) {
                 final AbstractGraphNode childNode = children.get(i);
                 Graph.LOGGER.debug("child   {}", childNode.getId());
                 if (childNode instanceof NextNode) {
                     final List<AbstractGraphNode> grandChildren = childNode
                             .getChildren();
                     // Adds a relation between parent and grand child.
                     for (int j = 0; j < grandChildren.size(); j++) {
                         final AbstractGraphNode grandChildNode = grandChildren
                                 .get(j);
                         this.addRelation(parentNode, grandChildNode);
                         this.removeRelation(parentNode, childNode);
                     }
                     // Restart the iterator.
                     ite = this.nodes.values().iterator();
                     i = children.size();
                     Graph.LOGGER.debug("Restarted");
                 }
             }
         }
         // Removes the next nodes and their relations.
         Graph.LOGGER.debug("-> Removing next nodes and their iterations");
         final Object[] set = this.nodes.keySet().toArray();
         for (int i = 0; i < set.length; i++) {
             final String key = (String) set[i];
             final AbstractGraphNode node = this.nodes.get(key);
             if (node instanceof NextNode) {
                 final List<AbstractGraphNode> children = node.getChildren();
                 for (int j = 0; j < children.size(); j++) {
                     final AbstractGraphNode childNode = children.get(j);
                     this.removeRelation(node, childNode);
                 }
                 this.nodes.remove(key);
             }
         }
 
         // Fusions the common nodes.
         Graph.LOGGER.debug("-> Fusionning common nodes");
         Iterator<AbstractGraphNode> it = this.nodes.values().iterator();
         while (it.hasNext()) {
             final AbstractGraphNode node = it.next();
             if (Graph.checkChildren(node)) {
                 // If there is a fusion, the iterator has to restart.
                 it = this.nodes.values().iterator();
             }
         }
 
         // Remove empty nodes.
         Graph.LOGGER.debug("-> Removing empty nodes");
         final Object[] keys = this.nodes.keySet().toArray();
         for (final Object key2 : keys) {
             final String key = (String) key2;
 
             final AbstractGraphNode node = this.nodes.get(key);
 
             int childrenSize = node.getChildren().size();
             int parentsSize = node.getParents().size();
             Graph.LOGGER.debug("node {}, parents {} children {}", new Object[] {
                     node.getId(), parentsSize, childrenSize });
             if ((childrenSize == 0) && (parentsSize == 0)) {
                 this.nodes.remove(key);
             }
         }
     }
 
     /*
      * (non-Javadoc)
      * @see java.lang.Object#toString()
      */
     @Override
     public final String toString() {
         String res = this.name + ":[" + this.graphState + '-'; //$NON-NLS-1$
         if (this.extraNodes) {
             res += "WithExtraNodes"; //$NON-NLS-1$
         } else {
             res += "WithoutExtraNodes"; //$NON-NLS-1$
         }
         res += "{" + this.startingNode + '-' + this.endingNode //$NON-NLS-1$
                 + "}(" + this.nodes.size() + ":\n"; //$NON-NLS-1$ //$NON-NLS-2$
         final List<String> children = new ArrayList<String>();
         children.addAll(this.nodes.keySet());
         Collections.sort(children);
         for (int i = 0; i < children.size(); i++) {
             final String key = children.get(i);
             final AbstractGraphNode node = this.nodes.get(key);
             String nodeString;
             if (node instanceof TextualGraphNode) {
                 nodeString = key + '-'
                         + ((TextualGraphNode) this.nodes.get(key)).getName()
                         + '\n';
             } else {
                 // TODO v1.0 omitir el id o la key, pero no ambas
                 nodeString = key + '-' + this.nodes.get(key).getId() + '\n';
             }
             res += nodeString;
         }
         res += ')';
         res += ']';
         return res;
     }
 }