# algorithms.graph.graph

## Module: `algorithms.graph.graph`

Inheritance diagram for `nipy.algorithms.graph.graph`:

This module implements two graph classes:

Graph: basic topological graph, i.e. vertices and edges. This kind of object only has topological properties

WeightedGraph (Graph): also has a value associated with edges, called weights, that are used in some computational procedures (e.g. path length computation). Importantly these objects are equivalent to square sparse matrices, which is used to perform certain computations.

This module also provides several functions to instantiate WeightedGraphs from data: - k nearest neighbours (where samples are rows of a 2D-array) - epsilon-neighbors (where sample rows of a 2D-array) - representation of the neighbors on a 3d grid (6-, 18- and 26-neighbors) - Minimum Spanning Tree (where samples are rows of a 2D-array)

Author: Bertrand Thirion, 2006–2011

## Classes

### `Graph`

class nipy.algorithms.graph.graph.Graph(V, E=0, edges=None)

  Bases: `object`

  Basic topological (non-weighted) directed Graph class

  Member variables:

  - V (int > 0): the number of vertices

  - E (int >= 0): the number of edges

  Properties:

  - vertices (list, type=int, shape=(V,)) vertices id

  - edges (list, type=int, shape=(E,2)): edges as vertices id tuples

  __init__(V, E=0, edges=None)

    Constructor

    Parameters:
      V int

        the number of vertices

      E int, optional

        the number of edges

      edges None or shape (E, 2) array, optional

        edges of graph

  adjacency()

    returns the adjacency matrix of the graph as a sparse coo matrix

    Returns:
      adj: scipy.sparse matrix instance,

        that encodes the adjacency matrix of self

  cc()

    Compte the different connected components of the graph.

    Returns:
      label: array of shape(self.V), labelling of the vertices
  degrees()

    Returns the degree of the graph vertices.

    Returns:
      rdegree: (array, type=int, shape=(self.V,)), the right degrees
      ldegree: (array, type=int, shape=(self.V,)), the left degrees
  get_E()

    To get the number of edges in the graph

  get_V()

    To get the number of vertices in the graph

  get_edges()

    To get the graph’s edges

  get_vertices()

    To get the graph’s vertices (as id)

  main_cc()

    Returns the indexes of the vertices within the main cc

    Returns:
      idx: array of shape (sizeof main cc)
  set_edges(edges)

    Sets the graph’s edges

    Preconditions:

    - edges has a correct size

    - edges take values in [1..V]

  show(ax=None)

    Shows the graph as a planar one.

    Parameters:
      ax, axis handle
    Returns:
      ax, axis handle
  to_coo_matrix()

    Return adjacency matrix as coo sparse

    Returns:
      sp: scipy.sparse matrix instance,

        that encodes the adjacency matrix of self

### `WeightedGraph`

