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;
018
019import java.util.ArrayList;
020import java.util.Collection;
021import java.util.Collections;
022import java.util.List;
023
024import net.automatalib.commons.util.mappings.Mapping;
025import net.automatalib.commons.util.mappings.MutableMapping;
026import net.automatalib.graphs.BidirectionalGraph;
027import net.automatalib.graphs.Graph;
028import net.automatalib.graphs.IndefiniteGraph;
029import net.automatalib.graphs.UniversalIndefiniteGraph;
030import net.automatalib.util.graphs.traversal.GraphTraversal;
031
032
033public abstract class Graphs {
034        
035                        
036        public static <N,E> Mapping<N,Collection<E>> incomingEdges(final Graph<N,E> graph) {
037                if(graph instanceof BidirectionalGraph)
038                        return new InEdgesMapping<N,E>((BidirectionalGraph<N,E>)graph);
039                
040                MutableMapping<N,Collection<E>> inEdgesMapping
041                        = graph.createStaticNodeMapping();
042                
043                for(N node : graph) {
044                        Collection<E> outEdges = graph.getOutgoingEdges(node);
045                        if(outEdges == null)
046                                continue;
047                        for(E e : outEdges) {
048                                N tgt = graph.getTarget(e);
049                                Collection<E> inEdges = inEdgesMapping.get(tgt);
050                                if(inEdges == null) {
051                                        inEdges = new ArrayList<E>();
052                                        inEdgesMapping.put(tgt, inEdges);
053                                }
054                                inEdges.add(e);
055                        }
056                }
057                
058                return inEdgesMapping;
059        }
060        
061        public static <N,E> List<E> findShortestPath(final IndefiniteGraph<N, E> graph, int limit, N start, Collection<? extends N> targets) {
062                FindShortestPathVisitor<N, E> vis = new FindShortestPathVisitor<N, E>(graph, targets);
063                
064                GraphTraversal.breadthFirst(graph, limit, Collections.singleton(start), vis);
065                
066                if(!vis.wasSuccessful())
067                        return null;
068                
069                return vis.getTargetPath().getSecond();
070        }
071        
072        
073        public static <N,NP> Mapping<N,NP> nodeProperties(final UniversalIndefiniteGraph<N, ?, NP, ?> graph) {
074                return new Mapping<N,NP>() {
075                        @Override
076                        public NP get(N elem) {
077                                return graph.getNodeProperty(elem);
078                        }
079                };
080        }
081        
082        public static <E,EP> Mapping<E,EP> edgeProperties(final UniversalIndefiniteGraph<?, E, ?, EP> graph) {
083                return new Mapping<E,EP>() {
084                        @Override
085                        public EP get(E elem) {
086                                return graph.getEdgeProperty(elem);
087                        }
088                };
089        }
090        
091        private Graphs() {}
092}