Opened 2 years ago

Closed 7 months ago

#24089 closed enhancement (fixed)

Max common neighbors for Graphs

Reported by: afrancis Owned by: gh-rajat1433
Priority: major Milestone: sage-8.8
Component: graph theory Keywords: neighbors, graphs, link prediction, sd90
Cc: dcoudert Merged in:
Authors: Amanda Francis, Rajat Mittal Reviewers: David Coudert
Report Upstream: N/A Work issues:
Branch: f081682 (Commits) Commit: f081682b9db13f14e226cd70a0768dd4a133858d
Dependencies: Stopgaps:

Description

Use adjacency matrix to implement maximum common neighbors score for graphs.

Change History (37)

comment:1 Changed 2 years ago by afrancis

  • Keywords sd90 added
  • Priority changed from minor to major

comment:2 Changed 2 years ago by afrancis

  • Branch set to u/afrancis/max_common_neighbors_for_graphs

comment:3 Changed 2 years ago by git

  • Commit set to 96bd2b7f4bda8de468a7176bb15c00622b9c94e7

Branch pushed to git repo; I updated commit sha1. New commits:

96bd2b7Max common neighbors added to graphs.py

comment:4 Changed 2 years ago by git

  • Commit changed from 96bd2b7f4bda8de468a7176bb15c00622b9c94e7 to a749b9313f955b0cf1bf91486969d66be0f9ae31

Branch pushed to git repo; I updated commit sha1. New commits:

a749b93Added to documentation

comment:5 Changed 2 years ago by afrancis

  • Authors set to Amanda Francis

comment:6 Changed 2 years ago by git

  • Commit changed from a749b9313f955b0cf1bf91486969d66be0f9ae31 to 9436b14b27e08b757044161e118490d6f63970e4

Branch pushed to git repo; I updated commit sha1. New commits:

9436b14Added authorship line

comment:7 Changed 2 years ago by afrancis

  • Status changed from new to needs_review

comment:8 Changed 2 years ago by dcoudert

  • Status changed from needs_review to needs_work

Here I have similar comments as for #24094. You can have a look to [doc.sagemath.org/html/en/developer/coding_basics.html].

comment:9 Changed 7 months ago by gh-rajat1433

  • Cc dcoudert added
  • Milestone changed from sage-8.1 to sage-8.8
  • Owner changed from (none) to gh-rajat1433

comment:10 Changed 7 months ago by gh-rajat1433

  • Authors changed from Amanda Francis to Amanda Francis, Rajat Mittal
  • Branch changed from u/afrancis/max_common_neighbors_for_graphs to u/gh-rajat1433/24089_max_common_neighbors
  • Commit 9436b14b27e08b757044161e118490d6f63970e4 deleted
  • Milestone changed from sage-8.8 to sage-8.7
  • Reviewers set to David Coudert

comment:11 Changed 7 months ago by git

  • Commit set to 514a29a2555b8c3e4d9a3cd771ba6d3c4abeff39

Branch pushed to git repo; I updated commit sha1. New commits:

514a29aAdded Neighbors Method

comment:12 Changed 7 months ago by gh-rajat1433

Done a lot of refactoring and improvement in the original author's code , following the pep8 guidelines and also added vertices option to common_neighbors_matrix method.

comment:13 Changed 7 months ago by gh-rajat1433

  • Status changed from needs_work to needs_review

comment:14 Changed 7 months ago by git

  • Commit changed from 514a29a2555b8c3e4d9a3cd771ba6d3c4abeff39 to 4935d5e2bbda1e51382f2bf6831e26bec812b27e

Branch pushed to git repo; I updated commit sha1. New commits:

4935d5eremoved_xtra_space

comment:15 Changed 7 months ago by dcoudert

  • Status changed from needs_review to needs_work

several comments