class nipy.algorithms.graph.graph.WeightedGraph(V, edges=None, weights=None)

  Bases: `Graph`

  Basic weighted, directed graph class

  Member variables:

  - V (int): the number of vertices

  - E (int): the number of edges

  Methods

  - vertices (list, type=int, shape=(V,)): vertices id

  - edges (list, type=int, shape=(E,2)): edges as vertices id tuples

  - weights (list, type=int, shape=(E,)): weights / lengths of the graph’s edges

  __init__(V, edges=None, weights=None)

    Constructor

    Parameters:
      V int

        (int > 0) the number of vertices

      edges(E, 2) array, type int

        edges of the graph

      weights(E, 2) array, type=int

        weights/lengths of the edges

  adjacency()

    returns the adjacency matrix of the graph as a sparse coo matrix

    Returns:
      adj: scipy.sparse matrix instance,

        that encodes the adjacency matrix of self

  anti_symmeterize()

    anti-symmeterize self, i.e. produces the graph whose adjacency matrix would be the antisymmetric part of its current adjacency matrix

  cc()

    Compte the different connected components of the graph.

    Returns:
      label: array of shape(self.V), labelling of the vertices
  cliques()

    Extraction of the graphe cliques these are defined using replicator dynamics equations

    Returns:
      cliques: array of shape (self.V), type (np.intp)

        labelling of the vertices according to the clique they belong to

  compact_neighb()

    returns a compact representation of self

    Returns:
      idx: array of of shape(self.V + 1):

        the positions where to find the neighbors of each node within neighb and weights

      neighb: array of shape(self.E), concatenated list of neighbors
      weights: array of shape(self.E), concatenated list of weights
  copy()

    returns a copy of self

  cut_redundancies()

    Returns a graph with redundant edges removed: ecah edge (ab) is present only once in the edge matrix: the correspondng weights are added.

    Returns:
      the resulting WeightedGraph
  degrees()

    Returns the degree of the graph vertices.

    Returns:
      rdegree: (array, type=int, shape=(self.V,)), the right degrees
      ldegree: (array, type=int, shape=(self.V,)), the left degrees
  dijkstra(seed=0)

    Returns all the [graph] geodesic distances starting from seed x

    > seed (int, >-1, <self.V) or array of shape(p)

    >   edge(s) from which the distances are computed

    Returns:
      dg: array of shape (self.V),

        the graph distance dg from ant vertex to the nearest seed

    Notes

    It is mandatory that the graph weights are non-negative

  floyd(seed=None)

    Compute all the geodesic distances starting from seeds

    Parameters:
      seed: None or array of shape (nbseed), type np.intp

        vertex indexes from which the distances are computed if seed==None, then every edge is a seed point

    Returns:
      dg array of shape (nbseed, self.V)

        the graph distance dg from each seed to any vertex

    Notes

    It is mandatory that the graph weights are non-negative. The algorithm proceeds by repeating Dijkstra’s algo for each seed. Floyd’s algo is not used (O(self.V)^3 complexity…)

  from_3d_grid(xyz, k=18)

    Sets the graph to be the topological neighbours graph of the three-dimensional coordinates set xyz, in the k-connectivity scheme

    Parameters:
      xyz: array of shape (self.V, 3) and type np.intp,
      k = 18: the number of neighbours considered. (6, 18 or 26)
    Returns:
      E(int): the number of edges of self
  get_E()

    To get the number of edges in the graph

  get_V()

    To get the number of vertices in the graph

  get_edges()

    To get the graph’s edges

  get_vertices()

    To get the graph’s vertices (as id)

  get_weights()
  is_connected()

    States whether self is connected or not

  kruskal()

    Creates the Minimum Spanning Tree of self using Kruskal’s algo. efficient is self is sparse

    Returns:
      K, WeightedGraph instance: the resulting MST

    Notes

    If self contains several connected components, will have the same number k of connected components

  left_incidence()

    Return left incidence matrix

    Returns:
      left_incid: list

        the left incidence matrix of self as a list of lists: i.e. the list[[e.0.0, .., e.0.i(0)], .., [e.V.0, E.V.i(V)]] where e.i.j is the set of edge indexes so that e.i.j[0] = i

  list_of_neighbors()

    returns the set of neighbors of self as a list of arrays

  main_cc()

    Returns the indexes of the vertices within the main cc

    Returns:
      idx: array of shape (sizeof main cc)
  normalize(c=0)

    Normalize the graph according to the index c Normalization means that the sum of the edges values that go into or out each vertex must sum to 1

    Parameters:
      c=0 in {0, 1, 2}, optional: index that designates the way

        according to which D is normalized c == 0 => for each vertex a, sum{edge[e, 0]=a} D[e]=1 c == 1 => for each vertex b, sum{edge[e, 1]=b} D[e]=1 c == 2 => symmetric (‘l2’) normalization

    Notes

    Note that when sum_{edge[e, .] == a } D[e] = 0, nothing is performed

  remove_edges(valid)

    Removes all the edges for which valid==0

    Parameters:
      valid(self.E,) array
  remove_trivial_edges()

    Removes trivial edges, i.e. edges that are (vv)-like self.weights and self.E are corrected accordingly

    Returns:
      self.E (int): The number of edges
  right_incidence()

    Return right incidence matrix

    Returns:
      right_incid: list

        the right incidence matrix of self as a list of lists: i.e. the list[[e.0.0, .., e.0.i(0)], .., [e.V.0, E.V.i(V)]] where e.i.j is the set of edge indexes so that e.i.j[1] = i

  set_edges(edges)

    Sets the graph’s edges

    Preconditions:

    - edges has a correct size

    - edges take values in [1..V]

  set_euclidian(X)

    Compute the weights of the graph as the distances between the corresponding rows of X, which represents an embedding of self

    Parameters:
      X array of shape (self.V, edim),

        the coordinate matrix of the embedding

  set_gaussian(X, sigma=0)

    Compute the weights of the graph as a gaussian function of the distance between the corresponding rows of X, which represents an embedding of self

    Parameters:
      X array of shape (self.V, dim)

        the coordinate matrix of the embedding

      sigma=0, float: the parameter of the gaussian function

    Notes

    When sigma == 0, the following value is used: `sigma = sqrt(mean(||X[self.edges[:, 0], :]-X[self.edges[:, 1], :]||^2))`

  set_weights(weights)

    Set edge weights

    Parameters:
      weights: array

        array shape(self.V): edges weights

  show(X=None, ax=None)

    Plots the current graph in 2D

    Parameters:
      X None or array of shape (self.V, 2)

        a set of coordinates that can be used to embed the vertices in 2D. If X.shape[1]>2, a svd reduces X for display. By default, the graph is presented on a circle

      ax: None or int, optional

        ax handle

    Returns:
      ax: axis handle

    Notes

    This should be used only for small graphs.

  subgraph(valid)

    Creates a subgraph with the vertices for which valid>0 and with the corresponding set of edges

    Parameters:
      valid, array of shape (self.V): nonzero for vertices to be retained
    Returns:
      G, WeightedGraph instance, the desired subgraph of self

    Notes

    The vertices are renumbered as [1..p] where p = sum(valid>0) when sum(valid==0) then None is returned

  symmeterize()

    Symmeterize self, modify edges and weights so that self.adjacency becomes the symmetric part of the current self.adjacency.

  to_coo_matrix()

    Return adjacency matrix as coo sparse

    Returns:
      sp: scipy.sparse matrix instance

        that encodes the adjacency matrix of self

  voronoi_diagram(seeds, samples)

    Defines the graph as the Voronoi diagram (VD) that links the seeds. The VD is defined using the sample points.

    Parameters:
      seeds: array of shape (self.V, dim)
      samples: array of shape (nsamples, dim)

    Notes

    By default, the weights are a Gaussian function of the distance The implementation is not optimal

  voronoi_labelling(seed)

    Performs a voronoi labelling of the graph

    Parameters:
      seed: array of shape (nseeds), type (np.intp),

        vertices from which the cells are built

    Returns:
      labels: array of shape (self.V) the labelling of the vertices

