10
\$\begingroup\$

I wanted to implement a simple oriented graph as part of an exercise in both Object Oriented Programming and Data Structures. I wanted to make it as class-focused as possible, so I don't know if my implementation follows the standard adjacency list/matrix implementations.

I started reading on software design patterns, but I am still very new to them. Any suggestions to make this code leverage the applicable design pattern(s) is appreciated. Other than that, I'd like feedback on:

  • Style & readability
  • Maintainability & scalability
  • Efficiency
  • API Design

Graph.java

public interface Graph<T> {
    boolean contains(T item);
    void addVertex(T vertex);
    boolean areAdjacent(T a, T b) throws Exception;
    void removeVertex(T vertex) throws Exception;
    void addEdge(T from, T to, int weight) throws Exception;
    void removeEdge(T from, T to) throws Exception;
    Collection<T> getNeighborsFor(T vertex) throws Exception;
    void depthSearch(T start) throws Exception;
    void breathSearch(T start) throws Exception;
}

OrientedGraph.java

public class OrientedGraph<T> implements Graph<T> {
    private HashMap<T, Vertex<T>> graph;

    public OrientedGraph() {
        graph = new HashMap<>();
    }

    public boolean contains(T vertex) {
        return graph.containsKey(vertex);
    }

    public boolean areAdjacent(T src, T dest) throws NoSuchVertexException {
        Vertex<T> srcVertex = graph.get(src);
        Vertex<T> destVertex = graph.get(dest);

        if (srcVertex == null || destVertex == null)
            throw new NoSuchVertexException();

        return srcVertex.hasNeighbor(destVertex);
    }

    public void addVertex(T vertex) {
        Vertex<T> vertexNode = new Vertex<>(vertex);
        graph.put(vertex, vertexNode);
    }

    public void removeVertex(T vertex) throws NoSuchVertexException {
        Vertex<T> vertexNode = graph.get(vertex);

        if (vertexNode == null)
            throw new NoSuchVertexException();

        Iterator<Vertex<T>> iterator = graph.values().iterator();
        while (iterator.hasNext()) {
            Vertex<T> possibleLink = iterator.next();
            possibleLink.removeEdgeTo(vertexNode);
        }

        graph.remove(vertex);
    }

    public void addEdge(T from, T to, int weight) throws NoSuchVertexException {
        Vertex<T> fromVertex = graph.get(from);
        Vertex<T> toVertex = graph.get(to);

        if (fromVertex == null || toVertex == null)
            throw new NoSuchVertexException();

        Edge<T> edge = new Edge<>(fromVertex, toVertex, weight);
        fromVertex.addEdge(edge);
    }

    public void removeEdge(T from, T to) throws NoSuchVertexException {
        Vertex<T> fromVertex = graph.get(from);
        Vertex<T> toVertex = graph.get(to);

        if (fromVertex == null || toVertex == null)
            throw new NoSuchVertexException();

        if (fromVertex.hasNeighbor(toVertex)) {
            fromVertex.removeEdgeTo(toVertex);
        }
    }

    public List<T> getNeighborsFor(T vertex) throws NoSuchVertexException {
        if (graph.get(vertex) == null)
            throw new NoSuchVertexException();

        return graph.get(vertex).getNeighbors();
    }

    public void depthSearch(T start) throws NoSuchVertexException {     
        if (graph.get(start) == null)
            throw new NoSuchVertexException();

        Collection<T> visited = new HashSet<>();
        visited.add(start);

        Stack<T> stack = new Stack<>();
        stack.push(start);

        System.out.println(start);
        while (!stack.empty()) {
            T current = stack.peek();
            T neighbor = null;
            Iterator<T> iterator = getNeighborsFor(current).iterator();

            while (iterator.hasNext()) {
                neighbor = iterator.next();
                if (!visited.contains(neighbor))
                    break;
            }

            if (neighbor != null && !visited.contains(neighbor)) {
                visited.add(neighbor);
                System.out.println(neighbor);
                stack.push(neighbor);
            } else {
                stack.pop();
            }
        }
    }

    public void breathSearch(T start) throws NoSuchVertexException {
        if (graph.get(start) == null)
            throw new NoSuchVertexException();

        Collection<T> visited = new HashSet<>();
        visited.add(start);

        Queue<T> queue = new ArrayDeque<>();
        queue.add(start);

        System.out.println(start);
        while (!queue.isEmpty()) {
            T current = queue.remove();
            T neighbor= null;
            Iterator<T> iterator = getNeighborsFor(current).iterator();

            while (iterator.hasNext()) {
                neighbor = iterator.next();
                if (!visited.contains(neighbor)) {
                    visited.add(neighbor);
                    System.out.println(neighbor);
                    queue.add(neighbor);
                }
            }
        }
    }
}

