import graphlib.graphs.UndirectedGraph; import org.junit.Assert; import org.junit.Test; import java.util.Collection; public class SimpleTest { @Test public void square(){ CliqueFinder finder = new BBCliqueFinder(); var graph = makeGraph(4); for (int i = 0; i < 4; i++) { graph.addEdge(graph.getNode(i), graph.getNode((i+1) % 4)); } var clique = finder.maxClique(graph); testClique(graph, clique, 2); } @Test public void house(){ CliqueFinder finder = new BBCliqueFinder(); var graph = makeGraph(5); for (int i = 0; i < 4; i++) { graph.addEdge(graph.getNode(i), graph.getNode((i+1) % 4)); } graph.addEdge(graph.getNode(2),graph.getNode(4)); graph.addEdge(graph.getNode(3),graph.getNode(4)); testClique(graph, finder.maxClique(graph), 3); } @Test public void petersen(){ CliqueFinder finder = new BBCliqueFinder(); var graph = readGraph6("IheA@GUAo"); testClique(graph, finder.maxClique(graph), 2); } @Test public void K10(){ CliqueFinder finder = new BBCliqueFinder(); var graph = readGraph6("I~~~~~~~w"); testClique(graph, finder.maxClique(graph), 10); } @Test public void J10(){ CliqueFinder finder = new BBCliqueFinder(); var graph = readGraph6("I~~~~~~~o"); testClique(graph, finder.maxClique(graph), 9); } @Test public void Fv22224(){ CliqueFinder finder = new BBCliqueFinder(); //Smallest graph with clique number 3 and chromatic number 5 var graph = readGraph6("JqKDmY^\\bY_"); testClique(graph, finder.maxClique(graph), 3); } @Test public void Paley43(){ CliqueFinder finder = new BBCliqueFinder(); int[] dists = new int[]{7, 9, 13, 14, 15, 17, 18}; var graph = makeGraph(43); for (int i = 0; i < 43; i++) { for (int d : dists) { graph.addEdge(graph.getNode(i), graph.getNode((i+d) % 43)); } } var clique = finder.maxClique(graph); testClique(graph, clique, 3); } @Test(timeout = 5000) public void ml(){ CliqueFinder finder = new BBCliqueFinder(); var graph = readGraph6("~?Aa~~~~~~~~~~~~~~~~~~~~~~~~~~~~~}yb~Yh~pL~}E^~uw^~jh^~kM~~tJn~~~|h~~~qv|rt~fzZV~Nw{~~N|sL~~~Yc~~~wNr~~~bK~~~{z{\\ley|yZri}]qzxm^V[\\|ff{{Zn\\h~jhvZmV~Munxil~Mx^uVJ~eu{vtjzxjuryu|~cvzVY^^|Rn]mXz~x\\[tVnz|xYzInnv}}Jx\\b^~Z~Q|jcz~n^{JNc}~n^~gr]L||}~}nT|vMd~qU^i}zNB~kNZ^f}FF~Krt{uZ^Mymxu^Xrftujmuy|gzvUvy\\^r{hnvL^wt~uuF}]\\NrN~zUmi~d|drn}tVT^s}wz\\~tfk|uVg~mn~M^LmxlR|t~}rltinvpL~vur]yT^vgr~znT\\|ovmJnz|nrU}yRvPv|}v}hn[]^ZRv^l~xd}quzquz|v~op~eEA~~~~~~oM?Xx|~~~~~~U~xls{^^K]_lL^|fmMfnkfSSjmh~fxq~NBwKrmvwtr{unjY^g`t^qVZti}nI}gblnLT}tvrfS{sT}nfT]{zurT]dE~ms{~VFzblK}cf|uZZtt]yZpZjD^vVrK~N]FfbNwN~ldVv]ZI~jTZIj~janm}VD~VavDf~vNiye}vovkk[nvtrt\\U^jyR|Eer}zlR|ubvhu}hA^n]}lVm{VlZftaE}zz|hvtJm{T~[_tz}n|XzyF^YJ}yPJz|^}a~eEWF~~{e{N~~~gOE]X}~~~uO{~~~s}lzuZRBOfv^tz}yrxz^eZQQc^j}v^|rfmtrzTHe@|~V^l}zfnJl{xEXAz~j^r|zrn{Krvw?]Fv~m~f|{zB{r|wWE]~f{^v}~c~]oQ_zVi~]}~vm~}Jz{_sB]lVzvv}|v~{KBB~K]^}F|x~~u^~{J{{?r`ff}}^~nN~~yOAC}t}yh}v~nl~}~va@?vq~\\TnZ~vu~~^}znvF][n]vDkorm_tDSL~kmusz{yLscmtCkKp\\~E|[{m|ivQg\\pgdQRZ}fYz[\\}TupS\\hSU`Rm{nj\\t\\nXZcLTlPJBPz^Ftzku|mMsckvaKgk^]tv^LY}jL[XwiNhF@H|zMzzJZt[yhZQX\\W[GZzttlnil|W|FsIwjdEH]zty]^VJyxZJiRS\\bEO~\\uNm}rMZ|ic[mhJMdAm~Zd|vrRX~dWjFeKrY_f^zrrrB|}W^wrfaKxe`w^}NK{rrv~_^cuXpNFcEFf~\\SnmV^Iy~cqm`SveCY~nZRVuM~Dt~RP\\_izTCT~^mfygvnsV^adlkct[SL|^zX|TMvybnwS{yeInBA}n~W_?^}N~~~F~?p~oK?n~~|`~}?FB~~~_B~w?~oLN~~q|~rNMU@wFp~zoGE^[^~pi}jVytYQLB~|sEsGZs|z}t^Jty{]EHQ~|uCxGMul}~jVhff}]KKBv~raXoBs[~|}yzxme^hICv^Vyg@qVq~M~njnXte}bOK}y~kOEo}lz\\}~S~jGeG}Y]n~yxRCIZZzzn~Q~spEC|dl^~tslGHjVvv^~gvNoN?`~xz~fwoW[Zx}^^~yIKB{Nvfff{^~b?WxF~xn~}S?SvXvjfj|]~qCidemn~z~\\G?kzfl\\l^jv~GHTXUt~~^}x}r~rMG]WFA@`{v}}{^~uNXX}{N{rhe@`MW@n~x^B}^nr}c}rkn{lGhCQsGn~Vjulz}zufNj[t}f`DaBM@F~yx}fl~]}YxzmuY^r?dI_Epvl}|qvy~myvflveU~QCJP?[flnzmk~t}vq~KyvaMCneZdSOj~}lfY~zzLy~I|NcUG^XfQw_f~|]VT~vvUx~cz~KB@W^}B@eU~x~dx~f^{]^x_hBmN^R\\p@TRy|~rT|^|}S~zIAoZhvtf\\GDT]n^|hnV~^hV~kc_E^fs~rNE?L~b~rR~rv{[~~WnnkggDTCFlT\\zd\\^~\\tlN~v~g^^[SSAiaF[i|vQz^}zjin~n~[Z_@~er{?B~r@~{o^}~~KJ~^~^EF~_ER?BNG^~aF~z~[B~|~z~}ogORVVwArSyzrM]u~vvJVv|~|z`aAMmn_Sqj\\uiu{z}}zR^^n~nv?cajOO]~H{ve}ttnr}v{ft~y~~?bDSgOl~EzZX~Jy^r|z{Zm~t~~_IGh@clx]m{n[vVnV~lJ|l~|^~wAPD_ck}Nt]tmmr|j~{l]z^}n~~?HQ@KiuLzVLzyzh|^|mZ^t~N~~{?aoBKZcz]Yz^\\tZy~xu]}z{~~~w"); testClique(graph, finder.maxClique(graph), 21); } @Test(timeout = 8000) public void keller(){ CliqueFinder finder = new BBCliqueFinder(); var graph = readGraph6("~?Aj??????W?c`IAKBE@Q?g`CS_Os?o_@CA{cGmGQd`@WsGOySOOxaOHYcG`sW?EEhR?hUKgDIdLGHXQk`OOwN@OF`w@Cst]Zodirtm@jSh~VBNIT~MAstJzi`UjE}u_itJyuVDNI^fTXS^b{X^`Wp}NprxQs{^Ttwg{]Vs|[IeVhxnfAcnfpMNviI{~HX|]SLy}dT{{EcS^xxfxbIOn|\\TvOpgR~jimwFEG^}]W^_bJ]hmm}nxDY|dlm}^pIT}YtvX~sck~U[|t^{Op|iZrn{}yDNtdmm~jzGh{xjZ\\^^tPJytfV[~^sWR~aQ~~m}ikD~qQn~znibC^|@N~~NrKXB~pE^}^~e@}Xrc`_EXG?Zrk[uB?BL_BI^N?N{N???{Kvg\\w]WW?F_Fve[~GW@}Rw]|{rfNB?K}O~vVMpr{K?luB~nu\\b}oW?|lw^]ze^xG]Ff}?Ex}r}[cK{~N?B[vR{{uBoz^oBJr{\\zeoXw|}?X]ZyXrcfe]XHeZe^wrfHrrKq[ovKvqk[uVTRLdVJrBwuMZTtPetTdx_b|w@~hxB_F~n~{nozo}ov_NB}~~X[}C~o~o@Npvl|kyV]Nff_Bxbu||rpxB~byGcnhjnyxs|A~q}Gcjwtv|TmSzq{tpCnTMm~jljF]ffUPH|Ptv|ZLn`F}^_XE]U|ni\\jPzw{roqNomvnjLNO~o|ow^~?M~~JJFfaF~Fbpw]E~~aY~f{~GPx}^w]zu^`~{r~N@o{~o~vlr{N~Nrr{FBl~B~n\\rNN}\\z}oPw|~w^^\\e]^~c[~Hxf}Rx}xuffz~rK^fNK~H~N[zbr|v{qfNNK{}R~vLs~Nl~eKx}]Xfrf}xnFx|rxqM^jilmq~|xg||yFrg[~jij\\i~zrQzzsFrkNuVTVlnVzr`vvwFxuJzTtRuvt|xpZz{C}^faq}nZ}ix]wM}}wnr{{ejyz^yjJvAvvvI^rNsc~rr~Kr]rRr}tK~e^pM]^f~eE|fFf|sW~f{wHx~}]Xezefxzj_~r}[bN{~NrB\\rb{|yofrn[qV^VntVJz@zzwtO}\\zed\\{|~TX^WV^^FSB}Xp~`_F~N~zfx}FeF~~rkZ~B?N|n~zr{rrro~}^|AN|~G}K~|z^Ktv{Nyvp\\w~]^oNf~Zvdf\\x~dr{xB~jzJcn~jnwmlf}]e^jOn|ni\\I~|\\~Etk~rsX}yC~s~ppN~vl{Rv^o~_l}J^Fu]}P}^u|xxV]^x@l}d]Vum{dy~tvxZRx~eaU~bNRzj]c}nyz{mh{~rQF{^~HB~~~o?v{r{NN~o~~}Z~eo^~~}?X^xe]]^xx~~NfsnmN}aZ}mkni~?}jxje^Npnkn}HZ}\\X^U}@}frfDnUzr[||C~\\]enj\\BV|Q|Mvl\\yu^^CnvNRVtu`l}p^ErzxR}fyMtnljJzmoVj]Jw}^^Qnw~azM}lX^]uA}jpnJU|VnjR^FY~UyY}|cM^xNcvlzN^fF]VX~Tst||G\\^s^PulyNvFm^F~}Du|zxE}^xh\\}U|R|JvVd~|Syz|la{~rtTvTnW~c|yy^~iMm~ZgnN{|e]wrx{g~p~{]^bnZ{ff^`~uc^qvh]w}}]N~eNZvleZx~fBu]E^^EM}~Fr{{lz^ksz{N|wnKM^NKZ}^Vft|L\\~ds[~r}XV[bNfiU~Vrt|^Em~rYM^x~TLu_~~~~wW@~}?]^}F~~_?@~~~~~~~fN~NKqO{t\\~{~K~rvNRN{~~N~f~BrH{BYz~{{{~r^prH~~|zf~xwXkFxNZ}}}^`~M{X|^~~f}v}EXlwXU|~^]]^xV\\eM~~|~n~r~??~or~{~r~~~oB~oB~~~~~B?N~~B~Zo~~{?{N~rN~^~~~~wW@~}F~{}F~~_?^~~e^zz~~~~`w^~w@~}g^~~`_F~xf~nf~~~~BNN~oB~}_~~{{?N~{r~^F~~fN~NK}O~~L~[~k~rvKrM^n~~x~{~w^xN`~f^vfnf}Ze]X}Z}~|zf~xxZkF~}Zy}}~`~E]Xm~^~~{~u~ovlnB~rnjzzr~Gr{rj|~^~}[~{{~NBr|r~rxr~N~pKxq~r~}^~N}Ff~wF|f~xlx~fxzeRe~e~~f}v}FZ~wX}x~^M}^xm|eK^nx~}|r~{{]~B{~k~^Zno~zmKuNn{v~~fN~N{qR{~\\vs~L{FvNR~{nTv~~{x~~xeRffzn^exv`]xzx~dymz~x~{~}]XNe^vZ|ffh}b}M^Nzt\\~~r~x~r{q^o~mz~JNb}F{^q^vizv~n[~~^RLd~Nz\\tvo|Rxvf^jzV]N~vm^~vpet^f|nZZw^P{ztvt|jnE~~f}v}mXlyx}|nZ]W~bV\\mm~l\\m^~{~u~yrLnjNvmzjrJ{izmxv|jlr^|~n~r~o@~p~~{NrN~~gQ~wRz{r~~z~^~f}Gd~h~~xj`~~}aJ~cNve^}~z~^~f}PH~p~~xt`~~}cR~gVve^}^|~n~r~BG~q~~{~BN~~ca~pbz{r~?"); testClique(graph, finder.maxClique(graph), 11); } @Test(timeout = 8000) public void emp(){ CliqueFinder finder = new BBCliqueFinder(); var graph = readGraph6("~?AO????AGCaAC_C_H?GGCO?C_?c?AA?CO?AkqHXXDQeYKRRDOehT?S{cOKjT?DWZC?jKaQtdcTEqeYLBcspSf??`PEP?AgcX??JH@o?AR@WO?GEXEO?AHeP_??gmD_??cS[E?Ch\\HG@d@rPKOPSO^Da@D@Gtos?R@R_XcO\\?e`P[GLCBIcS[@p?T`CrGDo?C_?GIDcyH??A_iZDGG??aJJPcO??aHLJ_OWUPCES?sQDd__UO@pGcsS@R?DcOTKa@L?F?cqJ?AgmQkOXFO?UQpdOcYM?OgmQePBDo?cpkLOCh\\?APcYY_O[sO?sSbSoP@{O@cSeT_@Gto?KROki?uz||~\\t~}|~lzz^vzm~|^rnnz^uzv~n^d{~|v|\\z~|vbZl~||vVn~|oz]n~t}zl~~wBnm~|uzu~~|_Vr|~|tvn^~y?vz\\|^^|z^~\\|^|vZm~}vv~nZ\\~VZy~~uv~|^D}~\\v\\~zv^}{w}z\\|^^~z]|~fB|yz^V~~u|^|kFnmz\\v~}}n^ngF{~\\v\\~~v\\vvoBZnvv|vV~zvvt~\\|~Z}v]~|z~ZnvZvu~nv\\~y~vu}Vr~v^tvn~v^r|wuz||~\\t~}||~^Vz]}v|}zn~V}~vlM}~l~Zn^}|~nv\\d{~|v|\\z~|v|~Nouz^~^\\tz~~^f|~Bly~~Vzmv~~lnz{Bnm~|uzu~~|nnzwD{~^~\\\\zv~}vv|wBZl~||vVn~|~^fBvz]n~t}zl~~zzmo}rnm~|uzu~~|~jyFyVr|~|tvn^~z~Zo^oz}mvt~~ln~y}v|n}vz\\|^^|z^~\\|^v^|N}zlv^~Zz~vlv|z|d}~\\v\\~zv^}{~^v]wvz\\|^^|z^~\\~^V^^nnyz^V~}u~~j~]u}|r~mz\\v~u}~|z|v]v}d}~\\v\\~zv^}|~NvN~Bzlvt|~~lzv}^v~f^o~]mvt~~|nV~Z}~uz{Fnmz\\v~}}n^nnzzzn_^r|v\\v~~\\v^^^vvv]?}z\\|^^~z]|~vx}|vBv~]mvt~~|nV~zmz}zBz]}zlv^~zy|~}nj~m`}f{~\\v\\~~v\\v~u|n|o^ov~||~|t~]|^f|~xv~f^n~z^~zm}|^lnz~Zn|mr~~z^}zv}n\\nnzzznnmd~~|v~\\z~\\uvv|||vvvB^~vv~vV|zt~^fzv^n\\vz~}v~}znnVzzmz}zvzmr~~z^}zv}n\\~jy~zl~myV~~v^|vn|vZ~Zu~vN~\\o~nz~zzn}zmvfz}zvzn^o}~^~^|vz]|\\|^v^|l~vo]~z~vznzy|vlv|z|znvwFz|~}~v^ly~Vu~l~rv~]?}~^~^|vz]|\\~^V^^l|{Nn|}~~^znu|^j~]u}|zzo~fn}~|}z}}n\\z|v]v}z^`}f|~^~^\\~v\\u|~NvN~[~`zb~~~~~~~~~~v^~^v}~^v}~~~~~~~~~~~}z~|}~^z}~zv~~~~~~~~~~zn~^z}~nz}}^~~~~~~~~~~v^~^v|~^vnw~~~~~~~~~~|~|v~vn~^vnv~~~~~~~~~~}~}|~z^~nzzz^~~~~~~~~~~n~l~}z~z}z}f~~~~~~~~~~|~|v~v^~^r~o~~~~~~~~~~~v^~\\~|v|~|v^~~~~~~~~~~~n^}z~znz~zmv~~~~~~~~~~~l~}z~znz~zmf~~~~~~~~~~~v^~\\~|v|~|vB~~~~~~~~~~~|v|~^v|~^v\\v~~~~~~~~~~~~u~nz}~nz}zmv~~~~~~~~~~~|z}~nz}~nzmy^~~~~~~~~~~~|v|~^v|~^v\\o"); testClique(graph, finder.maxClique(graph), 16); } /* Een uitdaging: @Test(timeout = 1000) public void random(){ CliqueFinder finder = new BBCliqueFinder(); var graph = readGraph6("~?Ai~~~~~}v~~~~~~~~~~~~~~~~~|~l~~|~~~~~~~~~~~~^~~n~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~|~~~~~~~~~~~~~~~~~~~~~~~~~n~~~~~~\\~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~}~~~~~~~~~~~~~~~~~~~}~~~~n~~~~~~~~~|~~~~^~~~~~~||~~^~~~~~~|n~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~v~~~~~~~~~~~~~}~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~n~~~~~~~~~~~~~~~~~~~~~~~~~z~~~~~~~~~~~~~~~~~~~~~~|~~~~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~z~~~~~~~~^~~}~~u~~~~~v~|~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~|~~~~~~~~~~~~~~~~~~~v~~n~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~}~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~z^~~~~~~~~~~~v~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~v~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~}~~~~~~~~~~~~~~z~z~~~~~~~v}~~~~~~~~~|~~v~~~~|~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~zz~~~~~~~~~~~~~~~~~~~~~~~~~~~~v~~v~~~~~~}~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~|~~~~~~~~~~~~~~~~~~~~~~~~~}~~~~~~~~~~~~^~~~~~^}~~~~~~~~~~~~~~~^~~~v~~~~~~~~~~~~~~~~~|~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~z~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~n~~~~~~~~~~z~~~~~z^~~~~~^~~~~~~~~~z~|z~~~~~~~~~n~~~v~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~|~~~~~~n~~~~~~~~~~~~~~~~~~~~~~~~~~|~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~^~~~~~~~~~~~~~~}^~~~~~~z~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~x^~~~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~n~~~~~}~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~}~~~~~~~~~~~~~~~~~n~~~~~~~~~n~~~^~~~~~~~~~~~~~~~~~~~~~}~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~|~~|~~~~~~~~~~~~~~~~~~~~~~z~~~~~~~~~~~~~~~~~~~~~~~~~~~~zz~~~|~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~z~~~~~~~~~^~|~~~~~~~~~~~~~~~~~~~}~~~~~~~~~~~~~~~~~~~~~~~~~~~~~]~~~~~~~~~~~~~~~n~z~~~~~~~~~~~~~~~~~}~z~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~v~~~~~~~~~~~~~~~~~~~~~~~~~~~n~~~~~~~v~~~~~~~~~~~~z~~~~~~~~~~~~~~~~~~~~~~~|~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~|~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~n~~~~~~~~n~~~~|~~~~~~~~~~~~~z~~}~~~~~~~~~~~~~~~~~~~~~~~~~~~}~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~z~~~~~~~~~~~~~~~~~~~~~~v~~~~~~~~^~~~~|~~~~~~~~~~~vvv~~^v~~~~~~~~~~~~~~~~~~~~~^~~~~~~~~~~}z~~~~~~~~^v~~}~~~~~v~~~~~~~~~~~~~~|~z~~~~~~~~~~~~~~~~~~~~~v~~~~}~~~~~~~~~~~~|~~~~~~~~~~~~~v~~~~~~~~~~~v~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~z~~~^~~~~~_"); testClique(graph, finder.maxClique(graph), 109); } */ public static void testClique(UndirectedGraph graph, Collection clique, int optimal){ for(int v: clique){ for(int w: clique){ Assert.assertTrue(graph.containsNode(w)); if(v != w){ Assert.assertTrue("The given nodes do not form a clique.", graph.containsEdge(graph.getNode(v),graph.getNode(w))); } } } Assert.assertEquals(optimal, clique.size()); } public static UndirectedGraph makeGraph(int order){ UndirectedGraph graph = new UndirectedGraph<>(); for(int i = 0; i < order; i++){ graph.addNode(i); } return graph; } public static int graph6N(String graph6String){ if(graph6String.charAt(0) != 126){ return graph6String.charAt(0) - 63; } int nr = graph6String.charAt(1) - 63; nr <<= 6; nr |= graph6String.charAt(2) - 63; nr <<= 6; nr |= graph6String.charAt(3) - 63; return nr; } public static UndirectedGraph readGraph6(String graph6String){ int order = graph6N(graph6String); var graph = makeGraph(order); int i = order < 63 ? 1 : 4; int x = 0; int y = 1; for(; i < graph6String.length(); ++i) { char c = (char) (graph6String.charAt(i) - 63); for (int j = 5; j >= 0; j--) { if ((c & (1 << j)) > 0) { graph.addEdge(graph.getNode(x), graph.getNode(y)); } if (x + 1 < y) { x++; } else { y++; x = 0; } } } return graph; } }