/*

  * Created on Apr 1, 2007

  *

  * Copyright (c) 2007, the JUNG Project and the Regents of the University 

  * of California

  * All rights reserved.

  *

  * This software is open-source under the BSD license; see either

  * "license.txt" or

  * http://jung.sourceforge.net/license.txt for a description.

  */

 package edu.uci.ics.jung.graph;

 import java.util.ArrayList;

 import java.util.Collection;

 import java.util.Collections;

 import java.util.HashMap;

 import java.util.Map;

 import org.apache.commons.collections15.Factory;

 import edu.uci.ics.jung.graph.util.EdgeType;

 import edu.uci.ics.jung.graph.util.Pair;

 /**

  * An implementation of <code>UndirectedGraph</code> that is suitable

  * for sparse graphs.

  */

 @SuppressWarnings("serial")

 public class UndirectedSparseGraph<V, E> extends AbstractTypedGraph<V, E>

         implements UndirectedGraph<V, E>

 {

     /**

      * Returns a {@code Factory} that creates an instance of this graph type.

      * @param <V> the vertex type for the graph factory

      * @param <E> the edge type for the graph factory

      */

     public static <V,E> Factory<UndirectedGraph<V,E>> getFactory() {

         return new Factory<UndirectedGraph<V,E>> () {

             public UndirectedGraph<V,E> create() {

                 return new UndirectedSparseGraph<V,E>();

             }

         };

     }

     protected Map<V, Map<V,E>> vertices; // Map of vertices to adjacency maps of vertices to incident edges

     protected Map<E, Pair<V>> edges;    // Map of edges to incident vertex sets

     /**

      * Creates an instance.

      */

     public UndirectedSparseGraph() {

             super(EdgeType.UNDIRECTED);

         vertices = new HashMap<V, Map<V,E>>();

         edges = new HashMap<E, Pair<V>>();

     }

     @Override

     public boolean addEdge(E edge, Pair<? extends V> endpoints, EdgeType edgeType)

     {

             this.validateEdgeType(edgeType);

         Pair<V> new_endpoints = getValidatedEndpoints(edge, endpoints);

         if (new_endpoints == null)

             return false;

         V v1 = new_endpoints.getFirst();

         V v2 = new_endpoints.getSecond();

         if (findEdge(v1, v2) != null)

             return false;

         edges.put(edge, new_endpoints);

         if (!vertices.containsKey(v1))

             this.addVertex(v1);

         if (!vertices.containsKey(v2))

             this.addVertex(v2);

         // map v1 to <v2, edge> and vice versa

         vertices.get(v1).put(v2, edge);

         vertices.get(v2).put(v1, edge);

         return true;

     }

     public Collection<E> getInEdges(V vertex)

     {

         return this.getIncidentEdges(vertex);

     }

     public Collection<E> getOutEdges(V vertex)

     {

         return this.getIncidentEdges(vertex);

     }

     public Collection<V> getPredecessors(V vertex)

     {

         return this.getNeighbors(vertex);

     }

     public Collection<V> getSuccessors(V vertex)

     {

         return this.getNeighbors(vertex);

     }

     @Override

     public E findEdge(V v1, V v2)

     {

         if (!containsVertex(v1) || !containsVertex(v2))

             return null;

         return vertices.get(v1).get(v2);

     }

     @Override

     public Collection<E> findEdgeSet(V v1, V v2)

     {

         if (!containsVertex(v1) || !containsVertex(v2))

             return null;

         ArrayList<E> edge_collection = new ArrayList<E>(1);

 //        if (!containsVertex(v1) || !containsVertex(v2))

 //            return edge_collection;

         E e = findEdge(v1, v2);

         if (e == null)

             return edge_collection;

         edge_collection.add(e);

         return edge_collection;

     }

     public Pair<V> getEndpoints(E edge)

     {

         return edges.get(edge);

     }

     public V getSource(E directed_edge)

     {

         return null;

     }

     public V getDest(E directed_edge)

     {

         return null;

     }

     public boolean isSource(V vertex, E edge)

     {

         return false;

     }

     public boolean isDest(V vertex, E edge)

     {

         return false;

     }

     public Collection<E> getEdges()

     {

         return Collections.unmodifiableCollection(edges.keySet());

     }

     public Collection<V> getVertices()

     {

         return Collections.unmodifiableCollection(vertices.keySet());

     }

     public boolean containsVertex(V vertex)

     {

         return vertices.containsKey(vertex);

     }

     public boolean containsEdge(E edge)

     {

         return edges.containsKey(edge);

     }

     public int getEdgeCount()

     {

         return edges.size();

     }

     public int getVertexCount()

     {

         return vertices.size();

     }

     public Collection<V> getNeighbors(V vertex)

     {

         if (!containsVertex(vertex))

             return null;

         return Collections.unmodifiableCollection(vertices.get(vertex).keySet());

     }

     public Collection<E> getIncidentEdges(V vertex)

     {

         if (!containsVertex(vertex))

             return null;

         return Collections.unmodifiableCollection(vertices.get(vertex).values());

     }

     public boolean addVertex(V vertex)

     {

         if(vertex == null) {

             throw new IllegalArgumentException("vertex may not be null");

         }

         if (!containsVertex(vertex)) {

             vertices.put(vertex, new HashMap<V,E>());

             return true;

         } else {

             return false;

         }

     }

     public boolean removeVertex(V vertex)

     {

         if (!containsVertex(vertex))

             return false;

         // iterate over copy of incident edge collection

         for (E edge : new ArrayList<E>(vertices.get(vertex).values()))

             removeEdge(edge);

         vertices.remove(vertex);

         return true;

     }

     public boolean removeEdge(E edge)

     {

         if (!containsEdge(edge))

             return false;

         Pair<V> endpoints = getEndpoints(edge);

         V v1 = endpoints.getFirst();

         V v2 = endpoints.getSecond();

         // remove incident vertices from each others' adjacency maps

         vertices.get(v1).remove(v2);

         vertices.get(v2).remove(v1);

         edges.remove(edge);

         return true;

     }

 }