001 /* 002 * Sonar, open source software quality management tool. 003 * Copyright (C) 2008-2012 SonarSource 004 * mailto:contact AT sonarsource DOT com 005 * 006 * Sonar is free software; you can redistribute it and/or 007 * modify it under the terms of the GNU Lesser General Public 008 * License as published by the Free Software Foundation; either 009 * version 3 of the License, or (at your option) any later version. 010 * 011 * Sonar is distributed in the hope that it will be useful, 012 * but WITHOUT ANY WARRANTY; without even the implied warranty of 013 * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU 014 * Lesser General Public License for more details. 015 * 016 * You should have received a copy of the GNU Lesser General Public 017 * License along with Sonar; if not, write to the Free Software 018 * Foundation, Inc., 51 Franklin Street, Fifth Floor, Boston, MA 02 019 */ 020 package org.sonar.graph; 021 022 import java.util.ArrayList; 023 import java.util.Collection; 024 import java.util.HashMap; 025 import java.util.HashSet; 026 import java.util.List; 027 import java.util.Map; 028 import java.util.Set; 029 030 public class DirectedGraph<V, E extends Edge<V>> implements DirectedGraphAccessor<V, E> { 031 032 private EdgeFactory<V, E> edgeFactory; 033 private Map<V, Map<V, E>> outgoingEdgesByVertex = new HashMap<V, Map<V, E>>(); 034 private Map<V, Map<V, E>> incomingEdgesByVertex = new HashMap<V, Map<V, E>>(); 035 private Set<V> vertices = new HashSet<V>(); 036 037 public DirectedGraph() { 038 } 039 040 public DirectedGraph(EdgeFactory<V, E> edgeFactory) { 041 this.edgeFactory = edgeFactory; 042 } 043 044 public static DirectedGraph<String, StringEdge> createStringDirectedGraph() { 045 return new DirectedGraph<String, StringEdge>(new StringEdgeFactory()); 046 } 047 048 public DirectedGraph<V, E> addEdge(V from, V to) { 049 checkEdgeFacory(); 050 E edge = edgeFactory.createEdge(from, to); 051 return addEdge(edge); 052 } 053 054 public DirectedGraph<V, E> addEdge(V from, V to, int weight) { 055 checkEdgeFacory(); 056 E edge = edgeFactory.createEdge(from, to, weight); 057 return addEdge(edge); 058 } 059 060 private void checkEdgeFacory() { 061 if (edgeFactory == null) { 062 throw new IllegalStateException( 063 "EdgeFactory<V, E> has not been defined. Please use the 'public E addEdge(V from, V to, E edge)' method."); 064 } 065 } 066 067 public DirectedGraph<V, E> addEdge(E edge) { 068 addEdgeToMap(edge.getFrom(), edge.getTo(), edge, outgoingEdgesByVertex); 069 addEdgeToMap(edge.getTo(), edge.getFrom(), edge, incomingEdgesByVertex); 070 vertices.add(edge.getFrom()); 071 vertices.add(edge.getTo()); 072 return this; 073 } 074 075 private void addEdgeToMap(V vertexKey1, V vertexKey2, E edge, Map<V, Map<V, E>> edgesByVertex) { 076 Map<V, E> edges = edgesByVertex.get(vertexKey1); 077 if (edges == null) { 078 edges = new HashMap<V, E>(); 079 edgesByVertex.put(vertexKey1, edges); 080 } 081 if (edges.containsKey(vertexKey2)) { 082 throw new IllegalStateException("The graph already contains the edge : " + edge); 083 } 084 edges.put(vertexKey2, edge); 085 } 086 087 public E getEdge(V from, V to) { 088 Map<V, E> outgoingEdgesFrom = outgoingEdgesByVertex.get(from); 089 if (outgoingEdgesFrom == null) { 090 return null; 091 } else { 092 return outgoingEdgesFrom.get(to); 093 } 094 } 095 096 public boolean hasEdge(V from, V to) { 097 Map<V, E> outgoingEdges = outgoingEdgesByVertex.get(from); 098 if (outgoingEdges == null) { 099 return false; 100 } 101 return outgoingEdges.containsKey(to); 102 } 103 104 public void addVertex(V vertex) { 105 vertices.add(vertex); 106 } 107 108 public void addVertices(Collection<V> vertices) { 109 for (V vertex : vertices) { 110 addVertex(vertex); 111 } 112 } 113 114 public Set<V> getVertices() { 115 return vertices; 116 } 117 118 public List<E> getEdges(Collection<V> vertices) { 119 List<E> result = new ArrayList<E>(); 120 for (V vertice : vertices) { 121 Collection<E> outgoingEdges = getOutgoingEdges(vertice); 122 if (outgoingEdges != null) { 123 result.addAll(outgoingEdges); 124 } 125 } 126 return result; 127 } 128 129 public Collection<E> getOutgoingEdges(V from) { 130 Map<V, E> outgoingEdges = outgoingEdgesByVertex.get(from); 131 if (outgoingEdges == null) { 132 return new HashSet<E>(); 133 } 134 return outgoingEdges.values(); 135 } 136 137 public Collection<E> getIncomingEdges(V to) { 138 Map<V, E> incomingEdges = incomingEdgesByVertex.get(to); 139 if (incomingEdges == null) { 140 return new HashSet<E>(); 141 } 142 return incomingEdges.values(); 143 } 144 }