1
\$\begingroup\$

There is a Graph implementation. I'm using Set to store unique Edges and Map to store Vertices and their associated edges. Assume Vertex and Edge class has been defined somewhere else implementing hashcode() and equals() working fine.

public class Graph
{
    static class Vertex {}

    static class Edge {}

    private Map<Vertex, Set<Edge>> vertexSetMap;
    private Set<Edge> edgeSet;

    public Graph()
    {
        edgeSet = new LinkedHashSet<>();
        vertexSetMap = new LinkedHashMap<>();
    }

    public boolean addVertex(Vertex vertex)
    {
        if(!vertexSetMap.containsKey(vertex))
        {
            vertexSetMap.put(vertex, new LinkedHashSet <>());
            return true;
        }
        return false;
    }

    public boolean addEdge(Vertex v1, Vertex v2, Edge edge)
    {
        if(edgeSet.add(edge))
        {
            vertexSetMap.get(v1).add(edge);
            vertexSetMap.get(v2).add(edge);
            return true;
        }
        return false;
    }

    public Set<Edge> getEdges(Vertex vertex)
    {
        return vertexSetMap.get(vertex);
    }

    public Set<Vertex> getNeighborsOf(Vertex vertex)
    {
        Set<Vertex> neighbors = new LinkedHashSet <>();
        for(Edge edge : vertexSetMap.get(vertex))
        {
            Vertex v1 = edge.getVertex1();
            Vertex v2 = edge.getVertex2();
            if(v1.equals(vertex)) neighbors.add(v2);
            else neighbors.add(v1);
        }
        return neighbors;
    }

    public void removeVertex(Vertex vertex)
    {
        Set<Edge> deleteEdges = getEdges(vertex);
        vertexSetMap.remove(vertex);
        edgeSet.removeAll(deleteEdges);
        vertexSetMap.keySet().forEach(vertex1 -> 
        vertexSetMap.get(vertex1).removeAll(deleteEdges));
    }

    public void removeEdge(Edge edge)
    {
        edgeSet.remove(edge);
        Vertex v1 = edge.getVertex1();
        Vertex v2 = edge.getVertex2();
        vertexSetMap.get(v1).remove(edge);
        vertexSetMap.get(v2).remove(edge);
    }

    public boolean containsVertex(Vertex vertex)
    {
        return vertexSetMap.containsKey(vertex);
    }

    public boolean containsEdge(Vertex v1, Vertex v2, Edge edge)
    {
        return (edgeSet.contains(edge) && vertexSetMap.get(v1).contains(edge)
            && vertexSetMap.get(v2).contains(edge));
    }

    public boolean containsEdge(Vertex v1, Vertex v2)
    {
        for(Edge e : vertexSetMap.get(v1)) 
            if(vertexSetMap.get(v2).contains(e)) return true;
        return false;
    }

    public int totalVertices()
    {
        return vertexSetMap.keySet().size();
    }

    public int totalEdges()
    {
        return edgeSet.size();
    }

    public Set<Vertex> getAllVertices()
    {
        return new LinkedHashSet <>(vertexSetMap.keySet());
    }

    public Set<Edge> getAllEdges()
    {
        return edgeSet;
    }

    public void clear()
    {
        edgeSet = null;
        edgeSet = new LinkedHashSet <>();
        vertexSetMap = null;
        vertexSetMap = new LinkedHashMap <>();
    }
}
\$\endgroup\$
0
\$\begingroup\$

As of now, you only use LinkedHashSet and LinkedHashMap, thus declaring edgeSet and vertexMap as HashSet and HashMap is pointless. You could deploy Inversion of Control in order to demand some Set and Map at construction.


Method getEdges(...) could possibly return null, so you may want to wrap the return value in an Optional. Using Optional, you can also unify the behaviour of Map#get(Object) (which may or may not throw a NPE if a null is passed as argument):

public Optional<Set<Edge>> getEdges(Vertex vertex)
{
    Optional<Set<Edge>> result = Optional.empty();
    try 
    {
        result = Optional.ofNullable(vertex);
    }
    catch (NullPointerException e)
    {
        // No action needed, we return an empty Optional
    }
    return result;
}

Your remove...(...)-methods throw a NPE if the Vertex/Edge provided is not contained within the graph or is null. As with Map#get(Object), Set#remove(Object) may or may not throw a NPE. You can rewrite them to not throw:

public void removeVertex(Vertex vertex)
{
    Optional<Set<Edge>> deleteEdges = getEdges(vertex);
    if (deleteEdges.isPresent())
    {
        vertexSetMap.remove(vertex);
        edgeSet.removeAll(deleteEdges.get());
        vertexSetMap.keySet().forEach(vertex1 ->
                vertexSetMap.get(vertex1).removeAll(deleteEdges.get()));
    }
}

public void removeEdge(Edge edge)
{
    try
    {
        if (edgeSet.remove(edge))
        {
            Vertex v1 = edge.getVertex1();
            Vertex v2 = edge.getVertex2();
            vertexSetMap.get(v1).remove(edge);
            vertexSetMap.get(v2).remove(edge);
        }
    }
    catch (NullPoionterException e)
    {
        // No action needed, there is nothing to remove.
    }
}

When you add methods

public boolean containsVertex(Vertex vertex)
public boolean getOther(Vertex vertex)

To your Edge-class, you can rewrite getNeighborsOf(...) to use Streams

public Set<Vertex> getNeighborsOf(Vertex vertex) {
    return vertexSetMap.get(vertex).stream()
          .filter(edge -> edge.contains(vertex))
          .map(edge -> edge.getOther(vertex))
          .collect(Collectors.toSet());
}

What is missing is a Set<Vertex> getVertices() method (you have one for Edges, so I would expect one for Vertexs as well). This would probably require creating an additional field Set<Vertex> vertices in your Graph class.

\$\endgroup\$
  • \$\begingroup\$ Unless one needs to distinguish between an empty set and no set at all - which is not the case here - Optional<Set<X>> just adds an unnecessary level of complexity. Instead of returning null it would be better to have getEdges just return an empty set which can be done, for example, with: return vertexSetMap.getOrDefault(vertex, Collections.emptySet()); \$\endgroup\$ – RoToRa Jan 23 at 13:51

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.