common_neighbors_matrix

  • We could shorten the short description to
    Return a matrix of numbers of common neighbors between each pairs.
    
    an then add the explanation about (i, j) entry
  • pep8:
    -        - ``nonedgesonly``-- Boolean (default: `True`); if ``true``, assigns
    +        - ``nonedgesonly``-- boolean (default: ``True``); if ``True``, assigns
    
  • remove # add edge. Not useful
                sage: G = Graph([(0,0)],loops=True) # add edges
    
  • same here
                sage: G = graphs.CompleteGraph(4) # Check Complete Graph
    
  • you must document at the begining of the method that it is working for simple graphs only, and so that neither loops nor multiple edges are accepted. Then instead of this test, you could use:
    -        if self.has_loops():
    -            raise ValueError('Unable to compute simple graph common neighbors for graphs with loops')
    +        self._scream_if_not_simple()
    
  • this method is defined in graph.py, so self is not directed.
  • use vertices = list(self) but the documentation of the vertices parameter says that default in self.vertices().
  • range(0, self.order()): no need to add 0 -> range(self.order())
  • we expect the matrix to be symmetric, so
    -        for v in range(0, self.order()):
    -            for w in range(0, self.order()):
    -                if v == w:
    -                    M[v, w] = 0
    -                if nonedgesonly == True:
    -                    if A[v, w] > 0:
    -                        M[v, w] = 0
    +        for v in range(self.order()):
    +            M[v, v] = 0
    +            for w in range(v + 1, self.order()):
    +                if nonedgesonly and A[v, w]:
    +                    M[v, w] = M[w, v] = 0
    

most_common_neighbors

  • ``nonedgesonly`` -- Boolean (default: `True`); if ``True``, same as above
  • non-adajacent -> non-adjacent`
  • alignment 80 columns
    +        The common neighbors matrix  for a fan on 6 vertices counting only non-adjacent vertex pairs ::
    
  • remove #Check Complete Graph
  • document that the method is for simple graphs only and add self._scream_if_not_simple()
  • document that the method is defined for graphs of order \geq 2 and do
    -            raise ValueError('Unable to find node pairs with common neighbors for graphs with less than 2 nodes')
    +            raise ValueError('this method is defined for graphs with at least 2 vertices')
    
  • what is max(max(M) ?
  • The matrix is symmetric, and the current implementation outputs pair (u, v) and (v, u).

comment:16 Changed 7 months ago by git

  • Commit changed from 4935d5e2bbda1e51382f2bf6831e26bec812b27e to 2039233a1141798e812d8fe7c5a7e8471d4b960c

Branch pushed to git repo; I updated commit sha1. New commits:

2039233changes_as_per_review

comment:17 follow-up: Changed 7 months ago by gh-rajat1433

    what is max(max(M))

Its the maximum value in a 2d matrix.

    The matrix is symmetric, and the current implementation outputs pair (u, v) and (v, u).

no it outputed only (u,v) bcoz second loop started from v.

use vertices = list(self) but the documentation of the vertices parameter says that default in self.vertices(). 

I have now restored self.vertices in the code. (Or should I do other way round including list(self) in documentation as well as code?

All the changes suggested are commited.


New commits:

2039233changes_as_per_review

New commits:

2039233changes_as_per_review

comment:18 Changed 7 months ago by gh-rajat1433

  • Status changed from needs_work to needs_review

comment:19 in reply to: ↑ 17 Changed 7 months ago by dcoudert

Replying to gh-rajat1433:

    what is max(max(M))

Its the maximum value in a 2d matrix.

I don't think so

sage: G = graphs.CycleGraph(4)
sage: A = G.adjacency_matrix()
sage: M = A**2
sage: M
[2 0 2 0]
[0 2 0 2]
[2 0 2 0]
[0 2 0 2]
sage: M[1, 1] = 3
sage: M
[2 0 2 0]
[0 3 0 2]
[2 0 2 0]
[0 2 0 2]
sage: max(max(M))
2
sage: max(M)
(2, 0, 2, 0)

max(M) returns the "maximum" row according some definition, apparently lexicographic.

use for instance max(M.coefficients())

I have now restored self.vertices in the code. (Or should I do other way round including list(self) in documentation as well as code?

it's consistent with `adjacency_matrix, so it's OK.

comment:20 Changed 7 months ago by gh-rajat1433

fixed for maximum value

comment:21 Changed 7 months ago by git

  • Commit changed from 2039233a1141798e812d8fe7c5a7e8471d4b960c to 4b5431f11938fb6d573356a77b0a09b5a02cf0e6

Branch pushed to git repo; I updated commit sha1. New commits:

4b5431ffixing max value

comment:22 Changed 7 months ago by dcoudert

almost done ;)

             for v in range(self.num_verts()):
-                for w in range(v, self.num_verts()):
+                for w in range(v + 1, self.num_verts()):

and also, you can do

-            ValueError: This method is not known to work on graphs with loops. Perhaps this method can be updated to handle them, but in the meantime if you want to use it please disallow loops using allow_loops().
+            ValueError: This method is not known to work on graphs with
+            multiedges. Perhaps this method can be updated to handle them, but
+            in the meantime if you want to use it please disallow multiedges
+            using allow_multiple_edges().

