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}