Graph symmetries (permutations) that map the graph onto itself.
499852
def symmetries(self):
        """"""

        symmetry_cycles = set([])
        symmetries = set([])
        for match in GraphSearch(EqualPattern(self))(self):
            match.cycles = match.get_closed_cycles()
            if match.cycles in symmetry_cycles:
                raise RuntimeError("Duplicates in EqualMatch")
            symmetry_cycles.add(match.cycles)
            symmetries.add(match)
        return symmetries
1168296
def symmetrize(self, method=None, copy=False):
    ''''''
    if copy:
      return SymmEdgePairGraph(self._pairs.copy(),
                               num_vertices=self._num_vertices)
    shape = (self._num_vertices, self._num_vertices)
    flat_inds = np.union1d(np.ravel_multi_index(self._pairs.T, shape),
                           np.ravel_multi_index(self._pairs.T[::-1], shape))
    self._pairs = np.transpose(np.unravel_index(flat_inds, shape))
    return self
765231
def _edge_mapping(G):
    
    edge_mapping = {edge: idx for idx, edge in enumerate(G.edges)}
    edge_mapping.update({(e1, e0): idx for (e0, e1), idx in edge_mapping.items()})
    return edge_mapping
114136
private long[] refine(long[] invariants, boolean[] hydrogens) {

        int ord = g.length;

        InvariantRanker ranker = new InvariantRanker(ord);

        // current/next vertices, these only hold the vertices which are
        // equivalent
        int[] currVs = new int[ord];
        int[] nextVs = new int[ord];

        // fill with identity (also set number of non-unique)
        int nnu = ord;
        for (int i = 0; i < ord; i++)
            currVs[i] = i;

        long[] prev = invariants;
        long[] curr = Arrays.copyOf(invariants, ord);

        // initially all labels are 1, the input invariants are then used to
        // refine this coarse partition
        Arrays.fill(prev, 1L);

        // number of ranks
        int n = 0, m = 0;

        // storage of symmetry classes
        long[] symmetry = null;

        while (n < ord) {

            // refine the initial invariants using product of primes from
            // adjacent ranks
            while ((n = ranker.rank(currVs, nextVs, nnu, curr, prev)) > m && n < ord) {
                nnu = 0;
                for (int i = 0; i < ord && nextVs[i] >= 0; i++) {
                    int v = nextVs[i];
                    currVs[nnu++] = v;
                    curr[v] = hydrogens[v] ? prev[v] : primeProduct(g[v], prev, hydrogens);
                }
                m = n;
            }

            if (symmetry == null) {

                // After symmetry classes have been found without hydrogens we add
                // back in the hydrogens and assign ranks. We don't refine the
                // partition until the next time round the while loop to avoid
                // artificially splitting due to hydrogen representation, for example
                // the two hydrogens are equivalent in this SMILES for ethane '[H]CC'
                for (int i = 0; i < g.length; i++) {
                    if (hydrogens[i]) {
                        curr[i] = prev[g[i][0]];
                        hydrogens[i] = false;
                    }
                }
                n = ranker.rank(currVs, nextVs, nnu, curr, prev);
                symmetry = Arrays.copyOf(prev, ord);

                // Update the buffer of non-unique vertices as hydrogens next
                // to discrete heavy atoms are also discrete (and removed from
                // 'nextVs' during ranking.
                nnu = 0;
                for (int i = 0; i < ord && nextVs[i] >= 0; i++) {
                    currVs[nnu++] = nextVs[i];
                }
            }

            // partition is discrete or only symmetry classes are needed
            if (symOnly || n == ord) return symmetry;

            // artificially split the lowest cell, we perturb the value
            // of all vertices with equivalent rank to the lowest non-unique
            // vertex
            int lo = nextVs[0];
            for (int i = 1; i < ord && nextVs[i] >= 0 && prev[nextVs[i]] == prev[lo]; i++)
                prev[nextVs[i]]++;

            // could also swap but this is cleaner
            System.arraycopy(nextVs, 0, currVs, 0, nnu);
        }

        return symmetry;
    }
1220853
def laplacian_reordering(G):
  ''''''
  L = G.laplacian()
  vals, vecs = np.linalg.eigh(L)
  min_positive_idx = np.argmax(vals == vals[vals>0].min())
  vec = vecs[:, min_positive_idx]
  return permute_graph(G, np.argsort(vec))
