Source code for pymatgen.analysis.chemenv.utils.graph_utils

import networkx as nx
import numpy as np
from monty.json import MSONable
import itertools
import operator

__author__ = 'waroquiers'


[docs]def get_delta(node1, node2, edge_data): if node1.isite == edge_data['start'] and node2.isite == edge_data['end']: return np.array(edge_data['delta'], dtype=np.int) elif node2.isite == edge_data['start'] and node1.isite == edge_data['end']: return -np.array(edge_data['delta'], dtype=np.int) else: raise ValueError('Trying to find a delta between two nodes with an edge ' 'that seems not to link these nodes.')
[docs]def get_all_simple_paths_edges(graph, source, target, cutoff=None, data=True): edge_paths = [] if not graph.is_multigraph(): for path in nx.all_simple_paths(graph, source, target, cutoff=cutoff): edge_paths.append([(path[ii], path[ii+1]) for ii in range(len(path) - 1)]) return edge_paths node_paths = [] for path in nx.all_simple_paths(graph, source, target, cutoff=cutoff): exists = False for path2 in node_paths: if len(path2) == len(path) and np.all(path == path2): exists = True break if exists: continue node_paths.append(path) current_edge_paths = [[]] for (node1, node2) in [(node1, path[inode1 + 1]) for inode1, node1 in enumerate(path[:-1])]: new_edge_paths = [] for key, edge_data in graph[node1][node2].items(): for tmp_edge_path in current_edge_paths: if data: new_path = [(n1, n2, k, d) for (n1, n2, k, d) in tmp_edge_path] new_path.append((node1, node2, key, edge_data)) new_edge_paths.append(new_path) else: new_path = [(n1, n2, k) for (n1, n2, k) in tmp_edge_path] new_path.append((node1, node2, key)) new_edge_paths.append(new_path) current_edge_paths = new_edge_paths edge_paths.extend(current_edge_paths) return edge_paths
def _c2index_isreverse(c1, c2): """ Private helper function to get the index c2_0_index of the first node of cycle c1 in cycle c2 and whether the cycle c2 should be reversed or not. Returns None if the first node of cycle c1 is not found in cycle c2. The reverse value depends on the index c2_1_index of the second node of cycle c1 in cycle c2 : if it is *just after* the c2_0_index, reverse is False, if it is *just before* the c2_0_index, reverse is True, otherwise the function returns None). """ c1_0 = c1.nodes[0] c1_1 = c1.nodes[1] if c1_0 not in c2.nodes: return None, None, 'First node of cycle c1 not found in cycle c2.' if c1_1 not in c2.nodes: return None, None, 'Second node of cycle c1 not found in cycle c2.' c2_0_index = c2.nodes.index(c1_0) c2_1_index = c2.nodes.index(c1_1) if c2_0_index == 0: if c2_1_index == 1: reverse = False elif c2_1_index == len(c2.nodes) - 1: reverse = True else: return None, None, 'Second node of cycle c1 is not second or last in cycle c2 ' \ '(first node of cycle c1 is first in cycle c2).' elif c2_0_index == len(c2.nodes) - 1: if c2_1_index == 0: reverse = False elif c2_1_index == c2_0_index - 1: reverse = True else: return None, None, 'Second node of cycle c1 is not first or before last in cycle c2 ' \ '(first node of cycle c1 is last in cycle c2).' else: if c2_1_index == c2_0_index + 1: reverse = False elif c2_1_index == c2_0_index - 1: reverse = True else: return None, None, 'Second node of cycle c1 in cycle c2 is not just after or ' \ 'just before first node of cycle c1 in cycle c2.' return c2_0_index, reverse, ''
[docs]class SimpleGraphCycle(MSONable): """ Class used to describe a cycle in a simple graph (graph without multiple edges). Note that the convention used here is the networkx convention for which simple graphs allow to have self-loops in a simple graph. No simple graph cycle with two nodes is possible in a simple graph. The graph will not be validated if validate is set to False. By default, the "ordered" parameter is None, in which case the SimpleGraphCycle will be ordered. If the user explicitly sets ordered to False, the SimpleGraphCycle will not be ordered. """ def __init__(self, nodes, validate=True, ordered=None): self.nodes = tuple(nodes) if validate: self.validate() if ordered is not None: self.ordered = ordered else: self.order() def _is_valid(self, check_strict_ordering=False): """Check if a SimpleGraphCycle is valid. This method checks : - that there are no duplicate nodes, - that there are either 1 or more than 2 nodes :return: True if the SimpleGraphCycle is valid, False otherwise. """ if len(self.nodes) == 1: return True, '' elif len(self.nodes) == 2: return False, 'Simple graph cycle with 2 nodes is not valid.' elif len(self.nodes) == 0: return False, 'Empty cycle is not valid.' if len(self.nodes) != len(set(self.nodes)): # Should not have duplicate nodes return False, 'Duplicate nodes.' if check_strict_ordering: try: sorted_nodes = sorted(self.nodes) except TypeError as te: msg = te.args[0] if '\'<\' not supported between instances of' in msg: return False, 'The nodes are not sortable.' raise res = all(i < j for i, j in zip(sorted_nodes, sorted_nodes[1:])) if not res: return False, 'The list of nodes in the cycle cannot be strictly ordered.' return True, ''
[docs] def validate(self, check_strict_ordering=False): is_valid, msg = self._is_valid(check_strict_ordering=check_strict_ordering) if not is_valid: raise ValueError('SimpleGraphCycle is not valid : {}'.format(msg))
[docs] def order(self, raise_on_fail=True): """Orders the SimpleGraphCycle. The ordering is performed such that the first node is the "lowest" one and the second node is the lowest one of the two neighbor nodes of the first node. If raise_on_fail is set to True a RuntimeError will be raised if the ordering fails. :param raise_on_fail: If set to True, will raise a RuntimeError if the ordering fails. :return: None """ # always validate the cycle if it needs to be ordered # also validates that the nodes can be strictly ordered try: self.validate(check_strict_ordering=True) except ValueError as ve: msg = ve.args[0] if 'SimpleGraphCycle is not valid :' in msg and not raise_on_fail: self.ordered = False return raise if len(self.nodes) == 1: self.ordered = True return # Not sure whether the following should be checked here... if strict ordering was guaranteed by # the validate method, why would it be needed to have a unique class. One could have 2 subclasses of # the same parent class and things could be ok. To be checked what to do. (see also MultiGraphCycle) node_classes = set(n.__class__ for n in self.nodes) if len(node_classes) > 1: if raise_on_fail: raise ValueError('Could not order simple graph cycle as the nodes ' 'are of different classes.') self.ordered = False return min_index, min_node = min(enumerate(self.nodes), key=operator.itemgetter(1)) reverse = self.nodes[(min_index-1) % len(self.nodes)] < self.nodes[(min_index+1) % len(self.nodes)] if reverse: self.nodes = self.nodes[min_index::-1] + self.nodes[:min_index:-1] else: self.nodes = self.nodes[min_index:] + self.nodes[:min_index] self.ordered = True
def __hash__(self): return len(self.nodes) def __len__(self): return len(self.nodes) def __str__(self): out = ['Simple cycle with nodes :'] out.extend([str(node) for node in self.nodes]) return '\n'.join(out) def __eq__(self, other): if not self.ordered or not other.ordered: raise RuntimeError('Simple cycles should be ordered in order to be compared.') return self.nodes == other.nodes
[docs] @classmethod def from_edges(cls, edges, edges_are_ordered=True): """Constructs SimpleGraphCycle from a list edges. By default, the edges list is supposed to be ordered as it will be much faster to construct the cycle. If edges_are_ordered is set to False, the code will automatically try to find the corresponding edge order in the list. """ if edges_are_ordered: nodes = [e[0] for e in edges] if not all([e1e2[0][1] == e1e2[1][0] for e1e2 in zip(edges, edges[1:])]) or edges[-1][1] != edges[0][0]: raise ValueError('Could not construct a cycle from edges.') else: remaining_edges = list(edges) nodes = list(remaining_edges.pop()) while remaining_edges: prev_node = nodes[-1] for ie, e in enumerate(remaining_edges): if prev_node == e[0]: remaining_edges.pop(ie) nodes.append(e[1]) break elif prev_node == e[1]: remaining_edges.pop(ie) nodes.append(e[0]) break else: # did not find the next edge raise ValueError('Could not construct a cycle from edges.') if nodes[0] != nodes[-1]: raise ValueError('Could not construct a cycle from edges.') nodes.pop() return cls(nodes)
[docs] def as_dict(self): d = MSONable.as_dict(self) # Transforming tuple object to a list to allow BSON and MongoDB d['nodes'] = list(d['nodes']) return d
[docs] @classmethod def from_dict(cls, d, validate=False): return cls(nodes=d['nodes'], validate=validate, ordered=d['ordered'])
[docs]class MultiGraphCycle(MSONable): """Class used to describe a cycle in a multigraph. nodes are the nodes of the cycle and edge_indices are the indices of the edges in the cycle. The nth index in edge_indices corresponds to the edge index between the nth node in nodes and the (n+1)th node in nodes with the exception of the last one being the edge index between the last node in nodes and the first node in nodes Example: A cycle nodes: 1 - 3 - 4 - 0 - 2 - (1) edge_indices: 0 . 1 . 0 . 2 . 0 . (0) """ def __init__(self, nodes, edge_indices, validate=True, ordered=None): self.nodes = tuple(nodes) self.edge_indices = tuple(edge_indices) if validate: self.validate() if ordered is not None: self.ordered = ordered else: self.order() self.edge_deltas = None self.per = None def _is_valid(self, check_strict_ordering=False): """Check if a MultiGraphCycle is valid. This method checks : - that there are no duplicate nodes, - that there are either 1 or more than 2 nodes :return: True if the SimpleGraphCycle is valid, False otherwise. """ if len(self.nodes) != len(self.edge_indices): # Should have the same number of nodes and edges return False, 'Number of nodes different from number of edge indices.' if len(self.nodes) == 0: return False, 'Empty cycle is not valid.' if len(self.nodes) != len(set(self.nodes)): # Should not have duplicate nodes return False, 'Duplicate nodes.' if len(self.nodes) == 2: # Cycles with two nodes cannot use the same edge for the cycle if self.edge_indices[0] == self.edge_indices[1]: return False, 'Cycles with two nodes cannot use the same edge for the cycle.' if check_strict_ordering: try: sorted_nodes = sorted(self.nodes) except TypeError as te: msg = te.args[0] if '\'<\' not supported between instances of' in msg: return False, 'The nodes are not sortable.' raise res = all(i < j for i, j in zip(sorted_nodes, sorted_nodes[1:])) if not res: return False, 'The list of nodes in the cycle cannot be strictly ordered.' return True, ''
[docs] def validate(self, check_strict_ordering=False): is_valid, msg = self._is_valid(check_strict_ordering=check_strict_ordering) if not is_valid: raise ValueError('MultiGraphCycle is not valid : {}'.format(msg))
[docs] def order(self, raise_on_fail=True): """Orders the SimpleGraphCycle. The ordering is performed such that the first node is the "lowest" one and the second node is the lowest one of the two neighbor nodes of the first node. If raise_on_fail is set to True a RuntimeError will be raised if the ordering fails. :param raise_on_fail: If set to True, will raise a RuntimeError if the ordering fails. :return: None """ # always validate the cycle if it needs to be ordered # also validates that the nodes can be strictly ordered try: self.validate(check_strict_ordering=True) except ValueError as ve: msg = ve.args[0] if 'MultiGraphCycle is not valid :' in msg and not raise_on_fail: self.ordered = False return raise if len(self.nodes) == 1: self.ordered = True return # Not sure whether the following should be checked here... if strict ordering was guaranteed by # the validate method, why would it be needed to have a unique class. One could have 2 subclasses of # the same parent class and things could be ok. To be checked what to do. (see also SimpleGraphCycle) node_classes = set(n.__class__ for n in self.nodes) if len(node_classes) > 1: if raise_on_fail: raise ValueError('Could not order simple graph cycle as the nodes ' 'are of different classes.') self.ordered = False return min_index, min_node = min(enumerate(self.nodes), key=operator.itemgetter(1)) # Special case when number of nodes is 2 because the two # edge_indices refer to the same pair of nodes if len(self.nodes) == 2: self.nodes = tuple(sorted(self.nodes)) self.edge_indices = tuple(sorted(self.edge_indices)) self.ordered = True return reverse = self.nodes[(min_index-1) % len(self.nodes)] < self.nodes[(min_index+1) % len(self.nodes)] if reverse: self.nodes = self.nodes[min_index::-1] + self.nodes[:min_index:-1] min_edge_index = (min_index-1) % len(self.nodes) self.edge_indices = self.edge_indices[min_edge_index::-1] + self.edge_indices[:min_edge_index:-1] else: self.nodes = self.nodes[min_index:] + self.nodes[:min_index] self.edge_indices = self.edge_indices[min_index:] + self.edge_indices[:min_index] self.ordered = True
def __hash__(self): return len(self.nodes) def __len__(self): return len(self.nodes) def __str__(self): out = ['Multigraph cycle with nodes :'] cycle = [] for inode, node1, node2 in zip(itertools.count(), self.nodes[:-1], self.nodes[1:]): cycle.append('{} -*{:d}*- {}'.format(str(node1), self.edge_indices[inode], str(node2))) cycle.append('{} -*{:d}*- {}'.format(str(self.nodes[-1]), self.edge_indices[-1], str(self.nodes[0]))) # out.extend([str(node) for node in self.nodes]) out.extend(cycle) return '\n'.join(out) def __eq__(self, other): if not self.ordered or not other.ordered: raise RuntimeError('Multigraph cycles should be ordered in order to be compared.') return self.nodes == other.nodes and self.edge_indices == other.edge_indices
[docs]def get_all_elementary_cycles(graph): if not isinstance(graph, nx.Graph): raise TypeError("graph should be a networkx Graph object.") cycle_basis = nx.cycle_basis(graph) # print('CYCLE BASIS') # print(cycle_basis) if len(cycle_basis) < 2: return {SimpleGraphCycle(c) for c in cycle_basis} all_edges_dict = {} index2edge = [] nedges = 0 for n1, n2 in graph.edges: all_edges_dict[(n1, n2)] = nedges all_edges_dict[(n2, n1)] = nedges index2edge.append((n1, n2)) nedges += 1 cycles_matrix = np.zeros(shape=(len(cycle_basis), nedges), dtype=np.bool) for icycle, cycle in enumerate(cycle_basis): for in1, n1 in enumerate(cycle): n2 = cycle[(in1 + 1) % len(cycle)] iedge = all_edges_dict[(n1, n2)] cycles_matrix[icycle, iedge] = True # print(cycles_matrix) elementary_cycles_list = list() for ncycles in range(1, len(cycle_basis) + 1): for cycles_combination in itertools.combinations(cycles_matrix, ncycles): edges_counts = np.array(np.mod(np.sum(cycles_combination, axis=0), 2), dtype=np.bool) myedges = [edge for iedge, edge in enumerate(index2edge) if edges_counts[iedge]] # print(myedges) try: sgc = SimpleGraphCycle.from_edges(myedges, edges_are_ordered=False) # print(sgc) except ValueError as ve: msg = ve.args[0] if msg == 'SimpleGraphCycle is not valid : Duplicate nodes.': continue elif msg == 'Could not construct a cycle from edges.': continue raise elementary_cycles_list.append(sgc) return elementary_cycles_list