gistfile1.java

/**
 * @see <a href="http://en.wikipedia.org/wiki/Eulerian_path">Eulerian Path</a>
 */
public class EulerianPath {
    private final Logger log = Logger.getLogger(EulerianPath.class);
    private final Graph graph;

    public EulerianPath(Graph graph) {
        this.graph = graph;
    }

    public List<Vertex> findPath() {
        List<Vertex> path = new ArrayList<Vertex>();

        int oddsCount = 0; // count the odd nodes
        int edgeCount = 0; // count the edges
        Vertex firstNode = null;
        Vertex lastNode = null;

        Set<Vertex> vertices = graph.getVertices();

        for (Vertex vertex : vertices) {
            int degree = 0;
            Set<Vertex> adjacentVertices = graph.getAdjacentVerticesOf(vertex);

            for (Vertex adjacentVertex : adjacentVertices) {
                degree += graph.getEdgeCounterFor(
                    Edges.newEdge(vertex, adjacentVertex)
                );
            }

            edgeCount += degree;

            if (degree % 2 == 1) {
                oddsCount++;
                if (oddsCount == 1)
                    firstNode = vertex;
                else if (oddsCount == 2)
                    lastNode = vertex;
                else {
                    // if oddsCount > 2 there is no Eulerian path in the given graph
                    return null;
                }
            }
        }

        edgeCount = edgeCount / 2;

        log.debug("First node:" + firstNode);
        log.debug("Last node:" + lastNode);
        log.debug("Edge count:" + edgeCount);
        log.debug("Odds count:" + oddsCount);

        // if oddsCount = 0 then firstNode = lastNode = 0
        // find a first path from firstNode to lastNode

        path.add(firstNode);

        Vertex current = firstNode;
        do {
            Set<Vertex> adjacentVertices = graph.getAdjacentVerticesOf(current);
            for (Vertex adjacentVertex : adjacentVertices) {
                Edge e = Edges.newEdge(current, adjacentVertex);
                if (graph.getEdgeCounterFor(e) > 0) {
                    graph.decEdgeCounterFor(e);
                    graph.decEdgeCounterFor(Edges.newEdge(adjacentVertex, current));
                    path.add(adjacentVertex);
                    current = adjacentVertex;
                    break;
                }
            }
        } while (!current.equals(lastNode));

        while (path.size() < edgeCount + 1) {
            // find a node in path with free edges
            Vertex hold = null;
            search:
            for (Vertex pathVertex : path) {
                Set<Vertex> adjacentVertices = graph.getAdjacentVerticesOf(pathVertex);
                for (Vertex adjacentVertex : adjacentVertices) {
                    if (graph.getEdgeCounterFor(Edges.newEdge(pathVertex, adjacentVertex)) > 0) {
                        hold = pathVertex;
                        break search;
                    }
                }
            }

            // find a closed in-path from hold to hold
            ArrayList<Vertex> inPath = new ArrayList<Vertex>();
            current = hold;
            do {
                // find a neighbor of the current node
                Set<Vertex> adjacentVertices = graph.getAdjacentVerticesOf(current);
                for (Vertex adjacentVertex : adjacentVertices) {
                    Edge e = Edges.newEdge(current, adjacentVertex);
                    if (graph.getEdgeCounterFor(e) > 0) {
                        graph.decEdgeCounterFor(e);
                        graph.decEdgeCounterFor(Edges.newEdge(adjacentVertex, current));

                        if (!adjacentVertex.equals(hold)) {
                            inPath.add(adjacentVertex);
                        }
                        current = adjacentVertex;
                        break;
                    }
                }
            } while (!current.equals(hold));

            // insert the in-path into a new path
            ArrayList<Vertex> newPath = new ArrayList<Vertex>();
            boolean done = false;
            for (Vertex pathVertex : path) {
                if (done || (!pathVertex.equals(hold))) {
                    newPath.add(pathVertex);
                } else {
                    newPath.add(pathVertex);

                    for (Vertex inPathVertex : inPath)
                        newPath.add(inPathVertex);

                    done = true;
                    newPath.add(pathVertex);
                }
            }
            path = newPath;
        }

        return path;
    }
}