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 */
020package org.sonar.graph;
021
022import java.util.ArrayList;
023import java.util.Collection;
024import java.util.HashMap;
025import java.util.HashSet;
026import java.util.List;
027import java.util.Map;
028import java.util.Set;
029
030public 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}