Utilities on Graphs. More...
Functions | |
| void | ComputeDigraph (const Groups &brd, HexColor color, PointToBitset &nbs) |
| Computes neighbours of all empty cells going through groups of color. | |
| bitset_t | BFS (HexPoint p, PointToBitset &group_nbs, bitset_t stopSet, int *distFromEdge=NULL, int *numShortestPathsThrough=NULL) |
| Performs BFS starting at the given point. | |
Variables | |
| static const int | NOT_REACHED = -1 |
| The distance from the start cell to all unreachable cells. | |
Utilities on Graphs.
| bitset_t GraphUtils::BFS | ( | HexPoint | p, | |
| PointToBitset & | group_nbs, | |||
| bitset_t | stopSet, | |||
| int * | distFromEdge = NULL, |
|||
| int * | numShortestPathsThrough = NULL | |||
| ) |
Performs BFS starting at the given point.
Distances from this point are stored in distFromEdge (whose memory has been already initialized, it is assumed). Bitset returned contains all empty cells reachable from p. The stopSet is a set of empty cells that may be visited but from which the BFS is not expanded. Note that the starting point will never be stopped, regardless of the stopSet.
Definition at line 37 of file GraphUtils.cpp.
References BITSETSIZE, HexAssert, NOT_REACHED, benzene_bitset< _Nb >::reset(), benzene_bitset< _Nb >::set(), and benzene_bitset< _Nb >::test().
Referenced by DfsSolver::SolveDecomposition().
| void GraphUtils::ComputeDigraph | ( | const Groups & | brd, | |
| HexColor | color, | |||
| PointToBitset & | nbs | |||
| ) |
Computes neighbours of all empty cells going through groups of color.
Neighbours of groups of color are also included in nbs.
Definition at line 14 of file GraphUtils.cpp.
References Groups::CaptainOf(), HexColorSetUtil::ColorOrEmpty(), EMPTY, Groups::Nbs(), and benzene_bitset< _Nb >::reset().
Referenced by DfsSolver::SolveDecomposition().
const int GraphUtils::NOT_REACHED = -1 [static] |
The distance from the start cell to all unreachable cells.
Definition at line 30 of file GraphUtils.hpp.
Referenced by BFS().