CellularPathFollower< ACellHolder > Class Template Reference

Implements to pick up of the highest value path in neighborhood Following high value paths can be done two ways. More...

#include <CellularPathFollower.h>

Static Public Member Functions
static std::vector< Path< ACellHolder > >	followAll (const std::vector< ACellHolder * > &cellHolders, const std::vector< WeightedRelation< ACellHolder > > &cellHolderRelations, Weight minStateToFollow=-INFINITY)
	Follow paths from all start cells marked with the start flag.
static Path< ACellHolder >	followSingle (ACellHolder *startCellHolder, const std::vector< WeightedRelation< ACellHolder > > &cellHolderRelations, Weight minStateToFollow=-INFINITY)
	Follows a single maximal path starting with the given start cell.

Static Private Member Functions
static void	growAllPaths (Path< ACellHolder > &path, const std::vector< WeightedRelation< ACellHolder > > &cellHolderRelations, std::vector< Path< ACellHolder > > &paths)
	Helper function for recursively growing paths.
static bool	validStartCell (const AutomatonCell &automatonCell, Weight minStateToFollow)
	Helper function to determine, if the cell has all flags indicating to be a start cell and that its state exceeds the minimal requirement.
static bool	isHighestContinuation (const WeightedRelation< ACellHolder > &relation)
	Helper function determining if the given neighbor is one of the best to be followed.
static bool	isHighestContinuation (const ACellHolder &cellHolder, Weight relationWeight, const ACellHolder &neighborCellHolder)
	Helper function determining if the given neighbor is one of the best to be followed.

Detailed Description

template<class ACellHolder>
class Belle2::TrackingUtilities::CellularPathFollower< ACellHolder >

Implements to pick up of the highest value path in neighborhood Following high value paths can be done two ways.

First construct a single path that has the highest value of all. This carried out by follow single which uses the highest cell returned by the cellular automaton. Second construct all paths which are maximal. A maximal path means that there is no longer path including this path. If there are many disjoint paths this is the way to get them. However you most certainly pick up a lot of elements twice if there are many start culminating into a common long path. This is carried out recursively by followAll over the start cells marked with start flag.

Definition at line 37 of file CellularPathFollower.h.

Member Function Documentation

followAll()

template<class ACellHolder>

static std::vector< Path< ACellHolder > > followAll ( const std::vector< ACellHolder * > & cellHolders, const std::vector< WeightedRelation< ACellHolder > > & cellHolderRelations, Weight minStateToFollow = -INFINITY )

inlinestatic

Follow paths from all start cells marked with the start flag.

Definition at line 41 of file CellularPathFollower.h.

      {
        B2ASSERT("Expected the relations to be sorted",
                 std::is_sorted(cellHolderRelations.begin(), cellHolderRelations.end()));
 
        // Result
        std::vector<Path<ACellHolder> > paths;
 
        // Stack for back tracking
        Path<ACellHolder> path;
 
        for (ACellHolder* cellHolder : cellHolders) {
          const AutomatonCell& automatonCell = cellHolder->getAutomatonCell();
 
          if (validStartCell(automatonCell, minStateToFollow)) {
            // Cell marks a start point of a path
 
            // Start new path
            path.clear();
 
            // Insert a pointer to the cell into the path
            path.push_back(cellHolder);
 
            // Recursively grow the path
            growAllPaths(path, cellHolderRelations, paths);
            path.pop_back();
          }
        }
        return paths;
      }

followSingle()

template<class ACellHolder>

static Path< ACellHolder > followSingle ( ACellHolder * startCellHolder, const std::vector< WeightedRelation< ACellHolder > > & cellHolderRelations, Weight minStateToFollow = -INFINITY )

inlinestatic

Follows a single maximal path starting with the given start cell.

If the start cell is nullptr or has a state lower than the minimum state to follow an empty vector is returned.

