001/*
002MIT License
003
004Copyright (c) 2020 earlygrey
005
006Permission is hereby granted, free of charge, to any person obtaining a copy
007of this software and associated documentation files (the "Software"), to deal
008in the Software without restriction, including without limitation the rights
009to use, copy, modify, merge, publish, distribute, sublicense, and/or sell
010copies of the Software, and to permit persons to whom the Software is
011furnished to do so, subject to the following conditions:
012
013The above copyright notice and this permission notice shall be included in all
014copies or substantial portions of the Software.
015
016THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND, EXPRESS OR
017IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF MERCHANTABILITY,
018FITNESS FOR A PARTICULAR PURPOSE AND NONINFRINGEMENT. IN NO EVENT SHALL THE
019AUTHORS OR COPYRIGHT HOLDERS BE LIABLE FOR ANY CLAIM, DAMAGES OR OTHER
020LIABILITY, WHETHER IN AN ACTION OF CONTRACT, TORT OR OTHERWISE, ARISING FROM,
021OUT OF OR IN CONNECTION WITH THE SOFTWARE OR THE USE OR OTHER DEALINGS IN THE
022SOFTWARE.
023 */
024package squidpony.squidai.graph;
025
026import java.io.Serializable;
027import java.util.Collection;
028
029/**
030 * A kind of {@link Graph} where all connections between vertices are two-way and have equal cost for traveling A to B
031 * or B to A.
032 * @see DefaultGraph The DefaultGraph class supports the common case where V is Coord and all costs are 1.
033 * @param <V> the vertex type; often {@link squidpony.squidmath.Coord}
034 * @author earlygrey
035 */
036public class UndirectedGraph<V> extends Graph<V> implements Serializable {
037    private static final long serialVersionUID = 1L;
038
039    UndirectedGraphAlgorithms<V> algorithms;
040
041    //================================================================================
042    // Constructors
043    //================================================================================
044
045    public UndirectedGraph() {
046        super();
047        algorithms = new UndirectedGraphAlgorithms<>(this);
048    }
049
050    public UndirectedGraph(Collection<V> vertices) {
051        super(vertices);
052        algorithms = new UndirectedGraphAlgorithms<>(this);
053    }
054
055
056    //================================================================================
057    // Graph building
058    //================================================================================
059
060    @Override
061    protected Connection<V> obtainEdge() {
062        return new Connection.UndirectedConnection<V>();
063    }
064
065    @Override
066    protected Connection<V> addConnection(Node<V> a, Node<V> b, float weight) {
067        Connection<V> e = a.addEdge(b, weight);
068        edgeMap.put(e, e);
069        b.addEdge(a, weight);
070        return e;
071    }
072
073    @Override
074    protected boolean removeConnection(Node<V> a, Node<V> b) {
075        Connection<V> e = a.removeEdge(b);
076        if (e == null) return false;
077        b.removeEdge(a);
078        edgeMap.remove(e);
079        return true;
080    }
081
082    @Override
083    protected Connection<V> getEdge(Node<V> a, Node<V> b) {
084        Connection<V> edge = a.getEdge(b);
085        if (edge == null) return null;
086        edge = edgeMap.get(edge);
087        return edge;
088    }
089
090
091    //================================================================================
092    // Superclass implementations
093    //================================================================================
094
095    @Override
096    public boolean isDirected() {
097        return false;
098    }
099
100    @Override
101    protected Graph<V> createNew() {
102        return new UndirectedGraph<>();
103    }
104
105    @Override
106    public UndirectedGraphAlgorithms<V> algorithms() {
107        return algorithms;
108    }
109}