TICL/plugins/TICLGraph.cc

0001 #include "FWCore/MessageLogger/interface/MessageLogger.h"
0002 #include "TICLGraph.h"
0003
0004 namespace ticl {
0005
0006   void Node::findSubComponents(std::vector<Node>& graph, std::vector<unsigned int>& subComponent) {
0007     if (!alreadyVisited_) {
0008       alreadyVisited_ = true;
0009       subComponent.push_back(index_);
0010       for (auto const& neighbour : outerNeighboursId_) {
0011         graph[neighbour].findSubComponents(graph, subComponent);
0012       }
0013     }
0014   }
0015 }  // namespace ticl
0016
0017 TICLGraph::TICLGraph(std::vector<ticl::Node>& nodes) {
0018   nodes_ = nodes;
0019   rootNodes_.reserve(nodes_.size());
0020   findRootNodes();
0021   rootNodes_.shrink_to_fit();
0022 }
0023
0024 std::vector<std::vector<unsigned int>> TICLGraph::findSubComponents() {
0025   std::vector<std::vector<unsigned int>> components;
0026   for (auto const& node : nodes_) {
0027     auto const id = node.getId();
0028     if (isRootNode_[id]) {
0029       std::vector<unsigned int> tmpSubComponents;
0030       nodes_[id].findSubComponents(nodes_, tmpSubComponents);
0031       components.push_back(tmpSubComponents);
0032     }
0033   }
0034   // Second loop: DFS for non-root nodes that haven't been visited
0035   for (auto const& node : nodes_) {
0036     auto const id = node.getId();
0037     if (!node.alreadyVisited()) {  // Use the alreadyVisited() method
0038       // Node not visited yet, so perform DFS
0039       std::vector<unsigned int> tmpSubComponents;
0040       nodes_[id].findSubComponents(nodes_, tmpSubComponents);
0041       components.push_back(tmpSubComponents);
0042     }
0043   }
0044   return components;
0045 }
0046
0047 std::vector<std::vector<unsigned int>> TICLGraph::findSubComponents(std::vector<ticl::Node>& rootNodes) {
0048   std::vector<std::vector<unsigned int>> components;
0049   for (auto const& node : rootNodes) {
0050     auto const id = node.getId();
0051     //LogDebug("TICLGraph") << "DFS Starting From " << id << std::endl;
0052     std::vector<unsigned int> tmpSubComponents;
0053     nodes_[id].findSubComponents(nodes_, tmpSubComponents);
0054     components.push_back(tmpSubComponents);
0055   }
0056   return components;
0057 }
0058
0059 inline void TICLGraph::findRootNodes() {
0060   for (auto const& n : nodes_) {
0061     if (n.getInnerNeighbours().empty()) {
0062       rootNodes_.push_back(n);
0063     }
0064   }
0065 }
0066
0067 bool TICLGraph::isGraphOk() {
0068   for (const auto& n : nodes_) {
0069     if (n.getInnerNeighbours().size() > 1) {
0070       return false;
0071     }
0072   }
0073   return true;
0074 }