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.algorithms.graph.scc;
018
019import java.util.ArrayList;
020import java.util.List;
021
022import net.automatalib.commons.util.Holder;
023import net.automatalib.commons.util.mappings.MutableMapping;
024import net.automatalib.graphs.Graph;
025import net.automatalib.util.graphs.traversal.GraphTraversalAction;
026import net.automatalib.util.graphs.traversal.GraphTraversalVisitor;
027
028
029/**
030 * Depth-first traversal visitor realizing Tarjan's algorithm for finding all
031 * strongly-connected components (SCCs) in a graph.
032 * 
033 * @author Malte Isberner <malte.isberner@gmail.com>
034 *
035 * @param <N> node class
036 * @param <E> edge class
037 */
038public class TarjanSCCVisitor<N, E> implements
039                GraphTraversalVisitor<N, E, TarjanSCCRecord> {
040        
041        private static final int NODE_FINISHED = -1;
042        
043        private int counter = 0;
044        private final MutableMapping<N,TarjanSCCRecord> records;
045        private final List<N> currentScc = new ArrayList<>();
046        private final SCCListener<N> listener;
047        
048        /**
049         * Constructor.
050         * @param graph the graph
051         * @param listener the SCC listener to use, <b>may not be null</b>
052         */
053        public TarjanSCCVisitor(Graph<N,E> graph, SCCListener<N> listener) {
054                records = graph.createStaticNodeMapping();
055                this.listener = listener;
056        }
057        
058        /*
059         * (non-Javadoc)
060         * @see net.automatalib.util.graphs.traversal.GraphTraversalVisitor#processInitial(java.lang.Object, net.automatalib.commons.util.Holder)
061         */
062        @Override
063        public GraphTraversalAction processInitial(N initialNode, Holder<TarjanSCCRecord> outData) {
064                outData.value = createRecord();
065                return GraphTraversalAction.EXPLORE;
066        }
067        
068        /*
069         * (non-Javadoc)
070         * @see net.automatalib.util.graphs.traversal.GraphTraversalVisitor#startExploration(java.lang.Object, java.lang.Object)
071         */
072        @Override
073        public boolean startExploration(N node, TarjanSCCRecord data) {
074                records.put(node, data);
075                return true;
076        }
077        
078        /*
079         * (non-Javadoc)
080         * @see net.automatalib.util.graphs.traversal.GraphTraversalVisitor#finishExploration(java.lang.Object, java.lang.Object)
081         */
082        @Override
083        public void finishExploration(N node, TarjanSCCRecord data) {
084                currentScc.add(node);
085                if(data.lowLink == data.number) {
086                        listener.foundSCC(currentScc);
087                        currentScc.clear();
088                }
089                data.lowLink = NODE_FINISHED;
090        }
091        
092        /*
093         * (non-Javadoc)
094         * @see net.automatalib.util.graphs.traversal.GraphTraversalVisitor#processEdge(java.lang.Object, java.lang.Object, java.lang.Object, java.lang.Object, net.automatalib.commons.util.Holder)
095         */
096        @Override
097        public GraphTraversalAction processEdge(N srcNode,
098                        TarjanSCCRecord srcData, E edge, N tgtNode, Holder<TarjanSCCRecord> dataHolder) {
099                TarjanSCCRecord rec = records.get(tgtNode);
100                if(rec == null) {
101                        rec = createRecord();
102                        dataHolder.value = rec;
103                        return GraphTraversalAction.EXPLORE;
104                }
105                
106                if(rec.lowLink != NODE_FINISHED) {
107                        int tgtNum = rec.number;
108                        if(tgtNum < srcData.lowLink)
109                                srcData.lowLink = tgtNum;
110                }
111                return GraphTraversalAction.IGNORE;
112        }
113        
114        /*
115         * (non-Javadoc)
116         * @see net.automatalib.util.graphs.traversal.GraphTraversalVisitor#backtrackEdge(java.lang.Object, java.lang.Object, java.lang.Object, java.lang.Object, java.lang.Object)
117         */
118        @Override
119        public void backtrackEdge(N srcNode, TarjanSCCRecord srcData, E edge,
120                        N tgtNode, TarjanSCCRecord tgtData) {
121                int tgtLl = tgtData.lowLink;
122                if(tgtLl < srcData.lowLink)
123                        srcData.lowLink = tgtLl;
124        }
125        
126        public boolean hasVisited(N node) {
127                return (records.get(node) != null);
128        }
129
130        private TarjanSCCRecord createRecord() {
131                return new TarjanSCCRecord(counter++);
132        }
133        
134}