EgammaCoreTools/interface/GraphMap.h

0001 #ifndef RecoEcal_EgammaCoreTools_GraphMap_h
0002 #define RecoEcal_EgammaCoreTools_GraphMap_h
0003
0004 #include <vector>
0005 #include <array>
0006 #include <map>
0007 #include <algorithm>
0008
0009 /*
0010  * Class handling a sparse graph of clusters.
0011  *
0012  * Author: D. Valsecchi
0013  * Date:  08-02-2022
0014  */
0015
0016 namespace reco {
0017
0018   class GraphMap {
0019   public:
0020     GraphMap(uint nNodes);
0021
0022     enum NodeCategory { kNode, kSeed, kNcategories };
0023
0024     void addNode(const uint index, const NodeCategory category);
0025     void addNodes(const std::vector<uint> &indices, const std::vector<NodeCategory> &categories);
0026     void addEdge(const uint i, const uint j);
0027     void setAdjMatrix(const uint i, const uint j, const float score);
0028     void setAdjMatrixSym(const uint i, const uint j, const float score);
0029     void printGraphMap();
0030
0031     //Getters
0032     const std::vector<uint> &getOutEdges(const uint i) const;
0033     const std::vector<uint> &getInEdges(const uint i) const;
0034     uint getAdjMatrix(const uint i, const uint j) const;
0035     std::vector<float> getAdjMatrixRow(const uint i) const;
0036     std::vector<float> getAdjMatrixCol(const uint j) const;
0037
0038     enum CollectionStrategy {
0039       Cascade,          // Starting from the highest energy seed, collect all the nodes.
0040                         // Other seeds collected by higher energy seeds are ignored
0041       CollectAndMerge,  // First, for each simple node keep only the edge with the highest score.
0042                         // Then collect all the simple nodes around the other seeds.
0043                         // Edges between the seeds nodes are ignored.
0044                         // Finally, starting from the first seed, look for linked secondary seeds
0045                         // and if they pass the threshold, merge their noded.
0046       SeedsFirst,       // Like strategy D, but after solving the edges between the seeds,
0047                         // the simple nodes edges are cleaned to keep only the highest score link.
0048                         // Then proceed as strategy B.
0049       CascadeHighest    // First, for each simple node keep only the edge with the highest score.
0050       // Then proceed as strategy A, from the first seed node cascading to the others.
0051       // Secondary seeds linked are absorbed and ignored in the next iteration:
0052       // this implies that nodes connected to these seed  are lost.
0053     };
0054
0055     // Output of the collection  [{seed, [list of clusters]}]
0056     typedef std::vector<std::pair<uint, std::vector<uint>>> GraphOutput;
0057     typedef std::map<uint, std::vector<uint>> GraphOutputMap;
0058     // Apply the collection algorithms
0059     void collectNodes(GraphMap::CollectionStrategy strategy, float threshold);
0060     const GraphOutput &getGraphOutput() { return graphOutput_; };
0061
0062   private:
0063     uint nNodes_;
0064     // Map with list of indices of nodes for each category
0065     std::map<NodeCategory, std::vector<uint>> nodesCategories_;
0066     // Count of nodes for each category
0067     std::map<uint, uint> nodesCount_;
0068     // Incoming edges, one list for each node (no distinction between type)
0069     std::vector<std::vector<uint>> edgesIn_;
0070     // Outcoming edges, one list for each node
0071     std::vector<std::vector<uint>> edgesOut_;
0072     // Adjacency matrix (i,j) --> score
0073     // Rows are interpreted as OUT edges
0074     // Columns are interpreted as IN edges
0075     std::map<std::pair<uint, uint>, float> adjMatrix_;
0076
0077     // Store for the graph collection result
0078     GraphOutput graphOutput_;
0079
0080     // Functions for the collection strategies
0081     void collectCascading(float threshold);
0082     void assignHighestScoreEdge();
0083     // Return both the output graph with only seedss and a GraphOutputMap
0084     // of the collected simple nodes from each seed.
0085     std::pair<GraphOutput, GraphOutputMap> collectSeparately(float threshold);
0086     void mergeSubGraphs(float threshold, GraphOutput seedsGraph, GraphOutputMap nodesGraphMap);
0087     void resolveSuperNodesEdges(float threshold);
0088   };
0089
0090 }  // namespace reco
0091
0092 #endif