221859
def _iter_new_relations(self, init_match, subject_graph, edges0, constraints0, edges1):
        """"""
        # Count the number of unique edges0[i][1] values. This is also
        # the number of new relations.
        num_new_relations = len(set(j for i, j in edges0))

        def combine_small(relations, num):
            """iterate over all compatible combinations within one set of relations"""
            if len(relations) == 0:
                return
            for i, pivot in enumerate(relations):
                if num == 1:
                    yield (pivot, )
                else:
                    compatible_relations = list(
                        item for item in relations[:i]
                        if pivot[0]!=item[0] and pivot[1]!=item[1]
                    )
                    for tail in combine_small(compatible_relations, num-1):
                        yield (pivot, ) + tail

        # generate candidate relations
        candidate_relations = []
        icg = self._iter_candidate_groups(init_match, edges0, edges1)
        for end_vertices0, end_vertices1 in icg:
            if len(end_vertices0) > len(end_vertices1):
                return # this can never work, the subject graph is 'too small'
            elif not self.pattern.sub and \
                 len(end_vertices0) != len(end_vertices1):
                return # an exact match is sought, this can never work
            l = []
            for end_vertex0 in end_vertices0:
                for end_vertex1 in end_vertices1:
                    if self.pattern.compare(end_vertex0, end_vertex1, subject_graph):
                        l.append((end_vertex0, end_vertex1))
            # len(end_vertices0) = the total number of relations that must be
            # made in this group
            if len(l) > 0:
                # turn l into a list of sets of internally compatible candidate
                # relations in this group
                l = list(combine_small(l, len(end_vertices0)))
                candidate_relations.append(l)
        if len(candidate_relations) == 0:
            return
        self.print_debug("candidate_relations: %s" % candidate_relations)

        def combine_big(pos=0):
            """Iterate over all possible sets of relations"""
            # pos is an index in candidate_relations
            crs = candidate_relations[pos]
            if pos == len(candidate_relations)-1:
                for relations in crs:
                    yield relations
            else:
                for tail in combine_big(pos+1):
                    for relations in crs:
                        yield relations + tail

        # final loop
        for new_relations in combine_big():
            new_relations = set(new_relations)
            self.print_debug("new_relations: %s" % (new_relations, ))
            # check the total number of new relations
            if len(new_relations) != num_new_relations:
                continue
            # check sanity of relations
            forward = dict(new_relations)
            if len(forward) != num_new_relations:
                continue
            reverse = dict((j, i) for i, j in new_relations)
            if len(reverse) != num_new_relations:
                continue
            # check the constraints
            for a0, b0 in constraints0:
                if forward[a0] not in subject_graph.neighbors[forward[b0]]:
                    forward = None
                    break
            if forward is None:
                continue
            yield forward
994365
function graph(g) {
    init(g);

    var xs = [upperLeft(g), upperRight(g), lowerRight(g), lowerLeft(g)];

    g.nodes().forEach(function(u) {
      var xArray = [];
      for (var i = 0; i < xs.length; ++i) {
        xArray.push(xs[i][u]);
      }
      xArray.sort();
      g.node(u).x = (xArray[1] + xArray[2]) / 2;
    });
  }
636719
def graph_from_edges(edges: Iterable[Edge], **kwargs) -> BELGraph:
    """"""
    graph = BELGraph(**kwargs)

    for edge in edges:
        edge.insert_into_graph(graph)

    return graph
345089
def copy(self):
        
        other = DirectedGraph()
        other._vertices = set(self._vertices)
        other._forwards = {k: set(v) for k, v in self._forwards.items()}
        other._backwards = {k: set(v) for k, v in self._backwards.items()}
        return other
229407
def connected_subgraphs(self, directed=True, ordered=False):
    '''
    '''
    num_ccs, labels = self.connected_components(directed=directed)
    # check the trivial case first
    if num_ccs == 1:
      yield self
      raise StopIteration
    if ordered:
      # sort by descending size (num vertices)
      order = np.argsort(np.bincount(labels))[::-1]
    else:
      order = range(num_ccs)

    # don't use self.subgraph() here, because we can reuse adj
    adj = self.matrix('dense', 'csr', 'csc')
    for c in order:
      mask = labels == c
      sub_adj = adj[mask][:,mask]
      yield self.__class__.from_adj_matrix(sub_adj)
1083085
private int rankPermutationLexicographically(int[] permutation) {
        int rank = 0;
        int n = permutation.length;
        int[] counter = new int[n + 1];
        for (int i = 1; i < permutation.length; i++) {
            counter[i] = permutation[i - 1] + 1;
        }
        for (int j = 1; j <= n; j++) {
            rank += (counter[j] - 1) * factorial(n - j);
            for (int i = j + 1; i <= n; i++) {
                if (counter[i] > counter[j]) {
                    counter[i]--;
                }
            }
        }
        return rank + 1;
    }
1200458
def get_symmetry_operations(self, cartesian=False):
        
        rotation, translation = self._get_symmetry()
        symmops = []
        mat = self._structure.lattice.matrix.T
        invmat = np.linalg.inv(mat)
        for rot, trans in zip(rotation, translation):
            if cartesian:
                rot = np.dot(mat, np.dot(rot, invmat))
                trans = np.dot(trans, self._structure.lattice.matrix)
            op = SymmOp.from_rotation_and_translation(rot, trans)
            symmops.append(op)
        return symmops