Definition at line 80 of file CellularPathFollower.h.

      {
        Path<ACellHolder> path;
        if (not startCellHolder) return path;
        const AutomatonCell& startCell = startCellHolder->getAutomatonCell();
        if (not validStartCell(startCell, minStateToFollow)) return path;
 
        // Start new path
        path.reserve(20); // Just a guess
 
        // Insert a pointer to the cell into the path
        path.push_back(startCellHolder);
        bool grew = true;
        while (grew) {
          grew = false;
          ACellHolder* cellHolder = path.back();
 
          auto continuations = asRange(std::equal_range(cellHolderRelations.begin(),
                                                        cellHolderRelations.end(),
                                                        cellHolder));
 
          for (const WeightedRelation<ACellHolder>& relation : continuations) {
            // cppcheck-suppress useStlAlgorithm
            if (isHighestContinuation(relation)) {
              ACellHolder* neighbor = relation.getTo();
              path.push_back(neighbor);
              grew = true;
              break;
            }
          }
        }
        return path;
      }

growAllPaths()

template<class ACellHolder>

static void growAllPaths ( Path< ACellHolder > & path, const std::vector< WeightedRelation< ACellHolder > > & cellHolderRelations, std::vector< Path< ACellHolder > > & paths )

inlinestaticprivate

Helper function for recursively growing paths.

Parameters

[in]	path	Current path to be extended
[in]	cellHolderRelations	Considered relations to follow to extend the path
[out]	paths	Longest paths generated

Definition at line 123 of file CellularPathFollower.h.

      {
        auto growPathByRelation = [&](const WeightedRelation<ACellHolder>& neighborRelation) {
          if (!isHighestContinuation(neighborRelation)) return false;
          ACellHolder* neighbor(neighborRelation.getTo());
          path.push_back(neighbor);
          growAllPaths(path, cellHolderRelations, paths);
          path.pop_back();
          return true;
        };
 
        ACellHolder* lastCellHolder = path.back();
 
        auto continuations = asRange(std::equal_range(cellHolderRelations.begin(),
                                                      cellHolderRelations.end(),
                                                      lastCellHolder));
        int nRelationsUsed = std::count_if(continuations.begin(),
                                           continuations.end(),
                                           growPathByRelation);
 
        if (nRelationsUsed == 0) {
          // end point of the recursion copy maximal path to the vector.
          paths.push_back(path);
        }
      }

isHighestContinuation() [1/2]

template<class ACellHolder>

static bool isHighestContinuation ( const ACellHolder & cellHolder, Weight relationWeight, const ACellHolder & neighborCellHolder )

inlinestaticprivate

Helper function determining if the given neighbor is one of the best to be followed.

Since this is an algebraic property no comparison to the other alternatives is necessary.

Definition at line 187 of file CellularPathFollower.h.

      {
        const AutomatonCell& automatonCell = cellHolder.getAutomatonCell();
        const AutomatonCell& neighborAutomatonCell = neighborCellHolder.getAutomatonCell();
 
        return not neighborAutomatonCell.hasCycleFlag() and not neighborAutomatonCell.hasMaskedFlag() and
               (automatonCell.getCellState() ==
                (neighborAutomatonCell.getCellState() + relationWeight + automatonCell.getCellWeight()));
      }

isHighestContinuation() [2/2]

template<class ACellHolder>

static bool isHighestContinuation ( const WeightedRelation< ACellHolder > & relation )

inlinestaticprivate

Helper function determining if the given neighbor is one of the best to be followed.

Since this is an algebraic property on comparison to the other alternatives is necessary.

Definition at line 169 of file CellularPathFollower.h.

      {
        const ACellHolder* cellHolderPtr(relation.getFrom());
        const ACellHolder* neighborCellHolderPtr(relation.getTo());
 
        if (not cellHolderPtr or not neighborCellHolderPtr) return false;
 
        const ACellHolder& cellHolder = *cellHolderPtr;
        Weight relationWeight = relation.getWeight();
        const ACellHolder& neighborCellHolder = *neighborCellHolderPtr;
 
        return isHighestContinuation(cellHolder, relationWeight, neighborCellHolder);
      }

validStartCell()

template<class ACellHolder>

static bool validStartCell ( const AutomatonCell & automatonCell, Weight minStateToFollow )

inlinestaticprivate

Helper function to determine, if the cell has all flags indicating to be a start cell and that its state exceeds the minimal requirement.

Definition at line 155 of file CellularPathFollower.h.

      {
        return
          automatonCell.hasStartFlag() and
          not automatonCell.hasMaskedFlag() and
          not automatonCell.hasCycleFlag() and
          minStateToFollow <= automatonCell.getCellState();
      }

---

The documentation for this class was generated from the following file:

• tracking/trackingUtilities/ca/include/CellularPathFollower.h