In this post, we will solve HackerRank Diameter Minimization Problem Solution.
We define the diameter of a strongly-connected oriented graph, G = (V,E), as the minimum integer & such that for each u, v EG there is a path from u to v of length <d (recall that a path’s length is its number of edges).
Given two integers, n and m. build a strongly-connected oriented graph with n vertices where each vertex has outdegree m and the graph’s diameter is as small as possible (see the Scoring section below for more detail). Then print the graph according to the Output Format specified below.
Here’s a sample strongly-connected oriented graph with 3 nodes, whose outdegree is 2 and diameter is 1.
Note: Cycles and multiple edges between vertices are allowed.
Input Format
Two space-separated integers describing the respective values of n (the number of vertices) and m (the outdegree of each vertex).
Scoring
We denote the diameter of your graph as d and the diameter of the graph in the author’s solution as 8. Your score for each test case (as a real number from 0 to 1)
Output Format
First, print an integer denoting the diameter of your graph on a new line.
Next, print n lines where each line i (0 < i < n) contains m space-separated integers in the inclusive range from 0 ton – 1 describing the endpoints for each of vertex i’s outbound edges.
Sample Input 0
5 2Sample Output 0
2
1 4
2 0
3 1
4 2
0 3
Explanation 0
The diagram below depicts a strongly-connected oriented graph with n = 5 nodes where each node has an outdegree of m = 2
The diameter of this graph is d = 2, which is minimal as the outdegree of each node must be m. We cannot construct a graph with a smaller diameter of d = 1 because it requires an outbound edge from each vertex to each other vertex in the graph (so the outdegree of that graph would be n-1).
Diameter Minimization C++ Solution
#include <bits/stdc++.h>
using namespace std;
#define sz(x) ((int) (x).size())
#define forn(i,n) for (int i = 0; i < int(n); ++i)
typedef long long ll;
typedef long long i64;
typedef long double ld;
const int inf = int(1e9) + int(1e5);
const ll infl = ll(2e18) + ll(1e10);
int calcBest(int n, int m) {
int d = 0;
int onD = 1;
int cn = 1;
while (cn < n) {
onD *= m;
++d;
cn += onD;
}
return d;
}
const int maxn = 1005;
int g[maxn][maxn];
int n, m;
int dist[maxn];
int calcDiam(int s) {
fill(dist, dist + n, inf);
vector<int> q;
dist[s] = 0;
q.push_back(s);
forn (ii, sz(q)) {
int u = q[ii];
forn (i, m) {
int v = g[u][i];
if (dist[v] < inf)
continue;
dist[v] = dist[u] + 1;
q.push_back(v);
}
}
if (sz(q) < n)
return inf;
return dist[q.back()];
}
int main() {
cin >> n >> m;
forn (i, n) {
forn (j, m)
g[i][j] = (i * m + j) % n;
}
int diam = 0;
forn (i, n)
diam = max(diam, calcDiam(i));
int best = calcBest(n, m);
//cerr << "best " << best << '\n';
assert(diam <= best + 1);
assert(diam >= best);
cout << diam << '\n';
forn (i, n) {
forn (j, m)
cout << g[i][j] << ' ';
cout << '\n';
}
}Diameter Minimization C Sharp Solution
using System;
using System.Collections.Generic;
using System.Diagnostics;
using System.Linq;
using System.Text;
using static System.Math;
using static System.Console;
using static HackerRankUtils;
public class Solution
{
#region Variables
int m;
int n;
int BestDiameter = int.MaxValue;
bool toplevel;
Graph BestGraph = null;
public static Dictionary<Tuple<int, int>, Solution> memo = new Dictionary<Tuple<int, int>, Solution>();
public static readonly Random random = new Random(unchecked((int)0xDEADBEEF));
public static readonly Dictionary<int, List<Case>> cases = new Dictionary<int, List<Case>>();
#endregion
#region Constructor
static void Main(string[] args)
{
var sw = new Stopwatch();
sw.Start();
var input = ReadLine().Split(' ');
var n = int.Parse(input[0]);
var m = int.Parse(input[1]);
var sol = new Solution(n, m, true);
LaunchTimer(() =>
{
Report(sol);
return true;
}, TimeLimit);
Setup();
var g = sol.Solve();
Report(sol);
#if DEBUG
WriteLine(sw.Elapsed);
#endif
}
static void Report(Solution sol)
{
var g = sol.BestGraph;
WriteLine(sol.BestDiameter);
var list = new List<int>();
for (int i = 0; i < sol.n; i++)
{
list.Clear();
list.AddRange(g[i]);
while (list.Count < sol.m)
list.Add(list[0]);
WriteLine(string.Join(" ", list));
}
}
public static void Test()
{
for (int i=2; i<1000; i++)
for (int j=2; j<=5 && j<=i; j++)
{
var sol = new Solution(i, j);
sol.Solve();
}
}
public Solution(int n, int m, bool toplevel=false)
{
this.n = n;
this.m = m;
this.toplevel = toplevel;
}
#endregion
public Graph Solve()
{
var g = SolveCore();
if (g != null)
RecordGraph(g);
return BestGraph;
}
public Graph SolveCore()
{
if (m >= n - 1)
return Graph.Complete(n);
if (m==2)
{
RecordGraph(Graph.CycleGraph(n, m, true));
}
// Case Analysis
if (cases.ContainsKey(n))
{
foreach(var c in cases[n])
{
if (m < c.Degree)
continue;
var g = c.Action();
Debug.Assert(g.Diameter() == c.Diameter);
// Set the graph as an upper bound
RecordGraph(g);
}
}
// Divide and Conquer
if (n % 2 == 0 && m !=2)
{
var sol = Recurse(n / 2, m - 1);
// Diameter + 1, Degree + 1
var g = Graph.Product(sol.BestGraph, Graph.K2);
Debug.Assert(g.Diameter() == sol.BestDiameter + 1);
RecordGraph(g);
}
RecordGraph(Graph.ConnectedGraph(n,m));
/*
// Iterate through multiple random graphs
var limit = toplevel ? RandomIterationsTop : RandomIterations;
for (int i = 0; i < limit; i++)
{
RecordGraph(Graph.RandomGraph(n, m, true));
RecordGraph(Graph.RandomGraph(n, m, false));
}*/
// null means we are unsure;
return null;
}
public static Solution Recurse(int n, int m)
{
var tup = new Tuple<int, int>(n, m);
if (memo.ContainsKey(tup))
return memo[tup];
var sol = new Solution(n / 2, 2);
sol.Solve();
memo[tup] = sol;
return sol;
}
public void Attempt4()
{
if (n % 2 != 0) return;
var sol = Recurse(n / 2, 2);
var g = Graph.Product(sol.BestGraph, Graph.K2, false);
RecordGraph(g);
}
public void Attempt5()
{
if (n % 2 != 0) return;
var sol = Recurse(n / 2, 2);
var g0 = sol.BestGraph;
var g = Graph.Product(g0, Graph.K2, true);
RecordGraph(g);
}
public void RecordGraph(Graph g)
{
var diameter = g.Diameter(BestDiameter);
foreach(var e in g.g)
{
foreach(var v in e)
if (v>=g.g.Length || v<0) return;
}
if (g.g.Length < n) return;
if (BestGraph==null || diameter < BestDiameter)
{
BestGraph = g;
BestDiameter = diameter;
}
}
#region Case Analysis
public static void Setup()
{
AddCase(18, 3, 3, () => Graph.Graph33(18));
AddCase(16, 4, 2, () => Graph.G8(2));
AddCase(24, 5, 2, () => Graph.G8(3));
AddCase(4, 2, 2, () => Graph.CubeGraph(2));
AddCase(16, 4, 4, () => Graph.CubeGraph(4));
AddCase(32, 5, 5, () => Graph.CubeGraph(5));
// K3,3 = C6(1,3)
AddGraph(6, 3, 2, new[,] { { 0, 1 }, { 0, 3 }, { 0, 5 }, { 1, 2 }, { 1, 4 }, { 2, 3 }, { 2, 5 }, { 3, 4 }, { 4, 5 } });
// C8(1,4)
AddGraph(8, 3, 2, new[,] { { 0, 1 }, { 0, 4 }, { 0, 7 }, { 1, 2 }, { 1, 5 }, { 2, 3 }, { 2, 6 }, { 3, 4 }, { 3, 7 }, { 4, 5 }, { 5, 6 }, { 6, 7 } });
// P
AddGraph(10, 3, 2, new[,] { { 0, 1 }, { 0, 4 }, { 0, 5 }, { 1, 2 }, { 1, 6 }, { 2, 3 }, { 2, 7 }, { 3, 4 }, { 3, 8 }, { 4, 9 }, { 5, 7 }, { 5, 8 }, { 6, 8 }, { 6, 9 }, { 7, 9 } });
// C = Cml8(2:0,3)
//AddGraph(8, 3, 3, new[,] { { 0, 1 }, { 0, 3 }, { 0, 7 }, { 1, 2 }, { 1, 6 }, { 2, 3 }, { 2, 5 }, { 3, 4 }, { 4, 5 }, { 4, 7 }, { 5, 6 }, { 6, 7 } });
// C10(1,5)
AddGraph(10, 3, 3, new[,] { { 0, 1 }, { 0, 5 }, { 0, 9 }, { 1, 2 }, { 1, 6 }, { 2, 3 }, { 2, 7 }, { 3, 4 }, { 3, 8 }, { 4, 5 }, { 4, 9 }, { 5, 6 }, { 6, 7 }, { 7, 8 }, { 8, 9 } });
// C12(1,6)
AddGraph(12, 3, 3, new[,] { { 0, 1 }, { 0, 11 }, { 0, 6 }, { 1, 2 }, { 1, 7 }, { 2, 3 }, { 2, 8 }, { 3, 4 }, { 3, 9 }, { 4, 10 }, { 4, 5 }, { 5, 11 }, { 5, 6 }, { 6, 7 }, { 7, 8 }, { 8, 9 }, { 9, 10 }, { 10, 11 } });
// PP7(1,3) K2
//AddGraph(14, 3, 3, new[,] { { 0, 1 }, { 0, 6 }, { 0, 7 }, { 1, 2 }, { 1, 8 }, { 2, 3 }, { 2, 9 }, { 3, 10 }, { 3, 4 }, { 4, 11 }, { 4, 5 }, { 5, 12 }, { 5, 6 }, { 6, 13 }, { 7, 10 }, { 7, 11 }, { 8, 11 }, { 8, 12 }, { 9, 12 }, { 9, 13 }, { 10, 13 } });
// PP7(1,2) K2
//AddGraph(14, 3, 3, new[,] { { 0, 1 }, { 0, 6 }, { 0, 7 }, { 1, 2 }, { 1, 8 }, { 2, 3 }, { 2, 9 }, { 3, 10 }, { 3, 4 }, { 4, 11 }, { 4, 5 }, { 5, 12 }, { 5, 6 }, { 6, 13 }, { 7, 12 }, { 7, 9 }, { 8, 10 }, { 8, 13 }, { 9, 11 }, { 10, 12 }, { 11, 13 } });
// Heawood
AddGraph(14, 3, 3, new[,] { { 0, 1 }, { 0, 13 }, { 0, 5 }, { 1, 10 }, { 1, 2 }, { 2, 3 }, { 2, 7 }, { 3, 12 }, { 3, 4 }, { 4, 5 }, { 4, 9 }, { 5, 6 }, { 6, 11 }, { 6, 7 }, { 7, 8 }, { 8, 13 }, { 8, 9 }, { 9, 10 }, { 10, 11 }, { 11, 12 }, { 12, 13 } });
// O = C6(1,2)
AddGraph(6, 4, 2, new[,] { { 0, 1 }, { 0, 2 }, { 0, 4 }, { 0, 5 }, { 1, 2 }, { 1, 3 }, { 1, 5 }, { 2, 3 }, { 2, 4 }, { 3, 4 }, { 3, 5 }, { 4, 5 } });
// K4,4 = C8(1,3)
AddGraph(8, 4, 2, new[,] { { 0, 1 }, { 0, 3 }, { 0, 5 }, { 0, 7 }, { 1, 2 }, { 1, 4 }, { 1, 6 }, { 2, 3 }, { 2, 5 }, { 2, 7 }, { 3, 4 }, { 3, 6 }, { 4, 5 }, { 4, 7 }, { 5, 6 }, { 6, 7 } });
// K3 × K3
AddGraph(9, 4, 2, new[,] { { 0, 1 }, { 0, 2 }, { 0, 3 }, { 0, 6 }, { 1, 2 }, { 1, 4 }, { 1, 7 }, { 2, 5 }, { 2, 8 }, { 3, 4 }, { 3, 5 }, { 3, 6 }, { 4, 5 }, { 4, 7 }, { 5, 8 }, { 6, 7 }, { 6, 8 }, { 7, 8 } });
// C11(1,3)
AddGraph(11, 4, 2, new[,] { { 0, 1 }, { 0, 10 }, { 0, 3 }, { 0, 8 }, { 1, 2 }, { 1, 4 }, { 1, 9 }, { 2, 10 }, { 2, 3 }, { 2, 5 }, { 3, 4 }, { 3, 6 }, { 4, 5 }, { 4, 7 }, { 5, 6 }, { 5, 8 }, { 6, 7 }, { 6, 9 }, { 7, 10 }, { 7, 8 }, { 8, 9 }, { 9, 10 } });
// Cml15(5:1,4:2,5:3,7:4,4:4,7)
AddGraph(15, 4, 2, new[,] { { 0, 1 }, { 0, 11 }, { 0, 14 }, { 0, 8 }, { 1, 2 }, { 1, 5 }, { 1, 9 }, { 2, 12 }, { 2, 3 }, { 2, 7 }, { 3, 10 }, { 3, 14 }, { 3, 4 }, { 4, 11 }, { 4, 5 }, { 4, 8 }, { 5, 13 }, { 5, 6 }, { 6, 10 }, { 6, 14 }, { 6, 7 }, { 7, 12 }, { 7, 8 }, { 8, 9 }, { 9, 10 }, { 9, 13 }, { 10, 11 }, { 11, 12 }, { 12, 13 }, { 13, 14 } });
// C14(1,7)
AddGraph(14, 3, 4, new[,] { { 0, 1 }, { 0, 13 }, { 0, 7 }, { 1, 2 }, { 1, 8 }, { 2, 3 }, { 2, 9 }, { 3, 10 }, { 3, 4 }, { 4, 11 }, { 4, 5 }, { 5, 12 }, { 5, 6 }, { 6, 13 }, { 6, 7 }, { 7, 8 }, { 8, 9 }, { 9, 10 }, { 10, 11 }, { 11, 12 }, { 12, 13 } });
// C16(1,8)
AddGraph(16, 3, 4, new[,] { { 0, 1 }, { 0, 15 }, { 0, 8 }, { 1, 2 }, { 1, 9 }, { 2, 10 }, { 2, 3 }, { 3, 11 }, { 3, 4 }, { 4, 12 }, { 4, 5 }, { 5, 13 }, { 5, 6 }, { 6, 14 }, { 6, 7 }, { 7, 15 }, { 7, 8 }, { 8, 9 }, { 9, 10 }, { 10, 11 }, { 11, 12 }, { 12, 13 }, { 13, 14 }, { 14, 15 } });
// PP11(1,3) K2
AddGraph(22, 3, 4, new[,] { { 0, 1 }, { 0, 10 }, { 0, 11 }, { 1, 12 }, { 1, 2 }, { 2, 13 }, { 2, 3 }, { 3, 14 }, { 3, 4 }, { 4, 15 }, { 4, 5 }, { 5, 16 }, { 5, 6 }, { 6, 17 }, { 6, 7 }, { 7, 18 }, { 7, 8 }, { 8, 19 }, { 8, 9 }, { 9, 10 }, { 9, 20 }, { 10, 21 }, { 11, 14 }, { 11, 19 }, { 12, 15 }, { 12, 20 }, { 13, 16 }, { 13, 21 }, { 14, 17 }, { 15, 18 }, { 16, 19 }, { 17, 20 }, { 18, 21 } });
// McGee = Cml24(3:1,12:2,7:0,17)
AddGraph(24, 3, 4, new[,] { { 0, 1 }, { 0, 17 }, { 0, 23 }, { 1, 13 }, { 1, 2 }, { 2, 3 }, { 2, 9 }, { 3, 20 }, { 3, 4 }, { 4, 16 }, { 4, 5 }, { 5, 12 }, { 5, 6 }, { 6, 23 }, { 6, 7 }, { 7, 19 }, { 7, 8 }, { 8, 15 }, { 8, 9 }, { 9, 10 }, { 10, 11 }, { 10, 22 }, { 11, 12 }, { 11, 18 }, { 12, 13 }, { 13, 14 }, { 14, 15 }, { 14, 21 }, { 15, 16 }, { 16, 17 }, { 17, 18 }, { 18, 19 }, { 19, 20 }, { 20, 21 }, { 21, 22 }, { 22, 23 } });
// Tutte-Coxeter = Cml30(6:1,17:2,21:3,7)
AddGraph(30, 3, 4, new[,] { { 0, 1 }, { 0, 13 }, { 0, 29 }, { 1, 18 }, { 1, 2 }, { 2, 23 }, { 2, 3 }, { 3, 10 }, { 3, 4 }, { 4, 27 }, { 4, 5 }, { 5, 14 }, { 5, 6 }, { 6, 19 }, { 6, 7 }, { 7, 24 }, { 7, 8 }, { 8, 29 }, { 8, 9 }, { 9, 10 }, { 9, 16 }, { 10, 11 }, { 11, 12 }, { 11, 20 }, { 12, 13 }, { 12, 25 }, { 13, 14 }, { 14, 15 }, { 15, 16 }, { 15, 22 }, { 16, 17 }, { 17, 18 }, { 17, 26 }, { 18, 19 }, { 19, 20 }, { 20, 21 }, { 21, 22 }, { 21, 28 }, { 22, 23 }, { 23, 24 }, { 24, 25 }, { 25, 26 }, { 26, 27 }, { 27, 28 }, { 28, 29 } });
// K2 × K3,3
AddGraph(12, 4, 3, new[,] { { 0, 1 }, { 0, 10 }, { 0, 2 }, { 0, 6 }, { 1, 11 }, { 1, 3 }, { 1, 7 }, { 2, 3 }, { 2, 4 }, { 2, 8 }, { 3, 5 }, { 3, 9 }, { 4, 10 }, { 4, 5 }, { 4, 6 }, { 5, 11 }, { 5, 7 }, { 6, 7 }, { 6, 8 }, { 7, 9 }, { 8, 10 }, { 8, 9 }, { 9, 11 }, { 10, 11 } });
// K2 × P
AddGraph(20, 4, 3, new[,] { { 0, 1 }, { 0, 10 }, { 0, 2 }, { 0, 8 }, { 1, 11 }, { 1, 3 }, { 1, 9 }, { 2, 12 }, { 2, 3 }, { 2, 4 }, { 3, 13 }, { 3, 5 }, { 4, 14 }, { 4, 5 }, { 4, 6 }, { 5, 15 }, { 5, 7 }, { 6, 16 }, { 6, 7 }, { 6, 8 }, { 7, 17 }, { 7, 9 }, { 8, 18 }, { 8, 9 }, { 9, 19 }, { 10, 11 }, { 10, 14 }, { 10, 16 }, { 11, 15 }, { 11, 17 }, { 12, 13 }, { 12, 16 }, { 12, 18 }, { 13, 17 }, { 13, 19 }, { 14, 15 }, { 14, 18 }, { 15, 19 }, { 16, 17 }, { 18, 19 } });
// Moebius D
//AddGraph(20, 4, 3, new[,] { { 0, 10 }, { 0, 16 }, { 0, 19 }, { 0, 4 }, { 1, 11 }, { 1, 19 }, { 1, 2 }, { 1, 3 }, { 2, 12 }, { 2, 18 }, { 2, 6 }, { 3, 13 }, { 3, 4 }, { 3, 5 }, { 4, 14 }, { 4, 8 }, { 5, 15 }, { 5, 6 }, { 5, 7 }, { 6, 10 }, { 6, 16 }, { 7, 17 }, { 7, 8 }, { 7, 9 }, { 8, 12 }, { 8, 18 }, { 9, 10 }, { 9, 11 }, { 9, 19 }, { 10, 14 }, { 11, 12 }, { 11, 13 }, { 12, 16 }, { 13, 14 }, { 13, 15 }, { 14, 18 }, { 15, 16 }, { 15, 17 }, { 17, 18 }, { 17, 19 } });
// PP7(1,2,3) K3
AddGraph(21, 4, 3, new[,] { { 0, 1 }, { 0, 14 }, { 0, 6 }, { 0, 7 }, { 1, 15 }, { 1, 2 }, { 1, 8 }, { 2, 16 }, { 2, 3 }, { 2, 9 }, { 3, 10 }, { 3, 17 }, { 3, 4 }, { 4, 11 }, { 4, 18 }, { 4, 5 }, { 5, 12 }, { 5, 19 }, { 5, 6 }, { 6, 13 }, { 6, 20 }, { 7, 12 }, { 7, 14 }, { 7, 9 }, { 8, 10 }, { 8, 13 }, { 8, 15 }, { 9, 11 }, { 9, 16 }, { 10, 12 }, { 10, 17 }, { 11, 13 }, { 11, 18 }, { 12, 19 }, { 13, 20 }, { 14, 17 }, { 14, 18 }, { 15, 18 }, { 15, 19 }, { 16, 19 }, { 16, 20 }, { 17, 20 } });
// (4,6)-cage
AddGraph(26, 4, 3, new[,] { { 0, 1 }, { 0, 17 }, { 0, 25 }, { 0, 5 }, { 1, 10 }, { 1, 2 }, { 1, 22 }, { 2, 19 }, { 2, 3 }, { 2, 7 }, { 3, 12 }, { 3, 24 }, { 3, 4 }, { 4, 21 }, { 4, 5 }, { 4, 9 }, { 5, 14 }, { 5, 6 }, { 6, 11 }, { 6, 23 }, { 6, 7 }, { 7, 16 }, { 7, 8 }, { 8, 13 }, { 8, 25 }, { 8, 9 }, { 9, 10 }, { 9, 18 }, { 10, 11 }, { 10, 15 }, { 11, 12 }, { 11, 20 }, { 12, 13 }, { 12, 17 }, { 13, 14 }, { 13, 22 }, { 14, 15 }, { 14, 19 }, { 15, 16 }, { 15, 24 }, { 16, 17 }, { 16, 21 }, { 17, 18 }, { 18, 19 }, { 18, 23 }, { 19, 20 }, { 20, 21 }, { 20, 25 }, { 21, 22 }, { 22, 23 }, { 23, 24 }, { 24, 25 } });
// PP7(1,2,3,2) C4
AddGraph(28, 4, 3, new[,] { { 0, 1 }, { 0, 21 }, { 0, 6 }, { 0, 7 }, { 1, 2 }, { 1, 22 }, { 1, 8 }, { 2, 23 }, { 2, 3 }, { 2, 9 }, { 3, 10 }, { 3, 24 }, { 3, 4 }, { 4, 11 }, { 4, 25 }, { 4, 5 }, { 5, 12 }, { 5, 26 }, { 5, 6 }, { 6, 13 }, { 6, 27 }, { 7, 12 }, { 7, 14 }, { 7, 9 }, { 8, 10 }, { 8, 13 }, { 8, 15 }, { 9, 11 }, { 9, 16 }, { 10, 12 }, { 10, 17 }, { 11, 13 }, { 11, 18 }, { 12, 19 }, { 13, 20 }, { 14, 17 }, { 14, 18 }, { 14, 21 }, { 15, 18 }, { 15, 19 }, { 15, 22 }, { 16, 19 }, { 16, 20 }, { 16, 23 }, { 17, 20 }, { 17, 24 }, { 18, 25 }, { 19, 26 }, { 20, 27 }, { 21, 23 }, { 21, 26 }, { 22, 24 }, { 22, 27 }, { 23, 25 }, { 24, 26 }, { 25, 27 } });
// PP9(1,3) K2 U PP9(2,4) K2
AddGraph(18, 5, 2, new[,] { { 0, 1 }, { 0, 2 }, { 0, 7 }, { 0, 8 }, { 0, 9 }, { 1, 10 }, { 1, 2 }, { 1, 3 }, { 1, 8 }, { 2, 11 }, { 2, 3 }, { 2, 4 }, { 3, 12 }, { 3, 4 }, { 3, 5 }, { 4, 13 }, { 4, 5 }, { 4, 6 }, { 5, 14 }, { 5, 6 }, { 5, 7 }, { 6, 15 }, { 6, 7 }, { 6, 8 }, { 7, 16 }, { 7, 8 }, { 8, 17 }, { 9, 12 }, { 9, 13 }, { 9, 14 }, { 9, 15 }, { 10, 13 }, { 10, 14 }, { 10, 15 }, { 10, 16 }, { 11, 14 }, { 11, 15 }, { 11, 16 }, { 11, 17 }, { 12, 15 }, { 12, 16 }, { 12, 17 }, { 13, 16 }, { 13, 17 }, { 14, 17 } });
// D
AddGraph(20, 3, 5, new[,] { { 0, 16 }, { 0, 19 }, { 0, 4 }, { 1, 19 }, { 1, 2 }, { 1, 3 }, { 2, 18 }, { 2, 6 }, { 3, 4 }, { 3, 5 }, { 4, 8 }, { 5, 6 }, { 5, 7 }, { 6, 10 }, { 7, 8 }, { 7, 9 }, { 8, 12 }, { 9, 10 }, { 9, 11 }, { 10, 14 }, { 11, 12 }, { 11, 13 }, { 12, 16 }, { 13, 14 }, { 13, 15 }, { 14, 18 }, { 15, 16 }, { 15, 17 }, { 17, 18 }, { 17, 19 } });
// C × K2
AddGraph(16, 4, 4, new[,] { { 0, 1 }, { 0, 3 }, { 0, 7 }, { 0, 8 }, { 1, 2 }, { 1, 6 }, { 1, 9 }, { 2, 10 }, { 2, 3 }, { 2, 5 }, { 3, 11 }, { 3, 4 }, { 4, 12 }, { 4, 5 }, { 4, 7 }, { 5, 13 }, { 5, 6 }, { 6, 14 }, { 6, 7 }, { 7, 15 }, { 8, 11 }, { 8, 15 }, { 8, 9 }, { 9, 10 }, { 9, 14 }, { 10, 11 }, { 10, 13 }, { 11, 12 }, { 12, 13 }, { 12, 15 }, { 13, 14 }, { 14, 15 } });
// C5 × C5
AddGraph(25, 4, 4, new[,] { { 0, 1 }, { 0, 20 }, { 0, 4 }, { 0, 5 }, { 1, 2 }, { 1, 21 }, { 1, 6 }, { 2, 22 }, { 2, 3 }, { 2, 7 }, { 3, 23 }, { 3, 4 }, { 3, 8 }, { 4, 24 }, { 4, 9 }, { 5, 10 }, { 5, 6 }, { 5, 9 }, { 6, 11 }, { 6, 7 }, { 7, 12 }, { 7, 8 }, { 8, 13 }, { 8, 9 }, { 9, 14 }, { 10, 11 }, { 10, 14 }, { 10, 15 }, { 11, 12 }, { 11, 16 }, { 12, 13 }, { 12, 17 }, { 13, 14 }, { 13, 18 }, { 14, 19 }, { 15, 16 }, { 15, 19 }, { 15, 20 }, { 16, 17 }, { 16, 21 }, { 17, 18 }, { 17, 22 }, { 18, 19 }, { 18, 23 }, { 19, 24 }, { 20, 21 }, { 20, 24 }, { 21, 22 }, { 22, 23 }, { 23, 24 } });
// PP7(1,3) K2 × K2
//AddGraph(28, 4, 4, new[,] { { 0, 1 }, { 0, 14 }, { 0, 6 }, { 0, 7 }, { 1, 15 }, { 1, 2 }, { 1, 8 }, { 2, 16 }, { 2, 3 }, { 2, 9 }, { 3, 10 }, { 3, 17 }, { 3, 4 }, { 4, 11 }, { 4, 18 }, { 4, 5 }, { 5, 12 }, { 5, 19 }, { 5, 6 }, { 6, 13 }, { 6, 20 }, { 7, 10 }, { 7, 11 }, { 7, 21 }, { 8, 11 }, { 8, 12 }, { 8, 22 }, { 9, 12 }, { 9, 13 }, { 9, 23 }, { 10, 13 }, { 10, 24 }, { 11, 25 }, { 12, 26 }, { 13, 27 }, { 14, 15 }, { 14, 20 }, { 14, 21 }, { 15, 16 }, { 15, 22 }, { 16, 17 }, { 16, 23 }, { 17, 18 }, { 17, 24 }, { 18, 19 }, { 18, 25 }, { 19, 20 }, { 19, 26 }, { 20, 27 }, { 21, 24 }, { 21, 25 }, { 22, 25 }, { 22, 26 }, { 23, 26 }, { 23, 27 }, { 24, 27 } });
// Heawood × K2
AddGraph(28, 4, 4, new[,] { { 0, 1 }, { 0, 13 }, { 0, 14 }, { 0, 5 }, { 1, 10 }, { 1, 15 }, { 1, 2 }, { 2, 16 }, { 2, 3 }, { 2, 7 }, { 3, 12 }, { 3, 17 }, { 3, 4 }, { 4, 18 }, { 4, 5 }, { 4, 9 }, { 5, 19 }, { 5, 6 }, { 6, 11 }, { 6, 20 }, { 6, 7 }, { 7, 21 }, { 7, 8 }, { 8, 13 }, { 8, 22 }, { 8, 9 }, { 9, 10 }, { 9, 23 }, { 10, 11 }, { 10, 24 }, { 11, 12 }, { 11, 25 }, { 12, 13 }, { 12, 26 }, { 13, 27 }, { 14, 15 }, { 14, 19 }, { 14, 27 }, { 15, 16 }, { 15, 24 }, { 16, 17 }, { 16, 21 }, { 17, 18 }, { 17, 26 }, { 18, 19 }, { 18, 23 }, { 19, 20 }, { 20, 21 }, { 20, 25 }, { 21, 22 }, { 22, 23 }, { 22, 27 }, { 23, 24 }, { 24, 25 }, { 25, 26 }, { 26, 27 } });
// PP9(1,2,3,4) C4
AddGraph(36, 4, 4, new[,] { { 0, 1 }, { 0, 27 }, { 0, 8 }, { 0, 9 }, { 1, 10 }, { 1, 2 }, { 1, 28 }, { 2, 11 }, { 2, 29 }, { 2, 3 }, { 3, 12 }, { 3, 30 }, { 3, 4 }, { 4, 13 }, { 4, 31 }, { 4, 5 }, { 5, 14 }, { 5, 32 }, { 5, 6 }, { 6, 15 }, { 6, 33 }, { 6, 7 }, { 7, 16 }, { 7, 34 }, { 7, 8 }, { 8, 17 }, { 8, 35 }, { 9, 11 }, { 9, 16 }, { 9, 18 }, { 10, 12 }, { 10, 17 }, { 10, 19 }, { 11, 13 }, { 11, 20 }, { 12, 14 }, { 12, 21 }, { 13, 15 }, { 13, 22 }, { 14, 16 }, { 14, 23 }, { 15, 17 }, { 15, 24 }, { 16, 25 }, { 17, 26 }, { 18, 21 }, { 18, 24 }, { 18, 27 }, { 19, 22 }, { 19, 25 }, { 19, 28 }, { 20, 23 }, { 20, 26 }, { 20, 29 }, { 21, 24 }, { 21, 30 }, { 22, 25 }, { 22, 31 }, { 23, 26 }, { 23, 32 }, { 24, 33 }, { 25, 34 }, { 26, 35 }, { 27, 31 }, { 27, 32 }, { 28, 32 }, { 28, 33 }, { 29, 33 }, { 29, 34 }, { 30, 34 }, { 30, 35 }, { 31, 35 } });
// PP9(1,2,3,4,2) C5
AddGraph(45, 4, 4, new[,] { { 0, 1 }, { 0, 36 }, { 0, 8 }, { 0, 9 }, { 1, 10 }, { 1, 2 }, { 1, 37 }, { 2, 11 }, { 2, 3 }, { 2, 38 }, { 3, 12 }, { 3, 39 }, { 3, 4 }, { 4, 13 }, { 4, 40 }, { 4, 5 }, { 5, 14 }, { 5, 41 }, { 5, 6 }, { 6, 15 }, { 6, 42 }, { 6, 7 }, { 7, 16 }, { 7, 43 }, { 7, 8 }, { 8, 17 }, { 8, 44 }, { 9, 11 }, { 9, 16 }, { 9, 18 }, { 10, 12 }, { 10, 17 }, { 10, 19 }, { 11, 13 }, { 11, 20 }, { 12, 14 }, { 12, 21 }, { 13, 15 }, { 13, 22 }, { 14, 16 }, { 14, 23 }, { 15, 17 }, { 15, 24 }, { 16, 25 }, { 17, 26 }, { 18, 21 }, { 18, 24 }, { 18, 27 }, { 19, 22 }, { 19, 25 }, { 19, 28 }, { 20, 23 }, { 20, 26 }, { 20, 29 }, { 21, 24 }, { 21, 30 }, { 22, 25 }, { 22, 31 }, { 23, 26 }, { 23, 32 }, { 24, 33 }, { 25, 34 }, { 26, 35 }, { 27, 31 }, { 27, 32 }, { 27, 36 }, { 28, 32 }, { 28, 33 }, { 28, 37 }, { 29, 33 }, { 29, 34 }, { 29, 38 }, { 30, 34 }, { 30, 35 }, { 30, 39 }, { 31, 35 }, { 31, 40 }, { 32, 41 }, { 33, 42 }, { 34, 43 }, { 35, 44 }, { 36, 38 }, { 36, 43 }, { 37, 39 }, { 37, 44 }, { 38, 40 }, { 39, 41 }, { 40, 42 }, { 41, 43 }, { 42, 44 } });
// PP11(1,2,4,3,5) C5
AddGraph(55, 4, 4, new[,] { { 0, 1 }, { 0, 10 }, { 0, 11 }, { 0, 44 }, { 1, 12 }, { 1, 2 }, { 1, 45 }, { 2, 13 }, { 2, 3 }, { 2, 46 }, { 3, 14 }, { 3, 4 }, { 3, 47 }, { 4, 15 }, { 4, 48 }, { 4, 5 }, { 5, 16 }, { 5, 49 }, { 5, 6 }, { 6, 17 }, { 6, 50 }, { 6, 7 }, { 7, 18 }, { 7, 51 }, { 7, 8 }, { 8, 19 }, { 8, 52 }, { 8, 9 }, { 9, 10 }, { 9, 20 }, { 9, 53 }, { 10, 21 }, { 10, 54 }, { 11, 13 }, { 11, 20 }, { 11, 22 }, { 12, 14 }, { 12, 21 }, { 12, 23 }, { 13, 15 }, { 13, 24 }, { 14, 16 }, { 14, 25 }, { 15, 17 }, { 15, 26 }, { 16, 18 }, { 16, 27 }, { 17, 19 }, { 17, 28 }, { 18, 20 }, { 18, 29 }, { 19, 21 }, { 19, 30 }, { 20, 31 }, { 21, 32 }, { 22, 26 }, { 22, 29 }, { 22, 33 }, { 23, 27 }, { 23, 30 }, { 23, 34 }, { 24, 28 }, { 24, 31 }, { 24, 35 }, { 25, 29 }, { 25, 32 }, { 25, 36 }, { 26, 30 }, { 26, 37 }, { 27, 31 }, { 27, 38 }, { 28, 32 }, { 28, 39 }, { 29, 40 }, { 30, 41 }, { 31, 42 }, { 32, 43 }, { 33, 36 }, { 33, 41 }, { 33, 44 }, { 34, 37 }, { 34, 42 }, { 34, 45 }, { 35, 38 }, { 35, 43 }, { 35, 46 }, { 36, 39 }, { 36, 47 }, { 37, 40 }, { 37, 48 }, { 38, 41 }, { 38, 49 }, { 39, 42 }, { 39, 50 }, { 40, 43 }, { 40, 51 }, { 41, 52 }, { 42, 53 }, { 43, 54 }, { 44, 49 }, { 44, 50 }, { 45, 50 }, { 45, 51 }, { 46, 51 }, { 46, 52 }, { 47, 52 }, { 47, 53 }, { 48, 53 }, { 48, 54 }, { 49, 54 } });
// PP13(1,5,4,2,3,6) C6
AddGraph(78, 4, 4, new[,] { { 0, 1 }, { 0, 12 }, { 0, 13 }, { 0, 65 }, { 1, 14 }, { 1, 2 }, { 1, 66 }, { 2, 15 }, { 2, 3 }, { 2, 67 }, { 3, 16 }, { 3, 4 }, { 3, 68 }, { 4, 17 }, { 4, 5 }, { 4, 69 }, { 5, 18 }, { 5, 6 }, { 5, 70 }, { 6, 19 }, { 6, 7 }, { 6, 71 }, { 7, 20 }, { 7, 72 }, { 7, 8 }, { 8, 21 }, { 8, 73 }, { 8, 9 }, { 9, 10 }, { 9, 22 }, { 9, 74 }, { 10, 11 }, { 10, 23 }, { 10, 75 }, { 11, 12 }, { 11, 24 }, { 11, 76 }, { 12, 25 }, { 12, 77 }, { 13, 18 }, { 13, 21 }, { 13, 26 }, { 14, 19 }, { 14, 22 }, { 14, 27 }, { 15, 20 }, { 15, 23 }, { 15, 28 }, { 16, 21 }, { 16, 24 }, { 16, 29 }, { 17, 22 }, { 17, 25 }, { 17, 30 }, { 18, 23 }, { 18, 31 }, { 19, 24 }, { 19, 32 }, { 20, 25 }, { 20, 33 }, { 21, 34 }, { 22, 35 }, { 23, 36 }, { 24, 37 }, { 25, 38 }, { 26, 30 }, { 26, 35 }, { 26, 39 }, { 27, 31 }, { 27, 36 }, { 27, 40 }, { 28, 32 }, { 28, 37 }, { 28, 41 }, { 29, 33 }, { 29, 38 }, { 29, 42 }, { 30, 34 }, { 30, 43 }, { 31, 35 }, { 31, 44 }, { 32, 36 }, { 32, 45 }, { 33, 37 }, { 33, 46 }, { 34, 38 }, { 34, 47 }, { 35, 48 }, { 36, 49 }, { 37, 50 }, { 38, 51 }, { 39, 41 }, { 39, 50 }, { 39, 52 }, { 40, 42 }, { 40, 51 }, { 40, 53 }, { 41, 43 }, { 41, 54 }, { 42, 44 }, { 42, 55 }, { 43, 45 }, { 43, 56 }, { 44, 46 }, { 44, 57 }, { 45, 47 }, { 45, 58 }, { 46, 48 }, { 46, 59 }, { 47, 49 }, { 47, 60 }, { 48, 50 }, { 48, 61 }, { 49, 51 }, { 49, 62 }, { 50, 63 }, { 51, 64 }, { 52, 55 }, { 52, 62 }, { 52, 65 }, { 53, 56 }, { 53, 63 }, { 53, 66 }, { 54, 57 }, { 54, 64 }, { 54, 67 }, { 55, 58 }, { 55, 68 }, { 56, 59 }, { 56, 69 }, { 57, 60 }, { 57, 70 }, { 58, 61 }, { 58, 71 }, { 59, 62 }, { 59, 72 }, { 60, 63 }, { 60, 73 }, { 61, 64 }, { 61, 74 }, { 62, 75 }, { 63, 76 }, { 64, 77 }, { 65, 71 }, { 65, 72 }, { 66, 72 }, { 66, 73 }, { 67, 73 }, { 67, 74 }, { 68, 74 }, { 68, 75 }, { 69, 75 }, { 69, 76 }, { 70, 76 }, { 70, 77 }, { 71, 77 } });
// Robertson-Wegner
AddGraph(30, 5, 3, new[,] { { 0, 10 }, { 0, 15 }, { 0, 19 }, { 0, 2 }, { 0, 29 }, { 1, 12 }, { 1, 2 }, { 1, 21 }, { 1, 28 }, { 1, 4 }, { 2, 26 }, { 2, 3 }, { 2, 8 }, { 3, 13 }, { 3, 18 }, { 3, 22 }, { 3, 5 }, { 4, 15 }, { 4, 24 }, { 4, 5 }, { 4, 7 }, { 5, 11 }, { 5, 29 }, { 5, 6 }, { 6, 16 }, { 6, 21 }, { 6, 25 }, { 6, 8 }, { 7, 10 }, { 7, 18 }, { 7, 27 }, { 7, 8 }, { 8, 14 }, { 8, 9 }, { 9, 11 }, { 9, 19 }, { 9, 24 }, { 9, 28 }, { 10, 11 }, { 10, 13 }, { 10, 21 }, { 11, 12 }, { 11, 17 }, { 12, 14 }, { 12, 22 }, { 12, 27 }, { 13, 14 }, { 13, 16 }, { 13, 24 }, { 14, 15 }, { 14, 20 }, { 15, 17 }, { 15, 25 }, { 16, 17 }, { 16, 19 }, { 16, 27 }, { 17, 18 }, { 17, 23 }, { 18, 20 }, { 18, 28 }, { 19, 20 }, { 19, 22 }, { 20, 21 }, { 20, 26 }, { 21, 23 }, { 22, 23 }, { 22, 25 }, { 23, 24 }, { 23, 29 }, { 24, 26 }, { 25, 26 }, { 25, 28 }, { 26, 27 }, { 27, 29 }, { 28, 29 } });
// PP9(1,2,3,4) K4
AddGraph(36, 5, 3, new[,] { { 0, 1 }, { 0, 18 }, { 0, 27 }, { 0, 8 }, { 0, 9 }, { 1, 10 }, { 1, 19 }, { 1, 2 }, { 1, 28 }, { 2, 11 }, { 2, 20 }, { 2, 29 }, { 2, 3 }, { 3, 12 }, { 3, 21 }, { 3, 30 }, { 3, 4 }, { 4, 13 }, { 4, 22 }, { 4, 31 }, { 4, 5 }, { 5, 14 }, { 5, 23 }, { 5, 32 }, { 5, 6 }, { 6, 15 }, { 6, 24 }, { 6, 33 }, { 6, 7 }, { 7, 16 }, { 7, 25 }, { 7, 34 }, { 7, 8 }, { 8, 17 }, { 8, 26 }, { 8, 35 }, { 9, 11 }, { 9, 16 }, { 9, 18 }, { 9, 27 }, { 10, 12 }, { 10, 17 }, { 10, 19 }, { 10, 28 }, { 11, 13 }, { 11, 20 }, { 11, 29 }, { 12, 14 }, { 12, 21 }, { 12, 30 }, { 13, 15 }, { 13, 22 }, { 13, 31 }, { 14, 16 }, { 14, 23 }, { 14, 32 }, { 15, 17 }, { 15, 24 }, { 15, 33 }, { 16, 25 }, { 16, 34 }, { 17, 26 }, { 17, 35 }, { 18, 21 }, { 18, 24 }, { 18, 27 }, { 19, 22 }, { 19, 25 }, { 19, 28 }, { 20, 23 }, { 20, 26 }, { 20, 29 }, { 21, 24 }, { 21, 30 }, { 22, 25 }, { 22, 31 }, { 23, 26 }, { 23, 32 }, { 24, 33 }, { 25, 34 }, { 26, 35 }, { 27, 31 }, { 27, 32 }, { 28, 32 }, { 28, 33 }, { 29, 33 }, { 29, 34 }, { 30, 34 }, { 30, 35 }, { 31, 35 } });
// PP7(1,2,3,2) C4 × K2
AddGraph(56, 5, 4, new[,] { { 0, 1 }, { 0, 21 }, { 0, 28 }, { 0, 6 }, { 0, 7 }, { 1, 2 }, { 1, 22 }, { 1, 29 }, { 1, 8 }, { 2, 23 }, { 2, 3 }, { 2, 30 }, { 2, 9 }, { 3, 10 }, { 3, 24 }, { 3, 31 }, { 3, 4 }, { 4, 11 }, { 4, 25 }, { 4, 32 }, { 4, 5 }, { 5, 12 }, { 5, 26 }, { 5, 33 }, { 5, 6 }, { 6, 13 }, { 6, 27 }, { 6, 34 }, { 7, 12 }, { 7, 14 }, { 7, 35 }, { 7, 9 }, { 8, 10 }, { 8, 13 }, { 8, 15 }, { 8, 36 }, { 9, 11 }, { 9, 16 }, { 9, 37 }, { 10, 12 }, { 10, 17 }, { 10, 38 }, { 11, 13 }, { 11, 18 }, { 11, 39 }, { 12, 19 }, { 12, 40 }, { 13, 20 }, { 13, 41 }, { 14, 17 }, { 14, 18 }, { 14, 21 }, { 14, 42 }, { 15, 18 }, { 15, 19 }, { 15, 22 }, { 15, 43 }, { 16, 19 }, { 16, 20 }, { 16, 23 }, { 16, 44 }, { 17, 20 }, { 17, 24 }, { 17, 45 }, { 18, 25 }, { 18, 46 }, { 19, 26 }, { 19, 47 }, { 20, 27 }, { 20, 48 }, { 21, 23 }, { 21, 26 }, { 21, 49 }, { 22, 24 }, { 22, 27 }, { 22, 50 }, { 23, 25 }, { 23, 51 }, { 24, 26 }, { 24, 52 }, { 25, 27 }, { 25, 53 }, { 26, 54 }, { 27, 55 }, { 28, 29 }, { 28, 34 }, { 28, 35 }, { 28, 49 }, { 29, 30 }, { 29, 36 }, { 29, 50 }, { 30, 31 }, { 30, 37 }, { 30, 51 }, { 31, 32 }, { 31, 38 }, { 31, 52 }, { 32, 33 }, { 32, 39 }, { 32, 53 }, { 33, 34 }, { 33, 40 }, { 33, 54 }, { 34, 41 }, { 34, 55 }, { 35, 37 }, { 35, 40 }, { 35, 42 }, { 36, 38 }, { 36, 41 }, { 36, 43 }, { 37, 39 }, { 37, 44 }, { 38, 40 }, { 38, 45 }, { 39, 41 }, { 39, 46 }, { 40, 47 }, { 41, 48 }, { 42, 45 }, { 42, 46 }, { 42, 49 }, { 43, 46 }, { 43, 47 }, { 43, 50 }, { 44, 47 }, { 44, 48 }, { 44, 51 }, { 45, 48 }, { 45, 52 }, { 46, 53 }, { 47, 54 }, { 48, 55 }, { 49, 51 }, { 49, 54 }, { 50, 52 }, { 50, 55 }, { 51, 53 }, { 52, 54 }, { 53, 55 } });
}
public static void AddGraph(int n, int deg, int diam, int[,] array)
{
AddCase(new Case
{
N = n,
Degree = deg,
Diameter = diam,
Action = () =>
{
var g = new Graph(n, deg);
int len = array.GetLength(0);
for (int i = 0; i < len; i++)
g.AddBidirectionalEdge(array[i, 0], array[i, 1]);
return g;
},
});
}
public static void AddCase(int n, int m, int diam, Func<Graph> action)
{
AddCase(new Case
{
N= n,
Degree =m,
Diameter = diam,
Action = action,
});
}
public static void AddCase(Case c)
{
if (!cases.ContainsKey(c.N))
cases[c.N] = new List<Case>();
cases[c.N].Add(c);
}
public class Case
{
public int N;
public int Degree;
public int Diameter;
public Func<Graph> Action;
}
#endregion
public class Graph
{
int m;
int n;
int version;
public List<int>[] g;
public Graph(int n, int m)
{
this.n = n;
this.m = m;
g = new List<int>[n];
for (int i = 0; i < n; i++)
g[i] = new List<int>(m);
}
public List<int> this[int index] => g[index];
public static Graph CubeGraph(int m)
{
var n = 1 << m;
var g = new Graph(n, m);
for(int i=0; i<n; i++)
{
for (int j=0; j<m; j++)
g[i].Add(i ^ (1<<j));
}
return g;
}
public static Graph RandomGraph(int n, int degree, bool logN)
{
var g = CycleGraph(n, degree);
if (degree == 1) return g;
// Add second edges
if (logN)
g.ReduceDiameterToLogN();
// Add random edges
for (int i = 0; i < n; i++)
{
var list = g[i];
while (list.Count < degree)
{
// Excess edges
if (list.Count >= n - 1)
{
list.Add((i + random.Next(1, n)) % n);
continue;
}
int attach = random.Next(0, n - 1 - list.Count);
int attach2 = attach;
if (attach >= i) attach2++;
foreach (var v in list)
if (attach >= v) attach2++;
list.Add(attach2);
}
}
return g;
}
public int FastDiameter()
{
throw new NotImplementedException();
}
void ReduceDiameterToLogN()
{
int head = 0;
int[] next = new int[n];
next[n - 1] = -1;
for (int i = 0; i+1< n; i++)
next[i] = i + 1;
while (head != -1)
{
var cur = head;
var prev = -1;
int headorig = head;
while (cur != -1)
{
int tmp = cur;
cur = next[cur]!=-1 ? next[next[cur]] : -1;
if (prev == -1)
head = next[tmp];
else
next[prev] = next[tmp];
next[tmp] = cur;
g[tmp].Add(cur != -1 ? cur : head != -1 && g[tmp].Contains(headorig) ? head : headorig);
}
}
}
// http://combinatoricswiki.org/wiki/The_Degree/Diameter_Problem
static double MaximumOrderOfGraph(int degree, int diameter)
{
// Moore bound
return (degree * Pow(degree - 1, diameter) - 2) / (degree - 2);
// Undirected graphs
// complete graphs on d+1 vertices
// cycles on 2k+1 vertices (k=diameter)
// diameter2 - Peterseng graph
// no moore graphs for K>2 amd d>2
}
static double MaximumOrderOfDirectedGraph(int degree, int diameter)
{
// Moore bound
return (Pow(degree, diameter + 1) - 1) / (degree - 1);
// Directed graphs
// complete digraphs on d+1 vertices
// directed cycles on k+1 vertices (k=diameter)
// no moore graphs for K>1 amd d>1
}
// cube n=2^k nodes with both diameter and degree k / in digraph degree might equal 2k
// connect any two nodes whose index differ in only one digit ( i ^ j ) & (i ^ j) - 1 == 0
public int Diameter(int abortBound = int.MaxValue)
{
// Could use bitarray
var visited = new int[g.Length];
var queue = new Queue<int>();
int maxDiameter = 0;
for (int i = 0; i < n; i++)
{
Array.Clear(visited, 0, visited.Length);
queue.Enqueue(i);
visited[i] = 1;
while (queue.Count > 0)
{
var pop = queue.Dequeue();
var popdist = visited[pop];
foreach (var child in g[pop])
{
if (visited[child] != 0) continue;
visited[child] = popdist + 1;
queue.Enqueue(child);
if (popdist > maxDiameter)
{
maxDiameter = popdist;
if (maxDiameter >= abortBound)
return maxDiameter;
}
}
}
}
return maxDiameter;
}
//http://research.nii.ac.jp/graphgolf/2015/candar15/graphgolf2015-mizuno.pdf
public void AddBidirectionalEdge(int i, int j)
{
if (i == j) return;
if (!g[i].Contains(j)) g[i].Add(j);
if (!g[j].Contains(i)) g[j].Add(i);
}
public static readonly Graph K2 = Complete(2);
public static Graph Complete(int n)
{
// Degree n-1
// Diameter 1
var g = new Graph(n, n - 1);
for (int i=0; i<n; i++)
for (int j=i+1; j<n; j++)
g.AddBidirectionalEdge(i, j);
return g;
}
public static Graph Graph33(int n)
{
// Degree and diameter 3
int[] array = null;
switch(n)
{
case 8:
array = new[] {6,3,4,1,2,7,0,5};
break;
case 10:
array = new[] {7,6,5,9,8,2,1,0,3,4};
break;
case 12:
array = new[] { 10, 3, 8, 1, 6, 11, 4, 9, 2, 7, 0, 5 };
break;
case 14:
array = new[] { 5, 10, 7, 12, 9, 0, 11,
2, 13, 4, 1, 6, 3, 8 };
break;
case 18:
array = new[] { 14, 5, 9, 16, 12, 1,
11, 15, 13, 2, 17, 6,
4, 8, 0, 7, 3, 10, };
break;
}
if (array == null) return null;
var g = CycleGraph(n,3,true);
for (int i = 0; i < array.Length; i++)
g.AddBidirectionalEdge(i, array[i]);
return g;
}
public static Graph CycleGraph(int n, int m=1, bool bidrectional = false)
{
var g = new Graph(n, m);
g[n - 1].Add(0);
for (int i = 1; i < n; i++)
g[i - 1].Add(i);
if (bidrectional)
{
g[0].Add(n-1);
for (int i = 1; i< n; i++)
g[i].Add(i-1);
}
return g;
}
public static Graph ConnectedGraph(int n, int m)
{
var g = new Graph(n, m);
for (int i=0; i<n; i++)
for (int j=0; j<m; j++)
{
g[i].Add((i*m+j+Extra)%n);
}
return g;
}
public static Graph G8(int k)
{
// New order = 8 * k
// New degree = k + 2
// Diameter = 2
var g8 = new Graph(8 * k, k + 2);
for (int i = 0; i < k; i++)
{
g8.AddBidirectionalEdge(i * 8 + 0, i * 8 + 2);
g8.AddBidirectionalEdge(i * 8 + 0, i * 8 + 3);
g8.AddBidirectionalEdge(i * 8 + 0, i * 8 + 4);
g8.AddBidirectionalEdge(i * 8 + 1, i * 8 + 2);
g8.AddBidirectionalEdge(i * 8 + 1, i * 8 + 3);
g8.AddBidirectionalEdge(i * 8 + 1, i * 8 + 4);
g8.AddBidirectionalEdge(i * 8 + 2, i * 8 + 5);
g8.AddBidirectionalEdge(i * 8 + 3, i * 8 + 6);
g8.AddBidirectionalEdge(i * 8 + 4, i * 8 + 7);
g8.AddBidirectionalEdge(i * 8 + 5, i * 8 + 6);
g8.AddBidirectionalEdge(i * 8 + 5, i * 8 + 7);
g8.AddBidirectionalEdge(i * 8 + 6, i * 8 + 7);
}
for (int i=0; i<k; i++)
for (int j=0; j<k; j++)
{
if (i == j) continue;
g8.AddBidirectionalEdge(i * 8 + 0, j * 8 + 1);
g8.AddBidirectionalEdge(i * 8 + 1, j * 8 + 0);
g8.AddBidirectionalEdge(i * 8 + 2, j * 8 + 6);
g8.AddBidirectionalEdge(i * 8 + 3, j * 8 + 7);
g8.AddBidirectionalEdge(i * 8 + 4, j * 8 + 5);
g8.AddBidirectionalEdge(i * 8 + 5, j * 8 + 4);
g8.AddBidirectionalEdge(i * 8 + 6, j * 8 + 2);
g8.AddBidirectionalEdge(i * 8 + 7, j * 8 + 3);
}
return g8;
}
public static Graph Product(Graph g1, Graph g2, bool strong=false)
{
var g = new Graph(g1.n * g2.n, g1.m * g2.m + g1.m + g2.m);
var f = g2.n;
for (int i = 0; i < g1.n; i++)
{
var iedges = g1[i];
for (int j = 0; j < g2.n; j++)
{
var jedges = g2[j];
foreach (var e1 in iedges)
g[i * f + j].Add(e1 * f + j);
foreach (var e2 in jedges)
g[i * f + j].Add(i * f + e2);
if (strong)
{
foreach (var e1 in iedges)
foreach (var e2 in jedges)
g[i * f + j].Add(e1 * f + e2);
}
}
}
// Preserves diameter
// Order(g) = Order(g1) * Order(g2)
// Weak
// Degree(g) = Degree(g1)+Degree(g2)
// Diameter(g) = Diameter(g1) + Diameter(g2)
// Strong
// if (strong) Degree(g) = Degree(g1)*Degree(g2) + Degree(g1) + Degree(g2)
// Diameter(g) = Max(Diameter(g1), Diameter(g2))
// G(n/2,2) * C(2) -> G(n,5) // C(2) diameter=1
// G(n/3,2) * C(3) -> G(n/3,5) // C(2) diameter=2
// Question: Is C(3) degree 1
return g;
}
}
#if DEBUG
public static bool Verbose = true;
#else
public static bool Verbose = false;
#endif
}
public class TimestampedArray<T>
{
public T[] Array;
public int[] TimeStamp;
public int Time;
public T DefaultValue;
public TimestampedArray(int size, T defaultValue = default(T))
{
Array = new T[size];
TimeStamp = new int[size];
DefaultValue = defaultValue;
}
public T this[int x]
{
get
{
return TimeStamp[x] >= Time ? Array[x] : DefaultValue;
}
set
{
Array[x] = value;
TimeStamp[x] = Time;
}
}
public bool ContainsKey(int x)
{
return TimeStamp[x] >= Time;
}
public void InitializeAll()
{
for (int i = 0; i < Array.Length; i++)
{
if (TimeStamp[i] > Time) continue;
Array[i] = DefaultValue;
TimeStamp[i] = Time;
}
}
public void Clear()
{
Time++;
}
}
public static class HackerRankUtils
{
#region Reporting Answer
static volatile bool _reported;
static System.Threading.Timer _timer;
static Func<bool> _timerAction;
public static void LaunchTimer(Func<bool> action, long ms = 2800)
{
_timerAction = action;
_timer = new System.Threading.Timer(
delegate
{
Report();
#if !DEBUG
if (_reported)
Environment.Exit(0);
#endif
}, null, ms, 0);
}
public static void Report()
{
if (_reported) return;
_reported = true;
_reported = _timerAction();
}
[Conditional("DEBUG")]
public static void Trace(string s)
{
Console.WriteLine(s);
}
#endregion
public static int TimeLimit = 2000;
public static int RandomIterations = 20;
public static int RandomIterationsTop = RandomIterations + 20;
public static int Extra = 1;
}Diameter Minimization Java Solution
import java.io.*;
import java.util.*;
public class Solution {
static Deque<Integer> q = new LinkedList<>();
static int[] dis = new int[1001];
static int bfs(int n, int m, int x) {
Arrays.fill(dis, 1_000_000_000);
dis[x] = 0;
q.add(x);
int mmh = 0;
while (!q.isEmpty()) {
int k = q.removeFirst();
mmh = dis[k];
for (int i = 0; i < m; i++) {
int j = (k * m + i) % n;
if (dis[j] > mmh + 1) {
dis[j] = mmh + 1;
q.add(j);
}
}
}
return mmh;
}
public static void main(String[] args) throws IOException {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
BufferedWriter bw = new BufferedWriter(new FileWriter(System.getenv("OUTPUT_PATH")));
StringTokenizer st = new StringTokenizer(br.readLine());
int n = Integer.parseInt(st.nextToken());
int m = Integer.parseInt(st.nextToken());
dis = new int[n];
int mmh = 0;
for (int i = 0; i < n; i++) {
mmh = Math.max(mmh, bfs(n, m, i));
}
bw.write(mmh + "\n");
for (int i = 0; i < n; i++) {
for (int j = 0; j < m; j++) {
bw.write((i * m + j) % n + " ");
}
bw.write("\n");
}
bw.newLine();
bw.close();
br.close();
}
}Diameter Minimization Python Solution
#!/bin/python3
import sys
import math
def opt_diameter(n, m):
count = 1
depth = 0
while count < n:
depth += 1
count = m ** depth
return depth
def diameter(n, m):
count = 1
depth = 0
while count < n:
depth += 1
count += m**depth
left_over = m**depth - (count - n)
limit = m**(depth - 1)
discount = 1
if left_over > limit:
discount = 0
return max(depth, 2*depth - discount)
def solve(in_file, out_file):
n, m = (int(raw) for raw in in_file.readline().strip().split(' '))
out_file.write("{}\n".format(opt_diameter(n, m)))
count = 0
for _ in range(n):
ret = []
for _ in range(m):
val = count % n
count += 1
ret.append(str(val))
out_file.write("{}\n".format(" ".join(ret)))
if __name__ == '__main__':
from_file = False
if from_file:
path='Data\\'
name='mega_prime'
file_input = open(path+name+'.in', 'r')
file_output = open(path+name+'.out','w')
solve(file_input, file_output)
file_input.close()
file_output.close()
else:
solve(sys.stdin, sys.stdout)
