Find equally-weighted complete graphs

Question

Graph theory is used to study the relations between objects. A graph is composed of vertices and edges in a diagram such as this:

A-----B
|    / \  
|   /   \
|  /     E
| /     /
|/     /
C-----D

In the above diagram, A is linked to B and C; B is linked to A, C, and E; C is linked to A, B, and D; D is linked to C and E; and E is linked to B and D. As that description was rather wordy, a graph can be represented as a symmetric boolean matrix where a 1 represents a connection and a 0 represents the lack thereof. The above matrix is translated to this:

01100
10101
11010
00101
01010

For the purpose of this problem, the matrix definition can be extended to include the distances or weights of the paths between nodes. If individual ASCII characters in the diagram have weight 1, he matrix would be:

05500
50502
55050
00502
02020

A "complete graph" consists of a set of points such that each point is linked to every other point. The above graph is incomplete because it lacks connections from A to D and E, B to D, and C to E. However, the subgraph between A, B, and C is complete (and equally weighted). A 4-complete graph would look like this:

A---B
|\ /|
| X |
|/ \|
C---D

and would be represented by the matrix:

01111
10111
11011
11101
11110

This problem is as follows: Given a symmetric matrix representing a graph and a positive integer n, find the number of distinct equally-weighted complete subgraphs of size n contained within.

You may assume that the input matrix is numeric and symmetric, and may choose input/output format. An entry in the matrix may be part of multiple equally-weighted subgraphs as long as they are distinct and of equal size. You may assume that n is a positive integer greater than or equal to 3.

The winning criterion for this challenge is code golf. Standard rules apply.

Answer 1

Jelly, 16 bytes

ịⱮịŒDḊẎE
Jœcç€⁸S

Try it online!

Answer 2

Jelly,  18 16  15 bytes

Assumes self-connections may be any weight (i.e. they are not necessarily only either \$0\$ or the equal weight).

Jœcṗ2EÐḟœị³EƲ€S

Try it online!
the two subsets of size 3 being ACE and BCD
With n=2 all 10 subsets of size 2 work as its symmetric.

How?

Jœcṗ2EÐḟœị³EƲ€S - Link: list of lists of integers, M; integer, n
J               - range of length of M = [1,2,3,...,length(M)]
 œc             - Combinations of length n e.g. [[1,2,3],[1,2,4],[1,3,4],[2,3,4]]
             €  - for each:
            Ʋ   -   last four links as a monad:
   ṗ2           -     Cartesian power with 2
      Ðḟ        -     discard if:
     E          -       all-equal (i.e. diagonal co-ordinates like [3,3])
        œị      -     multi-dimensional index into:
          ³     -       program's 3rd argument (1st input), M
           E    -     all equal?
              S - sum

Answer 3

Python 2, 195 bytes 178 bytes 168 bytes

I'm sure there's a lot more golfing possible here, but for a change I want to get an entry in before there are dozens of other ones. I've provided a couple of test cases on TIO, but would love more examples.

First round of suggested golf steps: Remove some spaces, be smarter about the import. Shorter way of testing if the single link value in a set is zero (Thanks to M. XCoder).

Second round: ElPedro points out that in this case a program is shorter than the function. I was hoping to find a way to package this as a lambda, so was thinking "function" from the start. Thanks.

from itertools import*
r=set()
M,n=input()
for g in set(combinations(range(len(M)),n)):
 s={M[i][j]for i in g for j in g if i>j}
 if len(s)==1and{0}!=s:r.add(g)
print r

Try it online!

A slightly ungolfed version, to clarify logic:

from itertools import combinations
def f3(M,n):
  r = set()
  groups = set(combinations(range(len(M)), n)) # all possible combinations of indexes
  for group in groups:
      # Generate a set of link values associated with the current combination
      # This selects only non-diagonal indexes, assuming matrix symmetry.
      s = {M[i][j]for i in group for j in group if i>j}
      # If the set has only one member, and that's not zero, you have
      # a connected subgraph. 
      if len(s) == 1 and 0 not in s:  
          r.add(group)
  return r

Answer 4

Clean, 152 bytes

import StdEnv,Data.List
$m n=sum[1\\i<-subsequences[0..size m-1]|length i==n,j<-permutations i|case[m.[x,y]\\x<-i&y<-j]of[u:v]=all((==)u)v&&u>0;_=1<0]/2

Try it online!

TIO driver takes n as a command-line argument and the matrix through STDIN (weights up to 9).

The actual function $ :: {#{#Int}} Int -> Int works with any size weights.

Answer 5

Wolfram Language (Mathematica), 90 bytes

There is probably some room to further golf this, after some test cases are posted.

We construct a graph from the unitized adjacency matrix, and then use the FindClique function with All as the third argument to list out the vertices with complete subgraphs. We then select the submatrices of the original input corresponding to the cliques (which will have zeros along the diagonal) and count the number of distinct elements which should be 2 if the weights are equal.

In this implementation, self connections can have a weight other than zero and the graph will still be considered complete and equal weighted, so long as the weights of all self connections in the subgraph are identical.

Count[Length@*Union@@@(b[[#,#]]&/@FindClique[AdjacencyGraph[Unitize/@(b=#)],{#2},All]),2]&

Try it online!