/** * Copyright (c) 2018 by Contributors * @file dgl/graph_op.h * @brief Operations on graph index. */ #ifndef DGL_GRAPH_OP_H_ #define DGL_GRAPH_OP_H_ #include #include "graph.h" #include "immutable_graph.h" namespace dgl { class GraphOp { public: /** * @brief Return a new graph with all the edges reversed. * * The returned graph preserves the vertex and edge index in the original * graph. * * @return the reversed graph */ static GraphPtr Reverse(GraphPtr graph); /** * @brief Return the line graph. * * If i~j and j~i are two edges in original graph G, then * (i,j)~(j,i) and (j,i)~(i,j) are the "backtracking" edges on * the line graph. * * @param graph The input graph. * @param backtracking Whether the backtracking edges are included or not * @return the line graph */ static GraphPtr LineGraph(GraphPtr graph, bool backtracking); /** * @brief Return a disjoint union of the input graphs. * * The new graph will include all the nodes/edges in the given graphs. * Nodes/Edges will be relabled by adding the cumsum of the previous graph * sizes in the given sequence order. For example, giving input [g1, g2, g3], * where they have 5, 6, 7 nodes respectively. Then node#2 of g2 will become * node#7 in the result graph. Edge ids are re-assigned similarly. * * The input list must be either ALL mutable graphs or ALL immutable graphs. * The returned graph type is also determined by the input graph type. * * @param graphs A list of input graphs to be unioned. * @return the disjoint union of the graphs */ static GraphPtr DisjointUnion(std::vector graphs); /** * @brief Partition the graph into several subgraphs. * * This is a reverse operation of DisjointUnion. The graph will be partitioned * into num graphs. This requires the given number of partitions to evenly * divides the number of nodes in the graph. * * If the input graph is mutable, the result graphs are mutable. * If the input graph is immutable, the result graphs are immutable. * * @param graph The graph to be partitioned. * @param num The number of partitions. * @return a list of partitioned graphs */ static std::vector DisjointPartitionByNum( GraphPtr graph, int64_t num); /** * @brief Partition the graph into several subgraphs. * * This is a reverse operation of DisjointUnion. The graph will be partitioned * based on the given sizes. This requires the sum of the given sizes is equal * to the number of nodes in the graph. * * If the input graph is mutable, the result graphs are mutable. * If the input graph is immutable, the result graphs are immutable. * * @param graph The graph to be partitioned. * @param sizes The number of partitions. * @return a list of partitioned graphs */ static std::vector DisjointPartitionBySizes( GraphPtr graph, IdArray sizes); /** * @brief Map vids in the parent graph to the vids in the subgraph. * * If the Id doesn't exist in the subgraph, -1 will be used. * * @param parent_vid_map An array that maps the vids in the parent graph to * the subgraph. The elements store the vertex Ids in the parent graph, and * the indices indicate the vertex Ids in the subgraph. * @param query The vertex Ids in the parent graph. * @return an Id array that contains the subgraph node Ids. */ static IdArray MapParentIdToSubgraphId(IdArray parent_vid_map, IdArray query); /** * @brief Expand an Id array based on the offset array. * * For example, * ids: [0, 1, 2, 3, 4], * offset: [0, 2, 2, 5, 6, 7], * result: [0, 0, 2, 2, 2, 3, 4]. * The offset array has one more element than the ids array. * (offset[i], offset[i+1]) shows the location of ids[i] in the result array. * * @param ids An array that contains the node or edge Ids. * @param offset An array that contains the offset after expansion. * @return a expanded Id array. */ static IdArray ExpandIds(IdArray ids, IdArray offset); /** * @brief Convert the graph to a simple graph. * @param graph The input graph. * @return a new immutable simple graph with no multi-edge. */ static GraphPtr ToSimpleGraph(GraphPtr graph); /** * @brief Convert the graph to a mutable bidirected graph. * * If the original graph has m edges for i -> j and n edges for * j -> i, the new graph will have max(m, n) edges for both * i -> j and j -> i. * * @param graph The input graph. * @return a new mutable bidirected graph. */ static GraphPtr ToBidirectedMutableGraph(GraphPtr graph); /** * @brief Same as BidirectedMutableGraph except that the returned graph is * immutable. * @param graph The input graph. * @return a new immutable bidirected * graph. */ static GraphPtr ToBidirectedImmutableGraph(GraphPtr graph); /** * @brief Same as BidirectedMutableGraph except that the returned graph is * immutable and call gk_csr_MakeSymmetric in GKlib. This is more efficient * than ToBidirectedImmutableGraph. It return a null pointer if the conversion * fails. * * @param graph The input graph. * @return a new immutable bidirected graph. */ static GraphPtr ToBidirectedSimpleImmutableGraph(ImmutableGraphPtr ig); /** * @brief Get a induced subgraph with HALO nodes. * The HALO nodes are the ones that can be reached from `nodes` within * `num_hops`. * @param graph The input graph. * @param nodes The input nodes that form the core of the induced subgraph. * @param num_hops The number of hops to reach. * @return the induced subgraph with HALO nodes. */ static HaloSubgraph GetSubgraphWithHalo( GraphPtr graph, IdArray nodes, int num_hops); /** * @brief Reorder the nodes in the immutable graph. * @param graph The input graph. * @param new_order The node Ids in the new graph. The index in `new_order` is * old node Ids. * @return the graph with reordered node Ids */ static GraphPtr ReorderImmutableGraph( ImmutableGraphPtr ig, IdArray new_order); }; } // namespace dgl #endif // DGL_GRAPH_OP_H_