template<typename TIncidentEdges, typename TOpposite, typename TContainer, typename TAccumulator, typename TMark, typename TSolution, typename TPathCut>
class Diades::Graph::GraphSearch< TIncidentEdges, TOpposite, TContainer, TAccumulator, TMark, TSolution, TPathCut >
This class is the based class to implement derived seraches on graphs like BFS and DFS. This class is a template with several template attributes, listed below:
- TIncidentEdges is a class that implements the graph exploration. It has a constructor that takes as input the underlying graph 'g' (type TIncidentEdges::Graph), a search node 'n' (type TIncidentEdges::Node) and a TPathCut object 'cut' (see TPathCut for details). Two methods are then implenented (begin(),end()) that returns the set of edges (type TIncidentEdges::Edge) that can be triggered from the search node 'n' based on the graph 'g' that are not pruned by 'cut'. TIncidentEdges::Iterator::value_type must be TIncidentEdges::Edge
- TOpposite is a class that implements the generation of the TIncidentEdges::Node associated to a TIncidentEdges::Edge that is the opposite of a given TIncidentEdges::Node (either the source or target of the TIncidentEdges::Edge). TOpposite must implement the method 'const TIncidentEdges::Node & next(const TIncidentEdges::Edge &, const TIncidentEdges::Node).
- TContainer is the type of the container for the initialisation of the search. A TContainer must contains TIncidentEdges::Node objects. A TContainer 'container' must implement the c++11 for-loop for(const TIncidentEdges::Node & node : container) (any stl-container like list<TIncidentEdges::Node>, vector<TIncidentEdges::Node> will do the job).
- TAccumulator is the type of the container for gathering (accumulating) the result of the search (a collection of TIncidentEdges::Node). It must implement clear() and push_back() like (like vector<TIncidentEdges::Node>, deque<TIncidentEdges::Node> and list<TIncidentEdges::Node>)
- TMark must implement the marking functions when visiting TIncidentEdges::Node that are bool isMarked(const TIncidentEdges::Node &) and mark(const TIncidentEdges::Node &)
- TSolution checks whether a given TIncidentEdges::Node is a solution of the search, it must implement bool isSolution(const TIncidentEdges::Node &)
- TPathCut checks whether it is sure that there will be no solution after the given node. No requirement but need to be called by the constructor of TIncidentEdges
Definition at line 51 of file GraphSearch.hh.
template<typename TIncidentEdges , typename TOpposite , typename TContainer , typename TAccumulator , typename TMark , typename TSolution , typename TPathCut >
- Returns
- the current results of the search
- Postcondition
- !updated()
Definition at line 100 of file GraphSearch.hh.
References Diades::Graph::GraphSearch< TIncidentEdges, TOpposite, TContainer, TAccumulator, TMark, TSolution, TPathCut >::_results, and Diades::Graph::GraphSearch< TIncidentEdges, TOpposite, TContainer, TAccumulator, TMark, TSolution, TPathCut >::_updated.
template<typename TIncidentEdges , typename TOpposite , typename TContainer , typename TAccumulator , typename TMark , typename TSolution , typename TPathCut >
| virtual void Diades::Graph::GraphSearch< TIncidentEdges, TOpposite, TContainer, TAccumulator, TMark, TSolution, TPathCut >::initialize |
( |
| ) |
|
|
inlinevirtual |
initialisation of the search
- Postcondition
- !updated()
Reimplemented in Diades::Utils::GFS< TIncidentEdges, TOpposite, TContainer, TAccumulator, TMark, TSolution, TPathCut >, Diades::Graph::DFS< TIncidentEdges, TOpposite, TContainer, TAccumulator, TMark, TSolution, TPathCut >, and Diades::Graph::BFS< TIncidentEdges, TOpposite, TContainer, TAccumulator, TMark, TSolution, TPathCut >.
Definition at line 111 of file GraphSearch.hh.
References Diades::Graph::GraphSearch< TIncidentEdges, TOpposite, TContainer, TAccumulator, TMark, TSolution, TPathCut >::_results, and Diades::Graph::GraphSearch< TIncidentEdges, TOpposite, TContainer, TAccumulator, TMark, TSolution, TPathCut >::_updated.
Referenced by Diades::Utils::GFS< TIncidentEdges, TOpposite, TContainer, TAccumulator, TMark, TSolution, TPathCut >::initialize().
template<typename TIncidentEdges , typename TOpposite , typename TContainer , typename TAccumulator , typename TMark , typename TSolution , typename TPathCut >
| bool Diades::Graph::GraphSearch< TIncidentEdges, TOpposite, TContainer, TAccumulator, TMark, TSolution, TPathCut >::updated |
( |
| ) |
const |
|
inline |
template<typename TIncidentEdges , typename TOpposite , typename TContainer , typename TAccumulator , typename TMark , typename TSolution , typename TPathCut >
Definition at line 133 of file GraphSearch.hh.
Referenced by Diades::Utils::GFS< TIncidentEdges, TOpposite, TContainer, TAccumulator, TMark, TSolution, TPathCut >::next(), and Diades::Utils::GFS< TIncidentEdges, TOpposite, TContainer, TAccumulator, TMark, TSolution, TPathCut >::popStack().
template<typename TIncidentEdges , typename TOpposite , typename TContainer , typename TAccumulator , typename TMark , typename TSolution , typename TPathCut >
Definition at line 129 of file GraphSearch.hh.
Referenced by Diades::Utils::GFS< TIncidentEdges, TOpposite, TContainer, TAccumulator, TMark, TSolution, TPathCut >::next(), and Diades::Utils::GFS< TIncidentEdges, TOpposite, TContainer, TAccumulator, TMark, TSolution, TPathCut >::popStack().
template<typename TIncidentEdges , typename TOpposite , typename TContainer , typename TAccumulator , typename TMark , typename TSolution , typename TPathCut >
Definition at line 128 of file GraphSearch.hh.
Referenced by Diades::Utils::GFS< TIncidentEdges, TOpposite, TContainer, TAccumulator, TMark, TSolution, TPathCut >::setVisited(), and Diades::Utils::GFS< TIncidentEdges, TOpposite, TContainer, TAccumulator, TMark, TSolution, TPathCut >::visited().
template<typename TIncidentEdges , typename TOpposite , typename TContainer , typename TAccumulator , typename TMark , typename TSolution , typename TPathCut >
Definition at line 131 of file GraphSearch.hh.
Referenced by Diades::Utils::GFS< TIncidentEdges, TOpposite, TContainer, TAccumulator, TMark, TSolution, TPathCut >::next(), and Diades::Utils::GFS< TIncidentEdges, TOpposite, TContainer, TAccumulator, TMark, TSolution, TPathCut >::popStack().
template<typename TIncidentEdges , typename TOpposite , typename TContainer , typename TAccumulator , typename TMark , typename TSolution , typename TPathCut >
Definition at line 134 of file GraphSearch.hh.
Referenced by Diades::Graph::GraphSearch< TIncidentEdges, TOpposite, TContainer, TAccumulator, TMark, TSolution, TPathCut >::currentResults(), Diades::Graph::GraphSearch< TIncidentEdges, TOpposite, TContainer, TAccumulator, TMark, TSolution, TPathCut >::initialize(), and Diades::Utils::GFS< TIncidentEdges, TOpposite, TContainer, TAccumulator, TMark, TSolution, TPathCut >::next().
template<typename TIncidentEdges , typename TOpposite , typename TContainer , typename TAccumulator , typename TMark , typename TSolution , typename TPathCut >
template<typename TIncidentEdges , typename TOpposite , typename TContainer , typename TAccumulator , typename TMark , typename TSolution , typename TPathCut >
Definition at line 127 of file GraphSearch.hh.
Referenced by Diades::Graph::GraphSearch< TIncidentEdges, TOpposite, TContainer, TAccumulator, TMark, TSolution, TPathCut >::currentResults(), Diades::Graph::GraphSearch< TIncidentEdges, TOpposite, TContainer, TAccumulator, TMark, TSolution, TPathCut >::initialize(), Diades::Utils::GFS< TIncidentEdges, TOpposite, TContainer, TAccumulator, TMark, TSolution, TPathCut >::next(), and Diades::Graph::GraphSearch< TIncidentEdges, TOpposite, TContainer, TAccumulator, TMark, TSolution, TPathCut >::updated().
