Belle II Software development
Public Member Functions | Private Member Functions | Static Private Member Functions | List of all members
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>

Public Member Functions

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

Private Member Functions

void growAllPaths (Path< ACellHolder > &path, const std::vector< WeightedRelation< ACellHolder > > &cellHolderRelations, std::vector< Path< ACellHolder > > &paths) const
 Helper function for recursively growing paths.
 

Static Private Member Functions

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 (ACellHolder &cellHolder, Weight relationWeight, ACellHolder &neighborCellHolder)
 Helper function determining if the given neighbor is one of the best to be followed.
 

Detailed Description

template<class ACellHolder>
class Belle2::TrackFindingCDC::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 38 of file CellularPathFollower.h.

Member Function Documentation

◆ followAll()

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

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

Definition at line 42 of file CellularPathFollower.h.

46 {
47 B2ASSERT("Expected the relations to be sorted",
48 std::is_sorted(cellHolderRelations.begin(), cellHolderRelations.end()));
49
50 // Result
51 std::vector<Path<ACellHolder> > paths;
52
53 // Stack for back tracking
54 Path<ACellHolder> path;
55
56 for (ACellHolder* cellHolder : cellHolders) {
57 const AutomatonCell& automatonCell = cellHolder->getAutomatonCell();
58
59 if (validStartCell(automatonCell, minStateToFollow)) {
60 // Cell marks a start point of a path
61
62 // Start new path
63 path.clear();
64
65 // Insert a pointer to the cell into the path
66 path.push_back(cellHolder);
67
68 // Recursively grow the path
69 growAllPaths(path, cellHolderRelations, paths);
70 path.pop_back();
71 }
72 }
73 return paths;
74 }
Belle2::TrackFindingCDC::CellularPathFollower::growAllPaths
void growAllPaths(Path< ACellHolder > &path, const std::vector< WeightedRelation< ACellHolder > > &cellHolderRelations, std::vector< Path< ACellHolder > > &paths) const
Helper function for recursively growing paths.
Definition: CellularPathFollower.h:126
Belle2::TrackFindingCDC::CellularPathFollower::validStartCell
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 st...
Definition: CellularPathFollower.h:158

◆ followSingle()

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

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 81 of file CellularPathFollower.h.

84 {
85 assert(std::is_sorted(cellHolderRelations.begin(), cellHolderRelations.end()));
86
87 Path<ACellHolder> path;
88 if (not startCellHolder) return path;
89 const AutomatonCell& startCell = startCellHolder->getAutomatonCell();
90 if (not validStartCell(startCell, minStateToFollow)) return path;
91
92 // Start new path
93 path.reserve(20); // Just a guess
94
95 // Insert a pointer to the cell into the path
96 path.push_back(startCellHolder);
97 bool grew = true;
98 while (grew) {
99 grew = false;
100 ACellHolder* cellHolder = path.back();
101
102 auto continuations = asRange(std::equal_range(cellHolderRelations.begin(),
103 cellHolderRelations.end(),
104 cellHolder));
105
106 for (const WeightedRelation<ACellHolder>& relation : continuations) {
107 // cppcheck-suppress useStlAlgorithm
108 if (isHighestContinuation(relation)) {
109 ACellHolder* neighbor = relation.getTo();
110 path.push_back(neighbor);
111 grew = true;
112 break;
113 }
114 }
115 }
116 return path;
117 }
Belle2::TrackFindingCDC::CellularPathFollower::isHighestContinuation
static bool isHighestContinuation(const WeightedRelation< ACellHolder > &relation)
Helper function determining if the given neighbor is one of the best to be followed.
Definition: CellularPathFollower.h:172

◆ growAllPaths()

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

Helper function for recursively growing paths.

Parameters
[in]pathCurrent path to be extended
[in]cellHolderRelationsConsidered relations to follow to extend the path
[out]pathsLongest paths generated

Definition at line 126 of file CellularPathFollower.h.

129 {
130 auto growPathByRelation = [&](const WeightedRelation<ACellHolder>& neighborRelation) {
131 if (not this->isHighestContinuation(neighborRelation)) return false;
132 ACellHolder* neighbor(neighborRelation.getTo());
133 path.push_back(neighbor);
134 this->growAllPaths(path, cellHolderRelations, paths);
135 path.pop_back();
136 return true;
137 };
138
139 ACellHolder* lastCellHolder = path.back();
140
141 auto continuations = asRange(std::equal_range(cellHolderRelations.begin(),
142 cellHolderRelations.end(),
143 lastCellHolder));
144 int nRelationsUsed = std::count_if(continuations.begin(),
145 continuations.end(),
146 growPathByRelation);
147
148 if (nRelationsUsed == 0) {
149 // end point of the recursion copy maximal path to the vector.
150 paths.push_back(path);
151 }
152 }

◆ isHighestContinuation() [1/2]

static bool isHighestContinuation ( ACellHolder &  cellHolder,
Weight  relationWeight,
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 190 of file CellularPathFollower.h.

193 {
194 const AutomatonCell& automatonCell = cellHolder.getAutomatonCell();
195 const AutomatonCell& neighborAutomatonCell = neighborCellHolder.getAutomatonCell();
196
197 return not neighborAutomatonCell.hasCycleFlag() and not neighborAutomatonCell.hasMaskedFlag() and
198 (automatonCell.getCellState() ==
199 (neighborAutomatonCell.getCellState() + relationWeight + automatonCell.getCellWeight()));
200 }

◆ isHighestContinuation() [2/2]

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 172 of file CellularPathFollower.h.

173 {
174 ACellHolder* cellHolderPtr(relation.getFrom());
175 ACellHolder* neighborCellHolderPtr(relation.getTo());
176
177 if (not cellHolderPtr or not neighborCellHolderPtr) return false;
178
179 ACellHolder& cellHolder = *cellHolderPtr;
180 Weight relationWeight = relation.getWeight();
181 ACellHolder& neighborCellHolder = *neighborCellHolderPtr;
182
183 return isHighestContinuation(cellHolder, relationWeight, neighborCellHolder);
184 }

◆ validStartCell()

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 158 of file CellularPathFollower.h.

160 {
161 return
162 automatonCell.hasStartFlag() and
163 not automatonCell.hasMaskedFlag() and
164 not automatonCell.hasCycleFlag() and
165 minStateToFollow <= automatonCell.getCellState();
166 }
The documentation for this class was generated from the following file: