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

# 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-2018 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.
#
# Authors: Tomas Gavenciak <gavento@ucw.cz>
#          Aric Hagberg <aric.hagberg@lanl.gov>
"""Functions for reading and writing graphs in the *graph6* format.

The *graph6* file format is suitable for small graphs or large dense
graphs. For large sparse graphs, use the *sparse6* format.

For more information, see the `graph6`_ homepage.

.. _graph6: http://users.cecs.anu.edu.au/~bdm/data/formats.html

"""
from itertools import islice
import sys

import networkx as nx
from networkx.exception import NetworkXError
from networkx.utils import open_file, not_implemented_for

__all__ = ['from_graph6_bytes', 'read_graph6', 'to_graph6_bytes',
           'write_graph6']


def _generate_graph6_bytes(G, nodes, header):
    """Yield bytes in the graph6 encoding of a graph.

    `G` is an undirected simple graph. `nodes` is the list of nodes for
    which the node-induced subgraph will be encoded; if `nodes` is the
    list of all nodes in the graph, the entire graph will be
    encoded. `header` is a Boolean that specifies whether to generate
    the header ``b'>>graph6<<'`` before the remaining data.

    This function generates `bytes` objects in the following order:

    1. the header (if requested),
    2. the encoding of the number of nodes,
    3. each character, one-at-a-time, in the encoding of the requested
       node-induced subgraph,
    4. a newline character.

    This function raises :exc:`ValueError` if the graph is too large for
    the graph6 format (that is, greater than ``2 ** 36`` nodes).

    """
    n = len(G)
    if n >= 2 ** 36:
        raise ValueError('graph6 is only defined if number of nodes is less '
                         'than 2 ** 36')
    if header:
        yield b'>>graph6<<'
    for d in n_to_data(n):
        yield str.encode(chr(d + 63))
    # This generates the same as `(v in G[u] for u, v in combinations(G, 2))`,
    # but in "column-major" order instead of "row-major" order.
    bits = (nodes[j] in G[nodes[i]] for j in range(1, n) for i in range(j))
    chunk = list(islice(bits, 6))
    while chunk:
        d = sum(b << 5 - i for i, b in enumerate(chunk))
        yield str.encode(chr(d + 63))
        chunk = list(islice(bits, 6))
    yield b'\n'


