Fix conflict netcomp (#17)

* Fix imports * Move graph metrics to a sep dir * Add netcomp components * Correct license
aimclub · Dec 26, 2022 · 55063b2 · 55063b2
1 parent 147b896
commit 55063b2
Show file tree

Hide file tree

Showing 14 changed files with 281 additions and 18 deletions.
diff --git a/.github/workflows/unit-build.yml b/.github/workflows/unit-build.yml
@@ -30,7 +30,6 @@ jobs:
         pip install pytest
         pip install .[docs]
         pip install .[profilers]
-        pip install .[examples]
         pip install pytest-cov
     - name: Test with pytest
       run: |

diff --git a/examples/synthetic_graph_evolution/abstract_graph_search.py b/examples/synthetic_graph_evolution/abstract_graph_search.py
@@ -4,7 +4,7 @@
 from itertools import product
 from typing import Sequence, Type
 
-from examples.synthetic_graph_evolution.graph_metrics import *
+from golem.metrics.graph_metrics import *
 from examples.synthetic_graph_evolution.utils import draw_graphs_subplots
 from golem.core.adapter.nx_adapter import BaseNetworkxAdapter, nx_to_directed
 from golem.core.dag.verification_rules import has_no_self_cycled_nodes
@@ -16,8 +16,6 @@
 from golem.core.optimisers.graph import OptGraph, OptNode
 from golem.core.optimisers.objective import Objective
 from golem.core.optimisers.optimizer import GraphGenerationParams, GraphOptimizer
-from golem.core.optimisers.random.random_mutation_optimizer import RandomMutationSearchOptimizer
-from golem.core.optimisers.random.random_search import RandomSearchOptimizer
 
 NumNodes = int
 DiGraphGenerator = Callable[[NumNodes], nx.DiGraph]

diff --git a/examples/synthetic_graph_evolution/utils.py b/examples/synthetic_graph_evolution/utils.py
@@ -1,13 +1,12 @@
-from collections.abc import Sequence
 from datetime import datetime
-from typing import Tuple, Optional
+from typing import Tuple, Optional, Sequence
 
 import matplotlib.pyplot as plt
 import networkx as nx
 import numpy as np
 from networkx import gnp_random_graph
 
-from examples.synthetic_graph_evolution.graph_metrics import spectral_dists_all
+from golem.metrics.graph_metrics import spectral_dists_all
 from golem.core.adapter.nx_adapter import BaseNetworkxAdapter
 from golem.core.optimisers.opt_history_objects.opt_history import OptHistory
 from golem.visualisation.graph_viz import GraphVisualizer

diff --git a/golem/metrics/__init__.py b/golem/metrics/__init__.py
diff --git a/...nthetic_graph_evolution/graph_features.py → golem/metrics/graph_features.py b/...nthetic_graph_evolution/graph_features.py → golem/metrics/graph_features.py
@@ -1,11 +1,10 @@
-from collections.abc import Sequence
-from typing import Callable, Tuple
+from typing import Callable, Sequence, Tuple
 
 import networkx as nx
 import numpy as np
 
-from examples.synthetic_graph_evolution import mmd
-from examples.synthetic_graph_evolution.mmd import compute_mmd
+from golem.metrics import mmd
+from golem.metrics.mmd import compute_mmd
 
 
 def compute_all_stats(graph_prediction: Sequence[nx.Graph],

diff --git a/...ynthetic_graph_evolution/graph_metrics.py → golem/metrics/graph_metrics.py b/...ynthetic_graph_evolution/graph_metrics.py → golem/metrics/graph_metrics.py
@@ -1,15 +1,15 @@
 from datetime import timedelta
 from typing import Optional, Callable, Dict
 
-import netcomp
 import networkx as nx
 import numpy as np
-from netcomp import laplacian_matrix, normalized_laplacian_eig
-from netcomp.linalg import _eigs
 from networkx import graph_edit_distance
 
-from examples.synthetic_graph_evolution.graph_features import degree_stats
 from golem.core.optimisers.optimization_parameters import GraphRequirements
+from golem.metrics.graph_features import degree_stats
+from netcomp_components.distance import edit_distance
+from netcomp_components.eigenstuff import _eigs, normalized_laplacian_eig
+from netcomp_components.matrices import laplacian_matrix
 
 
 def nxgraph_stats(graph: nx.Graph):
@@ -67,7 +67,7 @@ def matrix_edit_dist(target_graph: nx.DiGraph, graph: nx.DiGraph) -> float:
         shape = (nmax, nmax)
         target_adj.resize(shape)
         adj.resize(shape)
-    value = netcomp.edit_distance(target_adj, adj)
+    value = edit_distance(target_adj, adj)
     return value
 
 

diff --git a/examples/synthetic_graph_evolution/mmd.py → golem/metrics/mmd.py b/examples/synthetic_graph_evolution/mmd.py → golem/metrics/mmd.py
diff --git a/netcomp_components/LICENSE b/netcomp_components/LICENSE
@@ -0,0 +1,21 @@
+MIT License
+
+Copyright (c) 2017 Peter Wills (https://github.com/peterewills/NetComp)
+
+Permission is hereby granted, free of charge, to any person obtaining a copy
+of this software and associated documentation files (the "Software"), to deal
+in the Software without restriction, including without limitation the rights
+to use, copy, modify, merge, publish, distribute, sublicense, and/or sell
+copies of the Software, and to permit persons to whom the Software is
+furnished to do so, subject to the following conditions:
+
+The above copyright notice and this permission notice shall be included in all
+copies or substantial portions of the Software.
+
+THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND, EXPRESS OR
+IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF MERCHANTABILITY,
+FITNESS FOR A PARTICULAR PURPOSE AND NONINFRINGEMENT. IN NO EVENT SHALL THE
+AUTHORS OR COPYRIGHT HOLDERS BE LIABLE FOR ANY CLAIM, DAMAGES OR OTHER
+LIABILITY, WHETHER IN AN ACTION OF CONTRACT, TORT OR OTHERWISE, ARISING FROM,
+OUT OF OR IN CONNECTION WITH THE SOFTWARE OR THE USE OR OTHER DEALINGS IN THE
+SOFTWARE.
diff --git a/netcomp_components/__init__.py b/netcomp_components/__init__.py
diff --git a/netcomp_components/distance.py b/netcomp_components/distance.py
@@ -0,0 +1,19 @@
+import numpy as np
+
+
+def edit_distance(A1, A2):
+    """The edit distance between graphs, defined as the number of changes one
+    needs to make to put the edge lists in correspondence.
+
+    Parameters
+    ----------
+    A1, A2 : NumPy matrices
+        Adjacency matrices of graphs to be compared
+
+    Returns
+    -------
+    dist : float
+        The edit distance between the two graphs
+    """
+    dist = np.abs((A1 - A2)).sum() / 2
+    return dist
diff --git a/netcomp_components/eigenstuff.py b/netcomp_components/eigenstuff.py
@@ -0,0 +1,132 @@
+"""
+**********
+Eigenstuff
+**********
+
+Functions for calculating eigenstuff of graphs.
+"""
+
+from scipy import sparse as sps
+import numpy as np
+from scipy.sparse import linalg as spla
+from numpy import linalg as la
+
+from scipy.sparse import issparse
+
+from netcomp_components.matrices import _flat, _eps
+
+
+######################
+## Helper Functions ##
+######################
+
+
+def _eigs(M, which='SR', k=None):
+    """ Helper function for getting eigenstuff.
+
+    Parameters
+    ----------
+    M : matrix, numpy or scipy sparse
+        The matrix for which we hope to get eigenstuff.
+    which : string in {'SR','LR'}
+        If 'SR', get eigenvalues with smallest real part. If 'LR', get largest.
+    k : int
+        Number of eigenvalues to return
+
+    Returns
+    -------
+    evals, evecs : numpy arrays
+        Eigenvalues and eigenvectors of matrix M, sorted in ascending or
+        descending order, depending on 'which'.
+
+    See Also
+    --------
+    numpy.linalg.eig
+    scipy.sparse.eigs        
+    """
+    n, _ = M.shape
+    if k is None:
+        k = n
+    if which not in ['LR', 'SR']:
+        raise ValueError("which must be either 'LR' or 'SR'.")
+    M = M.astype(float)
+    if issparse(M) and k < n - 1:
+        evals, evecs = spla.eigs(M, k=k, which=which)
+    else:
+        try:
+            M = M.todense()
+        except:
+            pass
+        evals, evecs = la.eig(M)
+        # sort dem eigenvalues
+        inds = np.argsort(evals)
+        if which == 'LR':
+            inds = inds[::-1]
+        else:
+            pass
+        inds = inds[:k]
+        evals = evals[inds]
+        evecs = np.matrix(evecs[:, inds])
+    return np.real(evals), np.real(evecs)
+
+
+#####################
+##  Get Eigenstuff ##
+#####################
+
+def normalized_laplacian_eig(A, k=None):
+    """Return the eigenstuff of the normalized Laplacian matrix of graph
+    associated with adjacency matrix A.
+
+    Calculates via eigenvalues if 
+
+    K = D^(-1/2) A D^(-1/2)
+
+    where `A` is the adjacency matrix and `D` is the diagonal matrix of
+    node degrees. Since L = I - K, the eigenvalues and vectors of L can 
+    be easily recovered.
+
+    Parameters
+    ----------
+    A : NumPy matrix
+        Adjacency matrix of a graph
+
+    k : int, 0 < k < A.shape[0]-1
+        The number of eigenvalues to grab. 
+
+    Returns
+    -------
+    lap_evals : NumPy array
+       Eigenvalues of L
+
+    evecs : NumPy matrix
+       Columns are the eigenvectors of L
+
+    Notes
+    -----
+    This way of calculating the eigenvalues of the normalized graph laplacian is
+    more numerically stable than simply forming the matrix L = I - K and doing
+    numpy.linalg.eig on the result. This is because the eigenvalues of L are
+    close to zero, whereas the eigenvalues of K are close to 1.
+
+    References
+    ----------
+
+    See Also
+    --------
+    nx.laplacian_matrix
+    nx.normalized_laplacian_matrix
+    """
+    n, m = A.shape
+    ##
+    ## TODO: implement checks on the adjacency matrix
+    ##
+    degs = _flat(A.sum(axis=1))
+    # the below will break if
+    inv_root_degs = [d ** (-1 / 2) if d > _eps else 0 for d in degs]
+    inv_rootD = sps.spdiags(inv_root_degs, [0], n, n, format='csr')
+    # build normalized diffusion matrix
+    K = inv_rootD * A * inv_rootD
+    evals, evecs = _eigs(K, k=k, which='LR')
+    lap_evals = 1 - evals
+    return np.real(lap_evals), np.real(evecs)
diff --git a/netcomp_components/matrices.py b/netcomp_components/matrices.py
@@ -0,0 +1,95 @@
+"""
+********
+Matrices
+********
+
+Matrices associated with graphs. Also contains linear algebraic helper functions.
+"""
+
+from scipy import sparse as sps
+from scipy.sparse import issparse
+import numpy as np
+
+_eps = 10 ** (-10)  # a small parameter
+
+
+######################
+## Helper Functions ##
+######################
+
+
+def _flat(D):
+    """Flatten column or row matrices, as well as arrays."""
+    if issparse(D):
+        raise ValueError('Cannot flatten sparse matrix.')
+    d_flat = np.array(D).flatten()
+    return d_flat
+
+
+def _pad(A, N):
+    """Pad A so A.shape is (N,N)"""
+    n, _ = A.shape
+    if n >= N:
+        return A
+    else:
+        if issparse(A):
+            # thrown if we try to np.concatenate sparse matrices
+            side = sps.csr_matrix((n, N - n))
+            bottom = sps.csr_matrix((N - n, N))
+            A_pad = sps.hstack([A, side])
+            A_pad = sps.vstack([A_pad, bottom])
+        else:
+            side = np.zeros((n, N - n))
+            bottom = np.zeros((N - n, N))
+            A_pad = np.concatenate([A, side], axis=1)
+            A_pad = np.concatenate([A_pad, bottom])
+        return A_pad
+
+
+########################
+## Matrices of Graphs ##
+########################
+
+
+def degree_matrix(A):
+    """Diagonal degree matrix of graph with adjacency matrix A
+
+    Parameters
+    ----------
+    A : matrix
+        Adjacency matrix
+
+    Returns
+    -------
+    D : SciPy sparse matrix
+        Diagonal matrix of degrees.
+    """
+    n, m = A.shape
+    degs = _flat(A.sum(axis=1))
+    D = sps.spdiags(degs, [0], n, n, format='csr')
+    return D
+
+
+def laplacian_matrix(A, normalized=False):
+    """Diagonal degree matrix of graph with adjacency matrix A
+
+    Parameters
+    ----------
+    A : matrix
+        Adjacency matrix
+    normalized : Bool, optional (default=False)
+        If true, then normalized laplacian is returned.
+
+    Returns
+    -------
+    L : SciPy sparse matrix
+        Combinatorial laplacian matrix.
+    """
+    n, m = A.shape
+    D = degree_matrix(A)
+    L = D - A
+    if normalized:
+        degs = _flat(A.sum(axis=1))
+        rootD = sps.spdiags(np.power(degs, -1 / 2), [0], n, n, format='csr')
+        L = rootD * L * rootD
+    return L
diff --git a/other_requirements/examples.txt b/other_requirements/examples.txt
diff --git a/requirements.txt b/requirements.txt
@@ -24,3 +24,6 @@ psutil>=5.9.2
 # Tests
 pytest>=6.2.*
 testfixtures>=6.18.*
+
+# Examples
+pyemd