13
\$\begingroup\$

A bipartite graph is a graph whose vertices can be divided into two disjoint set, such that no edge connects two vertices in the same set. A graph is bipartite if and only if it is 2-colorable.


Challenge

Your task is to, given the adjacency matrix of an undirected simple graph, determine whether it is a bipartite graph. That is, if an edge connects vertices i and j, both (i, j) and (j, i) entry of the matrix are 1.

Since the graph is undirected and simple, its adjacency matrix is symmetric and contains only 0 and 1.

Specifics

You should take an N-by-N matrix as input (in any form, e.g. list of lists, list of strings, C-like int** and size, flattened array, raw input, etc.).

The function/program should return/output a truthy value if the graph is bipartite, and falsy otherwise.

Test Cases

['00101',
 '00010',
 '10001',
 '01000',
 '10100'] : False
['010100',
 '100011',
 '000100',
 '101000',
 '010000',
 '010000'] : True (divide into {0, 2, 4, 5} and {1, 3})
['00',
 '00'] : True

Scoring

Builtins that compute the answer directly are banned.

This is , so the shortest program (in bytes) by the end of this month wins!

\$\endgroup\$
  • \$\begingroup\$ Related, and in fact borderline dupe, because being bipartite is equivalent to having no odd cycles, and most of the answers to that question work by enumerating all cycles and examining their lengths. \$\endgroup\$ – Peter Taylor Nov 17 '17 at 8:22
  • \$\begingroup\$ @PeterTaylor Yeah, but there are simpler ways to solve this problem. \$\endgroup\$ – Colera Su Nov 17 '17 at 16:27
  • \$\begingroup\$ @ColeraSu Instead of truthy / falsy, can we return -1 for falsy and any non-negative integer for truthy? \$\endgroup\$ – Mr. Xcoder Nov 17 '17 at 19:10
  • \$\begingroup\$ @MishaLavrov 0 -> Falsy, >0 -> Truthy is generally allowed by standard truthy/falsy rules. -1 and ≥ 0 is not that common, that's why I asked. \$\endgroup\$ – Mr. Xcoder Nov 17 '17 at 20:28
  • \$\begingroup\$ @Mr.Xcoder It's okay. \$\endgroup\$ – Colera Su Nov 19 '17 at 4:01
4
\$\begingroup\$

Husk, 17 bytes

§V¤=ṁΣṠMSȯDfm¬ṀfΠ

Prints a positive integer if the graph is bipartite, 0 if not. Try it online!

Explanation

This is a brute force approach: iterate through all subsets S of vertices, and see whether all edges in the graph are between S and its complement.

§V¤=ṁΣṠMSȯDfm¬ṀfΠ  Implicit input: binary matrix M.
                Π  Cartesian product; result is X.
                   Elements of X are binary lists representing subsets of vertices.
                   If M contains an all-0 row, the corresponding vertex is never chosen,
                   but it is irrelevant anyway, since it has no neighbors.
                   All-1 rows do not occur, as the graph is simple.
      ṠM           For each list S in X:
              Ṁf   Filter each row of M by S, keeping the bits at the truthy indices of S,
        S  fm¬     then filter the result by the element-wise negation of S,
         ȯD        and concatenate the resulting matrix to itself.
                   Now we have, for each subset S, a matrix containing the edges
                   from S to its complement, twice.
§V                 1-based index of the first matrix
  ¤=               that equals M
    ṁΣ             by the sum of all rows, i.e. total number of 1s.
                   Implicitly print.
