#!/usr/bin/env python3
# -*- coding: utf-8 -*-
"""
Created on Jul 24, 2019
"""
import numpy as np
from scipy import sparse
from sknetwork.utils.check import is_symmetric
[docs]def breadth_first_search(adjacency: sparse.csr_matrix, source: int, return_predecessors: bool = True):
"""Breadth-first ordering starting with specified node.
* Graphs
* Digraphs
Based on SciPy (scipy.sparse.csgraph.breadth_first_order)
Parameters
----------
adjacency :
The adjacency matrix of the graph
source : int
The node from which to start the ordering
return_predecessors : bool
If ``True``, the size predecessor matrix is returned
Returns
-------
node_array : np.ndarray
The breadth-first list of nodes, starting with specified node. The length of node_array is the number of nodes
reachable from the specified node.
predecessors : np.ndarray
Returned only if ``return_predecessors == True``. The list of predecessors of each node in a breadth-first tree.
If node ``i`` is in the tree, then its parent is given by ``predecessors[i]``. If node ``i`` is not in the tree
(and for the parent node) then ``predecessors[i] = -9999``.
"""
directed = not is_symmetric(adjacency)
return sparse.csgraph.breadth_first_order(adjacency, source, directed, return_predecessors)
[docs]def depth_first_search(adjacency: sparse.csr_matrix, source: int, return_predecessors: bool = True):
"""Depth-first ordering starting with specified node.
* Graphs
* Digraphs
Based on SciPy (scipy.sparse.csgraph.depth_first_order)
Parameters
----------
adjacency :
The adjacency matrix of the graph
source :
The node from which to start the ordering
return_predecessors:
If ``True``, the size predecessor matrix is returned
Returns
-------
node_array : np.ndarray
The depth-first list of nodes, starting with specified node. The length of node_array is the number of nodes
reachable from the specified node.
predecessors : np.ndarray
Returned only if ``return_predecessors == True``. The list of predecessors of each node in a depth-first tree.
If node ``i`` is in the tree, then its parent is given by ``predecessors[i]``. If node ``i`` is not in the tree
(and for the parent node) then ``predecessors[i] = -9999``.
"""
directed = not is_symmetric(adjacency)
return sparse.csgraph.depth_first_order(adjacency, source, directed, return_predecessors)