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.
\$\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
17
\$\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).

\$\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
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>

\$\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.

\$\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.