Warning

This documents an unmaintained version of NetworkX. Please upgrade to a maintained version and see the current NetworkX documentation.

Source code for networkx.readwrite.graph6

"""Graph6

Read and write graphs in graph6 format.

Format
------

"graph6 and sparse6 are formats for storing undirected graphs in a
compact manner, using only printable ASCII characters. Files in these
formats have text type and contain one line per graph."

See http://cs.anu.edu.au/~bdm/data/formats.txt for details.
"""
# Original author: D. Eppstein, UC Irvine, August 12, 2003.
# The original code at http://www.ics.uci.edu/~eppstein/PADS/ is public domain.
#    Copyright (C) 2004-2013 by
#    Aric Hagberg <hagberg@lanl.gov>
#    Dan Schult <dschult@colgate.edu>
#    Pieter Swart <swart@lanl.gov>
#    Tomas Gavenciak <gavento@ucw.cz>
#    All rights reserved.
#    BSD license.
import networkx as nx
from networkx.exception import NetworkXError
from networkx.utils import open_file, not_implemented_for
__author__ = """\n""".join(['Tomas Gavenciak <gavento@ucw.cz>',
                            'Aric Hagberg <aric.hagberg@lanl.gov'])
__all__ = ['read_graph6', 'parse_graph6', 'generate_graph6', 'write_graph6']

[docs]def parse_graph6(string): """Read a simple undirected graph in graph6 format from string. Parameters ---------- string : string Data in graph6 format Returns ------- G : Graph Raises ------ NetworkXError If the string is unable to be parsed in graph6 format Examples -------- >>> G = nx.parse_graph6('A_') >>> sorted(G.edges()) [(0, 1)] See Also -------- generate_graph6, read_graph6, write_graph6 References ---------- Graph6 specification: http://cs.anu.edu.au/~bdm/data/formats.txt for details. """ def bits(): """Return sequence of individual bits from 6-bit-per-value list of data values.""" for d in data: for i in [5,4,3,2,1,0]: yield (d>>i)&1 if string.startswith('>>graph6<<'): string = string[10:] data = graph6_to_data(string) n, data = data_to_n(data) nd = (n*(n-1)//2 + 5) // 6 if len(data) != nd: raise NetworkXError(\ 'Expected %d bits but got %d in graph6' % (n*(n-1)//2, len(data)*6)) G=nx.Graph() G.add_nodes_from(range(n)) for (i,j),b in zip([(i,j) for j in range(1,n) for i in range(j)], bits()): if b: G.add_edge(i,j) return G
@open_file(0,mode='rt')
[docs]def read_graph6(path): """Read simple undirected graphs in graph6 format from path. Parameters ---------- path : file or string File or filename to write. Returns ------- G : Graph or list of Graphs If the file contains multiple lines then a list of graphs is returned Raises ------ NetworkXError If the string is unable to be parsed in graph6 format Examples -------- >>> nx.write_graph6(nx.Graph([(0,1)]), 'test.g6') >>> G = nx.read_graph6('test.g6') >>> sorted(G.edges()) [(0, 1)] See Also -------- generate_graph6, parse_graph6, write_graph6 References ---------- Graph6 specification: http://cs.anu.edu.au/~bdm/data/formats.txt for details. """ glist = [] for line in path: line = line.strip() if not len(line): continue glist.append(parse_graph6(line)) if len(glist) == 1: return glist[0] else: return glist
@not_implemented_for('directed','multigraph')
[docs]def generate_graph6(G, nodes = None, header=True): """Generate graph6 format string from a simple undirected graph. Parameters ---------- G : Graph (undirected) nodes: list or iterable Nodes are labeled 0...n-1 in the order provided. If None the ordering given by G.nodes() is used. header: bool If True add '>>graph6<<' string to head of data Returns ------- s : string String in graph6 format Raises ------ NetworkXError If the graph is directed or has parallel edges Examples -------- >>> G = nx.Graph([(0, 1)]) >>> nx.generate_graph6(G) '>>graph6<<A_' See Also -------- read_graph6, parse_graph6, write_graph6 Notes ----- The format does not support edge or node labels, parallel edges or self loops. If self loops are present they are silently ignored. References ---------- Graph6 specification: http://cs.anu.edu.au/~bdm/data/formats.txt for details. """ if nodes is not None: ns = list(nodes) else: ns = list(G) def bits(): for (i,j) in [(i,j) for j in range(1,n) for i in range(j)]: yield G.has_edge(ns[i],ns[j]) n = G.order() data = n_to_data(n) d = 0 flush = False for i, b in zip(range(n * n), bits()): d |= b << (5 - (i % 6)) flush = True if i % 6 == 5: data.append(d) d = 0 flush = False if flush: data.append(d) string_data = data_to_graph6(data) if header: string_data = '>>graph6<<' + string_data return string_data
@open_file(1, mode='wt')
[docs]def write_graph6(G, path, nodes = None, header=True): """Write a simple undirected graph to path in graph6 format. Parameters ---------- G : Graph (undirected) path : file or string File or filename to write. nodes: list or iterable Nodes are labeled 0...n-1 in the order provided. If None the ordering given by G.nodes() is used. header: bool If True add '>>graph6<<' string to head of data Raises ------ NetworkXError If the graph is directed or has parallel edges Examples -------- >>> G = nx.Graph([(0, 1)]) >>> nx.write_graph6(G, 'test.g6') See Also -------- generate_graph6, parse_graph6, read_graph6 Notes ----- The format does not support edge or node labels, parallel edges or self loops. If self loops are present they are silently ignored. References ---------- Graph6 specification: http://cs.anu.edu.au/~bdm/data/formats.txt for details. """ path.write(generate_graph6(G, nodes=nodes, header=header)) path.write('\n') # helper functions
def graph6_to_data(string): """Convert graph6 character sequence to 6-bit integers.""" v = [ord(c)-63 for c in string] if len(v) > 0 and (min(v) < 0 or max(v) > 63): return None return v def data_to_graph6(data): """Convert 6-bit integer sequence to graph6 character sequence.""" if len(data) > 0 and (min(data) < 0 or max(data) > 63): raise NetworkXError("graph6 data units must be within 0..63") return ''.join([chr(d+63) for d in data]) def data_to_n(data): """Read initial one-, four- or eight-unit value from graph6 integer sequence. Return (value, rest of seq.)""" if data[0] <= 62: return data[0], data[1:] if data[1] <= 62: return (data[1]<<12) + (data[2]<<6) + data[3], data[4:] return ((data[2]<<30) + (data[3]<<24) + (data[4]<<18) + (data[5]<<12) + (data[6]<<6) + data[7], data[8:]) def n_to_data(n): """Convert an integer to one-, four- or eight-unit graph6 sequence.""" if n < 0: raise NetworkXError("Numbers in graph6 format must be non-negative.") if n <= 62: return [n] if n <= 258047: return [63, (n>>12) & 0x3f, (n>>6) & 0x3f, n & 0x3f] if n <= 68719476735: return [63, 63, (n>>30) & 0x3f, (n>>24) & 0x3f, (n>>18) & 0x3f, (n>>12) & 0x3f, (n>>6) & 0x3f, n & 0x3f] raise NetworkXError("Numbers above 68719476735 are not supported by graph6")