package com.c2kernel.graph.traversal;


import java.util.Vector;

import com.c2kernel.graph.model.GraphModel;
import com.c2kernel.graph.model.Vertex;


public class GraphTraversal
{
    public static final int kUp   = 1;
    public static final int kDown = 2;


    private GraphTraversal()
    {
    }


    public static Vertex[] getTraversal(GraphModel graphModel, Vertex startVertex, int direction, boolean ignoreBackLinks)
    {
        Vector path = new Vector(10, 10);

        graphModel.clearTags(startVertex);
        visitVertex(startVertex, graphModel, path, direction, startVertex, ignoreBackLinks);

        return vectorToVertexArray(path);
    }


    private static void visitVertex(Vertex vertex, GraphModel graphModel, Vector path, int direction, Object tag, boolean ignoreBackLinks)
    {
        Vertex[] children = null;
        int i = 0;

        if(direction == kDown)
        {
            children = graphModel.getOutVertices(vertex);
        }
        else
        {
            children = graphModel.getInVertices(vertex);
        }

        vertex.setTag(tag);
        path.add(vertex);

        for(i=0; i<children.length; i++)
        {
            if(!(children[i].hasTag(tag)))
            {
                boolean skipBackLink = false;
                if ( ignoreBackLinks &&
                    ((vertex.isJoin() && direction == kUp) ||
                    (vertex.isLoop() && direction == kDown))) {
                    Vertex[] following = getTraversal(graphModel, children[i], direction, false);
                    for (int j = 0; j < following.length; j++) {
                        if (following[j] == vertex) {
                            skipBackLink = true;
                            break;
                        }
                    }
                }
                if (!skipBackLink)
                    visitVertex(children[i], graphModel, path, direction, tag, ignoreBackLinks);
            }
        }
    }


    private static Vertex[] vectorToVertexArray(Vector vector)
    {
        Vertex[] vertices = new Vertex[vector.size()];
        int      i        = 0;


        for(i=0; i<vertices.length; i++)
        {
            vertices[i] = (Vertex)vector.elementAt(i);
        }

        return vertices;
    }
}