/* GraphView.java
 * =========================================================================
 * This file is part of the GrInvIn project - http://www.grinvin.org
 * 
 * Copyright (C) 2005-2008 Universiteit Gent
 * 
 * This program is free software; you can redistribute it and/or modify
 * it under the terms of the GNU General Public License as published by
 * the Free Software Foundation; either version 2 of the License, or (at
 * your option) any later version.
 * 
 * This program is distributed in the hope that it will be useful, but
 * WITHOUT ANY WARRANTY; without even the implied warranty of
 * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the GNU
 * General Public License for more details.
 * 
 * A copy of the GNU General Public License can be found in the file
 * LICENSE.txt provided with the source distribution of this program (see
 * the META-INF directory in the source jar). This license can also be
 * found on the GNU website at http://www.gnu.org/licenses/gpl.html.
 * 
 * If you did not receive a copy of the GNU General Public License along
 * with this program, contact the lead developer, or write to the Free
 * Software Foundation, Inc., 51 Franklin Street, Fifth Floor, Boston, MA
 * 02110-1301, USA.
 */

package org.grinvin.graphs;

import java.util.Iterator;

/**
 * <p>
 * Interface representing a read-only view of an abstract graph. An abstract
 * graph is a collection of vertices
 * (of type {@link Vertex}) connected by edges (of type {@link Edge}).
 * The endpoints of edges that belong to a graph must be vertices that also belong
 * to the graph.
 * </p>
 *
 * <p>
 * This interface only provides read access to the graph. Use the interface
 * {@link Graph} if you also need write access.
 * </p>
 */
public interface GraphView {
    
    /**
     * Returns the order, i.e. the number of vertices, of the graph.
     */
    public int getNumberOfVertices();
    
    /**
     * Returns the vertex with the given index in the graph. Vertices in a graph
     * are indexed in the range 0..n-1 where n is the number of vertices.
     * Note that the index of a vertex is allowed to change whenever
     * the graph is modified. Every graph should honour the following invariant
     * whenever {@code index} is in the correct range:
     * <pre>
     *    getVertex(index).getIndex() == index
     * </pre>
     * @throws IndexOutOfBoundsException when the index is not in the range
     * 0..n-1 where n is the number of vertices of the graph.
     */
    public Vertex getVertex(int index);
    
    /**
     * Returns the size, i.e. the number of edges, of the graph.
     */
    public int getNumberOfEdges();
    
    /**
     * Iterator over all edges of this graph.
     */
    public Iterator<Edge> edgeIterator();
    
    /**
     * Set of edges of this graph. This method returns an {@link Iterable}
     * and not a {@link java.util.Set} so its main purpose is to be used in
     * a 'for each' loop:
     * <pre>
     *    for (Edge e: graph.edges()) {
     *        // do something with e
     *    }
     * </pre>
     */
    public Iterable<Edge> edges();
    
    /**
     * Iterator over all vertices of this graph. If this iterator supports
     * the {@code remove} operation, it should also remove all edges incident
     * with the vertex that is removed.
     */
    public Iterator<Vertex> vertexIterator();
    
    /**
     * Set of vertices of this graph. This method returns an {@link Iterable}
     * and not a {@link java.util.Set} so its main purpose is to be used in
     * a 'for each' loop:
     * <pre>
     *    for (Vertex v: graph.vertices()) {
     *        // do something with v
     *    }
     * </pre>
     */
    public Iterable<Vertex> vertices();
    
    /**
     * Does the given vertex belong to this graph?
     */
    public boolean contains(Vertex vertex);
    
    /**
     * Does the given edge belong to this graph?
     */
    public boolean contains(Edge edge);
    
    /**
     * Return an edge joining the given vertices, or {@code null}
     * when no such edge exists.
     * @return an edge having {@code first} as its first endpoint and
     * {@code second} as its second endpoint.
     */
    public Edge getEdge(Vertex first, Vertex second);
    
    /**
     * Check whether the given vertices are adjacent in this graph.
     * Should return the same result as
     * <pre>
     *    getEdge (first,second) != null || getEgde (second,first) != null
     * </pre>
     */
    public boolean areAdjacent(Vertex v1, Vertex v2);
    
}