package shared;
import java.lang.*;
import java.io.*;
import java.util.*;

/** An instance G of the data type graph consists of a list V  of nodes
 * and a list E  of edges (node and edge are item types).
 * Distinct graphs have disjoint node and edge lists.
 * The value of a variable of type node is either the node of some graph, or the
 * special value nil (which is distinct from all nodes), or is undefined
 * (before the first assignment to the variable). A corresponding statement is
 * true for the variables of type edge.
 * <P>
 * A graph with empty node list is called  empty.
 * A pair of nodes (v,w) is associated with every
 * edge; v is called the  source of e and w is called the
 * target of e, and v and w are called  endpoints of e.
 * The edge e is said to be incident to its endpoints.
 * <P>
 * A graph is either  directed or  undirected. The difference between
 * directed and undirected graphs is the way the edges incident to a node
 * are stored and how the concept  adjacent is defined.
 * <P>
 * In directed graphs two lists of edges are associated with every node v:
 * adj_edges(v) = e  v = source(e),
 * i.e., the list of edges starting in v, and
 * in_edges(v) = e  Lvert v = target(e), i.e., the list of
 * edges ending in v.  The list adj_edges(v) is called the adjacency list
 * of node v and the edges in adj_edges(v) are called the edges
 * adjacent to node v. For directed graphs we often use out_edges(v)
 * as a synonym for adj_edges(v).
 * <P>
 * In undirected graphs only the list adj_edges(v) is defined
 * for every every node v. Here it contains all edges incident to v, i.e.,
 * adj_edges(v) = e   v  source(e),target(e).
 * An undirectect graph may not contain selfloops, i.e., it may not contain an
 * edge whose source is equal to its target.
 * <P>
 * In a directed graph an edge is adjacent to its source and in an undirected
 * graph it is adjacent to its source and target. In a directed graph a node w
 * is adjacent to a node v if there is an edge (v,w) E; in an undirected
 * graph w is adjacent to v if there is an edge (v,w) or (w,v) in the
 * graph.
 * <P>
 * A directed graph can be made undirected and vice versa:
 * G.make_undirected() makes the directed graph G undirected by
 * appending for each node v the list in_edges(v) to the list
 * adj_edges(v) (removing selfloops).  Conversely, G.make_directed()
 * makes the undirected graph G directed by splitting for
 * each node v the list adj_edges(v) into the lists out_edges(v) and
 * in_edges(v). Note that these two operations are not exactly inverse to
 * each other.
 * The data type ugraph (cf. section ref{Undirected Graphs)  can only
 * represent undirected graphs.
 * <P>
 * Reversal Information, Maps and Faces
 * The reversal information of an edge e is accessed through G.reversal(e), it has type edge and may or may not be defined (=nil).
 * Assume that G.reversal(e) is defined and let
 * e' = G.reversal(e). Then e = (v,w) and e' = (w,v) for some
 * nodes v and w, G.reversal(e') is defined and e = G.reversal(e'). In other words, reversal deserves its name.
 * <P>
 * We call a directed graph bidirected if for every edge of G the
 * reversed edge also belongs to G and we call a bidirected graph a map
 * if all edges have their reversal information defined. Maps are the data
 * structure of choice for embedded graphs. For an edge e of a map G let
 * face_cycle_succ(e) = cyclic_adj_succ(reversal(e)) and consider the sequence
 * e, face_cycle_succ(e), face_cycle_succ(face_cycle_succ(e)),. The
 * first edge to repeat in this sequence is e (why?) and the set of edges
 * appearing in this sequence is called the face cycle containing e.
 * Each edge is contained in some face cycle and face cycles are pairwise
 * disjoint. Let f be the number of face cycles, n be the number of nodes,
 * m be the number of edges, and let c be the number of connected components.
 * Then g = (m/2 - n - f)/2 + c is called the genus of the map
 * (note that m/2 is the number of edges in the underlying
 * undirected graph). The genus is zero if and only if the map is planar, i.e.,
 * there is an embedding of G into the plane such that for every node v the
 * counter-clockwise ordering of the edges around v agrees with the cyclic
 * ordering of v's adjacency list.
 * <P>
 * If a graph G is a map the faces of G can be constructed explicitely
 * by G.compute_faces(). Afterwards, the faces of G can be traversed
 * by different iterators, e.g., forall_faces(f,G) iterates over
 * all faces , forall_adj_faces(v) iterates over all faces adjacent
 * to node v. By using face maps or arrays (data types face_map
 * and face_array) additional information can be associated with
 * the faces of a graph. Note that any update operation performed on
 * G invalidates the list of faces. See the section on face operations
 * for a complete list of available operations for faces.
 *
 */
