gistfile1.java

package ee.suurhans.algorithms;

import com.sun.org.apache.xpath.internal.functions.FuncFalse;

import java.util.*;

/**
 * User: Tanel Suurhans
 * Date: 17.02.13
 */
class GraphNode {

    public String data;
    public boolean visited;
    public List<GraphNode> nodes;

    public GraphNode(String data) {
        this.data = data;
        this.visited = false;
        this.nodes = new ArrayList<GraphNode>();
    }

    public void visit() {
        this.visited = true;
    }

    public boolean isVisited() {
        return this.visited;
    }

    public String toString() {
        return this.data;
    }

}

public class Graph {

    public List<GraphNode> nodes;

    public Graph() {
        this.nodes = new ArrayList<GraphNode>();
    }

    public void addEdge(GraphNode node1, GraphNode node2) {

        if (!this.nodes.contains(node1))
            this.nodes.add(node1);

        if (!this.nodes.contains(node2))
            this.nodes.add(node2);

        if (!node1.nodes.contains(node2))
            node1.nodes.add(node2);

        if (!node2.nodes.contains(node1))
            node2.nodes.add(node1);

    }

    public void traverse(GraphNode node) {

        if (node == null)
            return;

        if (!node.isVisited()) {

            node.visit();

            System.out.println(node.toString());

            for (GraphNode sibling : node.nodes) {
                traverse(sibling);
            }
        }

    }

    public void findPath(GraphNode node1, GraphNode node2) {
        findPath(node1, node2, node1.toString());
    }

    public void findPath(GraphNode node1, GraphNode node2, String path) {

        if (!node1.isVisited()) {

            node1.visit();

            if (node1 == node2) {
                System.out.println(path);
            } else {
                for (GraphNode sibling : node1.nodes) {
                    findPath(sibling, node2, path + " " + sibling.toString());
                }
            }
        }

    }

    public static void main(String[] args) {

        GraphNode nodeA = new GraphNode("A");
        GraphNode nodeB = new GraphNode("B");
        GraphNode nodeC = new GraphNode("C");
        GraphNode nodeD = new GraphNode("D");

        Graph graph = new Graph();
        graph.addEdge(nodeA, nodeB);
        graph.addEdge(nodeA, nodeC);
        graph.addEdge(nodeB, nodeD);
        graph.addEdge(nodeC, nodeD);

        graph.findPath(nodeA, nodeD);

    }

}