| improve this answer | |
\$\endgroup\$
  • \$\begingroup\$ @Mr.Xcoder Well, suppose M = [[1,2,3],[4,5,6],[7,8,9]] and S = [1,0,1] (M is always a binary matrix in the program, but it's easier to explain this way). Filtering each row of M by S gives [[1,3],[4,6],[7,9]]: for each row, I remove the elements at those indices where S has a 0. Then I negate S element-wise to get [0,1,0], and filter M by that to get [[4,6]]: the first and last rows have 0 in the corresponding indices, so they are removed. \$\endgroup\$ – Zgarb Nov 17 '17 at 18:08
20
\$\begingroup\$

Wolfram Language (Mathematica), 26 25 bytes

Tr[#//.x_:>#.#.Clip@x]<1&

Try it online!

How it works

Given an adjacency matrix A, we find the fixed point of starting with B=A and then replacing B by A2B, occasionally clipping values larger than 1 to 1. The kth step of this process is equivalent up to the Clip to finding powers A2k+1, in which the (i,j) entry counts the number of paths of length 2k+1 from vertex i to j; therefore the fixed point ends up having a nonzero (i,j) entry iff we can go from i to j in an odd number of steps.

In particular, the diagonal of the fixed point has nonzero entries only when a vertex can reach itself in an odd number of steps: if there's an odd cycle. So the trace of the fixed point is 0 if and only if the graph is bipartite.

Another 25-byte solution of this form is Tr[#O@n//.x_:>#.#.x]===0&, in case this gives anyone ideas about how to push the byte count even lower.

Previous efforts

I've tried a number of approaches to this answer before settling on this one.

26 bytes: matrix exponentials

N@Tr[#.MatrixExp[#.#]]==0&

Also relies on odd powers of the adjacency matrix. Since x*exp(x2) is x + x3 + x5/2! + x7/4! + ..., when x is a matrix A this has a positive term for every odd power of A, so it will also have zero trace iff A has an odd cycle. This solution is very slow for large matrices.

29 bytes: large odd power

Tr[#.##&@@#~Table~Tr[2#!]]<1&

For an n by n matrix A, finds A2n+1 and then does the diagonal check. Here, #~Table~Tr[2#!] generates 2n copies of the n by n input matrix, and #.##& @@ {a,b,c,d} unpacks to a.a.b.c.d, multiplying together 2n+1 copies of the matrix as a result.

53 bytes: Laplacian matrix

(e=Eigenvalues)[(d=DiagonalMatrix[Tr/@#])+#]==e[d-#]&

Uses an obscure result in spectral graph theory (Proposition 1.3.10 in this pdf).

| improve this answer | |
\$\endgroup\$
  • \$\begingroup\$ I think you can shave a couple of bytes off your more efficient method with Tr[#.Nest[#.#&,#,Tr[#!]]]<1&. (This is an incredible answer that keeps getting better every time I look at it!) \$\endgroup\$ – Not a tree Nov 17 '17 at 7:52
  • 1
    \$\begingroup\$ This has fewer bytes that the semi-built-in (needs two functions)BipartiteGraphQ@AdjacencyGraph@#& \$\endgroup\$ – Kelly Lowder Nov 17 '17 at 14:53
  • 2
    \$\begingroup\$ @KellyLowder: for large matrices MatrixExp returns results in terms of unevaluated Root objects, which are not automatically simplified when added. The N@ forces these Roots to be calculated numerically so that the truthiness can then be evaluated. \$\endgroup\$ – Michael Seifert Nov 17 '17 at 15:09
  • 1
    \$\begingroup\$ @Notatree Your approach does indeed shave off a few bytes, but they cost; for 18x18 matrices, it's 1000 times slower, and it gets worse from there. I think if I make that change, I lose the right to call the efficient method "efficient". \$\endgroup\$ – Misha Lavrov Nov 17 '17 at 15:42
  • 1
    \$\begingroup\$ @KellyLowder You could shorten that to BipartiteGraphQ@*AdjacencyGraph, but it's still longer. \$\endgroup\$ – Martin Ender Nov 18 '17 at 13:46
4
+200
\$\begingroup\$

APL (Dyalog Extended), 16 13 bytes

⍱1 1⍉∨.∧⍣2⍣≡⍨

Try it online!

-3 bytes thanks to @H.PWiz.

Uses the algorithm from Misha Lavrov's top Mathematica answer: initialize A = B = M, left-multiply B twice to A and clamp it until it reaches the fixed point, and test if the diagonal entries are all zero.

The regular matrix product A+.×B counts the number of two-step paths from node m to node p passing through any intermediate node n. If we change the code to A∨.∧B, we instead get a boolean matrix indicating if there exists any two-step path from node m to node p. We don't need extra "clamping" operation that way.

How it works

⍱1 1⍉∨.∧⍣2⍣≡⍨  ⍝ Input: adjacency matrix M
          ⍣≡⍨  ⍝ Find the fixed point, with
               ⍝     Starting point A = Left arg B = M...
     ∨.∧⍣2     ⍝   Left-multiply (matmul) B twice to A
               ⍝   indicating existence of paths (boolean)
 1 1⍉          ⍝ Extract the main diagonal
⍱              ⍝ Test if all elements are zero
| improve this answer | |
\$\endgroup\$
  • \$\begingroup\$ Would it work to raise the matrix to a large odd power and check if the diagonal is all zero? \$\endgroup\$ – xnor Apr 25 at 2:11
  • \$\begingroup\$ @xnor Yes it's possible, but giving a computed iteration count is less concise than simple fixpoint. \$\endgroup\$ – Bubbler Apr 25 at 4:18
  • \$\begingroup\$ Weird, I don't know APL, but does it really take that many characters? Does APL not have matrix-powers built-in? If is does, it looks to me like you could compute a large value as the matrix size or number of elements or sum, make it odd by either bitwise-or with 1 or (yuck) raise 3 to that power, take the input matrix to that power, then only 1 1⍉ and remain. \$\endgroup\$ – xnor Apr 25 at 5:23
  • \$\begingroup\$ @xnor APL is basically not a golfing language. Matrix product alone is not a single built-in, but rather a combination of three built-ins +.× (which allows me to write a Boolean variant ∨.∧ at no extra cost). Matrix power is even more complex, and I lose tacit programming when I need to compute the power explicitly (that solution would be like ⍱1 1⍉{∨.∧⍣(2×≢⍵)⍨⍵} at 19 bytes). And APL doesn't even have bitwise ops. \$\endgroup\$ – Bubbler Apr 27 at 1:54
  • \$\begingroup\$ I recognize this piece of code :P \$\endgroup\$ – RGS Apr 28 at 15:40
3
\$\begingroup\$

JavaScript, 78 bytes

m=>!m.some((l,i)=>m.some((_,s)=>(l=m.map(t=>t.some((c,o)=>c&&l[o])))[i]&&s%2))

Input array of array of 0 / 1, output true / false.

f = 

m=>!m.some((l,i)=>m.some((_,s)=>(l=m.map(t=>t.some((c,o)=>c&&l[o])))[i]&&s%2))

run = () => o.value=f(i.value.trim().split('\n').map(v=>v.trim().split('').map(t=>+t)))
<textarea id=i oninput="o.value=''" style="width:100%;display:block;">010100
100011
000100
101000
010000
010000
</textarea>
<button type=button onclick="run()">Run</button>
<div>Result = <output id=o></output></div>

| improve this answer | |
\$\endgroup\$
2
\$\begingroup\$

Pyth, 25 bytes

xmyss.D.DRx0dQx1d.nM*FQss

Try it online!

This returns -1 for falsy, and any non-negative integer for truthy.

How it works

xmyss.D.DRx0dQx1d.nM*FQss ~ Full program, receives an adjacency matrix from STDIN.

                    *FQ   ~ Reduce (fold) by cartesian product.
                 .nM      ~ Flatten each.
 m                        ~ Map with a variable d.
         R   Q            ~ For each element in the input,
       .D                 ~ Delete the elements at indexes...
          x0d             ~ All indexes of 0 in d.
     .D                   ~ And from this list, delete the elements at indexes...
              x1d         ~ All indexes of 1 in d.
    s                     ~ Flatten.
   s                      ~ Sum. I could have used s if [] wouldn't appear.
  y                       ~ Double.
x                         ~ In the above mapping, get the first index of...
                       ss ~ The total number of 1's in the input matrix.

This works in commit d315e19, the current Pyth version TiO has.

| improve this answer | |
\$\endgroup\$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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