/**
 *  Copyright (c) 2020 by Contributors
 * @file dgl/graph_traversal.h
 * @brief common graph traversal operations
 */
#ifndef DGL_GRAPH_TRAVERSAL_H_
#define DGL_GRAPH_TRAVERSAL_H_

#include "array.h"
#include "base_heterograph.h"

namespace dgl {

///////////////////////// Graph Traverse routines //////////////////////////
/**
 * @brief Class for representing frontiers.
 *
 * Each frontier is a list of nodes/edges (specified by their ids).
 * An optional tag can be specified on each node/edge (represented by an int
 * value).
 */
struct Frontiers {
  /** @brief a vector store for the nodes/edges in all the frontiers */
  IdArray ids;

  /**
   * @brief a vector store for node/edge tags. Dtype is int64.
   * Empty if no tags are requested
   */
  IdArray tags;

  /** @brief a section vector to indicate each frontier Dtype is int64. */
  IdArray sections;
};

namespace aten {

/**
 * @brief Traverse the graph in a breadth-first-search (BFS) order.
 *
 * @param csr The input csr matrix.
 * @param sources Source nodes.
 * @return A Frontiers object containing the search result
 */
Frontiers BFSNodesFrontiers(const CSRMatrix& csr, IdArray source);

/**
 * @brief Traverse the graph in a breadth-first-search (BFS) order, returning
 *        the edges of the BFS tree.
 *
 * @param csr The input csr matrix.
 * @param sources Source nodes.
 * @return A Frontiers object containing the search result
 */
Frontiers BFSEdgesFrontiers(const CSRMatrix& csr, IdArray source);

/**
 * @brief Traverse the graph in topological order.
 *
 * @param csr The input csr matrix.
 * @return A Frontiers object containing the search result
 */
Frontiers TopologicalNodesFrontiers(const CSRMatrix& csr);

/**
 * @brief Traverse the graph in a depth-first-search (DFS) order.
 *
 * @param csr The input csr matrix.
 * @param sources Source nodes.
 * @return A Frontiers object containing the search result
 */
Frontiers DGLDFSEdges(const CSRMatrix& csr, IdArray source);

/**
 * @brief Traverse the graph in a depth-first-search (DFS) order and return the
 *        recorded edge tag if return_labels is specified.
 *
 * The traversal visit edges in its DFS order. Edges have three tags:
 * FORWARD(0), REVERSE(1), NONTREE(2)
 *
 * A FORWARD edge is one in which `u` has been visisted but `v` has not.
 * A REVERSE edge is one in which both `u` and `v` have been visisted and the
 * edge is in the DFS tree.
 * A NONTREE edge is one in which both `u` and `v` have been visisted but the
 * edge is NOT in the DFS tree.
 *
 * @param csr The input csr matrix.
 * @param sources Source nodes.
 * @param has_reverse_edge If true, REVERSE edges are included
 * @param has_nontree_edge If true, NONTREE edges are included
 * @param return_labels If true, return the recorded edge tags.
 * @return A Frontiers object containing the search result
 */
Frontiers DGLDFSLabeledEdges(
    const CSRMatrix& csr, IdArray source, const bool has_reverse_edge,
    const bool has_nontree_edge, const bool return_labels);

}  // namespace aten
}  // namespace dgl

#endif  // DGL_GRAPH_TRAVERSAL_H_