## Functions

nipy.algorithms.graph.graph.complete_graph(n)

  returns a complete graph with n vertices

nipy.algorithms.graph.graph.concatenate_graphs(G1, G2)

  Returns the concatenation of the graphs G1 and G2 It is thus assumed that the vertices of G1 and G2 represent disjoint sets

  Parameters:
    G1, G2: the two WeightedGraph instances to be concatenated
  Returns:
    G, WeightedGraph, the concatenated graph

  Notes

  This implies that the vertices of G corresponding to G2 are labeled [G1.V .. G1.V+G2.V]

nipy.algorithms.graph.graph.eps_nn(X, eps=1.0)

  Returns the eps-nearest-neighbours graph of the data

  Parameters:
    X, array of shape (n_samples, n_features), input data
    eps, float, optional: the neighborhood width
  Returns:
    the resulting graph instance

nipy.algorithms.graph.graph.graph_3d_grid(xyz, k=18)

  Utility that computes the six neighbors on a 3d grid

  Parameters:
    xyz: array of shape (n_samples, 3); grid coordinates of the points
    k: neighboring system, equal to 6, 18, or 26
  Returns:
    i, j, d 3 arrays of shape (E),

      where E is the number of edges in the resulting graph (i, j) represent the edges, d their weights

nipy.algorithms.graph.graph.knn(X, k=1)

  returns the k-nearest-neighbours graph of the data

  Parameters:
    X, array of shape (n_samples, n_features): the input data
    k, int, optional: is the number of neighbours considered
  Returns:
    the corresponding WeightedGraph instance

  Notes

  The knn system is symmetrized: if (ab) is one of the edges then (ba) is also included

nipy.algorithms.graph.graph.lil_cc(lil)

  Returns the connected components of a graph represented as a list of lists

  Parameters:
    lil: a list of list representing the graph neighbors
  Returns:
    label a vector of shape len(lil): connected components labelling

  Notes

  Dramatically slow for non-sparse graphs

nipy.algorithms.graph.graph.mst(X)

  Returns the WeightedGraph that is the minimum Spanning Tree of X

  Parameters:
    X: data array, of shape(n_samples, n_features)
  Returns:
    the corresponding WeightedGraph instance

nipy.algorithms.graph.graph.wgraph_from_3d_grid(xyz, k=18)

  Create graph as the set of topological neighbours of the three-dimensional coordinates set xyz, in the k-connectivity scheme

  Parameters:
    xyz: array of shape (nsamples, 3) and type np.intp,
    k = 18: the number of neighbours considered. (6, 18 or 26)
  Returns:
    the WeightedGraph instance

nipy.algorithms.graph.graph.wgraph_from_adjacency(x)

  Instantiates a weighted graph from a square 2D array

  Parameters:
    x: 2D array instance, the input array
  Returns:
    wg: WeightedGraph instance

nipy.algorithms.graph.graph.wgraph_from_coo_matrix(x)

  Instantiates a weighted graph from a (sparse) coo_matrix

  Parameters:
    x: scipy.sparse.coo_matrix instance, the input matrix
  Returns:
    wg: WeightedGraph instance