TrigCompositeUtils::NavGraph Class Reference

Structure to hold a transient Directed Acyclic Graph (DAG) structure. NavGraph is populated from, and forms a sub-graph over the full Run 3 trigger navigation graph in a single event. Requirements on specific chains, and the specification of allowable graph entry-points are considered in the construction of the NavGraph sub-graph. Once one of these sub-graphs is fully populated to a given specification, it is searched by the feature-retrieval code to find features. More...

#include <NavGraph.h>

Collaboration diagram for TrigCompositeUtils::NavGraph:

Public Member Functions
	NavGraph ()
	Construct an empty NavGraph. More...
	~NavGraph ()=default
	Destruct a NavGraph, default. More...
	NavGraph (const NavGraph &obj)=delete
	Prevent copy of a NavGraphNode. More...
	NavGraph (NavGraph &&obj)=delete
	Prevent move of a NavGraphNode. More...
void	addNode (const Decision *node, const Decision *comingFrom=nullptr)
	Add a new NavGraphNode which shadows the xAOD Decision object "node" from the full navigation graph. More...
const std::vector< NavGraphNode * > &	finalNodes () const
	Get all final nodes. More...
std::vector< NavGraphNode * >	allNodes ()
	Get all nodes. More...
size_t	nodes () const
size_t	edges () const
std::vector< const Decision * >	thin ()
	Perform thinning. More...
void	printAllPaths (MsgStream &log, MSG::Level msgLevel=MSG::VERBOSE) const
	Helper function. More...

Private Member Functions
void	rewireNodeForRemoval (NavGraphNode &toBeDeleted)
	Take all seeds (parents) of the supplied node and connect them to all the node's children. More...
void	recursivePrintNavPath (const NavGraphNode &nav, size_t level, MsgStream &log, MSG::Level msgLevel) const
	@bried Internal helper function. More...

Private Attributes
std::map< const Decision *, size_t >	m_nodePositionMap
	Map of Decision pointer and index of the node(that contains the Decision) in m_nodes. More...
std::vector< std::unique_ptr< NavGraphNode > >	m_nodes
	Vector of unique pointers to nodes in the graph. More...
std::vector< NavGraphNode * >	m_finalNodes
	Entry points into the navigation graph. More...
size_t	m_edges
	Statistics on the number of edges, connecting the nodes in the graph. More...

Detailed Description

Structure to hold a transient Directed Acyclic Graph (DAG) structure. NavGraph is populated from, and forms a sub-graph over the full Run 3 trigger navigation graph in a single event. Requirements on specific chains, and the specification of allowable graph entry-points are considered in the construction of the NavGraph sub-graph. Once one of these sub-graphs is fully populated to a given specification, it is searched by the feature-retrieval code to find features.

Definition at line 111 of file NavGraph.h.

Constructor & Destructor Documentation

NavGraph() [1/3]

TrigCompositeUtils::NavGraph::NavGraph

(

)

Construct an empty NavGraph.

Definition at line 74 of file NavGraph.cxx.

                     : m_nodePositionMap(), m_nodes(), m_finalNodes(), m_edges(0) {
  }

~NavGraph()

TrigCompositeUtils::NavGraph::~NavGraph ( )

default

Destruct a NavGraph, default.

NavGraph() [2/3]

TrigCompositeUtils::NavGraph::NavGraph ( const NavGraph &  obj )

delete

Prevent copy of a NavGraphNode.

NavGraph() [3/3]

TrigCompositeUtils::NavGraph::NavGraph ( NavGraph &&  obj )

delete

Prevent move of a NavGraphNode.

Member Function Documentation

addNode()

void TrigCompositeUtils::NavGraph::addNode	(	const Decision *	node,
		const Decision *	comingFrom = nullptr
	)

Add a new NavGraphNode which shadows the xAOD Decision object "node" from the full navigation graph.

Parameters

[in]	node	The xAOD Decision object which the new node will shadow. Will not cause duplication if node has already been added.
[in]	comingFrom	If not null, used to indicate which xAOD Decision object was the seed of "node". This is used to form an edge in the graph. Alternately, if comingFrom is null then "node" is taken as a final node (one of the locations from which the graph should be explored) and hence is added to the finalNodes vector.

