#ifndef __ROADMAP_H__
#define __ROADMAP_H__

#include <string>
#include <vector>

using std::vector;
using std::string;

class AbstractRoadMap {
  public:
    /* Add a road that connects city1 with city2.  All roads are bidirectional.
     */
    virtual void addRoad(const string & city1, const string & city2) = 0;

    /* Add a road that goes through all the cities in the cities
     * vector.  In other words, add a road between each pair of
     * adjacent cities in the vector.
     */
    virtual void addRoad(const vector<string> & cities) = 0;

    /* Clear the road map completely.
     */
    virtual void clear() = 0;

    /* Return the number of neighboring cities for the given city, or
     * -1 if the given city is not in the map.
     */
    virtual int neighborCountForCity(const string & city) const = 0;

    /* Return true if and only if there is a path that starts from a
     * city X and then leads back to X by taking each no more than
     * once.
     */
    virtual bool hasLoop() const = 0;

    /* Return true if there is a path from city1 to city2.
     */
    virtual bool reachable(const string & city1, const string & city2) const = 0;

    /* Return the number of "islands" in the map. An island is a
     * maximal group of cities that are reachable from each other.
     * All cities in an island are reachable from each other, but they
     * are not reachable from any another city from another island.
     */
    virtual int countIslands() const = 0;

    /* Destructor 
     */
    virtual ~AbstractRoadMap() {};
};

/* Return a new road map object that implements AbstractRoadMap. The
 * new road map must be empty, meaning that it does not contain any
 * road or city. 
*/
extern AbstractRoadMap * createRoadMap();

#endif // __ROADMAP_H__