Wednesday, July 13, 2011

Graph, Path, Node, and Edge classes in Java, along with algorithms

I created Graph, Path, Node, and Edge classes for playing around with graph algorithms. I didn't use best practices when designing the access etc... example: Node's members are all public. This is strictly for learning purposes!

Note: I forgot to escape the generic left/right brackets in LinkedList, so it's not showing up here. Add them if you're gonna use them

In Graph.java
public class Graph {
    private class Path implements Cloneable
    {
        GNode start = null;
        LinkedList edges = new LinkedList();
        private int weight = 0;
        public Path(GNode start)
        {
            this.start = start;
        }
        public void AddEdge(GEdge e)
        {
            weight += e.weight;
            edges.add(e);
        }
        @Override public String toString()
        {
            StringBuilder sb = new StringBuilder(1 + edges.size() * 2);
            sb.append("(" + start.data + ")");
            
            for(GEdge e : edges)
                sb.append(String.format("-%d->(%s)", e.weight, e.n.data));
            sb.append(" total weight=" + weight);
            return sb.toString();
        }
        @Override public Object clone() throws CloneNotSupportedException
        {
            Path p = new Path((GNode)start.clone());
            p.edges = (LinkedList)edges.clone();
            p.weight = this.weight;
            return p;
        }
    }


    
    public LinkedList nodes = new LinkedList();
    private Path searchPath = null;
    public void DFS(int value)
    {
        
        if(nodes.isEmpty()){
            System.out.println(
        "No nodes exist");
            return;
        }
        searchPath = null;
        DFS(value, nodes.getFirst(), new Path(nodes.getFirst()));
        System.out.println(searchPath.toString());
    }
    private void DFS(int value, GNode cur, Path curPath)
    {
        if(searchPath != null)
            return;
        if(value == cur.data)
        {
            searchPath = curPath;
            return;
        }
        else
        {
            for(GEdge e : cur.adjacent)
            {
                try{
                Path newPath = (Path)curPath.clone();
                newPath.AddEdge(e);
                DFS(value, e.n, newPath);
                }
                catch(CloneNotSupportedException c)
                {
                    System.out.println(c);
                    return;
                }
            }
        }
    }
    public void BFS(int value)
    {
    }
    public void Dijkstra(int fromVal, int toVal)
    {
    }
    
}

In GNode.java
public class GNode implements Cloneable
{
    public int data = 0;
    public boolean visited = false;
    public LinkedList adjacent = new LinkedList();
    public GNode(int data)
    {
        this.data = data;
    }

    @Override
    protected Object clone() throws CloneNotSupportedException
    {
        GNode gnode = new GNode(this.data);
        gnode.adjacent = (LinkedList)this.adjacent.clone();
        gnode.visited = this.visited;
        return gnode;
    }
    
}
In GEdge.java
public class GEdge implements Cloneable
{
    public int weight = Integer.MIN_VALUE;
    public GNode n = null;
    public GEdge(int weight, GNode N)
    {
        this.weight = weight;
        this.n = N;
    }
    @Override public Object clone() throws CloneNotSupportedException
    {
        GEdge gedge = new GEdge(this.weight, (GNode)this.n.clone());
        return gedge;
        
    }
}
 
Example of building a graph and running depth-first search for an element
public static void main(String[] args) {
        Graph g = new Graph();
        GNode node1 = new GNode(1);
        GNode node2 = new GNode(2);
        GNode node3 = new GNode(3);
        GNode node4 = new GNode(4);
        node1.adjacent.add(new GEdge(2, node3));
        node1.adjacent.add(new GEdge(1, node2));
        node2.adjacent.add(new GEdge(2, node3));
        node3.adjacent.add(new GEdge(3, node4));
        node4.adjacent.add(new GEdge(1, node1));
        g.nodes.add(node1);
        g.nodes.add(node2);
        g.nodes.add(node3);
        g.nodes.add(node4);
        g.DFS(3);
        
    }
This will print out: (1)-2->(3) total weight=2

No comments:

Post a Comment

There was an error in this gadget