Definition at line 78 of file NavGraph.cxx.

                                                                         {
    // m_node is a vector to preserve iteration ordering for stable output.
    // m_nodePositionMap assures that there is no duplicated NavGraphNode
    // with the same Decision pointer.
    auto nodePairIt = m_nodePositionMap.insert(std::make_pair(node, m_nodes.size()));
    if (nodePairIt.second) m_nodes.push_back( std::unique_ptr<NavGraphNode>(new NavGraphNode(node)) );
    NavGraphNode& nodeObj = *m_nodes[nodePairIt.first->second];
 
    if (comingFrom == nullptr) { // Not coming from anywhere - hence a final node.
      m_finalNodes.push_back( &nodeObj );
    } else {
      auto comingFromPairIt = m_nodePositionMap.insert( std::make_pair(comingFrom, m_nodes.size()) );
      if (comingFromPairIt.second) m_nodes.push_back( std::unique_ptr<NavGraphNode>(new NavGraphNode(comingFrom)) );
      NavGraphNode& comingFromNodeObj = *m_nodes[comingFromPairIt.first->second];
      const bool newEdge = comingFromNodeObj.linksTo( &nodeObj );
      if (newEdge) {
        ++m_edges;
      }
    }
  }

allNodes()

std::vector< NavGraphNode * > TrigCompositeUtils::NavGraph::allNodes

(

)

Get all nodes.

Returns

Vector of all nodes. Including all final, intermediate, and initial nodes.

Definition at line 104 of file NavGraph.cxx.

                                              {
    std::vector<NavGraphNode*> returnVec;
    returnVec.reserve(m_nodes.size());
    for (std::unique_ptr<NavGraphNode>& entry : m_nodes) {
      NavGraphNode& nodeObj = *entry;
      returnVec.push_back( &nodeObj );
    }
    return returnVec;
  }

edges()

size_t TrigCompositeUtils::NavGraph::edges

(

)

const

Returns

Total number of edges in the NavGraph.

Definition at line 120 of file NavGraph.cxx.

                               {
    return m_edges;
  }

finalNodes()

const std::vector< NavGraphNode * > & TrigCompositeUtils::NavGraph::finalNodes

(

)

const

Get all final nodes.

Returns

Vector of final nodes. These are the nodes which were added without any "comingFrom". To explore the NavGraph fully, one should explore recursively all paths originating from each of the final nodes.

Definition at line 100 of file NavGraph.cxx.

                                                             {
    return m_finalNodes;
  }

nodes()

size_t TrigCompositeUtils::NavGraph::nodes

(

)

const

Returns

Total number of nodes in the NavGraph.

Definition at line 115 of file NavGraph.cxx.

                               {
    return m_nodes.size();
  }

printAllPaths()

void TrigCompositeUtils::NavGraph::printAllPaths	(	MsgStream &	log,
		MSG::Level	msgLevel = MSG::VERBOSE
	)		const

Helper function.

Print the internal graph structure to the terminal.

Parameters

[in]	log	Athena messaging service reference.
[in]	msgLevel	Athena messaging service verbosity level.

Definition at line 166 of file NavGraph.cxx.

                                                                      {
    for (const NavGraphNode* finalNode : m_finalNodes) {
      recursivePrintNavPath(*finalNode, 0, log, msgLevel);
    }
  }

recursivePrintNavPath()

void TrigCompositeUtils::NavGraph::recursivePrintNavPath ( const NavGraphNode &  nav, size_t  level, MsgStream &  log, MSG::Level  msgLevel  ) const

private

@bried Internal helper function.

Recursively print the graph structure from a single given starting node.

Parameters

[in]	nav	The node to recursively explore.
[in]	level	The current depth of recursion. Used to pad output format.
[in]	log	Athena messaging service reference.
[in]	msgLevel	Athena messaging service verbosity level.

