00001 //---------------------------------------------------------------------------- 00002 /** @file GraphUtils.hpp 00003 */ 00004 //---------------------------------------------------------------------------- 00005 00006 #ifndef GRAPHUTILS_HPP 00007 #define GRAPHUTILS_HPP 00008 00009 #include "Hex.hpp" 00010 #include "Groups.hpp" 00011 00012 _BEGIN_BENZENE_NAMESPACE_ 00013 00014 //---------------------------------------------------------------------------- 00015 00016 class HexBoard; 00017 00018 /** Utilities on Graphs. */ 00019 namespace GraphUtils 00020 { 00021 /** Computes neighbours of all empty cells going through groups of 00022 color. Neighbours of groups of color are also included in 00023 nbs. */ 00024 void ComputeDigraph(const Groups& brd, HexColor color, 00025 PointToBitset& nbs); 00026 00027 //---------------------------------------------------------------------- 00028 00029 /** The distance from the start cell to all unreachable cells. */ 00030 static const int NOT_REACHED = -1; 00031 00032 /** Performs BFS starting at the given point. Distances from this 00033 point are stored in distFromEdge (whose memory has been 00034 already initialized, it is assumed). Bitset returned contains 00035 all empty cells reachable from p. The stopSet is a set of 00036 empty cells that may be visited but from which the BFS is not 00037 expanded. Note that the starting point will never be stopped, 00038 regardless of the stopSet. 00039 */ 00040 bitset_t BFS(HexPoint p, PointToBitset& group_nbs, bitset_t stopSet, 00041 int* distFromEdge=NULL, int* numShortestPathsThrough=NULL); 00042 00043 } 00044 00045 //---------------------------------------------------------------------------- 00046 00047 _END_BENZENE_NAMESPACE_ 00048 00049 #endif // GRAPHUTILS_HPP