001package org.clafer.graph;
002
003import java.util.Collection;
004import java.util.HashMap;
005import java.util.Map;
006
007/**
008 * A graph where every data is mapped to exactly one node.
009 * <p>
010 * There exists a injection from the data to the vertices. This graph maintains
011 * a mapping from data to its vertex. New vertices are created on-the-fly.
012 * </p>
013 * <p>For example, a 2-cycle graph:
014 * <pre>
015 * KeyGraph&lt;Character&gt;graph = new KeyGraph&lt;Character&gt;();
016 * graph.getVertex('a').addNeighbour(graph.getVertex('b'));
017 * graph.getVertex('b').addNeighbour(graph.getVertex('a'));
018 * </pre>
019 * </p>
020 *
021 * @param <V> the type of the data
022 * @author jimmy
023 */
024public class KeyGraph<V> implements Graph<V> {
025
026    private final Map<V, Vertex<V>> vertices = new HashMap<>();
027
028    /**
029     * Returns the vertex associated with the data. The data class should
030     * implement equals and hashCode.
031     *
032     * @param data the data
033     * @return the vertex containing the data
034     * @see Object#equals(Object)
035     * @see Object#hashCode()
036     */
037    public Vertex<V> getVertex(V data) {
038        Vertex<V> vertex = vertices.get(data);
039        if (vertex == null) {
040            vertex = new Vertex<>(data);
041            vertices.put(data, vertex);
042        }
043        return vertex;
044    }
045
046    public void addEdge(V from, V to) {
047        getVertex(from).addNeighbour(getVertex(to));
048    }
049
050    public void addUndirectedEdge(V from, V to) {
051        Vertex<V> fromV = getVertex(from);
052        Vertex<V> toV = getVertex(to);
053        fromV.addNeighbour(toV);
054        toV.addNeighbour(fromV);
055    }
056
057    /**
058     * {@inheritDoc}
059     */
060    @Override
061    public Collection<Vertex<V>> getVertices() {
062        return vertices.values();
063    }
064
065    @Override
066    public String toString() {
067        return vertices.toString();
068    }
069}