Negative Space Graphs

Question

Task

You will be given a positive integer and you must output a "self-complementary graph" with that many nodes. If you don't know what a self-complementary graph is the wikipedia article wont help you much so below are two explanations, a technical and a non-technical one.

Non-Technical

A graph is a set of nodes that are connected by lines. Each pair of points can be connected by one line or none. The "complement" of a graph is the result of taking a graph and connecting all the nodes that are not connected and disconnecting all the nodes that are.

A self-complementary graph is a graph whose complement can be rearranged into the shape of the original. Below is an example of a self-complementary graph and a demonstration of how.

Here is a graph with 5 nodes:

We will highlight the all the places where connections could go with red dotted lines:

Now we will find the complement of the graph by swapping the red and black edges:

This does not look like the original graph but if we move the nodes around like so (each step swaps two nodes):

We get the original graph! The graph and its complement are the same graph

Technical

A self-complementary graph is a graph that is isomorphic to its complement.

Specifications

You will receive an positive integer via whatever method suits you best. And you will output a graph in whatever method you deem appropriate, this includes but is not limited to Adjacency Matrix Form, Adjacency List Form, and of course pictures! The outputted graph must be its own complement and have as many nodes as the integer input. If no such graph exists you must output a falsy value.

This is code-golf and you should aim to minimize your byte count.

Test Cases

Below are pictures of possible outputs for several n

4

5

9

Answer 1

Haskell, 77 bytes

f n=[(a,b)|b<-[1..n],a<-[1..b-1],mod n 4<2,mod(a+(last$b:[a|odd n,n==b]))4<2]

Try it online!

This uses an easy-to-compute explicit criterion to decide whether an edge (a,b) belongs in the graph. Instantiates this algorithm, with the permutation cycling among the values modulo 4

4*m -> 4*m+1 -> 4*m+2 -> 4*m+3 -> 4*m

We include edges whose two endpoint vertices add to 0 or 1 modulo 4. Note that cycling vertices as per this permutation adds 2 modulo 4 to the vertex sum on each each, and so swaps edges and non-edges. This gives a permutation of vertices that complements the edges.

If the graph has an extra node beyond a multiple of 4, it is put in a cycle alone. We include edges with it when then other vertex is even. Permuting the vertices flips the parity, and so the graph remains self-complementary.

If the number of vertices isn't 0 or 1 modulo 4, no self-complementary graph is possible because there's an odd number of edges in the complete graph

Overall, here are the conditions:

• If the input n isn't 0 or 1 modulo 4, output an empty list
• Otherwise if n is even, include all edges (a,b) with a<b and a+b equal to 0 or 1 modulo 4.
• Otherwise if n is odd, do the same, but instead include edges of the form (a,n) when a is even.

The code combines the second and third cases by replacing the condition mod(a+b)4<2 with mod(a+a)4<2 when both odd n and b==n.

Answer 2

Brachylog 2, 24 bytes

{⟦₁⊇Ċ}ᶠpḍ.(\\ᵐcdl?∨?<2)∧

Try it online!

This is a function that returns a pair consisting of two adjacency lists: one for the graph, one for the complement graph. (In the Brachylog interpreter on TIO, you can ask it to evaluate a function, rather than a full program, via giving Z as a command line argument.) For example, the output for input 5 is:

[[[1,2],[1,3],[1,5],[3,5],[4,5]],[[2,5],[2,3],[2,4],[3,4],[1,4]]]

Here's what that looks like as an image (showing the two graphs):

As is common in Prolog-based languages, the function supports more than one call pattern. Notably, if you try to use it as a generator, it will output all possible self-complementary graphs with the given number of vertices (although I didn't take any effort to make this case usable, and notably it'll output each of the graphs many times each).

Explanation

