7
\$\begingroup\$

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.

\$\endgroup\$
5
  • 6
    \$\begingroup\$ Test cases wouldn't go amiss. \$\endgroup\$ Dec 30, 2018 at 16:32
  • \$\begingroup\$ Can complete graphs contain redundant self-connections (e.g. A to A)? \$\endgroup\$ Dec 30, 2018 at 16:40
  • \$\begingroup\$ ... and if so must they be n too? \$\endgroup\$ Dec 30, 2018 at 16:45
  • \$\begingroup\$ @JonathanAllan Complete graphs can but do not necessarily contain self-connections. \$\endgroup\$
    – Arcturus
    Dec 30, 2018 at 16:48
  • \$\begingroup\$ ... and if so must they be n too? \$\endgroup\$ Dec 30, 2018 at 16:54

5 Answers 5

1
\$\begingroup\$

Jelly, 16 bytes

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

Try it online!

\$\endgroup\$
1
\$\begingroup\$

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
\$\endgroup\$
1
\$\begingroup\$

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
\$\endgroup\$
3
  • 1
    \$\begingroup\$ 178 bytes. \$\endgroup\$
    – Mr. Xcoder
    Dec 31, 2018 at 10:25
  • 1
    \$\begingroup\$ 172 bytes. A program is cheaper than a function. \$\endgroup\$
    – ElPedro
    Dec 31, 2018 at 12:13
  • \$\begingroup\$ @Mr.Xcoder - really like and{0}!=s. Was trying to find a way to shorten that condition but didn't think of that. My suggestion goes to 168 if I use that. \$\endgroup\$
    – ElPedro
    Dec 31, 2018 at 12:15
0
\$\begingroup\$

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.

\$\endgroup\$
0
\$\begingroup\$

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!

\$\endgroup\$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

Not the answer you're looking for? Browse other questions tagged or ask your own question.