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}