CellularAutomaton< ACellHolder > Class Template Reference

Implements the weighted cellular automaton algorithm. More...

#include <CellularAutomaton.h>

Classes
class	CycleException
	Type for the very basic exception signal used in the detection of cycles. More...

Public Member Functions
ACellHolder *	applyTo (const std::vector< ACellHolder * > &cellHolders, const std::vector< WeightedRelation< ACellHolder >> &cellHolderRelations) const
	Applies the cellular automaton to the collection of cells and its neighborhood. More...

Private Member Functions
Weight	getFinalCellState (ACellHolder *cellHolder, const std::vector< WeightedRelation< ACellHolder >> &cellHolderRelations) const
	Gets the cell state of the cell holder. More...
Weight	updateState (ACellHolder *cellHolder, const std::vector< WeightedRelation< ACellHolder >> &cellHolderRelations) const
	Updates the state of a cell considering all continuations recursively.
void	prepareCellFlags (const std::vector< ACellHolder * > &cellHolders) const
	Helper function to prepare the stats. More...

Detailed Description

template<class ACellHolder>
class Belle2::TrackFindingCDC::CellularAutomaton< ACellHolder >

Implements the weighted cellular automaton algorithm.

Definition at line 30 of file CellularAutomaton.h.

Member Function Documentation

applyTo()

ACellHolder* applyTo ( const std::vector< ACellHolder * > &  cellHolders, const std::vector< WeightedRelation< ACellHolder >> &  cellHolderRelations  ) const

inline

Applies the cellular automaton to the collection of cells and its neighborhood.

Parameters

cellHolders	The range based iterable containing the cells.
cellHolderRelations	The weighted relations between the cells.

Returns

The cell holder with the highest cell state found.

Definition at line 43 of file CellularAutomaton.h.

      {
        B2ASSERT("Expected the relations to be sorted",
                 std::is_sorted(cellHolderRelations.begin(), cellHolderRelations.end()));
 
        // Set all cell states to -inf and the non permanent flags to unset.
        prepareCellFlags(cellHolders);
 
        for (ACellHolder* cellHolder : cellHolders) {
          AutomatonCell& cell = cellHolder->getAutomatonCell();
          if (cell.hasMaskedFlag()) continue;
          if (cell.hasCycleFlag()) continue;
 
          if (not cell.hasAssignedFlag()) {
            // Mark this cell as a start point of a long path since we encountered it in
            // at the top level of the recursion.
            cell.setStartFlag();
            // The flag will be unset when it appears on the _to_ side of a relation.
          }
 
          try {
            // Assignes flags and the cell state
            getFinalCellState(cellHolder, cellHolderRelations);
          } catch (CycleException) {
            // TODO: Come up with some handeling for cycles.
            // For now we continue to look for long paths in the graph
            // hoping to find a part that does not enter the cycle.
 
            // Thoughts:
            // If there is a single cycle in the graph we might be able to break it at some point.
            // However, if there are multiple cycles intertwined things get very tricky.
            // But can we actually distinguish the two situations?
          }
        }
 
        auto lessStartCellState = [](ACellHolder * lhs, ACellHolder * rhs) {
          const AutomatonCell& lhsCell = lhs->getAutomatonCell();
          const AutomatonCell& rhsCell = rhs->getAutomatonCell();
          return (std::make_pair(lhsCell.hasStartFlag(), lhsCell.getCellState()) <
                  std::make_pair(rhsCell.hasStartFlag(), rhsCell.getCellState()));
        };
 
        auto itStartCellHolder =
          std::max_element(cellHolders.begin(), cellHolders.end(), lessStartCellState);
        if (itStartCellHolder == cellHolders.end()) return nullptr;
        if (not(*itStartCellHolder)->getAutomatonCell().hasStartFlag()) return nullptr;
        return *itStartCellHolder;
      }

getFinalCellState()

Weight getFinalCellState ( ACellHolder *  cellHolder, const std::vector< WeightedRelation< ACellHolder >> &  cellHolderRelations  ) const

inlineprivate

Gets the cell state of the cell holder.

Determines it if necessary traversing the graph. Throws CycleException if it encounters a cycle in the graph.

Definition at line 99 of file CellularAutomaton.h.

prepareCellFlags()

void prepareCellFlags ( const std::vector< ACellHolder * > &  cellHolders ) const

inlineprivate

Helper function to prepare the stats.

Clears all temporary cell flags and sets the cell state to minus infinity.

Definition at line 201 of file CellularAutomaton.h.

---

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

• tracking/trackFindingCDC/ca/include/CellularAutomaton.h