[docs]def from_graph6_bytes(string): """Read a simple undirected graph in graph6 format from string. Parameters ---------- string : string Data in graph6 format, without a trailing newline. Returns ------- G : Graph Raises ------ NetworkXError If the string is unable to be parsed in graph6 format ValueError If any character ``c`` in the input string does not satisfy ``63 <= ord(c) < 127``. Examples -------- >>> G = nx.from_graph6_bytes(b'A_') >>> sorted(G.edges()) [(0, 1)] See Also -------- read_graph6, write_graph6 References ---------- .. [1] Graph6 specification <http://users.cecs.anu.edu.au/~bdm/data/formats.html> """ 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(b'>>graph6<<'): string = string[10:] if sys.version_info < (3, ): data = [ord(c) - 63 for c in string] else: data = [c - 63 for c in string] if any(c > 63 for c in data): raise ValueError('each input character must be in range(63, 127)') 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
[docs]def to_graph6_bytes(G, nodes=None, header=True): """Convert a simple undirected graph to bytes in graph6 format. 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<<' bytes to head of data. Raises ------ NetworkXNotImplemented If the graph is directed or is a multigraph. ValueError If the graph has at least ``2 ** 36`` nodes; the graph6 format is only defined for graphs of order less than ``2 ** 36``. Examples -------- >>> nx.to_graph6_bytes(nx.path_graph(2)) # doctest: +SKIP b'>>graph6<<A_\\n' See Also -------- from_graph6_bytes, read_graph6, write_graph6_bytes Notes ----- The returned bytes end with a newline character. The format does not support edge or node labels, parallel edges or self loops. If self loops are present they are silently ignored. References ---------- .. [1] Graph6 specification <http://users.cecs.anu.edu.au/~bdm/data/formats.html> """ if nodes is not None: G = G.subgraph(nodes) H = nx.convert_node_labels_to_integers(G) nodes = sorted(H.nodes()) return b''.join(_generate_graph6_bytes(H, nodes, header))
[docs]@open_file(0, mode='rb') 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 -------- You can read a graph6 file by giving the path to the file:: >>> import tempfile >>> with tempfile.NamedTemporaryFile() as f: ... _ = f.write(b'>>graph6<<A_\\n') ... _ = f.seek(0) ... G = nx.read_graph6(f.name) >>> list(G.edges()) [(0, 1)] You can also read a graph6 file by giving an open file-like object:: >>> import tempfile >>> with tempfile.NamedTemporaryFile() as f: ... _ = f.write(b'>>graph6<<A_\\n') ... _ = f.seek(0) ... G = nx.read_graph6(f) >>> list(G.edges()) [(0, 1)] See Also -------- from_graph6_bytes, write_graph6 References ---------- .. [1] Graph6 specification <http://users.cecs.anu.edu.au/~bdm/data/formats.html> """ glist = [] for line in path: line = line.strip() if not len(line): continue glist.append(from_graph6_bytes(line)) if len(glist) == 1: return glist[0] else: return glist
[docs]@not_implemented_for('directed') @not_implemented_for('multigraph') @open_file(1, mode='wb') def write_graph6(G, path, nodes=None, header=True): """Write a simple undirected graph to a path in graph6 format. Parameters ---------- G : Graph (undirected) path : str The path naming the file to which to write the graph. 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 ------ NetworkXNotImplemented If the graph is directed or is a multigraph. ValueError If the graph has at least ``2 ** 36`` nodes; the graph6 format is only defined for graphs of order less than ``2 ** 36``. Examples -------- You can write a graph6 file by giving the path to a file:: >>> import tempfile >>> with tempfile.NamedTemporaryFile() as f: ... nx.write_graph6(nx.path_graph(2), f.name) ... _ = f.seek(0) ... print(f.read()) # doctest: +SKIP b'>>graph6<<A_\\n' See Also -------- from_graph6_bytes, read_graph6 Notes ----- The function writes a newline character after writing the encoding of the graph. The format does not support edge or node labels, parallel edges or self loops. If self loops are present they are silently ignored. References ---------- .. [1] Graph6 specification <http://users.cecs.anu.edu.au/~bdm/data/formats.html> """ return write_graph6_file(G, path, nodes=nodes, header=header)
@not_implemented_for('directed') @not_implemented_for('multigraph') def write_graph6_file(G, f, nodes=None, header=True): """Write a simple undirected graph to a file-like object in graph6 format. Parameters ---------- G : Graph (undirected) f : file-like object The file 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 ------ NetworkXNotImplemented If the graph is directed or is a multigraph. ValueError If the graph has at least ``2 ** 36`` nodes; the graph6 format is only defined for graphs of order less than ``2 ** 36``. Examples -------- You can write a graph6 file by giving an open file-like object:: >>> import tempfile >>> with tempfile.NamedTemporaryFile() as f: ... nx.write_graph6(nx.path_graph(2), f) ... _ = f.seek(0) ... print(f.read()) # doctest: +SKIP b'>>graph6<<A_\\n' See Also -------- from_graph6_bytes, read_graph6 Notes ----- The function writes a newline character after writing the encoding of the graph. The format does not support edge or node labels, parallel edges or self loops. If self loops are present they are silently ignored. References ---------- .. [1] Graph6 specification <http://users.cecs.anu.edu.au/~bdm/data/formats.html> """ if nodes is not None: G = G.subgraph(nodes) H = nx.convert_node_labels_to_integers(G) nodes = sorted(H.nodes()) for b in _generate_graph6_bytes(H, nodes, header): f.write(b) 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. This function is undefined if `n` is not in ``range(2 ** 36)``. """ if n <= 62: return [n] elif n <= 258047: return [63, (n >> 12) & 0x3f, (n >> 6) & 0x3f, n & 0x3f] else: # if n <= 68719476735: return [63, 63, (n >> 30) & 0x3f, (n >> 24) & 0x3f, (n >> 18) & 0x3f, (n >> 12) & 0x3f, (n >> 6) & 0x3f, n & 0x3f]