dmlc--dgl
xiang song(charlie.song)
42b0c38f81
* traversal to new framework * add new * Fix compile * Pass test * keep old version * lint * lint * Fix * Fix * Fix compatability with new master * Fix test and tutorials * Update according to comments * Fix test Co-authored-by: Ubuntu <ubuntu@ip-172-31-51-214.ec2.internal>
103 行
3.1 KiB
C++
103 行
3.1 KiB
C++
/*!
|
|
* 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_
|