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