001 /*
002 * Sonar, open source software quality management tool.
003 * Copyright (C) 2008-2011 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 }