440477
def reverse(self):
        
        assert self.DIRECTED, "Undirected graph types such as %s cannot be reversed" % self.__class__.__name__
        
        N = self.__class__()
    
        #- Add the nodes
        N.add_nodes( n for n in self.nodes() )
    
        #- Add the reversed edges
        for (u, v) in self.edges():
            wt = self.edge_weight((u, v))
            label = self.edge_label((u, v))
            attributes = self.edge_attributes((u, v))
            N.add_edge((v, u), wt, label, attributes)
        return N
676258
def equivalent(kls, first, second):
    
    if first.empty() and second.empty():
      return True
    elif first.vertices.shape[0] != second.vertices.shape[0]:
      return False
    elif first.edges.shape[0] != second.edges.shape[0]:
      return False

    EPSILON = 1e-7

    vertex1, inv1 = np.unique(first.vertices, axis=0, return_inverse=True)
    vertex2, inv2 = np.unique(second.vertices, axis=0, return_inverse=True)

    vertex_match = np.all(np.abs(vertex1 - vertex2) < EPSILON)
    if not vertex_match:
      return False

    remapping = {}
    for i in range(len(inv1)):
      remapping[inv1[i]] = inv2[i]
    remap = np.vectorize(lambda idx: remapping[idx])

    edges1 = np.sort(np.unique(first.edges, axis=0), axis=1)
    edges1 = edges1[np.lexsort(edges1[:,::-1].T)]

    edges2 = remap(second.edges)
    edges2 = np.sort(np.unique(edges2, axis=0), axis=1)
    edges2 = edges2[np.lexsort(edges2[:,::-1].T)]
    edges_match = np.all(edges1 == edges2)

    if not edges_match:
      return False

    second_verts = {}
    for i, vert in enumerate(second.vertices):
      second_verts[tuple(vert)] = i
    
    for i in range(len(first.radii)):
      i2 = second_verts[tuple(first.vertices[i])]

      if first.radii[i] != second.radii[i2]:
        return False

      if first.vertex_types[i] != second.vertex_types[i2]:
        return False

    return True
1284201
def get_substructure_mapping(self, other, limit=1):
        
        i = self._matcher(other).subgraph_isomorphisms_iter()
        if limit == 1:
            m = next(i, None)
            if m:
                return {v: k for k, v in m.items()}
            return
        elif limit == 0:
            return ({v: k for k, v in m.items()} for m in i)
        return [{v: k for k, v in m.items()} for m in islice(i, limit)]
570980
function (graph, opts, params) {
    if (graph.children.length == 0) return '';

    function getRels(node) {
      var rels = [];
      node.children.forEach(function(childNode) {
        rels.push('(' + node.name + ')-[__rel_' + childNode.name + ':' + childNode.comp.rel + ']->(' + childNode.name + ')');
        rels.push.apply(rels, getRels(childNode));
      });
      return rels;
    }
    
    return 'CREATE UNIQUE ' + getRels(graph).join(',');
  }
787564
def _node_isomorphic(a, b, check_varprops=True):
    
    # first some quick checks
    a_var_refs = sorted(len(vd['refs']) for vd in a._vars.values())
    b_var_refs = sorted(len(vd['refs']) for vd in b._vars.values())
    if a_var_refs != b_var_refs:
        return False
    print()

    # these signature: [node] indices are meant to avoid unnecessary
    # comparisons; they also take care of "semantic feasibility"
    # constraints (comparing node values and properties). All that's
    # left is the "syntactic feasibility", or node-edge shapes.
    # nodedicts are {sig: [(id, edges), ...], ...}
    a_nd = _node_isomorphic_build_nodedict(a, check_varprops)
    #print('a', a_nd)
    b_nd = _node_isomorphic_build_nodedict(b, check_varprops)
    #print('b', b_nd)
    #return

    a_sigs = {}  # for node -> sig mapping
    # don't recurse when things are unique
    agenda = []
    isomap = {}
    for sig, a_pairs in sorted(a_nd.items(), key=lambda x: len(x[1])):
        b_pairs = b_nd.get(sig, [])
        if len(a_pairs) != len(b_pairs):
            return False
        if len(a_pairs) == 1:
            a_, a_edges = a_pairs[0]
            b_, b_edges = b_pairs[0]
            if len(a_edges) != len(b_edges):
                return False
            a_sigs[a_] = sig
            isomap[a_] = b_
            for edge, a_tgt in a_edges.items():
                if edge not in b_edges:
                    return False
                isomap[a_tgt] = b_edges[edge]
        else:
            for a_, ed in a_pairs:
                a_sigs[a_] = sig
                agenda.append((a_, sig, ed))
    #print(agenda)
    #return
    isomaps = _node_isomorphic(agenda, a_sigs, b_nd, isomap, {})
    # for sig, a_candidates in sorted(a_nodes.items(), key=lambda x: len(x[1])):
    #     b_candidates = b_nodes.get(sig, [])
    #     if len(a_candidates) != len(b_candidates): return False
    #     candidates.append((a_candidates, b_candidates))
    #
    # nodemaps = _isomorphic(a, b, candidates, {})
    try:
        next(isomaps)
        return True
    except StopIteration:
        return False