This is basically just a description of the problem, leaving the Prolog implementation to find the best method of solving it. (However, I doubt it will use an algorithm any better than brute force in this particular case, so it's likely fairly inefficient, and testing seems to confirm this, showing the performance getting much worse the larger the graph is.)

{⟦₁⊇Ċ}ᶠpḍ.(\\ᵐcdl?∨?<2)∧
 ⟦₁                       The range [1, 2, …, ?], where ? is the input
   ⊇                      A subset of that range…
    Ċ                     …which has exactly two elements
{    }ᶠ                   A list of everything that fits the above description
{⟦₁⊇Ċ}ᶠ                   All edges that could exist in a ?-element graph
       p                  Find a permutation of these…
        ḍ                 …so that splitting it into two equal parts…
          (       ∨   )   …either:
               dl?          produces ? distinct elements
           \                after transposing it
            \ᵐ              and transposing its elements
              c             and flattening one level;
                          or:
                   ?<2      ? was less than 2
         .             ∧  Once you've found it, . specifies what to output

Incidentally, I ended up having to spend a whole 6 bytes (¼ of the program, the characters (∨?<2)) dealing with the special cases of 0 and 1. Frustrating, but that's the nature of special cases.

The \\ᵐcdl? section is a little hard to understand, so here's a worked example. Its purpose is to check whether something is a graph and its complement, with corresponding edges in the graph and complement being in the same order within the lists. The graph/complement pair becomes the eventual output of the program. Here's an example case:

[[[1,2],[1,3],[1,5],[3,5],[4,5]],[[2,5],[2,3],[2,4],[3,4],[1,4]]]

Transposing this gives us a list of pairs of corresponding edges between the graph and the complement:

[[[1,2],[2,5]],[[1,3],[2,3]],[[1,5],[2,4]],[[3,5],[3,4]],[[4,5],[1,4]]

Next, we transpose inside the list elements and flatten one level; that gives us a list of pairs of corresponding elements between the graph and the complement:

[[1,2],[2,5],[1,2],[3,3],[1,2],[5,4],[3,3],[5,4],[4,1],[5,4]]

Clearly, what we want here is for there to be no more than 1 pair starting from each element (thus proving that the elements of the graph and the complement are in 1-to-1 correspondence). We can almost verify that just by stating that the list has at exactly ? distinct elements (i.e. a number of distinct elements equal to the number of vertices). In this case, the test succeeds; the distinct elements are:

[[1,2],[2,5],[3,3],[5,4],[4,1]]

However, this leaves room for a potential problem; if a vertex is entirely disconnected in the original graph, its correspondence won't be mentioned, leaving room for a duplicate correspondence from some other vertex. If this is the case, the complement graph must have an edge between that vertex (without loss of generality, let's say it's 1), and every other vertex, and so the list of correspondences will contain [1,2], [1,3], …, [1, ?]. When ? is large, this will lead to more correspondences total than we'd have otherwise, so there's no problem. The only issue happens when ? is 3 or lower, in which case we only end up adding one extra correspondence (whilst removing one from 1 not appearing in the input); however, this is not a problem in practice, because there are 3 possible edges on a 3-element graph, which is an odd number (likewise, 1 possible edge on a 2-element graph is also an odd number), and thus the test will fail at the \ step (you can't transpose a ragged list, i.e. ones whose elements have different lengths).

Answer 3

BBC BASIC, 161 bytes

Tokenised filesize 140 bytes

Download interpreter at http://www.bbcbasic.co.uk/bbcwin/bbcwin.html

I.m:IF2ANDm ORm<4P.0:END
r=400n=-2A.m:t=2*PI/n:F.i=1TOn*n:a=i DIVn:b=i MODn:c=b:IFa+b A.2a*=t:b*=t:L.r+r*SINa,r+r*COSa,r+r*SINb,r+r*COSb:IF 1A.m A.c DRAWr*3,0
N.

Ungolfed code

  INPUTm                           :REM get input
  IF2ANDm ORm<4PRINT0:END          :REM if m=4x+2 or 4x+3 or less than 4, print 0 and exit
  r=400                            :REM radius of diagram
  n=-2ANDm                         :REM n = m truncated to an even number
  t=2*PI/n                         :REM t = 1/n turns
  FORi=1TOn*n                      :REM for each combination of vertices
    a=i DIVn                       :REM extract a and b
    b=i MODn                       :REM make a copy of c
    c=b                            :REM if a+b MOD 4 = 2 or 3, convert a and b to angles and draw edge.
    IFa+b AND2 a*=t:b*=t:LINEr+r*SINa,r+r*COSa,r+r*SINb,r+r*COSb:IF 1ANDm ANDc DRAWr*3,0
  NEXT                             :REM if m is odd and c is odd, draw a line to the additional vertex for m=4x+1 input.

Explanation

This uses the same algorithm as Xnor, but produces a diagrammatic output.

Where n is of the form 4x+2 or 4x+3 there is no solution as the number of edges is odd.

Where n is of the form 4x we arrange all the vertices in a circle and draw those edges where (a+b) mod 4is 2 or 3 (not 0 or 1 as in Xnor's case, for golfing reasons. This is therefore the complement of the solution given by Xnor.)

To see this in a more pictoral sense, we take every second vertex and draw the edges to the vertices 1 and 2 places away in anticlockwise direction. This defines n parallel directions, half of the total. Then we add in all the other edges parallel to these.

The complement can be found by adding 1 to both a and b in each edge specification, or pictorally by rotating the diagram by a 1/n turn.

Where n is of the form 4x+1 we add another vertex, which is linked to every second vertex of the 4x graph. If it was placed at the centre the symmetry of the diagram would be preserved, but I chose to place it outside the main circle of points for clarity.

Output

The following are the first few cases for 4x+1. the 4x cases can be seen by deleting the vertex at bottom right and its associated edges.

Answer 4

JavaScript (ES6), 191 bytes

f=(n,a=[],v=n*~-n/4)=>v%1?0:eval(n>5?f(n-=4,a)&&'for(i=0;i<n;)a.push([i,n+1],[i++,n+2]);a.push([n,++n],[n,++n],[n,++n])-v':'for(l=x=0;x<n;x++)for(y=x;y<n;y++)l<v&y>>x&1?l=a.push([x,y]):a')||a

This function returns an adjacency list. It uses two algorithms, and differentiates between empty complementary graphs and non-outputs by returning 0 instead of [] when none exists. The first algorithm is based on Rado Graphs constructed using the BIT predicate, and creates valid 0-, 1-, 4- and 5-order complementary graphs. The other algorithm, found by our friends at mathematics, constructs a valid V+4 vertex complementary graph by applying a 4-path addition to a valid V vertex complementary graph.

It begins by validating the input to confirm the existence of a valid complementary graph (using n*~-n/4%1), and if that fails, returns 0. It then checks if n>5 and recurses to the n-4 case to construct a valid lower order solution, then applies the 4-addition to the returned adjacency list on the way back up the recursion chain. Lastly, if n>5 is not true, it iterates from 0 to n-1 for x and y, and checks if the (y>>x)&1 is true. If so, then those nodes are paired.

Here is a more readable format of the function, with ternary operators expanded to if-else statements and eval()s inlined:

// precalculate amount of required vertices in v
f = (n, a = [], v = n*~-n / 4) => {
  // if amount is non-integer
  if (v % 1) {
    // no valid complementary graph
    return 0;
  } else {
    if (n > 5) {
      // generate valid (n-4)-order complementary graph
      f(n -= 4, a);
      // apply 4-path addition
      for (i = 0; i < n;)
        a.push([i, n+1],[i++, n+2]);
      a.push([n, ++n], [n, ++n], [n, ++n]);
    } else {
      // construct Rado graph using BIT predicate
      for(l = x = 0; x < n; x++)
        for(y = x; y < n; y++)
          // if amount of pairs is less than required and xth bit of y is high
          if (l < v && (y>>x & 1))
            // vertices x and y should be paired
            a.push([x,y]);
    }
    return a;
  }
};

Demo

f=(n,a=[],v=n*~-n/4)=>v%1?0:eval(n>5?f(n-=4,a)&&'for(i=0;i<n;)a.push([i,n+1],[i++,n+2]);a.push([n,++n],[n,++n],[n,++n])-v':'for(l=x=0;x<n;x++)for(y=x;y<n;y++)l<v&y>>x&1?l=a.push([x,y]):a')||a

<input type="number" onchange="o.textContent=JSON.stringify(f(this.value))"><pre id="o"></pre>