graph.hpp

Go to the documentation of this file.

// Copyright (c) 2014-2023, Lawrence Livermore National Security, LLC.
// Produced at the Lawrence Livermore National Laboratory.
// Written by the LBANN Research Team (B. Van Essen, et al.) listed in
// the CONTRIBUTORS file. <lbann-dev@llnl.gov>
//
// LLNL-CODE-697807.
// All rights reserved.
//
// This file is part of LBANN: Livermore Big Artificial Neural Network
// Toolkit. For details, see http://software.llnl.gov/LBANN or
// https://github.com/LLNL/LBANN.
//
// Licensed under the Apache License, Version 2.0 (the "Licensee"); you
// may not use this file except in compliance with the License.  You may
// obtain a copy of the License at:
//
// http://www.apache.org/licenses/LICENSE-2.0
//
// Unless required by applicable law or agreed to in writing, software
// distributed under the License is distributed on an "AS IS" BASIS,
// WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or
// implied. See the License for the specific language governing
// permissions and limitations under the license.

#include "lbann/base.hpp"
#include <iostream>
#include <map>
#include <set>
#include <vector>

namespace lbann {
namespace graph {

void print(const std::set<El::Int>& nodes,
           const std::map<El::Int, std::set<El::Int>>& edges,
           std::ostream& os);

std::set<El::Int>
get_neighbors(El::Int node, const std::map<El::Int, std::set<El::Int>>& edges);

bool is_closure(const std::set<El::Int>& nodes,
                const std::map<El::Int, std::set<El::Int>>& edges);

bool is_topologically_sorted(const std::set<El::Int>& nodes,
                             const std::map<El::Int, std::set<El::Int>>& edges);

bool is_cyclic(const std::set<El::Int>& nodes,
               const std::map<El::Int, std::set<El::Int>>& edges);

std::map<El::Int, std::set<El::Int>>
transpose(const std::set<El::Int>& nodes,
          const std::map<El::Int, std::set<El::Int>>& edges);

std::map<El::Int, std::set<El::Int>>
induce_subgraph(const std::set<El::Int>& nodes,
                const std::map<El::Int, std::set<El::Int>>& edges);

std::vector<El::Int>
breadth_first_search(El::Int root,
                     const std::map<El::Int, std::set<El::Int>>& edges);

std::vector<El::Int>
depth_first_search(El::Int root,
                   const std::map<El::Int, std::set<El::Int>>& edges);

std::vector<El::Int>
topological_sort(const std::set<El::Int>& nodes,
                 const std::map<El::Int, std::set<El::Int>>& edges);

void condensation(const std::set<El::Int>& nodes,
                  const std::map<El::Int, std::set<El::Int>>& edges,
                  std::map<El::Int, std::set<El::Int>>& components,
                  std::set<El::Int>& condensation_nodes,
                  std::map<El::Int, std::set<El::Int>>& condensation_edges);

} // namespace graph
} // namespace lbann