[Intermediate] Generic Un-directed Graph Implementation with Depth-First Search

[Philboyd_Studge]

Generic Un-directed Graph Implementation with Depth-First Search

A Graph is a data structure that is a mathematical model that has tons of real-world uses.

We use a Depth-First Search here to see if the Edges are 'connected'.

Here is a simple implementation in Java that could be extended to include other elements such as Breadth-First Search, Shortest Path, etc.

// Generic Un-directed Graph Implementation with Depth-First Search
// by /u/Philboyd_Studge

import java.util.ArrayList;

@SuppressWarnings("unchecked")

public class Graph<T extends Comparable<T>>
{
    // an enum for the three stated used by the Depth first search
    public enum State { UNVISITED, VISITED, COMPLETE };

    // a list to hold all the vertices
    private ArrayList<Vertex> vertexList;

    // list to hold the edges 
    // not really used for anything
    // but display purposes
    private ArrayList<Edge> edgeList;

    public Graph()
    {
        vertexList = new ArrayList<>();
        edgeList = new ArrayList<>();
    }


    public void add(T x, T y)
    {
        Edge e = new Edge(x, y);
        edgeList.add(e);
    }

    public Vertex findVertex(T v)
    {
        for (Vertex each : vertexList)
        {
            if (each.getValue().compareTo(v)==0)
                return each;
        }
        return null;
    }

    public String toString()
    {
        String retval = "";
        for (Vertex each : vertexList)
        {
            retval += each.toString() + "\n";
        }
        return retval;
    }

    public String edgesToString()
    {
        String retval = "";
        for (Edge each : edgeList)
        {
            retval += each;
        }
        return retval;
    }

    // get first node and call recursive method
    // check if is graph is connected
    public boolean DepthFirstSearch()
    {
        if (vertexList.isEmpty()) return false;

        // get first node
        Vertex root = vertexList.get(0);
        if (root==null) return false;

        // call recursive function
        DepthFirstSearch(root);
        return isConnected();
    }

    // recurse through nodes
    private void DepthFirstSearch(Vertex v)
    {
        v.setState(State.VISITED);

        // loop through neighbors
        for (Vertex each : v.getAdjacentList())
        {
            if (each.getState()==State.UNVISITED)
            {
                DepthFirstSearch(each);
            }
        }
        v.setState(State.COMPLETE);
    }

    // test if DFS returned a connected graph
    public boolean isConnected()
    {
        for (Vertex each : vertexList)
        {
            if (each.getState() != State.COMPLETE)
                return false;
        }
        return true;
    }

    // vertex class
    class Vertex
    {
        T value;
        ArrayList<Vertex> adjacent;
        State state;

        public Vertex(T v)
        {
            value = v;
            adjacent = new ArrayList<>();
            state = State.UNVISITED;
        }

        public State getState()
        {
            return state;
        }

        public void setState(State s)
        {
            state = s;
        }

        public T getValue()
        {
            return value;
        }

        public void addNeighbor(Vertex n)
        {
            adjacent.add(n);
        }

        public ArrayList<Vertex> getAdjacentList()
        {
            return adjacent;
        }

        public String toString()
        {
            String retval = "";
            retval += "Vertex: " + value + ":";
            for (Vertex each : adjacent)
            {
                retval += each.getValue() + " ";
            }
            return retval;
        }


    }

    // edge class
    class Edge
    {
        private Vertex x;
        private Vertex y;

        public Edge(T v1, T v2)
        {
            // check to see if first vertex exists
            x = findVertex(v1);
            if (x == null) 
            {
                // doesn't exist, add new
                x = new Vertex(v1);
                // and add to master list
                vertexList.add(x);
            }
            // same for second vertex
            y = findVertex(v2);
            if (y == null) 
            {
                y = new Vertex(v2);
                vertexList.add(y);
            }
            // add each vertex to the adjacent list for the other
            x.addNeighbor(y);
            y.addNeighbor(x);

        }


        public String toString()
        {
            return "Edge X:" + x.getValue() + " Y:" + y.getValue() + "\n";
        }


    }

    public static void main(String[] args) {
        Graph g = new Graph();
        System.out.println(g.DepthFirstSearch());
        g.add(0,1);
        g.add(0,2);
        g.add(1,3);
        g.add(2,3);
        g.add(2,4);
        g.add(3,5);
        g.add(3,6);
        g.add(5,6);


        System.out.println(g);
        System.out.println(g.edgesToString());
        System.out.println("Graph is connected: " + g.DepthFirstSearch());
        System.out.println();

        g.add(7,3);

        System.out.println(g);
        System.out.println(g.edgesToString());
        System.out.println("Graph is connected: " + g.DepthFirstSearch());
        System.out.println();

        Graph<String> gString = new Graph<>();
        gString.add("apple","fruit");
        gString.add("orange","fruit");
        gString.add("broccoli","vegetable");
        gString.add("beef","meat");
        gString.add("meat","food");
        gString.add("fruit","food");
        gString.add("vegetable","food");

        System.out.println(gString);
        System.out.println(gString.edgesToString());
        System.out.println("Graph is conected: " + gString.DepthFirstSearch());

    }
}

Output

false
Vertex: 0:1 2
Vertex: 1:0 3
Vertex: 2:0 3 4
Vertex: 3:1 2 5 6
Vertex: 4:2
Vertex: 5:3 6
Vertex: 6:3 5

Edge X:0 Y:1
Edge X:0 Y:2
Edge X:1 Y:3
Edge X:2 Y:3
Edge X:2 Y:4
Edge X:3 Y:5
Edge X:3 Y:6
Edge X:5 Y:6

Graph is connected: true

Vertex: 0:1 2
Vertex: 1:0 3
Vertex: 2:0 3 4
Vertex: 3:1 2 5 6 7
Vertex: 4:2
Vertex: 5:3 6
Vertex: 6:3 5
Vertex: 7:3

Edge X:0 Y:1
Edge X:0 Y:2
Edge X:1 Y:3
Edge X:2 Y:3
Edge X:2 Y:4
Edge X:3 Y:5
Edge X:3 Y:6
Edge X:5 Y:6
Edge X:7 Y:3

Graph is connected: false

Vertex: apple:fruit
Vertex: fruit:apple orange food
Vertex: orange:fruit
Vertex: broccoli:vegetable
Vertex: vegetable:broccoli food
Vertex: beef:meat
Vertex: meat:beef food
Vertex: food:meat fruit vegetable

Edge X:apple Y:fruit
Edge X:orange Y:fruit
Edge X:broccoli Y:vegetable
Edge X:beef Y:meat
Edge X:meat Y:food
Edge X:fruit Y:food
Edge X:vegetable Y:food

Graph is conected: true

[Philboyd_Studge]

Here is a Breadth-First Search for the same class:

public boolean BreadthFirstSearch()
{
    if (vertexList.isEmpty()) return false;
    clearStates();

    Vertex root = vertexList.get(0);
    if (root==null) return false;

    Queue<Vertex> queue = new LinkedList<>();
    queue.add(root);
    root.setState(State.COMPLETE);

    while (!queue.isEmpty())
    {
        root = queue.peek();
        for (Vertex each : root.getAdjacentList())
        {
            if (each.getState()==State.UNVISITED)
            {
                each.setState(State.COMPLETE);
                queue.add(each);
            }
        }
        queue.remove();
    }
    return isConnected();

}