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}