Source code for netket.graph.graph

# Copyright 2021 The NetKet Authors - 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
# Unless required by applicable law or agreed to in writing, software
# distributed under the License is distributed on an "AS IS" BASIS,
# See the License for the specific language governing permissions and
# limitations under the License.

from typing import List, Optional, Sequence, Union

import numpy as np
import igraph

from netket.utils.deprecation import warn_deprecation
from import Permutation, PermutationGroup
from .abstract_graph import AbstractGraph, Edge, ColoredEdge, EdgeSequence

class Graph(AbstractGraph):
    A simple implementation of Graph based on an external graph library.

    The underlying implementation is based on igraph and supports conversion to
    networkx, but this is an implementation detail and could be changed in the future.

    # Initialization
    # ------------------------------------------------------------------------
[docs] def __init__( self, edges: Union[Sequence[Edge], Sequence[ColoredEdge]], n_nodes: Optional[int] = None, ): """ Construct the a graph starting from a list of edges and optionally a given number of nodes. Args: edges: list of (undirected) edges n_nodes: number of nodes. Can be used to specify the number vertices in the graph if not all vertices appear in an edge. """ edges, colors = self._clean_edges(edges) if n_nodes is None: if len(edges) > 0: n_nodes = max(max(e) for e in edges) + 1 else: n_nodes = 0 graph = igraph.Graph(directed=False) graph.add_vertices(n_nodes) graph.add_edges(edges, attributes={"color": colors}) self._igraph = graph self._automorphisms = None
@staticmethod def _clean_edges(edges): """Validate and normalize edges argument.""" if not isinstance(edges, Sequence): raise TypeError("edges must be a sequence.") if len(edges) == 0: return edges, [] e0 = edges[0] if not isinstance(e0, Sequence) or len(e0) not in (2, 3): raise ValueError( "Edges must be tuple of length 2 (or 3 for colored edges)." ) if not all(len(e) == len(e0) for e in edges): raise ValueError("Either all or none of the edges need to specify a color.") if len(e0) == 2: return edges, [0] * len(edges) else: return [(v, w) for (v, w, _) in edges], [c for (*_, c) in edges] # Conversion # ------------------------------------------------------------------------
[docs] @classmethod def from_igraph(cls, graph: igraph.Graph) -> "Graph": """ Creates a new Graph instance from an igraph.Graph instance. """ if graph.is_directed(): raise ValueError("Directed graphs are not currently supported.") self = cls.__new__(cls) self._igraph = graph.copy() self._automorphisms = None if "color" not in self._igraph.edge_attributes():"color", [0] * self._igraph.ecount()) else: if not all(isinstance(c, int) for c in self.edge_colors): raise ValueError( "graph has 'color' edge attributes, but not all colors are integers." ) return self
[docs] @classmethod def from_networkx(cls, graph) -> "Graph": """ Creates a new Graph instance from a networkx graph. """ ig = igraph.Graph.from_networkx(graph) return cls.from_igraph(ig)
[docs] def to_igraph(self): """ Returns a copy of this graph as an igraph.Graph instance. """ return self._igraph.copy()
[docs] def to_networkx(self): """ Returns a copy of this graph as an igraph.Graph instance. This method requires networkx to be installed. """ return self._igraph.to_networkx()
# Graph properties # ------------------------------------------------------------------------
[docs] def adjacency_list(self) -> List[List]: return self._igraph.get_adjlist()
[docs] def is_connected(self) -> bool: return self._igraph.is_connected()
[docs] def is_bipartite(self) -> bool: return self._igraph.is_bipartite()
@property def n_nodes(self) -> int: r"""The number of nodes (or vertices) in the graph""" return self._igraph.vcount() @property def n_edges(self): r"""The number of edges in the graph.""" return self._igraph.ecount()
[docs] def nodes(self) -> Sequence[int]: return range(self._igraph.vcount())
[docs] def edges( self, color=None, *, return_color: bool = False, filter_color: Optional[int] = None, ) -> EdgeSequence: if color is not None: warn_deprecation( "The color option has been split into return_color and filter_color." ) # need to check for bool first, because bool is a subclass of int if isinstance(color, bool): return_color = color elif isinstance(color, int): filter_color = color else: raise TypeError("Incorrect type for 'color'") if not return_color and filter_color is None: return self._igraph.get_edgelist() edges_with_color = zip(self._igraph.get_edgelist(), self.edge_colors) if filter_color is not None: edges_with_color = filter(lambda x: x[1] == filter_color, edges_with_color) if return_color: return [(*e, c) for (e, c) in edges_with_color] else: return [e for (e, _) in edges_with_color]
@property def edge_colors(self) -> Sequence[int]: r"""Sequence of edge colors, in the order of the edges returned by :code:`self.edges`.""" if self.n_edges > 0: return"color") else: return [] # Graph algorithms # ------------------------------------------------------------------------
[docs] def distances(self) -> List[List]: return np.array(self._igraph.shortest_paths())
def _compute_automorphisms(self): """ Compute the graph autmorphisms of this graph. """ colors = self.edge_colors result = self._igraph.get_isomorphisms_vf2( edge_color1=colors, edge_color2=colors ) # sort them s.t. the identity comes first result = np.unique(result, axis=0).tolist() result = PermutationGroup([Permutation(i) for i in result], self.n_nodes) return result # TODO turn into a struct.property_cached?
[docs] def automorphisms(self) -> PermutationGroup: if self._automorphisms is None: self._automorphisms = self._compute_automorphisms() return self._automorphisms
# Output and drawing # ------------------------------------------------------------------------ def __repr__(self): return "{}(n_nodes={}, n_edges={})".format( str(type(self)).split(".")[-1][:-2], self.n_nodes, self.n_edges ) def Edgeless(n_nodes: int) -> Graph: """ Construct a set graph (collection of unconnected vertices). Args: nodes: An integer number of nodes or a list of ints that index nodes of a graph. Example: >>> import netket >>> g=netket.graph.Edgeless([0,1,2,3]) >>> print(g.n_nodes) 4 >>> print(g.n_edges) 0 """ return Graph([], n_nodes) def DoubledGraph(graph: AbstractGraph) -> Graph: """ DoubledGraph(graph) Constructs a DoubledGraph representing the doubled hilbert space of a density operator. The resulting graph is composed of two disjoint sub-graphs identical to the input. Args: graph: The graph to double """ dedges = list(graph.edges()) n_v = graph.n_nodes dnodes = 2 * n_v dedges += [(edge[0] + n_v, edge[1] + n_v) for edge in graph.edges()] return Graph(n_nodes=dnodes, edges=dedges) def disjoint_union(graph_1: Graph, graph_2: Graph) -> Graph: """ Returns the disjoint union of two graphs. """ return Graph.from_igraph(igraph.disjoint_union([graph_1._igraph, graph_2._igraph]))