public class Graph implements ParamTypes{
    private static int node_data_slots = 0;
    private static int edge_data_slots = 0;
    
    private static int after = 0;
    private static int before = 1;
    
    private boolean undirected;
    
    private int max_node_index; //max_n_index //maximal node index
    private int max_edge_index; //max_e_index //maximal edge index
    private int max_face_index; //max_f_index //maximal face index
    
    private int[] data_sz;	//number of additional node/edge/face data slots
    private LinkedList[] free_data;	//list of unused node/edge/face data slots
    private LinkedList[] map_list;  //list of registered node/edge/face maps
    
    /** List of nodes in this graph.
     */    
    protected LinkedList v_list;	//list of all nodes
    private LinkedList v_free;	//list of free nodes
    
    private LinkedList e_list;	//list of all edges
    private LinkedList e_free;	//list of free edges
    private LinkedList h_list;	//list of hidden edges
    
    private LinkedList f_list;	//list of all faces
    private LinkedList f_free;	//list of free faces
    
    private LinkedList v_list_tmp;	//temporary list of nodes
    private LinkedList e_list_tmp;	//temporary list of edges
    private LinkedList f_list_tmp;	//temporary list of faces
    
    private GraphMap FaceOf;
    private GraphMap adj_iterator;
    
    /** The parent graph of this graph.
     */    
    protected Graph parent;
    
    /** Graph map of nodes.
     */    
    protected GraphMap node_data_map;	//GraphMap is originally graph_map
    /** Graph map of edges.
     */    
    protected GraphMap edge_data_map;
    
    private Graph GGG;			//needed for the sort functions
    
    /** Unused data member.
     */    
    public int space;
    
    /** Sorter class for edges.
     */    
    protected class EdgeSorter implements SortFunction{
        /** Compares edges.
         * @param edge1 First edge compared.
         * @param edge2 Second edge compared.
         * @return Always false.
         */        
        public boolean is_less_than(Object edge1, Object edge2){
            return false;
        }
    }
    
    /** Sorter class for nodes.
     */    
    protected class NodeSorter implements SortFunction{
        /** Compares nodes.
         * @param node1 First node compared.
         * @param node2 Second node compared.
         * @return Always false.
         */        
        public boolean is_less_than(Object node1, Object node2){
            return false;
        }
    }
    
    /** Ordering class for this graph.
     */    
    protected class Orderer implements OrderingFunction{
        /** Returns the value of the given object.
         * @param item The object for which a value calculated.
         * @return Always 0.
         */        
        public int order(Object item){
            return 0;
        }
    }
    
    /** Map edge ordering class.
     */    
    protected class MapEdgeOrd1 implements OrderingFunction {
        /** Returns the index value of the source node of the given edge.
         * @param the_item The edge for which a value is requested.
         * @return The index value.
         */        
        public int order(Object the_item){
            return (((Edge)the_item).source().index());
        }
    }
    
    /** Map edge ordering class.
     */    
    protected class MapEdgeOrd2 implements OrderingFunction {
        //needed for make_map() in Graph :JL
        /** Returns the index value of the target node of the given edge.
         * @param the_item The edge for which a value is requested.
         * @return The index value.
         */        
        public int order(Object the_item){
            return (((Edge)the_item).target().index());
        }
    }
    
    //	protected static NodeSorter node_comparer;
    //	protected static EdgeSorter edge_comparer;
    //	protected static Orderer order_alg;
    /** Comparison function for comparing edges.
     */    
    protected SortFunction edge_comparer;
    /** Comparison function for comparing nodes.
     */    
    protected SortFunction node_comparer;
    /** Ordering function for sorts.
     */    
    protected OrderingFunction order_alg;
    /** Map edge ordering instance.
     */    
    protected MapEdgeOrd1   map_edge_ord1;
    /** Map edge ordering instance.
     */    
    protected MapEdgeOrd2   map_edge_ord2;
    
    
    
