[Nauty-list] readgraph()

keith.briggs at bt.com keith.briggs at bt.com
Wed Feb 16 20:59:15 EST 2011


A much easier way to read graphs from geng than all that tricky C coding is this python function.   I've used it for years without problems.
It's not suitable for quick operations on a large number of graphs, but is fine for slow operations on a moderate number of graphs.   
It iterates over a dictionary representation of each graph (essentially a hash table with neighbour lists as values - see example below).
All your main python function has to do is

for graph in geng_iter(n):
   #  operate on graph ...

Keith

def geng_iter(n,connected=False):
  ' iterator over all graphs on n nodes, as dictionaries '
  import re
  from os import popen
  from sys import stderr,exit
  graph=re.compile(r'^Graph\s+(\d+),\s+order\s+(\d+).*?^(?P<n>\d+)\s+(?P<m>\d+).*?^(?P<edges>.*?)$',re.MULTILINE|re.DOTALL)
  edges=re.compile(r'(?P<u>\d+)\s+(?P<v>\d+)')
  f=popen('geng %s %d 2>/dev/null | showg -l0 -e'%(('','-c')[connected],n))
  o,s=f.read(),f.close()
  if s:
    print>>stderr,'geng_iter: geng failure'
    exit(3)
  for graph in graph.finditer(o):
    g=dict([(i,[]) for i in range(n)])
    n,m=int(graph.group('n')),int(graph.group('m'))
    for e in edges.finditer(graph.group('edges')):
      u,v=int(e.group('u')),int(e.group('v'))
      g[u].append(v)
      g[v].append(u)
    yield g


# example graph as dictionary:
      g={
        0:(1,),
        1:(0,2),
        2:(1,3,4),
        3:(2,),
        4:(2,),
      }

g[1] is (0,2) etc.

Dr. Keith M. Briggs http://keithbriggs.info
Senior Mathematician, Mobility, BT Innovate & Design.
Visiting Fellow, Linguistics, UWE.
phone: +44(0)1473 work: 641 911 home: 610 517 fax: 642 161
mail: Polaris 134, Adastral Park, Martlesham Heath, Suffolk IP5 3RE, UK
________________________________________
From: nauty-list-bounces at cs.anu.edu.au [nauty-list-bounces at cs.anu.edu.au] On Behalf Of William Rummler [w.a.rummler at gmail.com]
Sent: 15 February 2011 18:58
To: Susanne Niess
Cc: nauty-list at cs.anu.edu.au
Subject: Re: [Nauty-list] readgraph()

The easiest (and a very compact) way to save packed graphs is by
writing them to a file with writeg6(). They can then be loaded from
that file with opengraphfile() and, for each graph, readg(). Also, by
saving them this way, you can very easily use your file of saved
graphs with all of the gtools programs.

If you want a human-readable way to save them, I think I would still
recommend this approach but also mention that you can use the gtools
program listg on your saved file to view or convert the graphs in your
graph6 file to a human-readable format.

- William





More information about the Nauty mailing list