Definition at line 173 of file NavGraph.cxx.

                                                                                                                     {
    const Decision* node = nav.node();
    const ElementLink<DecisionContainer> nodeEL = decisionToElementLink( node );
    std::stringstream ss;
    for (size_t i = 0; i < level; ++i) {
      ss << "  ";
    }
 
    ss << "|-> " << nodeEL.dataID() << " #" << nodeEL.index() << " Name(" << node->name() << ") Passing(" << node->decisions().size() << ")";
    if (nav.getKeep()) ss << " [KEEP]";
    if (node->hasObjectLink(featureString())) {
      SG::sgkey_t key;
      uint32_t clid;
      Decision::index_type index;
      node->typelessGetObjectLink(featureString(), key, clid, index);
#ifndef XAOD_STANDALONE // Athena or AthAnalysis
      ss << " Feature(#" << index << ", " << CLIDRegistry::CLIDToTypeinfo(clid)->name() << ", " << key << ")"; 
#else 
      ss << " Feature(#" << index << ", " << key << ")";
#endif
    }
    if (node->hasObjectLink(viewString())) ss << " [View]";
    if (node->hasObjectLink(roiString())) ss << " [RoI]";
    if (node->hasObjectLink(initialRoIString())) ss << " [InitialRoI]";
    log << msgLevel << ss.str() << endmsg;
    for (const NavGraphNode* seed : nav.seeds()) {
      recursivePrintNavPath(*seed, level + 1, log, msgLevel);
    }
  }

rewireNodeForRemoval()

void TrigCompositeUtils::NavGraph::rewireNodeForRemoval ( NavGraphNode &  toBeDeleted )

private

Take all seeds (parents) of the supplied node and connect them to all the node's children.

Unlink the parents and children from the node. For the case of Parent nodes, P, node to be deleted, N, and Child nodes, C, this function converts from P P P P P P | \ / | \ / N , N , N , N | | / \ / \ C C C C C C to P P P P P P | \ / | |\ /| | , | , | , | | | | | / \ |/ | C C C C C C where N is orphaned from the graph, with no parents or children.

Parameters

[in]

toBeDeleted

Node to rewire out of the navigation graph prior to its removal.

Definition at line 140 of file NavGraph.cxx.

                                                               {
    const std::vector<NavGraphNode*> myParents = toBeDeleted.seeds();
    const std::vector<NavGraphNode*> myChildren = toBeDeleted.children();
 
    // Perform the (potentially) many-to-many re-linking required to remove toBeDeleted from the graph
    for (NavGraphNode* child : myChildren) {
      for (NavGraphNode* parent : myParents) {
        bool newEdge = child->linksTo(parent);
        if (newEdge) {
          ++m_edges;
        }
      }
    }
 
    // Remove the edges connecting to toBeDeleted from all of its children and all of parents
    for (NavGraphNode* child : myChildren) {
      child->dropLinks(&toBeDeleted);
      --m_edges;
    }
    for (NavGraphNode* parent : myParents) {
      parent->dropLinks(&toBeDeleted);
      --m_edges;
    }
  }

thin()

std::vector< const Decision * > TrigCompositeUtils::NavGraph::thin

(

)

Perform thinning.

Removing all nodes which are not explicitly flagged as keep(), after having re-wired them out of the graph.

Returns

A vector of the Decision* behind the NavGraphNodes which were thinned from the NavGraph.

Definition at line 124 of file NavGraph.cxx.

                                            {
    std::vector<const Decision*> returnVec;
    std::vector<std::unique_ptr<NavGraphNode>>::iterator it;
    for (it = m_nodes.begin(); it != m_nodes.end(); /*noop*/) {
      if ((*it)->getKeep()) {
        (*it)->resetKeep();
        ++it;
      } else {
        returnVec.push_back((*it)->node());
        rewireNodeForRemoval(*(*it));
        it = m_nodes.erase(it);
      }
    }
    return returnVec;
  }

Member Data Documentation

m_edges

size_t TrigCompositeUtils::NavGraph::m_edges

private

Statistics on the number of edges, connecting the nodes in the graph.

Definition at line 214 of file NavGraph.h.

m_finalNodes

std::vector<NavGraphNode*> TrigCompositeUtils::NavGraph::m_finalNodes

private

Entry points into the navigation graph.

When iterating over the graph, start from all of these places.

Definition at line 213 of file NavGraph.h.

m_nodePositionMap

std::map<const Decision*, size_t> TrigCompositeUtils::NavGraph::m_nodePositionMap

private

Map of Decision pointer and index of the node(that contains the Decision) in m_nodes.

Definition at line 211 of file NavGraph.h.

m_nodes

std::vector<std::unique_ptr<NavGraphNode> > TrigCompositeUtils::NavGraph::m_nodes

private

Vector of unique pointers to nodes in the graph.

Definition at line 212 of file NavGraph.h.

---

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

• NavGraph.h
• NavGraph.cxx