001/* Copyright (C) 2013 TU Dortmund
002 * This file is part of AutomataLib, http://www.automatalib.net/.
003 * 
004 * AutomataLib is free software; you can redistribute it and/or
005 * modify it under the terms of the GNU Lesser General Public
006 * License version 3.0 as published by the Free Software Foundation.
007 * 
008 * AutomataLib is distributed in the hope that it will be useful,
009 * but WITHOUT ANY WARRANTY; without even the implied warranty of
010 * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the GNU
011 * Lesser General Public License for more details.
012 * 
013 * You should have received a copy of the GNU Lesser General Public
014 * License along with AutomataLib; if not, see
015 * http://www.gnu.de/documents/lgpl.en.html.
016 */
017package net.automatalib.util.graphs.traversal;
018
019/**
020 * A base implementation of a {@link DFSVisitor}.
021 * 
022 * @author Malte Isberner <malte.isberner@gmail.com>
023 *
024 * @param <N> node class
025 * @param <E> edge class
026 * @param <D> user data class
027 */
028public class BaseDFSVisitor<N, E, D> implements DFSVisitor<N, E, D> {
029
030        /*
031         * (non-Javadoc)
032         * @see net.automatalib.util.graphs.traversal.DFSVisitor#exploreInitial(java.lang.Object)
033         */
034        @Override
035        public D initialize(N node) {
036                return null;
037        }
038        
039        /*
040         * (non-Javadoc)
041         * @see net.automatalib.util.graphs.traversal.DFSVisitor#explore(java.lang.Object, java.lang.Object)
042         */
043        @Override
044        public void explore(N node, D data) {
045        }
046        
047        /**
048         * Most general edge handler. In their default implementations, the following methods
049         * resort to calling this method:
050         * <ul>
051         * <li>{@link #treeEdge(Object, Object, Object, Object)}
052         * <li>{@link #nontreeEdge(Object, Object, Object, Object, Object)}
053         * </ul>
054         * Provided that the latter is not overwritten, the following methods
055         * resort to this method indirectly in their default implementation:
056         * <ul>
057         * <li>{@link #grayTarget(Object, Object, Object, Object, Object)}
058         * <li>{@link #blackTarget(Object, Object, Object, Object, Object)}
059         * </ul>
060         * 
061         * @param srcNode the source node
062         * @param srcData the data associated with the source node
063         * @param edge the edge that is being processed
064         * @param tgtNode the target node of this edge
065         */
066        public void edge(N srcNode, D srcData, E edge, N tgtNode) {
067        }
068        
069        public void nontreeEdge(N srcNode, D srcData, E edge, N tgtNode, D tgtData) {
070                edge(srcNode, srcData, edge, tgtNode);
071        }
072
073        public void grayTarget(N srcNode, D srcData, E edge, N tgtNode, D tgtData) {
074                nontreeEdge(srcNode, srcData, edge, tgtNode, tgtData);
075        }
076        
077        public void blackTarget(N srcNode, D srcData, E edge, N tgtNode, D tgtData) {
078                nontreeEdge(srcNode, srcData, edge, tgtNode, tgtData);
079        }
080
081        /*
082         * (non-Javadoc)
083         * @see net.automatalib.util.graphs.traversal.DFSVisitor#treeEdge(java.lang.Object, java.lang.Object, java.lang.Object, java.lang.Object)
084         */
085        @Override
086        public D treeEdge(N srcNode, D srcData, E edge, N tgtNode) {
087                edge(srcNode, srcData, edge, tgtNode);
088                return null;
089        }
090
091        /*
092         * (non-Javadoc)
093         * @see net.automatalib.util.graphs.traversal.DFSVisitor#backEdge(java.lang.Object, java.lang.Object, java.lang.Object, java.lang.Object, java.lang.Object)
094         */
095        @Override
096        public void backEdge(N srcNode, D srcData, E edge, N tgtNode, D tgtData) {
097                grayTarget(srcNode, srcData, edge, tgtNode, tgtData);
098        }
099
100        /*
101         * (non-Javadoc)
102         * @see net.automatalib.util.graphs.traversal.DFSVisitor#crossEdge(java.lang.Object, java.lang.Object, java.lang.Object, java.lang.Object, java.lang.Object)
103         */
104        @Override
105        public void crossEdge(N srcNode, D srcData, E edge, N tgtNode, D tgtData) {
106                blackTarget(srcNode, srcData, edge, tgtNode, tgtData);
107        }
108
109        /*
110         * (non-Javadoc)
111         * @see net.automatalib.util.graphs.traversal.DFSVisitor#forwardEdge(java.lang.Object, java.lang.Object, java.lang.Object, java.lang.Object, java.lang.Object)
112         */
113        @Override
114        public void forwardEdge(N srcNode, D srcData, E edge, N tgtNode, D tgtData) {
115                blackTarget(srcNode, srcData, edge, tgtNode, tgtData);
116        }
117
118        /*
119         * (non-Javadoc)
120         * @see net.automatalib.util.graphs.traversal.DFSVisitor#finish(java.lang.Object, java.lang.Object)
121         */
122        @Override
123        public void finish(N node, D data) {
124        }
125
126        @Override
127        public void backtrackEdge(N srcNode, D srcDate, E edge, N tgtNode, D tgtData) {
128        }
129}