Author: Stefan Beyer <h...@sbeyer.at>
Branch: cpyext-gc-cycle
Changeset: r95614:2e7b85611e30
Date: 2018-12-21 11:55 +0100
http://bitbucket.org/pypy/pypy/changeset/2e7b85611e30/
Log: Added complex rawrefcount tests using dot files Adapted traverse
support in incminimark to support tests
diff too long, truncating to 2000 out of 9197 lines
diff --git a/rpython/memory/gc/incminimark.py b/rpython/memory/gc/incminimark.py
--- a/rpython/memory/gc/incminimark.py
+++ b/rpython/memory/gc/incminimark.py
@@ -3253,9 +3253,6 @@
else:
self._rrc_free(pyobject)
- def _rrc_visit_pyobj(self, pyobj):
- pass
-
def _rrc_visit(pyobj, self_ptr):
from rpython.rtyper.annlowlevel import cast_adr_to_nongc_instance
#
@@ -3265,13 +3262,18 @@
return rffi.cast(rffi.INT_real, 0)
def _rrc_traverse(self, pyobject):
+ from rpython.rlib.objectmodel import we_are_translated
from rpython.rtyper.annlowlevel import (cast_nongc_instance_to_adr,
llhelper)
#
pyobj = self._pyobj(pyobject)
- callback_ptr = llhelper(self.RAWREFCOUNT_VISIT,
- IncrementalMiniMarkGC._rrc_visit)
- self_ptr = rffi.cast(rffi.VOIDP, cast_nongc_instance_to_adr(self))
+ if we_are_translated():
+ callback_ptr = llhelper(self.RAWREFCOUNT_VISIT,
+ IncrementalMiniMarkGC._rrc_visit)
+ self_ptr = rffi.cast(rffi.VOIDP, cast_nongc_instance_to_adr(self))
+ else:
+ callback_ptr = self._rrc_visit_pyobj
+ self_ptr = None
self.rrc_tp_traverse(pyobj, callback_ptr, self_ptr)
def _rrc_gc_list_init(self, pygclist):
diff --git a/rpython/memory/gc/test/__init__.py
b/rpython/memory/gc/test/dot/__init__.py
copy from rpython/memory/gc/test/__init__.py
copy to rpython/memory/gc/test/dot/__init__.py
diff --git a/rpython/memory/gc/test/dot/dot_parser.py
b/rpython/memory/gc/test/dot/dot_parser.py
new file mode 100644
--- /dev/null
+++ b/rpython/memory/gc/test/dot/dot_parser.py
@@ -0,0 +1,555 @@
+"""Graphviz's dot language parser.
+
+The dotparser parses GraphViz files in
+dot and dot files and transforms them
+into a class representation defined by `pydot`.
+
+Author: Michael Krause <mich...@krause-software.de>
+Fixes by: Ero Carrera <e...@dkbza.org>
+"""
+from __future__ import division
+from __future__ import print_function
+import sys
+
+from pyparsing import (
+ nestedExpr, Literal, CaselessLiteral,
+ Word, OneOrMore,
+ Forward,
+ Group, Optional, Combine,
+ restOfLine, cStyleComment, nums, alphanums,
+ printables,
+ ParseException, ParseResults, CharsNotIn,
+ QuotedString)
+
+import pydot
+
+__author__ = ['Michael Krause', 'Ero Carrera']
+__license__ = 'MIT'
+
+
+PY3 = sys.version_info >= (3, 0, 0)
+if PY3:
+ str_type = str
+else:
+ str_type = basestring
+
+
+class P_AttrList(object):
+
+ def __init__(self, toks):
+
+ self.attrs = {}
+ i = 0
+
+ while i < len(toks):
+ attrname = toks[i]
+ if i+2 < len(toks) and toks[i+1] == '=':
+ attrvalue = toks[i+2]
+ i += 3
+ else:
+ attrvalue = None
+ i += 1
+
+ self.attrs[attrname] = attrvalue
+
+
+ def __repr__(self):
+
+ return "%s(%r)" % (self.__class__.__name__, self.attrs)
+
+
+
+class DefaultStatement(P_AttrList):
+
+ def __init__(self, default_type, attrs):
+
+ self.default_type = default_type
+ self.attrs = attrs
+
+ def __repr__(self):
+
+ return "%s(%s, %r)" % (self.__class__.__name__,
+ self.default_type, self.attrs)
+
+
+top_graphs = list()
+
+def push_top_graph_stmt(str, loc, toks):
+
+ attrs = {}
+ g = None
+
+ for element in toks:
+
+ if (isinstance(element, (ParseResults, tuple, list)) and
+ len(element) == 1 and
+ isinstance(element[0], str_type)):
+
+ element = element[0]
+
+ if element == 'strict':
+ attrs['strict'] = True
+
+ elif element in ['graph', 'digraph']:
+
+ attrs = {}
+
+ g = pydot.Dot(graph_type=element, **attrs)
+ attrs['type'] = element
+
+ top_graphs.append( g )
+
+ elif isinstance( element, str_type):
+ g.set_name( element )
+
+ elif isinstance(element, pydot.Subgraph):
+
+ g.obj_dict['attributes'].update( element.obj_dict['attributes'] )
+ g.obj_dict['edges'].update( element.obj_dict['edges'] )
+ g.obj_dict['nodes'].update( element.obj_dict['nodes'] )
+ g.obj_dict['subgraphs'].update( element.obj_dict['subgraphs'] )
+
+ g.set_parent_graph(g)
+
+ elif isinstance(element, P_AttrList):
+ attrs.update(element.attrs)
+
+ elif isinstance(element, (ParseResults, list)):
+ add_elements(g, element)
+
+ else:
+ raise ValueError(
+ 'Unknown element statement: {s}'.format(s=element))
+
+
+ for g in top_graphs:
+ update_parent_graph_hierarchy(g)
+
+ if len( top_graphs ) == 1:
+ return top_graphs[0]
+
+ return top_graphs
+
+
+def update_parent_graph_hierarchy(g, parent_graph=None, level=0):
+
+
+ if parent_graph is None:
+ parent_graph = g
+
+ for key_name in ('edges',):
+
+ if isinstance(g, pydot.frozendict):
+ item_dict = g
+ else:
+ item_dict = g.obj_dict
+
+ if key_name not in item_dict:
+ continue
+
+ for key, objs in item_dict[key_name].items():
+ for obj in objs:
+ if ('parent_graph' in obj and
+ obj['parent_graph'].get_parent_graph()==g):
+ if obj['parent_graph'] is g:
+ pass
+ else:
+ obj['parent_graph'].set_parent_graph(parent_graph)
+
+ if key_name == 'edges' and len(key) == 2:
+ for idx, vertex in enumerate( obj['points'] ):
+ if isinstance( vertex,
+ (pydot.Graph,
+ pydot.Subgraph, pydot.Cluster)):
+ vertex.set_parent_graph(parent_graph)
+ if isinstance( vertex, pydot.frozendict):
+ if vertex['parent_graph'] is g:
+ pass
+ else:
+ vertex['parent_graph'].set_parent_graph(
+ parent_graph)
+
+
+
+def add_defaults(element, defaults):
+
+ d = element.__dict__
+ for key, value in defaults.items():
+ if not d.get(key):
+ d[key] = value
+
+
+
+def add_elements(g, toks, defaults_graph=None,
+ defaults_node=None, defaults_edge=None):
+
+ if defaults_graph is None:
+ defaults_graph = {}
+ if defaults_node is None:
+ defaults_node = {}
+ if defaults_edge is None:
+ defaults_edge = {}
+
+ for elm_idx, element in enumerate(toks):
+
+ if isinstance(element, (pydot.Subgraph, pydot.Cluster)):
+
+ add_defaults(element, defaults_graph)
+ g.add_subgraph(element)
+
+ elif isinstance(element, pydot.Node):
+
+ add_defaults(element, defaults_node)
+ g.add_node(element)
+
+ elif isinstance(element, pydot.Edge):
+
+ add_defaults(element, defaults_edge)
+ g.add_edge(element)
+
+ elif isinstance(element, ParseResults):
+
+ for e in element:
+ add_elements(g, [e], defaults_graph,
+ defaults_node, defaults_edge)
+
+ elif isinstance(element, DefaultStatement):
+
+ if element.default_type == 'graph':
+
+ default_graph_attrs = pydot.Node('graph', **element.attrs)
+ g.add_node(default_graph_attrs)
+
+ elif element.default_type == 'node':
+
+ default_node_attrs = pydot.Node('node', **element.attrs)
+ g.add_node(default_node_attrs)
+
+ elif element.default_type == 'edge':
+
+ default_edge_attrs = pydot.Node('edge', **element.attrs)
+ g.add_node(default_edge_attrs)
+ defaults_edge.update(element.attrs)
+
+ else:
+ raise ValueError(
+ 'Unknown DefaultStatement: {s}'.format(
+ s=element.default_type))
+
+ elif isinstance(element, P_AttrList):
+
+ g.obj_dict['attributes'].update(element.attrs)
+
+ else:
+ raise ValueError(
+ 'Unknown element statement: {s}'.format(s=element))
+
+
+def push_graph_stmt(str, loc, toks):
+
+ g = pydot.Subgraph('')
+ add_elements(g, toks)
+ return g
+
+
+def push_subgraph_stmt(str, loc, toks):
+
+ g = pydot.Subgraph('')
+ for e in toks:
+ if len(e)==3:
+ e[2].set_name(e[1])
+ if e[0] == 'subgraph':
+ e[2].obj_dict['show_keyword'] = True
+ return e[2]
+ else:
+ if e[0] == 'subgraph':
+ e[1].obj_dict['show_keyword'] = True
+ return e[1]
+
+ return g
+
+
+def push_default_stmt(str, loc, toks):
+
+ # The pydot class instances should be marked as
+ # default statements to be inherited by actual
+ # graphs, nodes and edges.
+ #
+ default_type = toks[0][0]
+ if len(toks) > 1:
+ attrs = toks[1].attrs
+ else:
+ attrs = {}
+
+ if default_type in ['graph', 'node', 'edge']:
+ return DefaultStatement(default_type, attrs)
+ else:
+ raise ValueError(
+ 'Unknown default statement: {s}'.format(s=toks))
+
+
+def push_attr_list(str, loc, toks):
+
+ p = P_AttrList(toks)
+ return p
+
+
+def get_port(node):
+
+ if len(node)>1:
+ if isinstance(node[1], ParseResults):
+ if len(node[1][0])==2:
+ if node[1][0][0]==':':
+ return node[1][0][1]
+
+ return None
+
+
+def do_node_ports(node):
+
+ node_port = ''
+ if len(node) > 1:
+ node_port = ''.join( [str(a)+str(b) for a,b in node[1] ] )
+
+ return node_port
+
+
+def push_edge_stmt(str, loc, toks):
+
+ tok_attrs = [a for a in toks if isinstance(a, P_AttrList)]
+ attrs = {}
+ for a in tok_attrs:
+ attrs.update(a.attrs)
+
+ e = []
+
+ if isinstance(toks[0][0], pydot.Graph):
+
+ n_prev = pydot.frozendict(toks[0][0].obj_dict)
+ else:
+ n_prev = toks[0][0] + do_node_ports( toks[0] )
+
+ if isinstance(toks[2][0], ParseResults):
+
+ n_next_list = [[n.get_name(),] for n in toks[2][0] ]
+ for n_next in [n for n in n_next_list]:
+ n_next_port = do_node_ports(n_next)
+ e.append(pydot.Edge(n_prev, n_next[0]+n_next_port, **attrs))
+
+ elif isinstance(toks[2][0], pydot.Graph):
+
+ e.append(pydot.Edge(n_prev,
+ pydot.frozendict(toks[2][0].obj_dict),
+ **attrs))
+
+ elif isinstance(toks[2][0], pydot.Node):
+
+ node = toks[2][0]
+
+ if node.get_port() is not None:
+ name_port = node.get_name() + ":" + node.get_port()
+ else:
+ name_port = node.get_name()
+
+ e.append(pydot.Edge(n_prev, name_port, **attrs))
+
+ # if the target of this edge is the name of a node
+ elif isinstance(toks[2][0], str_type):
+
+ for n_next in [n for n in tuple(toks)[2::2]]:
+
+ if (isinstance(n_next, P_AttrList) or
+ not isinstance(n_next[0], str_type)):
+ continue
+
+ n_next_port = do_node_ports( n_next )
+ e.append(pydot.Edge(n_prev, n_next[0]+n_next_port, **attrs))
+
+ n_prev = n_next[0]+n_next_port
+ else:
+ raise Exception(
+ 'Edge target {r} with type {s} unsupported.'.format(
+ r=toks[2][0], s=type(toks[2][0])))
+
+ return e
+
+
+
+def push_node_stmt(s, loc, toks):
+
+ if len(toks) == 2:
+ attrs = toks[1].attrs
+ else:
+ attrs = {}
+
+ node_name = toks[0]
+ if isinstance(node_name, list) or isinstance(node_name, tuple):
+ if len(node_name)>0:
+ node_name = node_name[0]
+
+ n = pydot.Node(str(node_name), **attrs)
+ return n
+
+
+
+
+
+
+graphparser = None
+
+def graph_definition():
+
+ global graphparser
+
+ if not graphparser:
+
+ # punctuation
+ colon = Literal(":")
+ lbrace = Literal("{")
+ rbrace = Literal("}")
+ lbrack = Literal("[")
+ rbrack = Literal("]")
+ lparen = Literal("(")
+ rparen = Literal(")")
+ equals = Literal("=")
+ comma = Literal(",")
+ dot = Literal(".")
+ slash = Literal("/")
+ bslash = Literal("\\")
+ star = Literal("*")
+ semi = Literal(";")
+ at = Literal("@")
+ minus = Literal("-")
+
+ # keywords
+ strict_ = CaselessLiteral("strict")
+ graph_ = CaselessLiteral("graph")
+ digraph_ = CaselessLiteral("digraph")
+ subgraph_ = CaselessLiteral("subgraph")
+ node_ = CaselessLiteral("node")
+ edge_ = CaselessLiteral("edge")
+
+
+ # token definitions
+
+ identifier = Word(alphanums + "_." ).setName("identifier")
+
+ double_quoted_string = QuotedString(
+ '"', multiline=True, unquoteResults=False, escChar='\\') #
dblQuotedString
+
+ noncomma = "".join([c for c in printables if c != ","])
+ alphastring_ = OneOrMore(CharsNotIn(noncomma + ' '))
+
+ def parse_html(s, loc, toks):
+ return '<%s>' % ''.join(toks[0])
+
+
+ opener = '<'
+ closer = '>'
+ html_text = nestedExpr( opener, closer,
+ ( CharsNotIn( opener + closer ) )
+ ).setParseAction(parse_html).leaveWhitespace()
+
+ ID = ( identifier | html_text |
+ double_quoted_string | #.setParseAction(strip_quotes) |
+ alphastring_ ).setName("ID")
+
+
+ float_number = Combine(Optional(minus) +
+ OneOrMore(Word(nums + "."))).setName("float_number")
+
+ righthand_id = (float_number | ID ).setName("righthand_id")
+
+ port_angle = (at + ID).setName("port_angle")
+
+ port_location = (OneOrMore(Group(colon + ID)) |
+ Group(colon + lparen +
+ ID + comma + ID + rparen)).setName("port_location")
+
+ port = (Group(port_location + Optional(port_angle)) |
+ Group(port_angle + Optional(port_location))).setName("port")
+
+ node_id = (ID + Optional(port))
+ a_list = OneOrMore(ID + Optional(equals + righthand_id) +
+ Optional(comma.suppress())).setName("a_list")
+
+ attr_list = OneOrMore(lbrack.suppress() + Optional(a_list) +
+ rbrack.suppress()).setName("attr_list")
+
+ attr_stmt = (Group(graph_ | node_ | edge_) +
+ attr_list).setName("attr_stmt")
+
+ edgeop = (Literal("--") | Literal("->")).setName("edgeop")
+
+ stmt_list = Forward()
+ graph_stmt = Group(lbrace.suppress() + Optional(stmt_list) +
+ rbrace.suppress() +
+ Optional(semi.suppress())).setName("graph_stmt")
+
+
+ edge_point = Forward()
+
+ edgeRHS = OneOrMore(edgeop + edge_point)
+ edge_stmt = edge_point + edgeRHS + Optional(attr_list)
+
+ subgraph = Group(
+ subgraph_ + Optional(ID) + graph_stmt).setName("subgraph")
+
+ edge_point << Group(
+ subgraph | graph_stmt | node_id).setName('edge_point')
+
+ node_stmt = (
+ node_id + Optional(attr_list) +
+ Optional(semi.suppress())).setName("node_stmt")
+
+ assignment = (ID + equals + righthand_id).setName("assignment")
+ stmt = (assignment | edge_stmt | attr_stmt |
+ subgraph | graph_stmt | node_stmt).setName("stmt")
+ stmt_list << OneOrMore(stmt + Optional(semi.suppress()))
+
+ graphparser = OneOrMore(
+ (Optional(strict_) + Group((graph_ | digraph_)) +
+ Optional(ID) + graph_stmt).setResultsName("graph"))
+
+ singleLineComment = Group(
+ "//" + restOfLine) | Group("#" + restOfLine)
+
+
+ # actions
+
+ graphparser.ignore(singleLineComment)
+ graphparser.ignore(cStyleComment)
+
+ assignment.setParseAction(push_attr_list)
+ a_list.setParseAction(push_attr_list)
+ edge_stmt.setParseAction(push_edge_stmt)
+ node_stmt.setParseAction(push_node_stmt)
+ attr_stmt.setParseAction(push_default_stmt)
+
+ subgraph.setParseAction(push_subgraph_stmt)
+ graph_stmt.setParseAction(push_graph_stmt)
+ graphparser.setParseAction(push_top_graph_stmt)
+
+
+ return graphparser
+
+
+def parse_dot_data(s):
+ """Parse DOT description in (unicode) string `s`.
+
+ @return: Graphs that result from parsing.
+ @rtype: `list` of `pydot.Dot`
+ """
+ global top_graphs
+ top_graphs = list()
+ try:
+ graphparser = graph_definition()
+ graphparser.parseWithTabs()
+ tokens = graphparser.parseString(s)
+ return list(tokens)
+ except ParseException as err:
+ print(
+ err.line +
+ " "*(err.column-1) + "^" +
+ err)
+ return None
diff --git a/rpython/memory/gc/test/dot/free_self_cpython.dot
b/rpython/memory/gc/test/dot/free_self_cpython.dot
new file mode 100644
--- /dev/null
+++ b/rpython/memory/gc/test/dot/free_self_cpython.dot
@@ -0,0 +1,4 @@
+digraph G {
+ "a" [type=C, alive=n];
+ "a" -> "a";
+}
diff --git a/rpython/memory/gc/test/dot/free_self_pypy.dot
b/rpython/memory/gc/test/dot/free_self_pypy.dot
new file mode 100644
--- /dev/null
+++ b/rpython/memory/gc/test/dot/free_self_pypy.dot
@@ -0,0 +1,4 @@
+digraph G {
+ "a" [type=P, alive=n];
+ "a" -> "a";
+}
diff --git a/rpython/memory/gc/test/dot/free_simple_cross.dot
b/rpython/memory/gc/test/dot/free_simple_cross.dot
new file mode 100644
--- /dev/null
+++ b/rpython/memory/gc/test/dot/free_simple_cross.dot
@@ -0,0 +1,6 @@
+digraph G {
+ "a" [type=B, alive=n];
+ "b" [type=C, alive=n];
+ "a" -> "b";
+ "b" -> "a";
+}
diff --git a/rpython/memory/gc/test/dot/keep_self_cpython.dot
b/rpython/memory/gc/test/dot/keep_self_cpython.dot
new file mode 100644
--- /dev/null
+++ b/rpython/memory/gc/test/dot/keep_self_cpython.dot
@@ -0,0 +1,4 @@
+digraph G {
+ "a" [type=C, alive=y, ext_refcnt=1];
+ "a" -> "a";
+}
diff --git a/rpython/memory/gc/test/dot/keep_self_pypy.dot
b/rpython/memory/gc/test/dot/keep_self_pypy.dot
new file mode 100644
--- /dev/null
+++ b/rpython/memory/gc/test/dot/keep_self_pypy.dot
@@ -0,0 +1,4 @@
+digraph G {
+ "a" [type=P, alive=y, rooted=y];
+ "a" -> "a";
+}
diff --git a/rpython/memory/gc/test/dot/pydot.py
b/rpython/memory/gc/test/dot/pydot.py
new file mode 100644
--- /dev/null
+++ b/rpython/memory/gc/test/dot/pydot.py
@@ -0,0 +1,1943 @@
+"""An interface to GraphViz."""
+from __future__ import division
+from __future__ import print_function
+import copy
+import io
+import errno
+import os
+import re
+import subprocess
+import sys
+import tempfile
+import warnings
+
+try:
+ import dot_parser
+except Exception as e:
+ warnings.warn(
+ "Couldn't import dot_parser, "
+ "loading of dot files will not be possible.")
+
+
+__author__ = 'Ero Carrera'
+__version__ = '1.4.1.dev0'
+__license__ = 'MIT'
+
+
+PY3 = sys.version_info >= (3, 0, 0)
+if PY3:
+ str_type = str
+else:
+ str_type = basestring
+
+
+GRAPH_ATTRIBUTES = { 'Damping', 'K', 'URL', 'aspect', 'bb', 'bgcolor',
+ 'center', 'charset', 'clusterrank', 'colorscheme', 'comment', 'compound',
+ 'concentrate', 'defaultdist', 'dim', 'dimen', 'diredgeconstraints',
+ 'dpi', 'epsilon', 'esep', 'fontcolor', 'fontname', 'fontnames',
+ 'fontpath', 'fontsize', 'id', 'label', 'labeljust', 'labelloc',
+ 'landscape', 'layers', 'layersep', 'layout', 'levels', 'levelsgap',
+ 'lheight', 'lp', 'lwidth', 'margin', 'maxiter', 'mclimit', 'mindist',
+ 'mode', 'model', 'mosek', 'nodesep', 'nojustify', 'normalize', 'nslimit',
+ 'nslimit1', 'ordering', 'orientation', 'outputorder', 'overlap',
+ 'overlap_scaling', 'pack', 'packmode', 'pad', 'page', 'pagedir',
+ 'quadtree', 'quantum', 'rankdir', 'ranksep', 'ratio', 'remincross',
+ 'repulsiveforce', 'resolution', 'root', 'rotate', 'searchsize', 'sep',
+ 'showboxes', 'size', 'smoothing', 'sortv', 'splines', 'start',
+ 'stylesheet', 'target', 'truecolor', 'viewport', 'voro_margin',
+ # for subgraphs
+ 'rank' }
+
+
+EDGE_ATTRIBUTES = { 'URL', 'arrowhead', 'arrowsize', 'arrowtail',
+ 'color', 'colorscheme', 'comment', 'constraint', 'decorate', 'dir',
+ 'edgeURL', 'edgehref', 'edgetarget', 'edgetooltip', 'fontcolor',
+ 'fontname', 'fontsize', 'headURL', 'headclip', 'headhref', 'headlabel',
+ 'headport', 'headtarget', 'headtooltip', 'href', 'id', 'label',
+ 'labelURL', 'labelangle', 'labeldistance', 'labelfloat', 'labelfontcolor',
+ 'labelfontname', 'labelfontsize', 'labelhref', 'labeltarget',
+ 'labeltooltip', 'layer', 'len', 'lhead', 'lp', 'ltail', 'minlen',
+ 'nojustify', 'penwidth', 'pos', 'samehead', 'sametail', 'showboxes',
+ 'style', 'tailURL', 'tailclip', 'tailhref', 'taillabel', 'tailport',
+ 'tailtarget', 'tailtooltip', 'target', 'tooltip', 'weight',
+ 'rank' }
+
+
+NODE_ATTRIBUTES = { 'URL', 'color', 'colorscheme', 'comment',
+ 'distortion', 'fillcolor', 'fixedsize', 'fontcolor', 'fontname',
+ 'fontsize', 'group', 'height', 'id', 'image', 'imagescale', 'label',
+ 'labelloc', 'layer', 'margin', 'nojustify', 'orientation', 'penwidth',
+ 'peripheries', 'pin', 'pos', 'rects', 'regular', 'root', 'samplepoints',
+ 'shape', 'shapefile', 'showboxes', 'sides', 'skew', 'sortv', 'style',
+ 'target', 'tooltip', 'vertices', 'width', 'z',
+ # The following are attributes dot2tex
+ 'texlbl', 'texmode' }
+
+
+CLUSTER_ATTRIBUTES = { 'K', 'URL', 'bgcolor', 'color', 'colorscheme',
+ 'fillcolor', 'fontcolor', 'fontname', 'fontsize', 'label', 'labeljust',
+ 'labelloc', 'lheight', 'lp', 'lwidth', 'nojustify', 'pencolor',
+ 'penwidth', 'peripheries', 'sortv', 'style', 'target', 'tooltip' }
+
+
+DEFAULT_PROGRAMS = {
+ 'dot',
+ 'twopi',
+ 'neato',
+ 'circo',
+ 'fdp',
+ 'sfdp',
+}
+
+
+def is_windows():
+ # type: () -> bool
+ return os.name == 'nt'
+
+
+def is_anacoda():
+ # type: () -> bool
+ return os.path.exists(os.path.join(sys.prefix, 'conda-meta'))
+
+
+def get_executable_extension():
+ # type: () -> str
+ if is_windows():
+ return '.bat' if is_anacoda() else '.exe'
+ else:
+ return ''
+
+
+def call_graphviz(program, arguments, working_dir, **kwargs):
+ # explicitly inherit `$PATH`, on Windows too,
+ # with `shell=False`
+
+ if program in DEFAULT_PROGRAMS:
+ extension = get_executable_extension()
+ program += extension
+
+ if arguments is None:
+ arguments = []
+
+ env = {
+ 'PATH': os.environ.get('PATH', ''),
+ 'LD_LIBRARY_PATH': os.environ.get('LD_LIBRARY_PATH', ''),
+ }
+
+ program_with_args = [program, ] + arguments
+
+ process = subprocess.Popen(
+ program_with_args,
+ env=env,
+ cwd=working_dir,
+ shell=False,
+ stderr=subprocess.PIPE,
+ stdout=subprocess.PIPE,
+ **kwargs
+ )
+ stdout_data, stderr_data = process.communicate()
+
+ return stdout_data, stderr_data, process
+
+
+#
+# Extended version of ASPN's Python Cookbook Recipe:
+# Frozen dictionaries.
+# https://code.activestate.com/recipes/414283/
+#
+# This version freezes dictionaries used as values within dictionaries.
+#
+class frozendict(dict):
+ def _blocked_attribute(obj):
+ raise AttributeError('A frozendict cannot be modified.')
+ _blocked_attribute = property(_blocked_attribute)
+
+ __delitem__ = __setitem__ = clear = _blocked_attribute
+ pop = popitem = setdefault = update = _blocked_attribute
+
+ def __new__(cls, *args, **kw):
+ new = dict.__new__(cls)
+
+ args_ = []
+ for arg in args:
+ if isinstance(arg, dict):
+ arg = copy.copy(arg)
+ for k in arg:
+ v = arg[k]
+ if isinstance(v, frozendict):
+ arg[k] = v
+ elif isinstance(v, dict):
+ arg[k] = frozendict(v)
+ elif isinstance(v, list):
+ v_ = list()
+ for elm in v:
+ if isinstance(elm, dict):
+ v_.append( frozendict(elm) )
+ else:
+ v_.append( elm )
+ arg[k] = tuple(v_)
+ args_.append( arg )
+ else:
+ args_.append( arg )
+
+ dict.__init__(new, *args_, **kw)
+ return new
+
+ def __init__(self, *args, **kw):
+ pass
+
+ def __hash__(self):
+ try:
+ return self._cached_hash
+ except AttributeError:
+ h = self._cached_hash = hash(tuple(sorted(self.items())))
+ return h
+
+ def __repr__(self):
+ return "frozendict(%s)" % dict.__repr__(self)
+
+
+dot_keywords = ['graph', 'subgraph', 'digraph', 'node', 'edge', 'strict']
+
+id_re_alpha_nums = re.compile('^[_a-zA-Z][a-zA-Z0-9_,]*$', re.UNICODE)
+id_re_alpha_nums_with_ports = re.compile(
+ '^[_a-zA-Z][a-zA-Z0-9_,:\"]*[a-zA-Z0-9_,\"]+$', re.UNICODE)
+id_re_num = re.compile('^[0-9,]+$', re.UNICODE)
+id_re_with_port = re.compile('^([^:]*):([^:]*)$', re.UNICODE)
+id_re_dbl_quoted = re.compile('^\".*\"$', re.S|re.UNICODE)
+id_re_html = re.compile('^<.*>$', re.S|re.UNICODE)
+
+
+def needs_quotes( s ):
+ """Checks whether a string is a dot language ID.
+
+ It will check whether the string is solely composed
+ by the characters allowed in an ID or not.
+ If the string is one of the reserved keywords it will
+ need quotes too but the user will need to add them
+ manually.
+ """
+
+ # If the name is a reserved keyword it will need quotes but pydot
+ # can't tell when it's being used as a keyword or when it's simply
+ # a name. Hence the user needs to supply the quotes when an element
+ # would use a reserved keyword as name. This function will return
+ # false indicating that a keyword string, if provided as-is, won't
+ # need quotes.
+ if s in dot_keywords:
+ return False
+
+ chars = [ord(c) for c in s if ord(c)>0x7f or ord(c)==0]
+ if chars and not id_re_dbl_quoted.match(s) and not id_re_html.match(s):
+ return True
+
+ for test_re in [id_re_alpha_nums, id_re_num,
+ id_re_dbl_quoted, id_re_html,
+ id_re_alpha_nums_with_ports]:
+ if test_re.match(s):
+ return False
+
+ m = id_re_with_port.match(s)
+ if m:
+ return needs_quotes(m.group(1)) or needs_quotes(m.group(2))
+
+ return True
+
+
+def quote_if_necessary(s):
+ """Enclode attribute value in quotes, if needed."""
+ if isinstance(s, bool):
+ if s is True:
+ return 'True'
+ return 'False'
+
+ if not isinstance( s, str_type):
+ return s
+
+ if not s:
+ return s
+
+ if needs_quotes(s):
+ replace = {'"' : r'\"',
+ "\n" : r'\n',
+ "\r" : r'\r'}
+ for (a,b) in replace.items():
+ s = s.replace(a, b)
+
+ return '"' + s + '"'
+
+ return s
+
+
+
+def graph_from_dot_data(s):
+ """Load graphs from DOT description in string `s`.
+
+ @param s: string in [DOT language](
+ https://en.wikipedia.org/wiki/DOT_(graph_description_language))
+
+ @return: Graphs that result from parsing.
+ @rtype: `list` of `pydot.Dot`
+ """
+ return dot_parser.parse_dot_data(s)
+
+
+def graph_from_dot_file(path, encoding=None):
+ """Load graphs from DOT file at `path`.
+
+ @param path: to DOT file
+ @param encoding: as passed to `io.open`.
+ For example, `'utf-8'`.
+
+ @return: Graphs that result from parsing.
+ @rtype: `list` of `pydot.Dot`
+ """
+ with io.open(path, 'rt', encoding=encoding) as f:
+ s = f.read()
+ if not PY3:
+ s = unicode(s)
+ graphs = graph_from_dot_data(s)
+ return graphs
+
+
+
+def graph_from_edges(edge_list, node_prefix='', directed=False):
+ """Creates a basic graph out of an edge list.
+
+ The edge list has to be a list of tuples representing
+ the nodes connected by the edge.
+ The values can be anything: bool, int, float, str.
+
+ If the graph is undirected by default, it is only
+ calculated from one of the symmetric halves of the matrix.
+ """
+
+ if directed:
+ graph = Dot(graph_type='digraph')
+
+ else:
+ graph = Dot(graph_type='graph')
+
+ for edge in edge_list:
+
+ if isinstance(edge[0], str):
+ src = node_prefix + edge[0]
+ else:
+ src = node_prefix + str(edge[0])
+
+ if isinstance(edge[1], str):
+ dst = node_prefix + edge[1]
+ else:
+ dst = node_prefix + str(edge[1])
+
+ e = Edge( src, dst )
+ graph.add_edge(e)
+
+ return graph
+
+
+def graph_from_adjacency_matrix(matrix, node_prefix= u'', directed=False):
+ """Creates a basic graph out of an adjacency matrix.
+
+ The matrix has to be a list of rows of values
+ representing an adjacency matrix.
+ The values can be anything: bool, int, float, as long
+ as they can evaluate to True or False.
+ """
+
+ node_orig = 1
+
+ if directed:
+ graph = Dot(graph_type='digraph')
+ else:
+ graph = Dot(graph_type='graph')
+
+ for row in matrix:
+ if not directed:
+ skip = matrix.index(row)
+ r = row[skip:]
+ else:
+ skip = 0
+ r = row
+ node_dest = skip+1
+
+ for e in r:
+ if e:
+ graph.add_edge(
+ Edge( node_prefix + node_orig,
+ node_prefix + node_dest) )
+ node_dest += 1
+ node_orig += 1
+
+ return graph
+
+
+
+def graph_from_incidence_matrix(matrix, node_prefix='', directed=False):
+ """Creates a basic graph out of an incidence matrix.
+
+ The matrix has to be a list of rows of values
+ representing an incidence matrix.
+ The values can be anything: bool, int, float, as long
+ as they can evaluate to True or False.
+ """
+
+ node_orig = 1
+
+ if directed:
+ graph = Dot(graph_type='digraph')
+ else:
+ graph = Dot(graph_type='graph')
+
+ for row in matrix:
+ nodes = []
+ c = 1
+
+ for node in row:
+ if node:
+ nodes.append(c*node)
+ c += 1
+ nodes.sort()
+
+ if len(nodes) == 2:
+ graph.add_edge(
+ Edge( node_prefix + abs(nodes[0]),
+ node_prefix + nodes[1] ))
+
+ if not directed:
+ graph.set_simplify(True)
+
+ return graph
+
+
+class Common(object):
+ """Common information to several classes.
+
+ Should not be directly used, several classes are derived from
+ this one.
+ """
+
+
+ def __getstate__(self):
+
+ dict = copy.copy(self.obj_dict)
+
+ return dict
+
+
+ def __setstate__(self, state):
+
+ self.obj_dict = state
+
+
+ def __get_attribute__(self, attr):
+ """Look for default attributes for this node"""
+
+ attr_val = self.obj_dict['attributes'].get(attr, None)
+
+ if attr_val is None:
+ # get the defaults for nodes/edges
+
+ default_node_name = self.obj_dict['type']
+
+ # The defaults for graphs are set on a node named 'graph'
+ if default_node_name in ('subgraph', 'digraph', 'cluster'):
+ default_node_name = 'graph'
+
+ g = self.get_parent_graph()
+ if g is not None:
+ defaults = g.get_node( default_node_name )
+ else:
+ return None
+
+ # Multiple defaults could be set by having repeated 'graph [...]'
+ # 'node [...]', 'edge [...]' statements. In such case, if the
+ # same attribute is set in different statements, only the first
+ # will be returned. In order to get all, one would call the
+ # get_*_defaults() methods and handle those. Or go node by node
+ # (of the ones specifying defaults) and modify the attributes
+ # individually.
+ #
+ if not isinstance(defaults, (list, tuple)):
+ defaults = [defaults]
+
+ for default in defaults:
+ attr_val = default.obj_dict['attributes'].get(attr, None)
+ if attr_val:
+ return attr_val
+ else:
+ return attr_val
+
+ return None
+
+
+ def set_parent_graph(self, parent_graph):
+
+ self.obj_dict['parent_graph'] = parent_graph
+
+
+ def get_parent_graph(self):
+
+ return self.obj_dict.get('parent_graph', None)
+
+
+ def set(self, name, value):
+ """Set an attribute value by name.
+
+ Given an attribute 'name' it will set its value to 'value'.
+ There's always the possibility of using the methods:
+
+ set_'name'(value)
+
+ which are defined for all the existing attributes.
+ """
+
+ self.obj_dict['attributes'][name] = value
+
+
+ def get(self, name):
+ """Get an attribute value by name.
+
+ Given an attribute 'name' it will get its value.
+ There's always the possibility of using the methods:
+
+ get_'name'()
+
+ which are defined for all the existing attributes.
+ """
+
+ return self.obj_dict['attributes'].get(name, None)
+
+
+ def get_attributes(self):
+ """"""
+
+ return self.obj_dict['attributes']
+
+
+ def set_sequence(self, seq):
+
+ self.obj_dict['sequence'] = seq
+
+
+ def get_sequence(self):
+
+ return self.obj_dict['sequence']
+
+
+ def create_attribute_methods(self, obj_attributes):
+
+ #for attr in self.obj_dict['attributes']:
+ for attr in obj_attributes:
+
+ # Generate all the Setter methods.
+ #
+ self.__setattr__(
+ 'set_'+attr,
+ lambda x, a=attr :
+ self.obj_dict['attributes'].__setitem__(a, x) )
+
+ # Generate all the Getter methods.
+ #
+ self.__setattr__(
+ 'get_'+attr, lambda a=attr : self.__get_attribute__(a))
+
+
+
+class Error(Exception):
+ """General error handling class.
+ """
+ def __init__(self, value):
+ self.value = value
+ def __str__(self):
+ return self.value
+
+
+class InvocationException(Exception):
+ """Indicate ploblem while running any GraphViz executable.
+ """
+ def __init__(self, value):
+ self.value = value
+ def __str__(self):
+ return self.value
+
+
+
+class Node(Common):
+ """A graph node.
+
+ This class represents a graph's node with all its attributes.
+
+ node(name, attribute=value, ...)
+
+ name: node's name
+
+ All the attributes defined in the Graphviz dot language should
+ be supported.
+ """
+
+ def __init__(self, name = '', obj_dict = None, **attrs):
+
+ #
+ # Nodes will take attributes of
+ # all other types because the defaults
+ # for any GraphViz object are dealt with
+ # as if they were Node definitions
+ #
+
+ if obj_dict is not None:
+
+ self.obj_dict = obj_dict
+
+ else:
+
+ self.obj_dict = dict()
+
+ # Copy the attributes
+ #
+ self.obj_dict[ 'attributes' ] = dict( attrs )
+ self.obj_dict[ 'type' ] = 'node'
+ self.obj_dict[ 'parent_graph' ] = None
+ self.obj_dict[ 'parent_node_list' ] = None
+ self.obj_dict[ 'sequence' ] = None
+
+ # Remove the compass point
+ #
+ port = None
+ if isinstance(name, str_type) and not name.startswith('"'):
+ idx = name.find(':')
+ if idx > 0 and idx+1 < len(name):
+ name, port = name[:idx], name[idx:]
+
+ if isinstance(name, int):
+ name = str(name)
+
+ self.obj_dict['name'] = quote_if_necessary(name)
+ self.obj_dict['port'] = port
+
+ self.create_attribute_methods(NODE_ATTRIBUTES)
+
+ def __str__(self):
+ return self.to_string()
+
+
+ def set_name(self, node_name):
+ """Set the node's name."""
+
+ self.obj_dict['name'] = node_name
+
+
+ def get_name(self):
+ """Get the node's name."""
+
+ return self.obj_dict['name']
+
+
+ def get_port(self):
+ """Get the node's port."""
+
+ return self.obj_dict['port']
+
+
+ def add_style(self, style):
+
+ styles = self.obj_dict['attributes'].get('style', None)
+ if not styles and style:
+ styles = [ style ]
+ else:
+ styles = styles.split(',')
+ styles.append( style )
+
+ self.obj_dict['attributes']['style'] = ','.join( styles )
+
+
+ def to_string(self):
+ """Return string representation of node in DOT language."""
+
+
+ # RMF: special case defaults for node, edge and graph properties.
+ #
+ node = quote_if_necessary(self.obj_dict['name'])
+
+ node_attr = list()
+
+ for attr in sorted(self.obj_dict['attributes']):
+ value = self.obj_dict['attributes'][attr]
+ if value == '':
+ value = '""'
+ if value is not None:
+ node_attr.append(
+ '%s=%s' % (attr, quote_if_necessary(value) ) )
+ else:
+ node_attr.append( attr )
+
+
+ # No point in having nodes setting any defaults if the don't set
+ # any attributes...
+ #
+ if node in ('graph', 'node', 'edge') and len(node_attr) == 0:
+ return ''
+
+ node_attr = ', '.join(node_attr)
+
+ if node_attr:
+ node += ' [' + node_attr + ']'
+
+ return node + ';'
+
+
+
+class Edge(Common):
+ """A graph edge.
+
+ This class represents a graph's edge with all its attributes.
+
+ edge(src, dst, attribute=value, ...)
+
+ src: source node
+ dst: destination node
+
+ `src` and `dst` can be specified as a `Node` object,
+ or as the node's name string.
+
+ All the attributes defined in the Graphviz dot language should
+ be supported.
+
+ Attributes can be set through the dynamically generated methods:
+
+ set_[attribute name], i.e. set_label, set_fontname
+
+ or directly by using the instance's special dictionary:
+
+ Edge.obj_dict['attributes'][attribute name], i.e.
+
+ edge_instance.obj_dict['attributes']['label']
+ edge_instance.obj_dict['attributes']['fontname']
+
+ """
+
+ def __init__(self, src='', dst='', obj_dict=None, **attrs):
+ self.obj_dict = dict()
+ if isinstance(src, Node):
+ src = src.get_name()
+ if isinstance(dst, Node):
+ dst = dst.get_name()
+ points = (quote_if_necessary(src),
+ quote_if_necessary(dst))
+ self.obj_dict['points'] = points
+ if obj_dict is None:
+ # Copy the attributes
+ self.obj_dict[ 'attributes' ] = dict( attrs )
+ self.obj_dict[ 'type' ] = 'edge'
+ self.obj_dict[ 'parent_graph' ] = None
+ self.obj_dict[ 'parent_edge_list' ] = None
+ self.obj_dict[ 'sequence' ] = None
+ else:
+ self.obj_dict = obj_dict
+ self.create_attribute_methods(EDGE_ATTRIBUTES)
+
+ def __str__(self):
+ return self.to_string()
+
+
+ def get_source(self):
+ """Get the edges source node name."""
+
+ return self.obj_dict['points'][0]
+
+
+ def get_destination(self):
+ """Get the edge's destination node name."""
+
+ return self.obj_dict['points'][1]
+
+
+ def __hash__(self):
+
+ return hash( hash(self.get_source()) +
+ hash(self.get_destination()) )
+
+
+ def __eq__(self, edge):
+ """Compare two edges.
+
+ If the parent graph is directed, arcs linking
+ node A to B are considered equal and A->B != B->A
+
+ If the parent graph is undirected, any edge
+ connecting two nodes is equal to any other
+ edge connecting the same nodes, A->B == B->A
+ """
+
+ if not isinstance(edge, Edge):
+ raise Error('Can not compare and '
+ 'edge to a non-edge object.')
+
+ if self.get_parent_graph().get_top_graph_type() == 'graph':
+
+ # If the graph is undirected, the edge has neither
+ # source nor destination.
+ #
+ if ( ( self.get_source() == edge.get_source() and
+ self.get_destination() == edge.get_destination() ) or
+ ( edge.get_source() == self.get_destination() and
+ edge.get_destination() == self.get_source() ) ):
+ return True
+
+ else:
+
+ if (self.get_source()==edge.get_source() and
+ self.get_destination()==edge.get_destination()):
+ return True
+
+ return False
+
+
+
+ def parse_node_ref(self, node_str):
+
+ if not isinstance(node_str, str):
+ return node_str
+
+ if node_str.startswith('"') and node_str.endswith('"'):
+
+ return node_str
+
+ node_port_idx = node_str.rfind(':')
+
+ if (node_port_idx>0 and node_str[0]=='"' and
+ node_str[node_port_idx-1]=='"'):
+
+ return node_str
+
+ if node_port_idx>0:
+
+ a = node_str[:node_port_idx]
+ b = node_str[node_port_idx+1:]
+
+ node = quote_if_necessary(a)
+
+ node += ':'+quote_if_necessary(b)
+
+ return node
+
+ return node_str
+
+
+ def to_string(self):
+ """Return string representation of edge in DOT language."""
+
+ src = self.parse_node_ref( self.get_source() )
+ dst = self.parse_node_ref( self.get_destination() )
+
+ if isinstance(src, frozendict):
+ edge = [ Subgraph(obj_dict=src).to_string() ]
+ elif isinstance(src, int):
+ edge = [ str(src) ]
+ else:
+ edge = [ src ]
+
+ if (self.get_parent_graph() and
+ self.get_parent_graph().get_top_graph_type() and
+ self.get_parent_graph().get_top_graph_type() == 'digraph' ):
+
+ edge.append( '->' )
+
+ else:
+ edge.append( '--' )
+
+ if isinstance(dst, frozendict):
+ edge.append( Subgraph(obj_dict=dst).to_string() )
+ elif isinstance(dst, int):
+ edge.append( str(dst) )
+ else:
+ edge.append( dst )
+
+
+ edge_attr = list()
+
+ for attr in sorted(self.obj_dict['attributes']):
+ value = self.obj_dict['attributes'][attr]
+ if value == '':
+ value = '""'
+ if value is not None:
+ edge_attr.append(
+ '%s=%s' % (attr, quote_if_necessary(value) ) )
+ else:
+ edge_attr.append( attr )
+
+ edge_attr = ', '.join(edge_attr)
+
+ if edge_attr:
+ edge.append( ' [' + edge_attr + ']' )
+
+ return ' '.join(edge) + ';'
+
+
+
+
+
+class Graph(Common):
+ """Class representing a graph in Graphviz's dot language.
+
+ This class implements the methods to work on a representation
+ of a graph in Graphviz's dot language.
+
+ graph( graph_name='G', graph_type='digraph',
+ strict=False, suppress_disconnected=False, attribute=value, ...)
+
+ graph_name:
+ the graph's name
+ graph_type:
+ can be 'graph' or 'digraph'
+ suppress_disconnected:
+ defaults to False, which will remove from the
+ graph any disconnected nodes.
+ simplify:
+ if True it will avoid displaying equal edges, i.e.
+ only one edge between two nodes. removing the
+ duplicated ones.
+
+ All the attributes defined in the Graphviz dot language should
+ be supported.
+
+ Attributes can be set through the dynamically generated methods:
+
+ set_[attribute name], i.e. set_size, set_fontname
+
+ or using the instance's attributes:
+
+ Graph.obj_dict['attributes'][attribute name], i.e.
+
+ graph_instance.obj_dict['attributes']['label']
+ graph_instance.obj_dict['attributes']['fontname']
+ """
+
+
+ def __init__(self, graph_name='G', obj_dict=None,
+ graph_type='digraph', strict=False,
+ suppress_disconnected=False, simplify=False, **attrs):
+
+ if obj_dict is not None:
+ self.obj_dict = obj_dict
+
+ else:
+
+ self.obj_dict = dict()
+
+ self.obj_dict['attributes'] = dict(attrs)
+
+ if graph_type not in ['graph', 'digraph']:
+ raise Error((
+ 'Invalid type "{t}". '
+ 'Accepted graph types are: '
+ 'graph, digraph').format(t=graph_type))
+
+
+ self.obj_dict['name'] = quote_if_necessary(graph_name)
+ self.obj_dict['type'] = graph_type
+
+ self.obj_dict['strict'] = strict
+ self.obj_dict['suppress_disconnected'] = suppress_disconnected
+ self.obj_dict['simplify'] = simplify
+
+ self.obj_dict['current_child_sequence'] = 1
+ self.obj_dict['nodes'] = dict()
+ self.obj_dict['edges'] = dict()
+ self.obj_dict['subgraphs'] = dict()
+
+ self.set_parent_graph(self)
+
+
+ self.create_attribute_methods(GRAPH_ATTRIBUTES)
+
+ def __str__(self):
+ return self.to_string()
+
+
+ def get_graph_type(self):
+
+ return self.obj_dict['type']
+
+
+ def get_top_graph_type(self):
+
+ parent = self
+ while True:
+ parent_ = parent.get_parent_graph()
+ if parent_ == parent:
+ break
+ parent = parent_
+
+ return parent.obj_dict['type']
+
+
+ def set_graph_defaults(self, **attrs):
+
+ self.add_node( Node('graph', **attrs) )
+
+
+ def get_graph_defaults(self, **attrs):
+
+ graph_nodes = self.get_node('graph')
+
+ if isinstance( graph_nodes, (list, tuple)):
+ return [ node.get_attributes() for node in graph_nodes ]
+
+ return graph_nodes.get_attributes()
+
+
+
+ def set_node_defaults(self, **attrs):
+
+ self.add_node( Node('node', **attrs) )
+
+
+ def get_node_defaults(self, **attrs):
+
+
+ graph_nodes = self.get_node('node')
+
+ if isinstance( graph_nodes, (list, tuple)):
+ return [ node.get_attributes() for node in graph_nodes ]
+
+ return graph_nodes.get_attributes()
+
+
+ def set_edge_defaults(self, **attrs):
+
+ self.add_node( Node('edge', **attrs) )
+
+
+
+ def get_edge_defaults(self, **attrs):
+
+ graph_nodes = self.get_node('edge')
+
+ if isinstance( graph_nodes, (list, tuple)):
+ return [ node.get_attributes() for node in graph_nodes ]
+
+ return graph_nodes.get_attributes()
+
+
+
+ def set_simplify(self, simplify):
+ """Set whether to simplify or not.
+
+ If True it will avoid displaying equal edges, i.e.
+ only one edge between two nodes. removing the
+ duplicated ones.
+ """
+
+ self.obj_dict['simplify'] = simplify
+
+
+
+ def get_simplify(self):
+ """Get whether to simplify or not.
+
+ Refer to set_simplify for more information.
+ """
+
+ return self.obj_dict['simplify']
+
+
+ def set_type(self, graph_type):
+ """Set the graph's type, 'graph' or 'digraph'."""
+
+ self.obj_dict['type'] = graph_type
+
+
+
+ def get_type(self):
+ """Get the graph's type, 'graph' or 'digraph'."""
+
+ return self.obj_dict['type']
+
+
+
+ def set_name(self, graph_name):
+ """Set the graph's name."""
+
+ self.obj_dict['name'] = graph_name
+
+
+
+ def get_name(self):
+ """Get the graph's name."""
+
+ return self.obj_dict['name']
+
+
+
+ def set_strict(self, val):
+ """Set graph to 'strict' mode.
+
+ This option is only valid for top level graphs.
+ """
+
+ self.obj_dict['strict'] = val
+
+
+
+ def get_strict(self, val):
+ """Get graph's 'strict' mode (True, False).
+
+ This option is only valid for top level graphs.
+ """
+
+ return self.obj_dict['strict']
+
+
+
+ def set_suppress_disconnected(self, val):
+ """Suppress disconnected nodes in the output graph.
+
+ This option will skip nodes in
+ the graph with no incoming or outgoing
+ edges. This option works also
+ for subgraphs and has effect only in the
+ current graph/subgraph.
+ """
+
+ self.obj_dict['suppress_disconnected'] = val
+
+
+
+ def get_suppress_disconnected(self, val):
+ """Get if suppress disconnected is set.
+
+ Refer to set_suppress_disconnected for more information.
+ """
+
+ return self.obj_dict['suppress_disconnected']
+
+
+ def get_next_sequence_number(self):
+
+ seq = self.obj_dict['current_child_sequence']
+
+ self.obj_dict['current_child_sequence'] += 1
+
+ return seq
+
+
+
+ def add_node(self, graph_node):
+ """Adds a node object to the graph.
+
+ It takes a node object as its only argument and returns
+ None.
+ """
+
+ if not isinstance(graph_node, Node):
+ raise TypeError(
+ 'add_node() received ' +
+ 'a non node class object: ' + str(graph_node))
+
+
+ node = self.get_node(graph_node.get_name())
+
+ if not node:
+
+ self.obj_dict['nodes'][graph_node.get_name()] = [
+ graph_node.obj_dict ]
+
+ #self.node_dict[graph_node.get_name()] = graph_node.attributes
+ graph_node.set_parent_graph(self.get_parent_graph())
+
+ else:
+
+ self.obj_dict['nodes'][graph_node.get_name()].append(
+ graph_node.obj_dict )
+
+ graph_node.set_sequence(self.get_next_sequence_number())
+
+
+
+ def del_node(self, name, index=None):
+ """Delete a node from the graph.
+
+ Given a node's name all node(s) with that same name
+ will be deleted if 'index' is not specified or set
+ to None.
+ If there are several nodes with that same name and
+ 'index' is given, only the node in that position
+ will be deleted.
+
+ 'index' should be an integer specifying the position
+ of the node to delete. If index is larger than the
+ number of nodes with that name, no action is taken.
+
+ If nodes are deleted it returns True. If no action
+ is taken it returns False.
+ """
+
+ if isinstance(name, Node):
+ name = name.get_name()
+
+ if name in self.obj_dict['nodes']:
+
+ if (index is not None and
+ index < len(self.obj_dict['nodes'][name])):
+ del self.obj_dict['nodes'][name][index]
+ return True
+ else:
+ del self.obj_dict['nodes'][name]
+ return True
+
+ return False
+
+
+ def get_node(self, name):
+ """Retrieve a node from the graph.
+
+ Given a node's name the corresponding Node
+ instance will be returned.
+
+ If one or more nodes exist with that name a list of
+ Node instances is returned.
+ An empty list is returned otherwise.
+ """
+
+ match = list()
+
+ if name in self.obj_dict['nodes']:
+
+ match.extend(
+ [Node(obj_dict=obj_dict)
+ for obj_dict in self.obj_dict['nodes'][name]])
+
+ return match
+
+
+ def get_nodes(self):
+ """Get the list of Node instances."""
+
+ return self.get_node_list()
+
+
+ def get_node_list(self):
+ """Get the list of Node instances.
+
+ This method returns the list of Node instances
+ composing the graph.
+ """
+
+ node_objs = list()
+
+ for node in self.obj_dict['nodes']:
+ obj_dict_list = self.obj_dict['nodes'][node]
+ node_objs.extend( [ Node( obj_dict = obj_d )
+ for obj_d in obj_dict_list ] )
+
+ return node_objs
+
+
+
+ def add_edge(self, graph_edge):
+ """Adds an edge object to the graph.
+
+ It takes a edge object as its only argument and returns
+ None.
+ """
+
+ if not isinstance(graph_edge, Edge):
+ raise TypeError(
+ 'add_edge() received a non edge class object: ' +
+ str(graph_edge))
+
+ edge_points = ( graph_edge.get_source(),
+ graph_edge.get_destination() )
+
+ if edge_points in self.obj_dict['edges']:
+
+ edge_list = self.obj_dict['edges'][edge_points]
+ edge_list.append(graph_edge.obj_dict)
+
+ else:
+
+ self.obj_dict['edges'][edge_points] = [ graph_edge.obj_dict ]
+
+
+ graph_edge.set_sequence( self.get_next_sequence_number() )
+
+ graph_edge.set_parent_graph( self.get_parent_graph() )
+
+
+
+ def del_edge(self, src_or_list, dst=None, index=None):
+ """Delete an edge from the graph.
+
+ Given an edge's (source, destination) node names all
+ matching edges(s) will be deleted if 'index' is not
+ specified or set to None.
+ If there are several matching edges and 'index' is
+ given, only the edge in that position will be deleted.
+
+ 'index' should be an integer specifying the position
+ of the edge to delete. If index is larger than the
+ number of matching edges, no action is taken.
+
+ If edges are deleted it returns True. If no action
+ is taken it returns False.
+ """
+
+ if isinstance( src_or_list, (list, tuple)):
+ if dst is not None and isinstance(dst, int):
+ index = dst
+ src, dst = src_or_list
+ else:
+ src, dst = src_or_list, dst
+
+ if isinstance(src, Node):
+ src = src.get_name()
+
+ if isinstance(dst, Node):
+ dst = dst.get_name()
+
+ if (src, dst) in self.obj_dict['edges']:
+
+ if (index is not None and
+ index < len(self.obj_dict['edges'][(src, dst)])):
+ del self.obj_dict['edges'][(src, dst)][index]
+ return True
+ else:
+ del self.obj_dict['edges'][(src, dst)]
+ return True
+
+ return False
+
+
+ def get_edge(self, src_or_list, dst=None):
+ """Retrieved an edge from the graph.
+
+ Given an edge's source and destination the corresponding
+ Edge instance(s) will be returned.
+
+ If one or more edges exist with that source and destination
+ a list of Edge instances is returned.
+ An empty list is returned otherwise.
+ """
+
+ if isinstance( src_or_list, (list, tuple)) and dst is None:
+ edge_points = tuple(src_or_list)
+ edge_points_reverse = (edge_points[1], edge_points[0])
+ else:
+ edge_points = (src_or_list, dst)
+ edge_points_reverse = (dst, src_or_list)
+
+ match = list()
+
+ if edge_points in self.obj_dict['edges'] or (
+ self.get_top_graph_type() == 'graph' and
+ edge_points_reverse in self.obj_dict['edges']):
+
+ edges_obj_dict = self.obj_dict['edges'].get(
+ edge_points,
+ self.obj_dict['edges'].get( edge_points_reverse, None ))
+
+ for edge_obj_dict in edges_obj_dict:
+ match.append(
+ Edge(edge_points[0],
+ edge_points[1],
+ obj_dict=edge_obj_dict))
+
+ return match
+
+
+ def get_edges(self):
+ return self.get_edge_list()
_______________________________________________
pypy-commit mailing list
pypy-commit@python.org
https://mail.python.org/mailman/listinfo/pypy-commit
