How to implement Graph search (DFS) with Object Oriented design

Question

I'm not so sure about what's the best approach to model this problem in the object oriented world.

Suppose I have to represent a graph and its nodes in Java and suppose I want to traverse the graph using a depth first search (DFS).

What is the best approach in Software engineering among these two:

  • Create a class Node, a class Graph and a class GraphsFunctions where the GraphsFunctions class contains the DFS method which takes the Graph and a Node as parameters. Something like this: public void DFS(Graph g, Node n) and the call new GraphsFunctions().DFS(new Graph(), new Node())

  • Create a class Node and a class Graph where the class Graph contains the method DFS which only takes a Node as a parameter. Something like this: public void DFS(Node n) and the call new Graph().DFS(new Node())

I would rather use the first of the two options but I can't say why it's the best for me. Can you tell me what makes the best choice, actually the best?


Show source
| java   | oop   | graph   | design-patterns   | software-engineering   2016-11-25 19:11 2 Answers

Answers to How to implement Graph search (DFS) with Object Oriented design ( 2 )

  1. 2016-11-25 19:11

    This really depends on mostly two things:

    1. How much encapsulation you want in your project. More encapsulation is usually better, but it can come at the price of over engineering the problem, which can cause a lot more work which you want to avoid for small projects which wont grow over time.
    2. Your own personal style. Each developer will develop his or her own style over time which will be clearly distinguishable from other developers. The most important thing is consistency throughout a project

    Assuming you want (only) good encapsulation I would personally do it like the following..

    Create an interface GraphSearch and define your search(Graph g, Node n) method in there. Now have a class called DFSearch and possibliy BFSearch. If - at some point - a method wants to perform searches on a Graph you can specify the search algorithm which should be used.

    If you want great encapsulation, I would recommend using the iterator pattern as DFS and BFS are basically just iteration orders.

    Start by creating an Interface GraphIterator instead. It simply extends Iterator<Node> which means it can iterate over Nodes in some order.

    public interface GraphIterator extends Iterator<Node> {
    
    }
    

    Create as many implementations of this algorithm as you like. An empty construct for DFS looks like this:

    public class DFSIterator implements GraphIterator {
        private Graph g;
    
        public DFSIterator(Graph g) {
            this.g = g;
        }
    
        @Override
        public boolean hasNext() {
            // todo: implement
            return false;
        }
    
        @Override
        public Node next() {
            // todo: implement
            return null;
        }
    }
    

    Next you can still create your Interface GraphSearch..

    public interface GraphSearch {
        Node search(Graph g, Node n);
    }
    

    And one simple implementation would be IterationSearch which can only perform searches with a given Iterator.

    public class IterationSearch {
        public Node search(Graph g, Node n, GraphIterator iter){
            Node current = null;
            while (iter.hasNext()){
                current = iter.next();
                if (current.equals(n)){
                    return n;
                }
            }
            return null;
        }
    }
    

    It just iterates over the Iterator and compares each element to the searched node. Next create your class DFSearch which is the first actual GraphSearch...

    public class DFSearch extends IterationSearch implements GraphSearch{
        @Override
        public Node search(Graph g, Node n) {
            return search(g, n, new DFSIterator(g));
        }
    }
    

    Now your Graph can extend Itarable<Node> and return one of your iterators as the default iterator. This way you could nicely iterate over your Graph.

    public class Graph implements Iterable<Node> {
        @Override
        public Iterator<Node> iterator() {
            return new DFSIterator(this);
        }
    }
    

    and use it like the following:

    Graph g = createGraph();
    for (Node n : g) {
        // do things...
    }
    

    The great thing about this solution is that you can make the Iterators inner classes of your Graph, which allows them to access private members. This often improves performance significantly as you don't have to treat the Graph as a black box.

  2. 2016-11-25 19:11

    Best in terms of fast-to-code, easy-to-modify, or some other criterion? Unless you come up with a very precise definition of "what is good", do not expect to find "best".

    My first answer would be to use a graph library for Java. Most come with DFS already implemented:

    • Already implemented and debugged.
    • Good documentation.
    • No company will generally want me to reinvent the wheel.

    However, since your question is probably part of a do-it-yourself course, I would instead recommend:

    • Node class, which can provide access to neighbors, and has equals and hashcode methods.
    • Graphs class, which can build graphs and display them. Includes a Dfs(Graph g, Node start, DfsVisitor visitor) method. This would be a utility class with all-static methods, in the same vein as JDK's Collections or Files.
    • Graph class, with a list of nodes (and possibly other things, such as the possibility of returning an iterator to a list of edges).
    • DfsVisitor, an interface for visitors:
    • Main class, which builds a graph and calls your DFS on the graph with the useful payload in the visitor.

    Because DFS by itself is useless - it is just a node-visiting strategy. Its value is in what it does before and after it visits a node. Unless you allow this to be customized, placing a DFS algorithm into GraphsFunctions or Graphs makes no big difference: it is not likely to be reused outside of whatever payload you have built into it.

     public interface DfsVisitor() {
        void started(Graph g, Node node);   // when first encountered
        void finished(Graph g, Node node);  // when all children processed
     }
    

Leave a reply to - How to implement Graph search (DFS) with Object Oriented design

◀ Go back