60 lines
1.7 KiB
C++
60 lines
1.7 KiB
C++
#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__
|