and

-        The (`i` , `j`) entry of the matrix gives the number of common
+        The `(i , j)` entry of the matrix gives the number of common

comment:23 Changed 7 months ago by git

  • Commit changed from 4b5431f11938fb6d573356a77b0a09b5a02cf0e6 to 4ea2d8c1178dda31d95eeaffa1739d39223bdf79

Branch pushed to git repo; I updated commit sha1. New commits:

4ea2d8cfixing remaining bugs

comment:24 Changed 7 months ago by gh-rajat1433

Thanks for the review. I have fixed the remaining documentation bugs.

comment:25 Changed 7 months ago by dcoudert

  • Status changed from needs_review to positive_review

LGTM

comment:26 Changed 7 months ago by vbraun

  • Status changed from positive_review to needs_work

Merge conflict

comment:27 Changed 7 months ago by gh-rajat1433

  • Branch changed from u/gh-rajat1433/24089_max_common_neighbors to u/gh-rajat1433/24089_common_neighbors
  • Commit 4ea2d8c1178dda31d95eeaffa1739d39223bdf79 deleted

comment:28 Changed 7 months ago by git

  • Commit set to 2a9c447e048e16573ec1705ab676b1d21ef991a6

Branch pushed to git repo; I updated commit sha1. New commits:

comment:29 Changed 7 months ago by git

  • Commit changed from 2a9c447e048e16573ec1705ab676b1d21ef991a6 to d5cc829d4a3fd45bdba61a86e0e2c966c37614ab

Branch pushed to git repo; I updated commit sha1. New commits:

514a29aAdded Neighbors Method
4935d5eremoved_xtra_space
2039233changes_as_per_review
4b5431ffixing max value
4ea2d8cfixing remaining bugs
d5cc829merged with beta 8.7rc0

comment:30 Changed 7 months ago by gh-rajat1433

I have merged it with latest release i.e. 8.7 rc0 to avoid any conflicts. Is milestone 8.7 good or I have to make it 8.8 ?

Last edited 7 months ago by gh-rajat1433 (previous) (diff)

comment:31 Changed 7 months ago by gh-rajat1433

  • Status changed from needs_work to needs_review

comment:32 Changed 7 months ago by dcoudert

The milestone is now 8.8. Version 8.7 has been released. The last develop version is 8.7, and the first beta of 8.8 will be shortly released.

  • a better code when nonedgesonly = False
    -            for w in range(v + 1, self.order()):
    -                if nonedgesonly and A[v, w]:
    -                    M[v, w] = M[w, v] = 0
    +            if nonedgesonly:
    +                for w in range(v + 1, self.order()):
    +                    if A[v, w]:
    +                        M[v, w] = M[w, v] = 0
    
  • Add a . at the end of Return vertex pairs with maximal number of common neighbors
  • only 1 empty line before the INPUT block
  • Do simple validity test first
    -        verts = list(self)
    -        M = self.common_neighbors_matrix(vertices=verts, nonedgesonly=nonedgesonly)
    -        if self.num_verts() < 2:
    -            raise ValueError('this method is defined for graphs with at least 2 vertices')
    +        if self.num_verts() < 2:
    +            raise ValueError('this method is defined for graphs with at least 2 vertices')
    +        verts = list(self)
    +        M = self.common_neighbors_matrix(vertices=verts, nonedgesonly=nonedgesonly)
    
  • no need to call twice M.coefficients(). Use a variable coefficients = M.coefficients()

comment:33 Changed 7 months ago by gh-rajat1433

  • Milestone changed from sage-8.7 to sage-8.8

comment:34 Changed 7 months ago by git

  • Commit changed from d5cc829d4a3fd45bdba61a86e0e2c966c37614ab to f081682b9db13f14e226cd70a0768dd4a133858d

Branch pushed to git repo; I updated commit sha1. New commits:

f081682improved the code

comment:35 Changed 7 months ago by gh-rajat1433

Thanks for the review. I have made the changes.

comment:36 Changed 7 months ago by dcoudert

  • Status changed from needs_review to positive_review

LGTM

comment:37 Changed 7 months ago by vbraun

  • Branch changed from u/gh-rajat1433/24089_common_neighbors to f081682b9db13f14e226cd70a0768dd4a133858d
  • Resolution set to fixed
  • Status changed from positive_review to closed
Note: See TracTickets for help on using tickets.