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}