#!/usr/bin/env python3
# -*- coding: utf-8 -*-
#
# Copyright 2020 Alibaba Group Holding Limited. All Rights Reserved.
#
# Licensed under the Apache License, Version 2.0 (the "License");
# 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.
#
# Author: Ma JingYuan<[email protected]>
#
import json
from graphscope.framework.app import AppAssets
from graphscope.framework.app import not_compatible_for
from graphscope.framework.app import project_to_simple
__all__ = ["is_simple_path"]
[docs]@project_to_simple
@not_compatible_for("arrow_property")
def is_simple_path(graph, nodes):
"""Returns True if and only if `nodes` form a simple path in `G`.
A *simple path* in a graph is a nonempty sequence of nodes in which
no node appears more than once in the sequence, and each adjacent
pair of nodes in the sequence is adjacent in the graph.
Parameters
----------
graph (:class:`graphscope.Graph`): A simple graph.
nodes : list
A list of one or more nodes in the graph `G`.
Returns
-------
bool
Whether the given list of nodes represents a simple path in `G`.
Notes
-----
An empty list of nodes is not a path but a list of one node is a
path. Here's an explanation why.
This function operates on *node paths*. One could also consider
*edge paths*. There is a bijection between node paths and edge
paths.
The *length of a path* is the number of edges in the path, so a list
of nodes of length *n* corresponds to a path of length *n* - 1.
Thus the smallest edge path would be a list of zero edges, the empty
path. This corresponds to a list of one node.
To convert between a node path and an edge path, you can use code
like the following::
>>> from networkx.utils import pairwise
>>> nodes = [0, 1, 2, 3]
>>> edges = list(pairwise(nodes))
>>> edges
[(0, 1), (1, 2), (2, 3)]
>>> nodes = [edges[0][0]] + [v for u, v in edges]
>>> nodes
[0, 1, 2, 3]
Examples
--------
.. code:: python
>>> import graphscope
>>> from graphscope.dataset import load_p2p_network
>>> sess = graphscope.session(cluster_type="hosts", mode="eager")
>>> g = load_p2p_network(sess)
>>> # project to a simple graph (if needed)
>>> pg = g.project(vertices={"host": ["id"]}, edges={"connect": ["dist"]})
>>> c = graphscope.is_simple_path(pg, [2, 3, 8])
>>> print(c)
>>> sess.close()
"""
if isinstance(nodes, list):
n1json = json.dumps(nodes)
ctx = AppAssets(algo="is_simple_path", context="tensor")(graph, n1json)
return ctx.to_numpy("r", axis=0)[0]
raise ValueError("input nodes is not a list object!")