Talk:Graph colouring: Difference between revisions
Content deleted Content added
→Any tougher problems?: Amazom0601 |
|||
(One intermediate revision by the same user not shown) | |||
Line 10: | Line 10: | ||
:If you mean larger data sets you may take a look at [https://snap.stanford.edu/data/#socnets here], I haven't tried yet but did take a peek at one [https://snap.stanford.edu/data/bigdata/communities/com-dblp.ungraph.txt.gz sample] and it seems ready to be used. Hope this helps. --[[User:Hkdtam|Hkdtam]] ([[User talk:Hkdtam|talk]]) 03:39, 15 March 2020 (UTC) |
:If you mean larger data sets you may take a look at [https://snap.stanford.edu/data/#socnets here], I haven't tried yet but did take a peek at one [https://snap.stanford.edu/data/bigdata/communities/com-dblp.ungraph.txt.gz sample] and it seems ready to be used. Hope this helps. --[[User:Hkdtam|Hkdtam]] ([[User talk:Hkdtam|talk]]) 03:39, 15 March 2020 (UTC) |
||
::Hmm, 317,080 nodes and 1,049,866 edges (for the example you peeked at) is far more than I would ever have imagined... --[[User:Petelomax|Pete Lomax]] ([[User talk:Petelomax|talk]]) |
::Hmm, 317,080 nodes and 1,049,866 edges (for the example you peeked at) is far more than I would ever have imagined... --[[User:Petelomax|Pete Lomax]] ([[User talk:Petelomax|talk]]) |
||
:: 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) |
Latest revision as of 11:44, 16 March 2020
Thanks for open source
I am investigating a few graph algorithms hence this task. The ASCII diagrams of graphs came from this Perl CPAN module:
Graphviz doesn't do ASCII output so would be difficult to add its output to RC.
--Paddy3118 (talk) 20:31, 10 March 2020 (UTC)
Any tougher problems?
Are there any ready-made problems knocking about which might (frinst) give exhaustive search pause for thought? --Pete Lomax (talk) 22:37, 14 March 2020 (UTC)
- If you mean larger data sets you may take a look at here, I haven't tried yet but did take a peek at one sample and it seems ready to be used. Hope this helps. --Hkdtam (talk) 03:39, 15 March 2020 (UTC)
- Hmm, 317,080 nodes and 1,049,866 edges (for the example you peeked at) is far more than I would ever have imagined... --Pete Lomax (talk)
- amazon0601: Directed 403,394 nodes, 3,387,388 edges read in. Needed 11 colours.
- Reading the gzip file needed the following changes to the class:
- <lang python>from gzip import open as gzopen
- amazon0601: Directed 403,394 nodes, 3,387,388 edges read in. Needed 11 colours.
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>