    /** Constructor.
     */    
    public Graph(){
        int sz1 = node_data_slots;
        int sz2 = edge_data_slots;
        max_node_index = -1;
        max_edge_index = -1;
        max_face_index = -1;
        parent = null;
        undirected = false;
        data_sz = new int[3];
        data_sz[0] = sz1;
        data_sz[1] = sz2;
        data_sz[2] = 0;
        e_list = new LinkedList();
        e_free = new LinkedList();
        h_list = new LinkedList();
        e_list_tmp = new LinkedList();
        v_list = new LinkedList();
        v_free = new LinkedList();
        v_list_tmp = new LinkedList();
        f_list = new LinkedList();
        f_free = new LinkedList();
        f_list_tmp = new LinkedList();
        
        free_data = new LinkedList[3];
        for(int i = 0; i < 3; i++) free_data[i] = new LinkedList();
        while (sz1 != 0) free_data[0].addFirst(new Integer(sz1--));
        while (sz2 != 0) free_data[1].addFirst(new Integer(sz2--));
        map_list = new LinkedList[3];
        for(int i = 0; i < 3; i++) map_list[i] = new LinkedList();
        node_data_map = new GraphMap(this,0);
        edge_data_map = new GraphMap(this,1);
        adj_iterator  = new GraphMap(this,0,0);
        FaceOf = null;
    }
    
    /** Constructor.
     * @param sz1 Number of nodes.
     * @param sz2 Number of Edges.
     */    
    public Graph(int sz1, int sz2){
        max_node_index = -1;
        max_edge_index = -1;
        max_face_index = -1;
        parent = null;
        undirected = false;
        data_sz = new int[3];
        data_sz[0] = sz1;
        data_sz[1] = sz2;
        data_sz[2] = 0;
        free_data = new LinkedList[3];
        while (sz1 != 0) free_data[0].addFirst(new Integer(sz1--));
        while (sz2 != 0) free_data[1].addFirst(new Integer(sz2--));
        map_list = new LinkedList[3];
        node_data_map = new GraphMap(this,0);
        edge_data_map = new GraphMap(this,1);
        adj_iterator = new GraphMap(this,0,0);
        FaceOf = null;
    }
    
    /** SubGraph constructor.
     * @param a Parent graph.
     * @param nl List of nodes for this graph.
     * @param el List of edges for this graph.
     */    
    public Graph(Graph a, LinkedList nl, LinkedList el){
        // construct subgraph (nl,el) of graph a
        
        parent = a;
        Node v,w;
        Edge e;
        Node[] N = new Node[a.max_node_index+1];
        
        //obs		forall(v,nl)
        for(int position = 0; position < nl.size(); position++){
            v = (Node)nl.get(position);
            if (v.graph_of() != parent)
                System.err.println("graph: illegal node in subgraph constructor");	//error_handler 1
            N[position] = new Node(v.getData());
        }
        
        //obs		forall(e,el)
        for(int position = 0; position < el.size(); position++){
            e = (Edge)el.get(position);
            v = e.source();
            w = e.target();
            if ( e.graph_of()!= parent || N[v.index()] == null || N[w.index()] == null )
                System.err.println("graph: illegal edge in subgraph constructor");	//error_handler 1
            
            new_edge(N[v.index()],e,N[w.index()],null,null,after,after);
            //obs			new_edge(N[v.index()],N[w.index()],e);
        }
        undirected = a.undirected;
        N = null;
    }
    
    /** SubGraph constructor.
     * @param G Parent graph.
     * @param el List of Edges for this graph.
     */    
    public Graph(Graph G, LinkedList el){
        // construct subgraph of graph G with edge set el
        Node  v,w;
        Edge  e;
        Node[] N = new Node[G.max_node_index+1];
        for(ListIterator nodes = G.v_list.listIterator(); nodes.hasNext();){
            v =(Node)nodes.next();
            N[v.index()] = null;