Graph implementation for solving graph problems (java)

Posted on

Problem

I’ve currently started solving some competitive programming Graph questions. But Started using adjacency list as HashMap<Integer,ArrayList<Integer>> list . But in some problems, this doesn’t work. so I decided to implement class Graph other than this HashMap.
I would like a review of efficiency and general code quality. Please let me know if this follow standard adjacency list implementation and best and worst-case scenarios.

Node class

class Node
{
    public int id;
    public boolean visited;
    public List<Node> adjecent;
    Node(int id)
    {
        this.id =id;
        adjecent = new ArrayList<>();
    }
}

Graph

class Graph
{
   private List<Node> nodes;
    Graph()
    {
       nodes = new ArrayList<>();
    }
    boolean check(int id)
    {
        boolean flag = false;
        for(Node temp:nodes)
        {
            if(temp.id == id)
                flag =true;
        }

        return flag;
    }
    Node getNode(int id)
    {
        for(Node temp:nodes)
        {
            if(temp.id == id)
                return temp;
        }
        return null;
    }
    void addEdge(int src,int dest)
    {
        
        Node s = check(src) ? getNode(src):new Node(src);
        Node d = check(dest) ? getNode(dest):new Node(dest);
        s.adjecent.add(d);
        d.adjecent.add(s);
     

        if(!check(src)) nodes.add(s);
        if(!check(dest)) nodes.add(d);
    }

    void print()
    {
        for(Node temp : nodes)
        {
            System.out.print(temp.id+" -> ");
             temp.adjecent.forEach(e->System.out.print(e.id+" "));
            System.out.println();
        }
    }
    void dfs(Node root)
    {
        if(root == null) return;
        System.out.print(root.id+" ");
        root.visited = true;
        for(Node t : root.adjecent)
        {
            if(!t.visited)
                dfs(t);
        }
    }   
    void refresh()
    {
        for(Node temp : nodes)
        {
            temp.visited =false;
        }
    }
    void bfs(Node root)
    {
        Queue<Node> q =new LinkedList<>();
        root.visited =true;
        q.add(root);
        while(!q.isEmpty())
        {
            Node temp = q.poll();
            System.out.print(temp.id+" ");
            for(Node n:temp.adjecent)
            {
                if(!n.visited)
                    {
                        n.visited=true;
                        q.add(n);
                    }
            }
        }
    }


    public static void main(String[] args) {
        Graph g = new Graph();
        /*
         *                0
         *             /  |   
         *            1   2   3
         *           /       
         *          4  5    6   7
         */
        g.addEdge(0, 1);
        g.addEdge(0, 2);
        g.addEdge(0, 3);
        g.addEdge(1, 4);
        g.addEdge(1, 5);
        g.addEdge(2, 6);
        g.addEdge(3, 7);
        g.print();
        System.out.println(g.nodes.size());
        g.dfs(g.getNode(0));
        System.out.println();
        g.refresh();
        g.bfs(g.getNode(0));
        
    }
} 

Any suggestions to make this code leverage to better efficiency is appreciated.

Solution

Don’t store method flow flags as state in classes. This is a breach in object-oriented design.

class Node
{
    public boolean visited;
    // .. other
}

Search methods like dfs should use a map of some sort to store which nodes are visited.

By storing this flag incorrectly as state, you’ll get in trouble when multiple threads search the graph concurrently.

Leave a Reply

Your email address will not be published. Required fields are marked *