Anonymous user
Talk:Graph colouring: Difference between revisions
→Any tougher problems?: Amazom0601
(→Any tougher problems?: Coloured in 114) |
(→Any tougher problems?: Amazom0601) |
||
Line 12:
:: 317,080 nodes and 1,049,866 edges in 114 colours according to the Python prog. --[[User:Paddy3118|Paddy3118]] ([[User talk:Paddy3118|talk]]) 10:00, 16 March 2020 (UTC)
:: [https://snap.stanford.edu/data/amazon0601.html amazon0601]: Directed 403,394 nodes, 3,387,388 edges read in. Needed 11 colours.<br>
::Reading the gzip file needed the following changes to the class:
:::<lang python>from gzip import open as gzopen
class Graph:
def __init__(self, fname, directed=False):
self.name = fname
g = self.graph = defaultdict(list) # maps vertex to direct connections
with (gzopen(fname, 'rt') if fname.endswith('.gz')
else open(fname)) as f:
edges = odd = 0
for n, line in enumerate(f, start=1):
ln = line.strip().split()
if ln[0].startswith('#'):
continue
if len(ln) != 2:
odd +=1
continue
n1, n2 = (int(x) for x in ln)
g[n1].append(n2)
if not directed:
g[n2].append(n1) # Each the neighbour of the other
edges += 1
print(f"FILE {fname}:\n #Nodes: {len(g)}\n #Edges: {edges}")
print(f" #(Lines): {n}")
print(f" #(Odd): {odd}\n")
...</lang>
::--[[User:Paddy3118|Paddy3118]] ([[User talk:Paddy3118|talk]]) 11:42, 16 March 2020 (UTC)
| |||