Vertex.java

class Vertex<T> implements Iterable<Vertex<T>> {
    T info;
    ArrayList<Edge<T>> neighbors;

    Vertex(T info) {
        this.info = info;
        neighbors = new ArrayList<Edge<T>>();
    }

    private Edge<T> getEdgeTo(Vertex<T> target) {
        Iterator<Edge<T>> edges = neighbors.iterator();

        while (edges.hasNext()) {
            Edge<T> current = edges.next();
            if (current.dest().equals(target))
                return current;
        }

        return null;
    }

    @Override
    public int hashCode() {
        final int prime = 31;
        int result = 1;
        result = prime * result + ((info == null) ? 0 : info.hashCode());
        return result;
    }

    @Override
    @SuppressWarnings("unchecked")
    public boolean equals(Object obj) {
        if (this == obj)
            return true;
        if (obj == null)
            return false;
        if (getClass() != obj.getClass())
            return false;
        Vertex<T> other = (Vertex<T>) obj;
        if (info == null) {
            if (other.info != null)
                return false;
        } else if (!info.equals(other.info))
            return false;
        return true;
    }

    @Override
    public Iterator<Vertex<T>> iterator() {
        return new VertexIterator<T>(neighbors);
    }

    public void addEdge(Edge<T> edge) {
        if (neighbors.contains(edge))
            return;
        else {
            neighbors.add(edge);
        }
    }

    public boolean hasNeighbor(Vertex<T> neighbor) {
        Iterator<Vertex<T>> iterator = iterator();

        while (iterator.hasNext()) {
            if (iterator.next().equals(neighbor))
                return true;
        }

        return false;
    }

    public void removeEdgeTo(Vertex<T> neighbor) {
        Edge<T> edge = getEdgeTo(neighbor);
        neighbors.remove(edge);
    }

    public List<T> getNeighbors() {
        List<T> neighbors = new ArrayList<>();
        Iterator<Vertex<T>> iterator = iterator();

        while (iterator.hasNext()) {
            neighbors.add(iterator.next().value());
        }

        return neighbors;
    }

    public T value() {
        return info;
    }
}

Edge.java

class Edge<T> {
    Vertex<T> from;
    Vertex<T> to;
    int weight;

    Edge(Vertex<T> from, Vertex<T> to, int weight) {
        this.from = from;
        this.to = to;
        this.weight = weight;
    }

    Vertex<T> dest() {
        return to;
    }

    @Override
    public int hashCode() {
        final int prime = 31;
        int result = 1;
        result = prime * result + ((from == null) ? 0 : from.hashCode());
        result = prime * result + ((to == null) ? 0 : to.hashCode());
        result = prime * result + weight;
        return result;
    }

    @Override
    @SuppressWarnings("unchecked")
    public boolean equals(Object obj) {
        if (this == obj)
            return true;
        if (obj == null)
            return false;
        if (getClass() != obj.getClass())
            return false;
        Edge<T> other = (Edge<T>) obj;
        if (from == null) {
            if (other.from != null)
                return false;
        } else if (!from.equals(other.from))
            return false;
        if (to == null) {
            if (other.to != null)
                return false;
        } else if (!to.equals(other.to))
            return false;
        if (weight != other.weight)
            return false;
        return true;
    }
}

VertexIterator.java

class VertexIterator<T> implements Iterator<Vertex<T>> {
    Iterator<Edge<T>> iterator;

    VertexIterator(Collection<Edge<T>> neighbors) {
        iterator = neighbors.iterator();
    }

    @Override
    public boolean hasNext() {
        return iterator.hasNext();
    }

    @Override
    public Vertex<T> next() {
        return iterator.next().dest();
    }
}
\$\endgroup\$
  • \$\begingroup\$ Which concrete design patterns did you have in mind when you wrote that code? Could you elaborate please? \$\endgroup\$ – πάντα ῥεῖ Dec 17 '15 at 19:00
  • \$\begingroup\$ About creational patterns, how can I remove the object creation code from the Graph classes? Would that even be a good idea? \$\endgroup\$ – Stefan Rendevski Dec 17 '15 at 19:04
2
\$\begingroup\$

Make constructor private in order to remove object creation code. Replace with public or protected method which calls private constructor and returns a new instance; i.e., a factory pattern. Suppose one has numerous arguments required for construction. This could be implemented using the Builder design rather than an awful, lengthy parameter list in your constructor. Or what if one maintained a collection of object instances in the graph object, controlling how many instances are ever created; i.e., an object cache. Or one might want to provide an easy way to copy an existing object's data, providing a copy constructor method.

\$\endgroup\$

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.