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...
void	addNode (const Decision *node, const EventContext &ctx, const Decision *comingFrom=nullptr)
	Add a new NavGraphNode which shadows the xAOD Decision object "node" from the full navigation graph. More...
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 ElementLink< TrigCompositeUtils::DecisionContainer >, NavGraphNode >	m_nodes
	Map of 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 98 of file NavGraph.h.

Constructor & Destructor Documentation

NavGraph()

TrigCompositeUtils::NavGraph::NavGraph

(

)

Construct an empty NavGraph.

Definition at line 75 of file NavGraph.cxx.

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

Member Function Documentation

addNode()

void TrigCompositeUtils::NavGraph::addNode	(	const Decision *	node,
		const EventContext &	ctx,
		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]	ctx	The event context.
[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 79 of file NavGraph.cxx.

                                                                                                  {
 
    const ElementLink<DecisionContainer> nodeEL = decisionToElementLink(node, ctx);
    auto nodePairIt = m_nodes.insert( std::make_pair(nodeEL, NavGraphNode(node)) );
    NavGraphNode& nodeObj = nodePairIt.first->second;
    
    if (comingFrom == nullptr) { // Not coming from anywhere - hence a final node.
      m_finalNodes.push_back( &nodeObj );
    } else {
      const ElementLink<DecisionContainer> comingFromEL = decisionToElementLink(comingFrom, ctx);
      auto comingFromPairIt = m_nodes.insert( std::make_pair(comingFromEL, NavGraphNode(comingFrom)) );
      NavGraphNode& comingFromNodeObj = 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 103 of file NavGraph.cxx.

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

edges()

size_t TrigCompositeUtils::NavGraph::edges

(

)

const

Returns

Total number of edges in the NavGraph.

Definition at line 119 of file NavGraph.cxx.

                               {
    return m_edges;
  }

finalNodes()

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 99 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 114 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 165 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 172 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;
      uint16_t 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 139 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 123 of file NavGraph.cxx.

                                            {
    std::vector<const Decision*> returnVec;
    std::map<const ElementLink<TrigCompositeUtils::DecisionContainer>, NavGraphNode>::iterator it;
    for (it = m_nodes.begin(); it != m_nodes.end(); /*noop*/) {
      if (it->second.getKeep()) {
        it->second.resetKeep();
        ++it;
      } else {
        returnVec.push_back(*(it->first)); // Dereferencing ElementLink to element
        rewireNodeForRemoval(it->second);
        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 186 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 185 of file NavGraph.h.

m_nodes

std::map<const ElementLink<TrigCompositeUtils::DecisionContainer>, NavGraphNode> TrigCompositeUtils::NavGraph::m_nodes

private

Map of nodes in the graph.

Indexed on the underlying Decision object's ElementLink.

Definition at line 184 of file NavGraph.h.

---

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

• NavGraph.h
• NavGraph.cxx