import argparse
import random
import re
import math
import matplotlib.pyplot as plt
import mogutda
import networkx as nx
from pycliques.simplicial import clique_complex, nerve_of_sets
from pycliques.dominated import completely_pared_graph as p
from pycliques.dominated import (
has_dominated_vertex,
complete_s_collapse,
complete_s_collapse_edges
)
from pycliques.cliques import clique_graph as kfrom pycliques.cliques import clique_graph as k
from pycliques.cliques import Clique
from pycliques.helly import is_clique_helly
from pycliques.lists import list_graphs
from pycliques.surfaces import open_neighborhood
from homsmall import *
def plot_neighborhoods(g):
n = g.order()
for i in range(n):
rows = int(math.sqrt(n))
columns = math.ceil(n/rows)
plt.subplot(rows, columns, i+1)
plt.title(i)
nx.draw(open_neighborhood(g, i), node_size=200, with_labels='True')
plt.show()
#+RESULTS[504e152d7b74288cbb2350cb9467bcad79fb003c]:
from pycliques.simplicial import SimplicialComplex
s_c = SimplicialComplex([1,2,3,4,5,6], facet_set=[{1,3,4,6}, {1,2,4}, {2,4,5}, {3, 6}, {5, 6}])
homotopy_type_s_c(s_c)
#+RESULTS[c7b4607cda64ddb876b4b4efc30107c78cfc739b]:
'\\(S^{1}\\)'
suspend_string_with_s1s("\\(S^{1}\\vee S^{2}\\)", 2)
#+RESULTS[6141dcc69fd51c4df6b309bdf8b97d19ae0cc9c1]:
\(\vee_{2}S^{1}\vee S^{2}\)
graphs = nx.read_graph6("./data/graph10c015.g6")
len(graphs)
#+RESULTS[546eb37daa0b42ac2696b281d51dbc11a31a7bd3]:
100000
g = graphs[75299]
nx.draw(g, with_labels=True)
#+RESULTS[bf838a9617d4d5e4c17ea62a60be34d55b25c575]:
homotopy_type(g)
#+RESULTS[0a65031658d1b0a0ed4adf3237d00928c254e21c]:
\(\vee_{5}S^{1}\vee S^{2}\)
betti_numbers(nx.convert_node_labels_to_integers(g))
#+RESULTS[d72c9d11be723936ab591f972af1104a7dbbe304]:
[0, 5, 1]
h_type_using_star_cluster(g)
#+RESULTS[9666f24ed3bc3cb45703dbcf0394d7800867b4c8]:
False
h_type_by_special_neigh(g)
#+RESULTS[da82a8298c9583f11882248f10c133f02e86cb9c]:
False
graph = g
neighs = [(i, open_neighborhood(graph, i)) for i in graph.nodes()]
filt = [v for (v, nei) in neighs if is_disjoint_union_of_two_completes(nei)]
filt2 = [v for v in filt if nx.is_connected(graph.subgraph(set(graph.nodes()-{v})))]
filt2
#+RESULTS[8668091b812f4fea342b524d0a01a3dea36fab80]:
| 0 | 3 |
v = filt2[0]
h = graph.subgraph(set(graph.nodes())-{v})
h_type = homotopy_type(nx.convert_node_labels_to_integers(h))
h_type
#+RESULTS[f6415402789e78333a96309d7184a2954d598803]:
\(\vee_{3}S^{1}\vee S^{0}\vee S^{2}\)
nx.draw(h, with_labels=True)
#+RESULTS[9bc0ff8288ae7daa2abd0cdf6ee1469f4a44a3e0]:
betti_numbers(nx.convert_node_labels_to_integers(h))
#+RESULTS[16031949c7d82a5d16ec441e77f1923e1cdd30d3]:
| 0 | 2 | 1 |
homotopy_type(h)
#+RESULTS[29fe9fe1f949efd0d2a664d08528a50c55e174d9]:
\(\vee_{3}S^{1}\vee S^{0}\vee S^{2}\)
nx.draw(nx.complement(h))
#+RESULTS[cb38b21b18dad5c5a37e30d591aa0622597a19f1]:
h_type_using_star_cluster(h)
#+RESULTS[76008ebb38de474519ff9bca95c8280fc5928078]:
False
h_type_by_special_neigh(h)
#+RESULTS[4979ab9a7bd617753eb65e38e68840bb2f688935]:
\(\vee_{3}S^{1}\vee S^{0}\vee S^{2}\)
graph = h
neighs = [(i, open_neighborhood(graph, i)) for i in graph.nodes()]
filt = [v for (v, nei) in neighs if is_disjoint_union_of_two_completes(nei)]
filt2 = [v for v in filt if nx.is_connected(graph.subgraph(set(graph.nodes()-{v})))]
filt2
#+RESULTS[4a05f858d00b826b97365488589ff99942f79b57]:
[3, 6]
v = filt2[0]
h2 = graph.subgraph(set(graph.nodes())-{v})
h_type = homotopy_type(nx.convert_node_labels_to_integers(h2))
h_type
nx.draw(h2, with_labels=True)
#+RESULTS[5fefafb0a2db8053bd9ac986ea2b43f394b74f60]:
nx.draw(nx.complement(g), with_labels=True)
#+RESULTS[dac7ea45379cb9e5d94906e8ae5b91fdc695b488]:
kg = k(g)
kg.order()
#+RESULTS[59755e62105ba8e6b8505f94d21109ffd85c24ba]:
20
nx.draw(nx.complement(kg), with_labels=True)
#+RESULTS[e2e989d14cf8f110ee33a8a52036b6f910f71f10]:
%time homotopy_type(kg)
#+RESULTS[c040a406e02f5a4f791f5a3cf20cdb5e3ad246c6]:
CPU times: user 45.6 ms, sys: 414 µs, total: 46 ms
Wall time: 44.9 ms
\(S^{2}\vee \vee_{2}S^{3}\)
betti_numbers(nx.convert_node_labels_to_integers(kg))
#+RESULTS[a1726846ab78a7166ec8e225d9374c322c6026c3]:
[0, 0, 1, 2]
graph=kg
graph = nx.convert_node_labels_to_integers(graph)
c_graph = nx.complement(graph)
verts = [i for i in c_graph.nodes() if open_neighborhood(c_graph, i).size() == 0]
verts
#+RESULTS[6543c0f2292a2b3c513998c2d68e7ef8960119e5]:
[0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16, 17, 18, 19]
vertex=0
IG = clique_complex(graph)
ST = star(IG, vertex)
SC = star_cluster(IG, c_graph[vertex])
ST, SC
#+RESULTS[cdfde9bf52ede565cd0c3766d6234724e5afa2e7]:
'(Simplicial complex with vertex_set (0 1 2 3 4 5 6 7 8 9 10 11 12 13) and facets ((0 1 4 5 11) (0 1 2 3 10) (0 2 3 7 13) (0 1 10 11) (0 2 3 10 12 13) (0 1 2 3 4 5 6 7 8 9) (0 2 3 6 12) (0 10 11 12 13)). Simplicial complex with vertex_set (1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19) and facets ((8 19 5 14) (17 3 6 7 8 9) (16 2 10 12 13) (19 5 11 14 15) (16 2 12 6) (17 3 12 6) (18 4 6 7 8 9) (10 11 12 13 14 15 16 17 18 19) (17 3 10 12 13) (9 19 5 15) (1 4 5 8 14) (16 17 18 19 7 13) (19 5 6 7 8 9) (16 2 6 7 8 9) (18 4 11 14 15) (1 4 5 9 15) (16 17 18 19 8 14) (8 18 4 14) (16 2 13 7) (1 10 11 14 15) (6 7 8 9 16 17 18 19) (16 17 18 19 6 12) (16 17 18 19 9 15) (9 18 4 15) (17 3 13 7) (1 4 5 11 14 15)).)
int_c = intersection_complex(ST, SC)
int_c
#+RESULTS[f1f0510225ccfd0764ac48080bd667f8aace410e]:
Simplicial complex with vertex_set {1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13} and facets {{10, 11, 12, 13}, {2, 13, 7}, {2, 10, 12, 13}, {8, 1, 4, 5}, {1, 4, 5, 9}, {10, 3, 12, 13}, {3, 12, 6}, {1, 11, 4, 5}, {3, 6, 7, 8, 9}, {2, 12, 6}, {1, 10, 11}, {4, 6, 7, 8, 9}, {5, 6, 7, 8, 9}, {2, 6, 7, 8, 9}, {3, 13, 7}}.
csc = collapse(int_c)
csc
#+RESULTS[dd822ebb04f25f10c4ce061b62362bfddad241ee]:
Simplicial complex with vertex_set {1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13} and facets {{2, 13, 7}, {8, 1, 5}, {9, 4, 6}, {3, 12, 13}, {8, 1, 4}, {9, 4, 5}, {3, 13, 7}, {10, 12, 13}, {2, 12, 6}, {11, 4}, {8, 9, 6}, {11, 13}, {2, 6, 7}, {8, 4, 6}, {2, 10, 12}, {1, 4, 5}, {3, 6, 7}, {8, 9, 5}, {3, 12, 6}, {2, 10, 13}}.
special_vertex_in_s_c(csc)
#+RESULTS[6ae13e145ed25025971182030b30e8227d2d3dad]:
11
s_c = csc
vertex = 11
s_c2 = s_c.deletion(vertex)
h_type = homotopy_type_s_c(s_c2)
s_neigh = len(s_c.link(11).vertex_set)
h_type, s_neigh
#+RESULTS[695a1bcaa9ee8d00ab9b9131a38eaa229f0f9d33]:
('\\(\\vee_{2}S^{2}\\)', 2)
homotopy_type_s_c(csc)
#+RESULTS[c5d601cedec923c22244ef96602f93d0d3fc256e]:
\(S^{1}\vee \vee_{2}S^{2}\)
csc2 = csc.deletion(11)
csc2
#+RESULTS[e5b1b796e8a58796e6b1f86828fbd2b45899c73e]:
Simplicial complex with vertex_set {1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 12, 13} and facets {{2, 13, 7}, {8, 9, 6}, {8, 1, 5}, {2, 6, 7}, {9, 4, 6}, {3, 12, 13}, {10, 12, 13}, {8, 9, 5}, {3, 12, 6}, {2, 10, 13}, {2, 12, 6}, {8, 4, 6}, {2, 10, 12}, {1, 4, 5}, {8, 1, 4}, {3, 6, 7}, {9, 4, 5}, {3, 13, 7}}.
is_vertex_decomposable(csc2)
#+RESULTS[978d5a388faa9961ed7d7b66189d4b37e226a8f8]:
False
csc2.dong_matching(order_function=_shuff)
#+RESULTS[38c5b5b25b06d55c5245665253514a2ff3bd7585]:
{{2, 10, 12}, {9, 4, 5}}
is_vertex_decomposable(csc)
#+RESULTS[c2e0eaee9580a80bd52ebb98847acc1a339794ac]:
False
csc.is_clique_complex()
#+RESULTS[2f9774427da278b00f323bedbb2a593451ce6959]:
False
def _shuff(lista):
return random.sample(list(lista), len(lista))
csc.dong_matching(order_function=_shuff)
#+RESULTS[9ecbb04ea3c324fb3804719e482ae6d801e2793c]:
{{8, 9, 6}, {10, 12, 13}, {11, 13}}
betti_numbers_c(csc)
#+RESULTS[ee4037d4f65fb31beb9a5c1c562d899123df3c1d]:
[0, 1, 2]
graphs = nx.read_graph6("./data/graph10c016.g6")
len(graphs)
#+RESULTS[046fb76b6c91ca89e71eab45b54a0f7a6e054f78]:
100000
g = graphs[65424]
nx.draw(g, with_labels=True)
#+RESULTS[7b1f642e67623ed939b269e4f788fe48bb0d6ece]:
homotopy_type(g)
#+RESULTS[0a65031658d1b0a0ed4adf3237d00928c254e21c]:
\(\vee_{8}S^{2}\)
nx.draw(nx.complement(g), with_labels=True)
#+RESULTS[dac7ea45379cb9e5d94906e8ae5b91fdc695b488]:
c_v = find_special_cutpoint(g)
c_v
kg = k(g)
kg.order()
#+RESULTS[754a3660756ecbe6438f4931bf8d4ec945f79778]:
30
%time homotopy_type(kg)
nx.draw(nx.complement(kg))
#+RESULTS[470f322eec84af19d6222d75f97f716fea377d82]:
h_type_by_special_neigh(kg)
#+RESULTS[00fb8862b3e6559e2fba69866ba0d0dacafae2cc]:
False
h_type_using_star_cluster(kg)
#+RESULTS[12c9449c65728141c6f781e6b24de3cf1404c79b]:
\(\vee_{52}S^{3}\)
h_graph = g.subgraph(set(g.nodes())-{1})
kh = k(h_graph)
nx.draw(kh, with_labels=True)
#+RESULTS[325f36810743b4ef7707871af1faee9920f2eabb]:
homotopy_type(kh)
graph = kh
neighs = [(i, open_neighborhood(graph, i)) for i in graph.nodes()]
filt = [v for (v, nei) in neighs if is_disjoint_union_of_two_completes(nei)]
filt
#+RESULTS[521d754155f212e59d766c6319de8d8b1b010c77]:
[{8, 0}, {8, 2}, {8, 4}, {9, 4}, {0, 6}, {3, 6}, {0, 5, 7}]
u = Clique({0,8})
nx.draw(open_neighborhood(kh, u), with_labels=True)
#+RESULTS[d996ce5be6c616f677db37342d2a53d3b53bb223]:
h2_graph = kh.subgraph(set(kh.nodes())-{u})
nx.draw(h2_graph, with_labels=True)
graph = h2_graph
neighs = [(i, open_neighborhood(graph, i)) for i in graph.nodes()]
filt = [v for (v, nei) in neighs if is_disjoint_union_of_two_completes(nei)]
filt
#+RESULTS[87516e6e3648e73be1d93b3fe92ff481c6e0307b]:
[{8, 2}, {8, 4}, {9, 4}, {0, 6}, {3, 6}, {0, 5, 7}]
h3_graph = h2_graph.subgraph(set(h2_graph.nodes())-{Clique({8,2})})
nx.draw(h3_graph, with_labels=True)
#+RESULTS[b2225d4b30fc89dd9e10610d55455068c688f509]:
homotopy_type(h3_graph)
graph = h3_graph
neighs = [(i, open_neighborhood(graph, i)) for i in graph.nodes()]
filt = [v for (v, nei) in neighs if is_disjoint_union_of_two_completes(nei)]
filt
#+RESULTS[ba0fb0472e819f745bc112e4ad199192afdc6941]:
[{9, 4}, {0, 6}, {3, 6}, {0, 5, 7}]
read_betti_numbers([])
#+RESULTS[d8661ff22f52f9d57de1e50dc9b19f3636a8c4b2]:
Contractible
import mogutda
a=mogutda�[0m�[0;34m.�[0m�[0mSimplicialComplex�[0m�[0;34m(�[0m�[0msimplices�[0m�[0;34m=�[0m�[0m[])�[0m�[0;34m�[0m�[0;34m�[0m�[0m
#+RESULTS[ef76ade66dba9a4068d43683aac748ef4f6667bb]:
�[0;36m File �[0;32m"<ipython-input-35-6aae8895981f>"�[0;36m, line �[0;32m2�[0m �[0;31m a=mogutda�[0m�[0;34m.�[0m�[0mSimplicialComplex�[0m�[0;34m(�[0m�[0msimplices�[0m�[0;34m=�[0m�[0m[])�[0m�[0;34m�[0m�[0;34m�[0m�[0m�[0m �[0m ^�[0m �[0;31mSyntaxError�[0m�[0;31m:�[0m invalid syntax
g = graphs[41365]
nx.draw(g, with_labels=True)
#+RESULTS[7de4a73e73da4ead6e75ff6ab3fe8ec5172e9610]:
homotopy_type(g)
#+RESULTS[0a65031658d1b0a0ed4adf3237d00928c254e21c]:
\(\vee_{2}S^{1}\vee \vee_{2}S^{2}\)
kg = p(k(g))
kg.order()
#+RESULTS[77f867acb9b7426eb13c0ac87a7435acaa671ec3]:
18
betti_numbers(nx.convert_node_labels_to_integers(kg))
#+RESULTS[a1726846ab78a7166ec8e225d9374c322c6026c3]:
[0, 2, 0, 4]
c_v = find_special_cutpoint(g)
c_v
#+RESULTS[24c2d7d850014e31f9d7ca5b2c692f5dc5bc85ec]:
2
h_graph = g.subgraph(set(g.nodes())-{2})
kh = k(h_graph)
nx.draw(kh, with_labels=True)
#+RESULTS[f8f934337464729db2bbe040c8cbabfa57d7e987]:
graph = kh
neighs = [(i, open_neighborhood(graph, i)) for i in graph.nodes()]
filt = [v for (v, nei) in neighs if is_disjoint_union_of_two_completes(nei)]
filt
#+RESULTS[1c333d02cb5f4160999d7e525a48af2249087cea]:
[{0, 5}, {1, 5}]
h_type_by_special_neigh(kh)
#+RESULTS[c8bee3eb674935693937ec6c7532056381cba15e]:
\(S^{1}\vee \vee_{4}S^{3}\)
homotopy_type(kh)
#+RESULTS[521d754155f212e59d766c6319de8d8b1b010c77]:
\(S^{1}\vee \vee_{4}S^{3}\)
u = Clique({1,5})
nx.draw(open_neighborhood(kh, u), with_labels=True)
#+RESULTS[876b5d3b9083835dac2061923d5f97e8765dda32]:
is_disjoint_union_of_two_completes(open_neighborhood(kh,u))
#+RESULTS[7f32d6ad26df662b69aaa4454e74a3479a9d9643]:
False
homotopy_type(kh)
h_type_by_special_neigh(kh)
h2_graph = kh.subgraph(set(kh.nodes())-{u})
nx.draw(h2_graph, with_labels=True)
%time homotopy_type(h2_graph)
h_type_as_join_complement(kh)
#+RESULTS[21561281749cef2e2fdf0dd427553c1d2197a8c1]:
False
nx.draw(nx.complement(kh), with_labels=True)
#+RESULTS[d4983db439c31e201bf3d28762a2e4fcbcbe5269]:
h_type_using_star_cluster(kh)
#+RESULTS[70930637f383572927f9c6768ba6859ca2f9ff2e]:
False
h_type_by_special_neigh(kh)
#+RESULTS[c8bee3eb674935693937ec6c7532056381cba15e]:
False
g = graphs[41377]
nx.draw(g, with_labels=True)
homotopy_type(g)
#+RESULTS[0a65031658d1b0a0ed4adf3237d00928c254e21c]:
\(\vee_{2}S^{1}\vee \vee_{3}S^{2}\)
kg = p(k(g))
kg.order()
betti_numbers(nx.convert_node_labels_to_integers(kg))
homotopy_type(kg)
c_v = find_special_cutpoint(g)
c_v
h_graph = g.subgraph(set(g.nodes())-{2})
kh = k(h_graph)
nx.draw(kh, with_labels=True)
#+RESULTS[f8f934337464729db2bbe040c8cbabfa57d7e987]:
h_type_by_special_neigh(kh)
#+RESULTS[c8bee3eb674935693937ec6c7532056381cba15e]:
\(S^{1}\vee \vee_{9}S^{3}\)
u = Clique({1,5})
nx.draw(open_neighborhood(kh, u), with_labels=True)
#+RESULTS[ca5d9f7cb8dc4335a82e6d964885caacddedb3b4]:
h2_graph = kh.subgraph(set(kh.nodes())-{u})
nx.draw(h2_graph, with_labels=True)
#+RESULTS[b39777b6557dfe4e1e96de21cfb3f105b7e13328]:
%time homotopy_type(h2_graph)
#+RESULTS[edbe8985a6f591376e308ae1329b1dfc0765eb54]:
CPU times: user 42.8 ms, sys: 1.2 ms, total: 44 ms
Wall time: 42.8 ms
\(\vee_{9}S^{3}\)
g = graphs[41849]
nx.draw(g, with_labels=True)
#+RESULTS[114c0130d1799715370a5ba666c51ac7db5945bb]:
homotopy_type(g)
kg = p(k(g))
kg.order()
betti_numbers(nx.convert_node_labels_to_integers(kg))
c_v = find_special_cutpoint(g)
c_v
h_graph = g.subgraph(set(g.nodes())-{2})
kh = k(h_graph)
nx.draw(kh, with_labels=True)
u = Clique({0,5})
nx.draw(open_neighborhood(kh, u), with_labels=True)
#+RESULTS[247dba5f577c31a121a13b09f333c72e3e683776]:
h2_graph = kh.subgraph(set(kh.nodes())-{u})
nx.draw(h2_graph, with_labels=True)
%time homotopy_type(h2_graph)
g = graphs[49151]
nx.draw(g, with_labels=True)
#+RESULTS[ea9a05ee4da9383582111ca901061ab4679868a0]:
homotopy_type(g)
kg = p(k(g))
kg.order()
#+RESULTS[77f867acb9b7426eb13c0ac87a7435acaa671ec3]:
20
betti_numbers(nx.convert_node_labels_to_integers(kg))
#+RESULTS[a1726846ab78a7166ec8e225d9374c322c6026c3]:
[0, 2, 0, 7]
c_v = find_special_cutpoint(g)
c_v
h_graph = g.subgraph(set(g.nodes())-{3})
kh = k(h_graph)
nx.draw(kh, with_labels=True)
#+RESULTS[05a3ccf8359f7db8d093128b9d7972eb444ae21d]:
homotopy_type(kh)
#+RESULTS[521d754155f212e59d766c6319de8d8b1b010c77]:
\(S^{1}\vee \vee_{7}S^{3}\)
u = Clique({4,9})
nx.draw(open_neighborhood(kh, u), with_labels=True)
#+RESULTS[00371e6158d8ea50bd27f01bf714950dfd3951bd]:
h2_graph = kh.subgraph(set(kh.nodes())-{u})
nx.draw(h2_graph, with_labels=True)
%time homotopy_type(h2_graph)
#+RESULTS[edbe8985a6f591376e308ae1329b1dfc0765eb54]:
CPU times: user 46.3 ms, sys: 1.66 ms, total: 47.9 ms
Wall time: 46.7 ms
\(\vee_{9}S^{3}\)
graphs = nx.read_graph6("./data/graph10c035.g6")
len(graphs)
#+RESULTS[f7e4b70a6afee285c68b37799a88d28b91ddafc0]:
100000
g = graphs[82636]
nx.draw(g, with_labels=True)
#+RESULTS[8c5876fb2bd28ece850123d6ef1da730507fd1a7]:
homotopy_type(g)
kg = k(g)
kg.order()
homotopy_type(kg)
#+RESULTS[fbf2f7611a53e0e90798d306174f418b8531b3e5]:
\(\vee_{5}S^{1}\)
is_clique_helly(g)
#+RESULTS[25b59f4fd4275efb7ff1f1ec2c69970b8208da7e]:
True
graphs = nx.read_graph6("./data/graph10c055.g6")
len(graphs)
#+RESULTS[edb186c4eabe11e1f58844a4469f85f52950883d]:
100000
g = graphs[72330]
nx.draw(g, with_labels=True)
#+RESULTS[e72df4edfa21b46a6ab928aeea05f4762cdce169]:
homotopy_type(g)
nx.draw(nx.complement(g), with_labels=True)
kg = k(g)
kg.order()
#+RESULTS[59755e62105ba8e6b8505f94d21109ffd85c24ba]:
20
homotopy_type(kg)
#+RESULTS[fbf2f7611a53e0e90798d306174f418b8531b3e5]:
\(S^{1}\vee S^{2}\vee \vee_{2}S^{3}\)
betti_numbers(nx.convert_node_labels_to_integers(kg))
#+RESULTS[a1726846ab78a7166ec8e225d9374c322c6026c3]:
[0, 1, 1, 2]
c_v = find_special_cutpoint(g)
c_v
h_graph = g.subgraph(set(g.nodes())-{4})
kh = k(h_graph)
nx.draw(kh, with_labels=True)
#+RESULTS[70337cca21e6712f81f58f4264369dcba88157f5]:
h_type_by_special_neigh(kh)
betti_numbers(nx.convert_node_labels_to_integers(kh))
#+RESULTS[61b3999f0ae5711d79ca68d0a8e273d86e789fa4]:
[0, 0, 1, 2]
nx.draw(nx.complement(kh), with_labels=True)
#+RESULTS[d4983db439c31e201bf3d28762a2e4fcbcbe5269]:
graph=kh
graph = nx.convert_node_labels_to_integers(graph)
c_graph = nx.complement(graph)
verts = [i for i in c_graph.nodes() if open_neighborhood(c_graph, i).size() == 0]
verts
#+RESULTS[a4738238725b540172f856c4ef826f1c88324cd3]:
[0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16, 17]
vertex=0
IG = clique_complex(graph)
ST = star(IG, vertex)
SC = star_cluster(IG, c_graph[vertex])
ST, SC
int_c = intersection_complex(ST, SC)
int_c
csc = collapse(int_c)
csc
%time is_vertex_decomposable(csc)
#+RESULTS[b84eba05557e3a724a3d80c738f2bf53e2c72f1c]:
CPU times: user 820 ms, sys: 0 ns, total: 820 ms Wall time: 818 ms False
betti_numbers_c(csc)
#+RESULTS[ee4037d4f65fb31beb9a5c1c562d899123df3c1d]:
[0, 1, 2]
csc2 = csc.deletion(11)
csc2
is_vertex_decomposable(csc2)
csc2.dong_matching()
#+RESULTS[5a4b0c3d236b7952ba5cba5d513de5fa64c45888]:
{{8, 6, 7}, {9, 10, 12}}
g = graphs[72516]
nx.draw(g, with_labels=True)
homotopy_type(g)
#+RESULTS[0a65031658d1b0a0ed4adf3237d00928c254e21c]:
\(\vee_{4}S^{2}\)
nx.draw(nx.complement(g), with_labels=True)
graphs = nx.read_graph6("./data/graph10c065.g6")
len(graphs)
#+RESULTS[e33780d824681eaf8318bfdc5a9b028a9bd4b977]:
100000
g = graphs[85534]
nx.draw(g, with_labels=True)
homotopy_type(g)
#+RESULTS[0a65031658d1b0a0ed4adf3237d00928c254e21c]:
\(\vee_{3}S^{2}\)
nx.draw(nx.complement(g), with_labels=True)
kg = k(g)
kg.order()
%time homotopy_type(kg)
#+RESULTS[f1dadd0ddfb692dd1fb30b5c00423eba6e177baf]:
CPU times: user 3min 50s, sys: 12.7 ms, total: 3min 50s
Wall time: 3min 50s
\(S^{2}\vee \vee_{2}S^{3}\)
c_v = find_special_cutpoint(g)
c_v
nx.draw(nx.complement(kg), with_labels=True)
#+RESULTS[e2e989d14cf8f110ee33a8a52036b6f910f71f10]:
graph = kg
graph = nx.convert_node_labels_to_integers(graph)
c_graph = nx.complement(graph)
verts = [i for i in c_graph.nodes() if open_neighborhood(c_graph, i).size() == 0]
verts
#+RESULTS[b1813d3ca52e93bf6fd1477d7e900a1fd5867203]:
[6, 19]
vertex = verts[0]
IG = clique_complex(graph)
ST = star(IG, vertex)
SC = star_cluster(IG, c_graph[vertex])
int_c = intersection_complex(ST, SC)
csc = collapse(int_c)
csc
#+RESULTS[97f86fd2577bfb1d192e30a1d45ca10375913cb7]:
Simplicial complex with vertex_set {0, 1, 2, 3, 4, 5, 7, 8, 11, 12, 16, 17, 18, 19} and facets {{8, 2, 11}, {0, 17, 4}, {16, 11}, {0, 17, 5}, {8, 1, 2}, {1, 2, 3}, {2, 3, 7}, {1, 18, 4}, {8, 11, 12}, {11, 12, 7}, {0, 1, 4}, {17, 18, 4}, {8, 3, 12}, {19, 4}, {8, 1, 3}, {17, 18, 5}, {1, 18, 5}, {16, 19}, {3, 12, 7}, {0, 1, 5}, {2, 11, 7}}.
csc2 = csc.deletion(19)
csc2.dong_matching()
#+RESULTS[528a6511520c44a6868dddc96f4415fc0c2e3876]:
{{17, 18, 5}, {8, 11, 12}}
graphs = nx.read_graph6("./data/graph10c066.g6")
len(graphs)
#+RESULTS[76d537c8cfea619e648bd1c0ce45c60cc2af6517]:
100000
g = graphs[399]
nx.draw(g, with_labels=True)
#+RESULTS[37ce8f7a5a6b00e949a7a375dd3da6ebca03c934]:
homotopy_type(g)
#+RESULTS[0a65031658d1b0a0ed4adf3237d00928c254e21c]:
\(\vee_{3}S^{2}\)
kg = k(g)
kg.order(), kg.size()
pkg = p(kg)
pkg.order()
#+RESULTS[dcac00d60f7289f5fbaf68de70876427a1732889]:
20
nx.draw(nx.complement(g), with_labels=True)
graph = kg
graph = nx.convert_node_labels_to_integers(graph)
c_graph = nx.complement(graph)
verts = [i for i in c_graph.nodes() if open_neighborhood(c_graph, i).size() == 0]
verts
ckg = nx.convert_node_labels_to_integers(kg)
ckg = simplify_ht(ckg)
ckg.order(), ckg.size()
graph = ckg
graph = nx.convert_node_labels_to_integers(graph)
c_graph = nx.complement(graph)
verts = [i for i in c_graph.nodes() if open_neighborhood(c_graph, i).size() == 0]
verts
#+RESULTS[c8c6a0eda89cba81d362b5cadbab1bf338e54fae]:
[]
nx.draw(ckg)
#+RESULTS[bb450c62797435e966a00375aa7041d2bbcfa6ff]:
h_type_by_special_edges(kg)
#+RESULTS[e784e0b574945ef52532cdfc67ad30d378af372f]:
False
nx.draw(nx.complement(ckg))
#+RESULTS[b212c3a4ff89ab1ad1c5877a0a813a07603f565b]:
h_type_by_special_neigh(kg)
#+RESULTS[00fb8862b3e6559e2fba69866ba0d0dacafae2cc]:
False
h_type_by_special_neigh(ckg)
#+RESULTS[b01403a6f89ed897c31677a788f4afd6b22dd8d1]:
False
clique_complex(ckg).dong_matching()
#+RESULTS[7872d9fdf3083e58f8c5af4a6e162341421db55a]:
| 16 | 17 | 18 | 19 |
| 16 | 18 | 12 | 13 |
| 8 | 13 | 15 | |
| 16 | 17 | 19 | 14 |
| 16 | 17 | 18 | 11 |
is_vertex_decomposable(clique_complex(ckg))
#+RESULTS[ca4d14e1e91a13e5f2d5919bf3ae79b6d7e8d5f2]:
True
betti_numbers(ckg)
#+RESULTS[71850be91e56462762c64db3e0dee04891590581]:
| 0 | 0 | 1 | 4 |
g = graphs[27381]
nx.draw(g, with_labels=True)
#+RESULTS[324f283630eda193461afcd4f9f088862005fd88]:
plot_neighborhoods(g)
#+RESULTS[243ffa5633f36445681fa803d39a9bec9dbbe20d]:
nx.draw(nx.complement(g), with_labels=True)
#+RESULTS[dac7ea45379cb9e5d94906e8ae5b91fdc695b488]:
homotopy_type(g)
kg = k(g)
kg.order(), kg.size()
#+RESULTS[6b5d363ef99d596b2eb54409586f787e392b1c2a]:
(21, 142)
nx.draw(kg, with_labels=True)
#+RESULTS[6e26723d9a6fb88c3c21e0ed06083e108594e11a]:
graph = kg
graph = nx.convert_node_labels_to_integers(graph)
c_graph = nx.complement(graph)
verts = [i for i in c_graph.nodes() if open_neighborhood(c_graph, i).size() == 0]
verts
h_type_using_star_cluster(kg)
#+RESULTS[12c9449c65728141c6f781e6b24de3cf1404c79b]:
\(S^{2}\vee \vee_{2}S^{3}\)
homotopy_type(kg)
ckg = nx.convert_node_labels_to_integers(kg)
ckg = simplify_ht(ckg)
ckg.order(), ckg.size()
#+RESULTS[5a1911e0998e998bb6f2060ae6b855b2a27cfae8]:
(17, 58)
nx.draw(ckg, with_labels=True)
#+RESULTS[c911913d8c5e512f8c50308fdf534b10a01a4b46]:
h_type_by_cutpoints(ckg)
#+RESULTS[0ca15b6e2686985da438d1b69864a417e00d41e3]:
\(S^{2}\vee S^{3}\)
find_cutpoints(ckg)
#+RESULTS[c4c26a5938a0c36e5aabf5d678a1c8e2e24e0bea]:
| 5 |
vertex = 5
graph = ckg
c_graph = graph.copy()
c_graph.remove_node(vertex)
comps = [c.union({vertex}) for c in nx.connected_components(c_graph)]
comps
#+RESULTS[f6f81d1f8046a7a517a8aaabd43882bf566f2a61]:
[{0, 1, 4, 5, 12, 13, 16, 17}, {5, 6, 7, 11, 14, 15, 18}]
nx.draw(ckg, with_labels=True)
#+RESULTS[c911913d8c5e512f8c50308fdf534b10a01a4b46]:
nx.draw(nx.complement(kg), with_labels=True)
c_v = find_special_cutpoint(g)
c_v
graph = kg
graph = nx.convert_node_labels_to_integers(graph)
c_graph = nx.complement(graph)
verts = [i for i in c_graph.nodes() if open_neighborhood(c_graph, i).size() == 0]
verts
h_type_using_star_cluster(kg)
#+RESULTS[12c9449c65728141c6f781e6b24de3cf1404c79b]:
\(S^{2}\vee S^{3}\)
h_type_by_special_neigh(kg)
#+RESULTS[00fb8862b3e6559e2fba69866ba0d0dacafae2cc]:
False
betti_numbers(nx.convert_node_labels_to_integers(kg))
#+RESULTS[a1726846ab78a7166ec8e225d9374c322c6026c3]:
[0, 1, 0, 2]
plot_neighborhoods(nx.convert_node_labels_to_integers(kg))
#+RESULTS[d8015d41c502990d614a67f19e60a361daa0de34]:
kg.order(), kg.size()
#+RESULTS[13e30c4e91fe1289132d1811993158267f59294f]:
(18, 101)
ckg = nx.convert_node_labels_to_integers(kg)
ckg = simplify_ht(ckg)
ckg.order(), ckg.size()
#+RESULTS[5a1911e0998e998bb6f2060ae6b855b2a27cfae8]:
(18, 60)
plot_neighborhoods(nx.convert_node_labels_to_integers(ckg))
#+RESULTS[bf9a6cf863135c8f6c0cc5c7a9502210b8c67241]:
h_type_using_star_cluster(ckg)
#+RESULTS[d4ddca658c347c9173216d66679f2e72a04c39ea]:
False
graph = ckg
graph = nx.convert_node_labels_to_integers(graph)
c_graph = nx.complement(graph)
verts = [i for i in c_graph.nodes() if open_neighborhood(c_graph, i).size() == 0]
verts
#+RESULTS[c8c6a0eda89cba81d362b5cadbab1bf338e54fae]:
[]
h_type_by_special_neigh(ckg)
#+RESULTS[b01403a6f89ed897c31677a788f4afd6b22dd8d1]:
False
nx.draw(open_neighborhood(ckg, 15), with_labels=True)
#+RESULTS[987da8d2145fd6c99c27a357e0368eba7e27135b]:
cs = collapse(clique_complex(ckg))
cs
cs.is_clique_complex()
#+RESULTS[14cf65f0a20cabeaa2cc6aac59fb3d105ce2c735]:
True
nx.is_isomorphic(cs.one_skeleton_graph(), ckg)
#+RESULTS[8dea93180d5e64ac928ff4190877b9e000e3fe43]:
True
nx.draw(ckg, with_labels=True)
#+RESULTS[c911913d8c5e512f8c50308fdf534b10a01a4b46]:
h_type_by_special_edges(ckg)
#+RESULTS[06675e1443ee3a3ebbb3d0c2c809d9b93e984a19]:
\(S^{1}\vee \vee_{2}S^{3}\)
[f for f in clique_complex(ckg).facet_set if len(f)==2]
#+RESULTS[7dc6088be2d4a86f8874e8971955b16816966a45]:
[{16, 17}, {13, 15}]
find_special_edges(ckg)
#+RESULTS[291f568263b38c7e90ea83483624d338c45cc126]:
[(13, 15), (16, 17)]
cckg = ckg.copy()
cckg.remove_edges_from([(13, 15), (16, 17)])
ckg.size(), cckg.size()
#+RESULTS[13afd6a96d6970d8fb1339d9d3f5f0231b595576]:
| 60 | 58 |
[cckg.subgraph(c) for c in nx.connected_components(cckg)]
#+RESULTS[31404cc8384d01f18ab51192f057ec0108ab92b7]:
[<networkx.classes.graph.Graph at 0x7f8f4878ed90>, <networkx.classes.graph.Graph at 0x7f8f41c19ee0>]
[{x} for x in ckg.nodes() if x not in {13,15,16,17}]
#+RESULTS[54c50ff0bbe561f746bd557b2e38ade189c87e73]:
[{0}, {1}, {2}, {3}, {4}, {5}, {6}, {7}, {8}, {9}, {10}, {11}, {12}, {14}]
partition = [{0}, {1}, {2}, {3}, {4}, {5}, {6}, {7}, {8}, {9}, {10}, {11}, {12}, {14}]+[{16, 17}, {13, 15}]
ckgq = nx.quotient_graph(ckg, partition, relabel=True)
nx.draw(ckgq, with_labels=True)
#+RESULTS[f97239c6dc749358930ebe28c3f0d55c7a184d81]:
homotopy_type(ckgq)
cskg = collapse(clique_complex(kg))
cskg.is_clique_complex()
#+RESULTS[a1c3b81a4d1ebbb26e1bc1997fe833f6c98cfd25]:
False
[f for f in cskg.facet_set if len(f)==2]
#+RESULTS[8075a9d673ade061aea0fa94efdcf1ff200dac61]:
[{{2, 5, 7}, {0, 4, 7}}, {{2, 5, 7}, {9, 3, 5}}]
homotopy_type(ckg)
#+RESULTS[469096a8f96d9a744cf894a2ca26df77d71ca87a]:
\(S^{2}\vee \vee_{4}S^{3}\)
nx.draw(nx.complement(ckg), with_labels=True)
#+RESULTS[e4201da8efe32ae30c03157741bf4a6c602637a6]:
g = graphs[28002]
nx.draw(g, with_labels=True)
#+RESULTS[6ffa63970d42ed9bafd209664f26977588bc38a1]:
plot_neighborhoods(g)
#+RESULTS[243ffa5633f36445681fa803d39a9bec9dbbe20d]:
kg = k(g)
kg.order(), kg.size()
#+RESULTS[6b5d363ef99d596b2eb54409586f787e392b1c2a]:
(23, 169)
kg = p(kg)
kg.order(), kg.size()
#+RESULTS[29423a14fb712e2122d5f94a72255f2792500836]:
| 23 | 169 |
ckg = nx.convert_node_labels_to_integers(kg)
ckg = simplify_ht(ckg)
ckg.order(), ckg.size()
nx.draw(nx.complement(g), with_labels=True)
#+RESULTS[dac7ea45379cb9e5d94906e8ae5b91fdc695b488]:
homotopy_type(g)
nx.draw(kg, with_labels=True)
#+RESULTS[6e26723d9a6fb88c3c21e0ed06083e108594e11a]:
nx.draw(ckg, with_labels=True)
#+RESULTS[c911913d8c5e512f8c50308fdf534b10a01a4b46]:
plot_neighborhoods(ckg)
#+RESULTS[9df4019ef47d047156d11366e8f427095fbd12e2]:
�[0;31m�[0m
�[0;31mKeyError�[0mTraceback (most recent call last)
�[0;32m<ipython-input-23-652907fca1d3>�[0m in �[0;36m<module>�[0;34m�[0m
�[0;32m----> 1�[0;31m �[0mplot_neighborhoods�[0m�[0;34m(�[0m�[0mckg�[0m�[0;34m)�[0m�[0;34m�[0m�[0;34m�[0m�[0m
�[0m
�[0;32m<ipython-input-2-f037bb5bfcab>�[0m in �[0;36mplot_neighborhoods�[0;34m(g)�[0m
�[1;32m 28�[0m �[0mplt�[0m�[0;34m.�[0m�[0msubplot�[0m�[0;34m(�[0m�[0mrows�[0m�[0;34m,�[0m �[0mcolumns�[0m�[0;34m,�[0m �[0mi�[0m�[0;34m+�[0m�[0;36m1�[0m�[0;34m)�[0m�[0;34m�[0m�[0;34m�[0m�[0m
�[1;32m 29�[0m �[0mplt�[0m�[0;34m.�[0m�[0mtitle�[0m�[0;34m(�[0m�[0mi�[0m�[0;34m)�[0m�[0;34m�[0m�[0;34m�[0m�[0m
�[0;32m---> 30�[0;31m �[0mnx�[0m�[0;34m.�[0m�[0mdraw�[0m�[0;34m(�[0m�[0mopen_neighborhood�[0m�[0;34m(�[0m�[0mg�[0m�[0;34m,�[0m �[0mi�[0m�[0;34m)�[0m�[0;34m,�[0m �[0mnode_size�[0m�[0;34m=�[0m�[0;36m200�[0m�[0;34m,�[0m �[0mwith_labels�[0m�[0;34m=�[0m�[0;34m'True'�[0m�[0;34m)�[0m�[0;34m�[0m�[0;34m�[0m�[0m
�[0m�[1;32m 31�[0m �[0mplt�[0m�[0;34m.�[0m�[0mshow�[0m�[0;34m(�[0m�[0;34m)�[0m�[0;34m�[0m�[0;34m�[0m�[0m
�[0;32m~/Python/pycliques-dev/pycliques/src/pycliques/surfaces.py�[0m in �[0;36mopen_neighborhood�[0;34m(graph, v)�[0m
�[1;32m 21�[0m �[0;32mdef�[0m �[0mopen_neighborhood�[0m�[0;34m(�[0m�[0mgraph�[0m�[0;34m,�[0m �[0mv�[0m�[0;34m)�[0m�[0;34m:�[0m�[0;34m�[0m�[0;34m�[0m�[0m
�[1;32m 22�[0m �[0;34m"""Return a copy(), otherwise the subgraph is frozen."""�[0m�[0;34m�[0m�[0;34m�[0m�[0m
�[0;32m---> 23�[0;31m �[0;32mreturn�[0m �[0mgraph�[0m�[0;34m.�[0m�[0msubgraph�[0m�[0;34m(�[0m�[0mgraph�[0m�[0;34m[�[0m�[0mv�[0m�[0;34m]�[0m�[0;34m)�[0m�[0;34m.�[0m�[0mcopy�[0m�[0;34m(�[0m�[0;34m)�[0m�[0;34m�[0m�[0;34m�[0m�[0m
�[0m�[1;32m 24�[0m �[0;34m�[0m�[0m
�[1;32m 25�[0m �[0;34m�[0m�[0m
�[0;32m~/Python/pycliques-dev/lib/python3.9/site-packages/networkx/classes/graph.py�[0m in �[0;36m__getitem__�[0;34m(self, n)�[0m
�[1;32m 511�[0m �[0mAtlasView�[0m�[0;34m(�[0m�[0;34m{�[0m�[0;36m1�[0m�[0;34m:�[0m �[0;34m{�[0m�[0;34m}�[0m�[0;34m}�[0m�[0;34m)�[0m�[0;34m�[0m�[0;34m�[0m�[0m
�[1;32m 512�[0m """
�[0;32m--> 513�[0;31m �[0;32mreturn�[0m �[0mself�[0m�[0;34m.�[0m�[0madj�[0m�[0;34m[�[0m�[0mn�[0m�[0;34m]�[0m�[0;34m�[0m�[0;34m�[0m�[0m
�[0m�[1;32m 514�[0m �[0;34m�[0m�[0m
�[1;32m 515�[0m �[0;32mdef�[0m �[0madd_node�[0m�[0;34m(�[0m�[0mself�[0m�[0;34m,�[0m �[0mnode_for_adding�[0m�[0;34m,�[0m �[0;34m**�[0m�[0mattr�[0m�[0;34m)�[0m�[0;34m:�[0m�[0;34m�[0m�[0;34m�[0m�[0m
�[0;32m~/Python/pycliques-dev/lib/python3.9/site-packages/networkx/classes/coreviews.py�[0m in �[0;36m__getitem__�[0;34m(self, name)�[0m
�[1;32m 79�[0m �[0;34m�[0m�[0m
�[1;32m 80�[0m �[0;32mdef�[0m �[0m__getitem__�[0m�[0;34m(�[0m�[0mself�[0m�[0;34m,�[0m �[0mname�[0m�[0;34m)�[0m�[0;34m:�[0m�[0;34m�[0m�[0;34m�[0m�[0m
�[0;32m---> 81�[0;31m �[0;32mreturn�[0m �[0mAtlasView�[0m�[0;34m(�[0m�[0mself�[0m�[0;34m.�[0m�[0m_atlas�[0m�[0;34m[�[0m�[0mname�[0m�[0;34m]�[0m�[0;34m)�[0m�[0;34m�[0m�[0;34m�[0m�[0m
�[0m�[1;32m 82�[0m �[0;34m�[0m�[0m
�[1;32m 83�[0m �[0;32mdef�[0m �[0mcopy�[0m�[0;34m(�[0m�[0mself�[0m�[0;34m)�[0m�[0;34m:�[0m�[0;34m�[0m�[0;34m�[0m�[0m
�[0;31mKeyError�[0m: 6
c_v = find_special_cutpoint(g)
c_v
graph = kg
graph = nx.convert_node_labels_to_integers(graph)
c_graph = nx.complement(graph)
verts = [i for i in c_graph.nodes() if open_neighborhood(c_graph, i).size() == 0]
verts
h_type_using_star_cluster(kg)
graph = ckg
graph = nx.convert_node_labels_to_integers(graph)
c_graph = nx.complement(graph)
verts = [i for i in c_graph.nodes() if open_neighborhood(c_graph, i).size() == 0]
verts
#+RESULTS[c8c6a0eda89cba81d362b5cadbab1bf338e54fae]:
[]
list9 = list_graphs(9)
len(list9)
#+RESULTS[5fcb20c913b13f6a4ccf07bdc6cfd06d773f581d]:
261080
g = list9[249562]
nx.draw(g, with_labels=True)
#+RESULTS[6d901e94c46f1c3c64bf02d14fe1d9895007c9d8]:
nx.draw(g.subgraph(set(g.nodes())-{5}))
#+RESULTS[2bc4e7e8038cc51b07b5fc445cfa400b11e9013b]:
homotopy_type(g)
#+RESULTS[0a65031658d1b0a0ed4adf3237d00928c254e21c]:
\(S^{1}\)
kg = p(k(g))
homotopy_type(kg), kg.order()
#+RESULTS[075292cec2b78ad443b0b7c282cb1130c6136186]:
| \(S1\) | 14 |
k2g = p(k(kg))
homotopy_type(k2g), k2g.order(), is_clique_helly(k2g)
#+RESULTS[d2490139a40c4720cad420c9c4689e7cbd3dfc83]:
| \(S1\) | 8 | False |
nx.draw(k2g)
#+RESULTS[937bef7f9f4460c9f004dc3f36fe7c9b168b4146]:
k3g = p(k(k2g))
homotopy_type(k3g), k3g.order(), is_clique_helly(k3g)
#+RESULTS[a51f2c803c85cfc51898b171df50e7ae67a29071]:
| \(S1\) | 9 | False |
k4g = p(k(k3g))
homotopy_type(k4g), k4g.order(), is_clique_helly(k4g)
#+RESULTS[c75ae1e2b13737a5d598340d8c91903d703d343d]:
| \(S1\) | 4 | True |
c_v = find_special_cutpoint(g)
c_v
#+RESULTS[24c2d7d850014e31f9d7ca5b2c692f5dc5bc85ec]:
2
h_type_clique_graph_cutpoint(g, 2)
#+RESULTS[23e4cb3ebb784e10881ff61fe2a7d20146f8911f]:
\(\vee_{2}S^{1}\vee S^{3}\)
betti_numbers(nx.convert_node_labels_to_integers(kg))
#+RESULTS[a1726846ab78a7166ec8e225d9374c322c6026c3]:
[0, 1, 0, 1]
h_graph = g.subgraph(set(g.nodes())-{2})
kh = k(h_graph)
k_h_type = homotopy_type(kh)
k_h_type
#+RESULTS[ac47b07def517291e505b48a7a57797ac8ae5843]:
Contractible
betti_numbers(nx.convert_node_labels_to_integers(kh))
#+RESULTS[61b3999f0ae5711d79ca68d0a8e273d86e789fa4]:
[]
h_type_as_join_complement(nx.convert_node_labels_to_integers(kh))
#+RESULTS[ae9dcf45ad337a6a8ad81a055168520e557f5f16]:
Contractible
nx.draw(kh, with_labels=True)
#+RESULTS[c66c52dc1ed2fad241175524dc1374ac4dad7d41]:
nx.draw(nx.complement(kh), with_labels=True)
#+RESULTS[d4983db439c31e201bf3d28762a2e4fcbcbe5269]:
h_type_using_star_cluster(kg)
#+RESULTS[12c9449c65728141c6f781e6b24de3cf1404c79b]:
False
h_type_by_special_neigh(kh)
#+RESULTS[c8bee3eb674935693937ec6c7532056381cba15e]:
\(\vee_{3}S^{1}\)
nx.draw(kh, with_labels=True)
#+RESULTS[c66c52dc1ed2fad241175524dc1374ac4dad7d41]:
graph = kh
neighs = [(i, open_neighborhood(graph, i)) for i in graph.nodes()]
twok2 = nx.disjoint_union(nx.complete_graph(2), nx.complete_graph(2))
filt = [v for (v, nei) in neighs if nx.is_isomorphic(nei, twok2)]
filt
#+RESULTS[9526e0823409b91d986dc77976a2f589227fcab9]:
[{1, 6}, {3, 6}, {3, 7}]
v = filt[0]
h = graph.subgraph(set(graph.nodes())-{v})
h_type = homotopy_type(nx.convert_node_labels_to_integers(h))
h_type
#+RESULTS[b64294d988d42382c6a374c55a36ca073fd3e014]:
\(\vee_{2}S^{1}\)
betti_numbers(nx.convert_node_labels_to_integers(kh))
#+RESULTS[61b3999f0ae5711d79ca68d0a8e273d86e789fa4]:
[0, 3]
g = list9[108411]
nx.draw(g, with_labels=True)
#+RESULTS[18d382bc4cf1edd5aa2a32aa68320fdec4eee8c7]:
homotopy_type(g)
#+RESULTS[0a65031658d1b0a0ed4adf3237d00928c254e21c]:
\(\vee_{3}S^{2}\)
kg = p(k(g))
kg.order(), kg.size(), max_degree(kg)
#+RESULTS[57955a49b6ee4ebea68a4c6ccf3c79f6c1cbdd32]:
| 18 | 113 | 13 |
nx.draw(kg, with_labels=True)
#+RESULTS[6e26723d9a6fb88c3c21e0ed06083e108594e11a]:
kg = nx.convert_node_labels_to_integers(kg)
htkg = simplify_ht(kg)
htkg.order(), htkg.size()
#+RESULTS[405081e8ac86a6d3e3f147f4715a9f6f9c74a8b1]:
| 17 | 56 |
betti_numbers(htkg)
#+RESULTS[54e8bfdf798dda4ac874ac5f53debac35856dd03]:
[0, 0, 1, 2]
ckg = collapse(clique_complex(kg))
#+RESULTS[0d89893ea531b8c2ad15a88a3fbf69648727f95e]:
is_vertex_decomposable(ckg)
#+RESULTS[4b598375fba5a9784878928a1e2360e1d99701a3]:
False
list9 = list_graphs(9)
len(list9)
#+RESULTS[5fcb20c913b13f6a4ccf07bdc6cfd06d773f581d]:
261080
g = list9[7459]
nx.draw(g, with_labels=True)
#+RESULTS[e4f7fa529ccd3da77116d6b5f9b5d8b32a5ee45b]:
kg = p(k(g))
kg.order()
#+RESULTS[77f867acb9b7426eb13c0ac87a7435acaa671ec3]:
13
kg = nx.convert_node_labels_to_integers(kg)
homotopy_type(kg)
#+RESULTS[38082e24b891549a88276b5ee49eaaa6b299c259]:
\(\vee_{6}S^{1}\)
homotopy_type(g)
#+RESULTS[0a65031658d1b0a0ed4adf3237d00928c254e21c]:
\(\vee_{6}S^{1}\)
c_v = find_special_cutpoint(g)
c_v
#+RESULTS[24c2d7d850014e31f9d7ca5b2c692f5dc5bc85ec]:
1
pg = p(g)
pg.order()
#+RESULTS[f20ada2e11f697c41c2a828788aeab057af58a84]:
9
h_type_clique_graph_cutpoint(g, 1)
h_graph = g.subgraph(set(g.nodes())-{1})
kh = k(h_graph)
k_h_type = homotopy_type(kh)
nx.draw(kh, with_labels=True)
#+RESULTS[c66c52dc1ed2fad241175524dc1374ac4dad7d41]:
h_type_as_join_complement(kh)
#+RESULTS[21561281749cef2e2fdf0dd427553c1d2197a8c1]:
False
h_type_using_star_cluster(kh)
#+RESULTS[70930637f383572927f9c6768ba6859ca2f9ff2e]:
False
h_type_by_special_neigh(kh)
graph = kh
neighs = [(i, open_neighborhood(graph, i)) for i in graph.nodes()]
twok2 = nx.disjoint_union(nx.complete_graph(2), nx.complete_graph(2))
filt = [v for (v, nei) in neighs if nx.is_isomorphic(nei, twok2)]
filt
#+RESULTS[9526e0823409b91d986dc77976a2f589227fcab9]:
[{2, 6}, {2, 7}]
v = filt[0]
sssh = graph.subgraph(set(graph.nodes())-{v})
h_type = homotopy_type(sssh)
nx.draw(sssh, with_labels=True)
#+RESULTS[aaea6a0e68f5015d91f9ad4eb66135d46e4a0146]:
simplify_ht(sssh)
sssh2 = nx.convert_node_labels_to_integers(sssh)
sssh2
#+RESULTS[0cc048c5882ceeed634d90f0355fa5b7a3d2182a]:
<networkx.classes.graph.Graph at 0x7f5d9ef7b8b0>
kh = nx.convert_node_labels_to_integers(simplify_ht(k(h_graph)))
h_type_by_special_neigh(kh)
#+RESULTS[7eff5ed4fbc7f01018b2eae26cff8aede4917234]:
False
kg = nx.convert_node_labels_to_integers(kg)
neighs = [(i, open_neighborhood(kg, i)) for i in kg.nodes()]
twok2 = nx.disjoint_union(nx.complete_graph(2), nx.complete_graph(2))
filt = [v for (v, nei) in neighs if nx.is_isomorphic(nei, twok2)]
filt
#+RESULTS[6a42c34782934efc116ec6942dbd4759b3e648f1]:
[{0, 4}]
h_type_by_special_neigh(kg)
#+RESULTS[474e4b17b8bc7d460a354b7f0b629dec9991b0f5]:
'\\(S^{1}\\vee \\vee_{4}S^{3}\\)'
kg = nx.convert_node_labels_to_integers(kg)
c_graph = nx.complement(kg)
verts = [i for i in c_graph.nodes() if open_neighborhood(c_graph, i).size() == 0]
vertex=verts[0]
vertex
IG = clique_complex(kg)
ST = star(IG, vertex)
SC = star_cluster(IG, c_graph[vertex])
ST, SC
int_c = intersection_complex(ST, SC)
# int_c
csc=collapse(int_c)
# csc
# is_vertex_decomposable(csc)
h_type_using_star_cluster(kg)
#+RESULTS[8e939360396fc0663174744be3f773cfe386ef1b]:
'\\(S^{2}\\vee \\vee_{2}S^{3}\\)'
nx.draw(nx.complement(g))
#+RESULTS[02415e765b1122b92970a6cb9d8c4401d94c4620]:
%time h_type_as_suspension(g)
#+RESULTS[be617beacdfedb29f6b9da189ad2a8b2095f7109]:
CPU times: user 1.11 ms, sys: 0 ns, total: 1.11 ms
Wall time: 1.12 ms
\(\vee_{2}S^{3}\)
%time homotopy_type(g)
#+RESULTS[fceb4189bcd4d03c2518884d2dfb1473f5e66e15]:
CPU times: user 4.46 ms, sys: 55 µs, total: 4.51 ms
Wall time: 4.24 ms
\(\vee_{2}S^{3}\)
cadena = _h_type_clique_graph_cutpoint(g, 1)
cadena
#+RESULTS[738c0982157bc007f36e5cea279358cf323d0a95]:
\(\vee_{2}S^{1}\vee S^{2}\)
kg = k(g)
homotopy_type(g), homotopy_type(kg)
#+RESULTS[4aadb372ceee352aae4282c4279f3d4381f3885d]:
| \(∨2S1∨ S2\) | \(∨2S1∨ S2\) |
kg = nx.convert_node_labels_to_integers(kg)
betti_numbers(g), betti_numbers(kg)
#+RESULTS[f973f29bc7434f6137d43a332f6a4a5712de80a1]:
([0, 2, 1], [0, 2, 1])
k2g = k(kg, 20)
k2g.order()
#+RESULTS[fbe8476bbe0cae7f0020d61846cc3222291bbeab]:
19
k2g = nx.convert_node_labels_to_integers(k2g)
betti_numbers(k2g)
#+RESULTS[d7d42f92aedd7bbcc745b235fe7409c016b441b2]:
[0, 2, 0, 1]
import re
pat = r"{(\d+)}"
m = re.sub(pat, r"{\1}", cadena)
m
#+RESULTS[d5a626e2b6a79c3e5b5802e753a173d15fd8e44b]:
\(S^{1}\vee \vee_{3}S^{1}\)
pat = r"\_\{\d+\}S\^\{1\}"
m = re.search(pat, cadena)
m.group(), m.span()
#+RESULTS[77cd1ecfd76d82e0c43687caa8be78ac86386448]:
('_{3}S^{1}', (16, 25))
pat = r"\_\{(\d+)\}S\^\{1\}"
m = re.search(pat, cadena)
m.group(), m.span(), m.group(1), m.span(1)
#+RESULTS[ec50a62e0bc24b23a920bc8e7c0f8af1c6615951]:
('_{3}S^{1}', (16, 25), '3', (18, 19))
cadena[18]
newcadena = cadena[:18]+str(int(cadena[18])+1)+cadena[19:]
newcadena
#+RESULTS[fcfc54654c0fb95d04ad19e1b8a6368464a0dada]:
\(S^{1}\vee \vee_{4}S^{1}\)
cadena[18]
newcadena = cadena[:18]+str(int(cadena[18])+1)+cadena[19:]
newcadena
inds = m.span(1)
cadena[inds[0]: inds[1]]
#+RESULTS[c92790e19bbdeb9f5ef1e670a14df572d62592e1]:
'3'
cadena2 = "\(S^{1}\vee \vee_{30}S^{1}\)"
pat = r"\_\{(\d+)\}S\^\{1\}"
m = re.search(pat, cadena2)
m.group(), m.span(), m.group(1), m.span(1)
#+RESULTS[efe15090529b7ccbfad9b5a183db2ba0cacd455e]:
('_{30}S^{1}', (14, 24), '30', (16, 18))
inds = m.span(1)
cadena2[inds[0]: inds[1]]
#+RESULTS[297445c3e0d02c0c0fb3dee438c923198381467a]:
'30'
g = list9[239843]
nx.draw(g, with_labels=True)
#+RESULTS[9157ca66c1e9f4e2bf517bc12ef853fe086b0c31]:
kg = p(k(g))
kg.order(), kg.size(), max_degree(kg)
#+RESULTS[57955a49b6ee4ebea68a4c6ccf3c79f6c1cbdd32]:
| 18 | 111 | 13 |
ckg = collapse(clique_complex(kg))
#+RESULTS[129f17f95c4298c72def41cf05d7d76b4b385a15]:
is_vertex_decomposable(ckg)
g = list9[22146]
nx.draw(g, with_labels=True)
#+RESULTS[37bd35a28940856dcdad7638e8e4c3da311a563f]:
_find_special_cutpoint(g)
#+RESULTS[86cd7bed40ae3e2a7434260f743dd37df5ecbba1]:
4
h = g.subgraph(set(g.nodes())-{4})
nx.draw(h, with_labels=True)
#+RESULTS[ee3e2d2bc7189d356616f2ef17f5c3f13f55c069]:
homotopy_type(h)
#+RESULTS[29fe9fe1f949efd0d2a664d08528a50c55e174d9]:
\(\vee_{3}S^{2}\)
kh = k(h)
nx.draw(kh, with_labels=True)
#+RESULTS[29cf14ac016877cfff7b226b8bdef6c3445a24ba]:
See Thesis of Andrés Carnero
import networkx as nx
g = nx.tensor_product(nx.cycle_graph(7), nx.complete_graph(3))
cg = nx.complement(g)
nx.draw(cg, with_labels=True)
#+RESULTS[31094c5b6f4b3728864e3c5d5c62ee3758c540fd]:
homotopy_type(cg)
#+RESULTS[badda7e2aa6c69094586ac638c3f071b41f4bccc]:
\(\vee_{14}S^{3}\)