#!/usr/bin/python
# -*- coding: Latin-1 -*-
"""Convert graphviz graphs to LaTeX-friendly formats

Various tools for converting graphs generated by the graphviz library
to formats for use with LaTeX.

Copyright (c) 2006-2007, Kjell Magne Fauske

"""

# Copyright (c) 2006-2007, Kjell Magne Fauske
#
# Permission is hereby granted, free of charge, to any person obtaining a copy
# of this software and associated documentation files (the "Software"), to
# deal in the Software without restriction, including without limitation the
# rights to use, copy, modify, merge, publish, distribute, sublicense, and/or
# sell copies of the Software, and to permit persons to whom the Software is
# furnished to do so, subject to the following conditions:
#
# The above copyright notice and this permission notice shall be included in
# all copies or substantial portions of the Software.
#
# THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND, EXPRESS OR
# IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF MERCHANTABILITY,
# FITNESS FOR A PARTICULAR PURPOSE AND NONINFRINGEMENT. IN NO EVENT SHALL THE
# AUTHORS OR COPYRIGHT HOLDERS BE LIABLE FOR ANY CLAIM, DAMAGES OR OTHER
# LIABILITY, WHETHER IN AN ACTION OF CONTRACT, TORT OR OTHERWISE, ARISING
# FROM, OUT OF OR IN CONNECTION WITH THE SOFTWARE OR THE USE OR OTHER DEALINGS
# IN THE SOFTWARE.

__author__ = 'Kjell Magne Fauske'
__version__ = '2.7.0'
__license__ = 'MIT'

        
from itertools import izip
from optparse import OptionParser
import optparse
import sys, tempfile, os, string,re
import logging
import tempfile
from StringIO import StringIO

# intitalize logging module
log = logging.getLogger("dot2tex")
console = logging.StreamHandler()
console.setLevel(logging.WARNING)
# set a format which is simpler for console use
formatter = logging.Formatter('%(levelname)-8s %(message)s')
# tell the handler to use this format
console.setFormatter(formatter)
log.addHandler(console)


try:
    import pydot
except:
    log.error("Could not load the pydot module.")
    sys.exit(1)

DEFAULT_TEXTENCODING = 'utf8'
DEFAULT_OUTPUT_FORMAT = 'pgf'

# label margins in inches
DEFAULT_LABEL_XMARGIN = 0.11
DEFAULT_LABEL_YMARGIN = 0.055
DEFAULT_EDGELABEL_XMARGIN = 0.01
DEFAULT_EDGELABEL_YMARGIN = 0.01
DEFAULT_GRAPHLABEL_XMARGIN = 0.01
DEFAULT_GRAPHLABEL_YMARGIN = 0.01

DEFAULT_NODE_WIDTH = 0.75
DEFAULT_NODE_HEIGHT = 0.5


# Todo: set papersize based on bb
# Todo: Fontcolor

# Todo: Support linewidth in draw string
# Todo: Support linestyle in draw string
# Todo: Need to reconsider edge draw order.
# See for instance html2.xdot


# Inch to bp conversion factor
in2bp = 72.0

# Examples of draw strings
# c 5 -black F 14.000000 11 -Times-Roman T 99 159 0 44 8 -a_1 test


special_chars = ['$','\\','%','_','#','{',r'}','^','&']
special_chars_escape = [r'\$', r'$\backslash$',r'\%',r'\_',r'\#',
                        r'\{',r'\}',r'\^{}',r'\&']
charmap = dict(zip(special_chars,special_chars_escape))

# Pydot has hardcoded Graphviz' graph, node and edge attributes.
# Dot2tex extends the DOT language with several new attributes. Fortunately
# it is possible to modify pydot at runtime to accept the new attributes.
special_graph_attrs = [
    'd2tdocpreamble',
    'd2tfigpreamble',
    'd2tfigpostamble',
    'd2tgraphstyle',
    'd2talignstr',
    'd2tvalignmode',
    'd2tnominsize',
    'texlbl',
    'd2ttikzedgelabels',
    'd2toutputformat',
    'd2tstyleonly',
    'd2tnodeoptions',
    'd2tedgeoptions',
    'd2toptions',
]

special_nodeandedge_attrs = [
    'texmode',
    'texlbl',
    'lblstyle',
    'topath',
    'exstyle',
]

# Modify pydot to understand dot2tex's extensions to the DOT language
pydot.Graph.attributes.extend(special_graph_attrs)
pydot.Edge.attributes.extend(special_nodeandedge_attrs)
pydot.Node.attributes.extend(special_nodeandedge_attrs)

helpmsg = """\
Failed to parse the input data. Is it a valid dot file?
Try to input xdot data directly. Example:
    dot -Txdot file.dot | dot2tex > file.tex

If this does not work, check that you have an updated version of PyParsing and
Graphviz. Users have reported problems with old versions. You can also run
dot2tex in debug mode using the --debug option:
    dot2tex --debug file.dot
A file dot2tex.log will be written to the current directory with detailed
information useful for debugging."""

def mreplace(s, chararray, newchararray):
    for a, b in zip(chararray, newchararray):
        s = s.replace(a, b)
    return s

def escapeTeXChars(string):
    r"""Escape the special LaTeX-chars %{}_^

    Examples:
        
    >>> escapeTeXChars('10%')
    '10\\%'
    >>> escapeTeXChars('%{}_^\\$')
    '\\%\\{\\}\\_\\^{}$\\backslash$\\$'
    """
    return "".join([charmap.get(c,c) for c in string])
    

def nsplit(seq, n=2):
    """Split a sequence into pieces of length n

    If the lengt of the sequence isn't a multiple of n, the rest is discareded.
    Note that nsplit will strings into individual characters.

    Examples:
    >>> nsplit('aabbcc')
    [('a', 'a'), ('b', 'b'), ('c', 'c')]
    >>> nsplit('aabbcc',n=3)
    [('a', 'a', 'b'), ('b', 'c', 'c')]
    
    # Note that cc is discarded
    >>> nsplit('aabbcc',n=4)
    [('a', 'a', 'b', 'b')]
    """
    return [xy for xy in izip(*[iter(seq)]*n)]

def chunks(s, cl):
    """Split a string or sequence into pieces of length cl and return an iterator
    """
    for i in xrange(0, len(s), cl):
        yield s[i:i+cl]
    
def replaceTags(template, tags, tagsreplace):
    """Replace occurences of tags with tagreplace

    Example:
    >>> replaceTags('a b c d',('b','d'),{'b':'bbb','d':'ddd'})
    'a bbb c ddd'
    """
    s = template
    for tag in tags:
        replacestr = tagsreplace.get(tag, '')
        if not replacestr:
            replacestr = ''
        s = s.replace(tag, replacestr)
    return s

def getboolattr(item, key, default):
    if str(getattr(item,key,'')).lower() == 'true':
        return True
    else:
        return False

def createXdot(dotdata,prog='dot'):
    # The following code is from the pydot module written by Ero Carrera
    progs = pydot.find_graphviz()
    
    #prog = 'dot'
    if progs is None:
        return None
    if not progs.has_key(prog):
        log.warning('Invalid prog=%s',prog)
        # Program not found ?!?!
        return None

    tmp_fd, tmp_name = tempfile.mkstemp()
    os.close(tmp_fd)
    f = open(tmp_name,'w')
    f.write(dotdata)
    f.close()
    format = 'xdot'
    cmd = progs[prog]+' -T'+format+' '+tmp_name
    log.debug('Creating xdot data with: %s',cmd)
    stdin, stdout, stderr = os.popen3(cmd,'t')
    stdin.close()
    stderr.close()
    
    # I'm not quite sure why this is necessary, but some files
    # produces data with line endings that confuses pydot/pyparser.
    data = stdout.readlines()
    lines = [line for line in data if line.strip()]
    data = "".join(lines)
    
    stdout.close()
    os.unlink(tmp_name)
    
    return data

def parseDotData(dotdata):
    """Wrapper for pydot.graph_from_dot_data

    Redirects error messages to the log.
    """
    saveout = sys.stdout
    fsock = StringIO()
    sys.stdout = fsock
    graph = pydot.graph_from_dot_data(dotdata)
    log.debug('Output from pydot:\n'+fsock.getvalue())
    fsock.close()
    sys.stdout = sys.__stdout__
    return graph

def parseDrawString(drawstring):
    """Parse drawstring and returns a list of draw operations"""
    # The draw string parser is a bit clumsy and slow
    def doeE(c,s):
        # E x0 y0 w h  Filled ellipse ((x-x0)/w)^2 + ((y-y0)/h)^2 = 1
        # e x0 y0 w h  Unfilled ellipse ((x-x0)/w)^2 + ((y-y0)/h)^2 = 1
        tokens = s.split()[0:4]
        if not tokens: return None
        points = map(int,tokens)
        didx = sum(map(len,tokens))+len(points)+1
        return didx, (c , points[0], points[1], points[2], points[3])
    
    def doPLB(c, s):
        # P n x1 y1 ... xn yn  Filled polygon using the given n points
        # p n x1 y1 ... xn yn  Unfilled polygon using the given n points
        # L n x1 y1 ... xn yn  Polyline using the given n points
        # B n x1 y1 ... xn yn  B-spline using the given n control points
        # b n x1 y1 ... xn yn  Filled B-spline using the given n control points
        tokens = s.split()
        n = int(tokens[0])
        points = map(int,tokens[1:n*2+1])
        didx = sum(map(len,tokens[1:n*2+1]))+n*2+2
        npoints = nsplit(points, 2)
        return didx, (c, npoints)
    
    def doCS(c,s):
        # C n -c1c2...cn  Set fill color. 
        # c n -c1c2...cn  Set pen color.
        # Graphviz uses the following color formats:
        #   "#%2x%2x%2x"    Red-Green-Blue (RGB)
        #   "#%2x%2x%2x%2x" Red-Green-Blue-Alpha (RGBA)
        #   H[, ]+S[, ]+V   Hue-Saturation-Value (HSV) 0.0 <= H,S,V <= 1.0
        #   string  color name
        tokens = s.split()
        n = int(tokens[0])
        tmp = len(tokens[0])+3
        d = s[tmp:tmp+n]
        didx = len(d)+tmp+1
        return didx, (c, d)
    
    def doFont(c,s):
        # F s n -c1c2...cn
        # Set font. The font size is s points. The font name consists of
        # the n characters following '-'.
        tokens = s.split()
        size = tokens[0]
        n = int(tokens[1])
        tmp = len(size)+len(tokens[1])+4
        d = s[tmp:tmp+n]
        didx = len(d)+tmp
        return didx, (c, size, d)
    
    def doText(c,s):
        # T x y j w n -c1c2...cn
        # Text drawn using the baseline point (x,y). The text consists of the
        # n characters following '-'. The text should be left-aligned
        #(centered, right-aligned) on the point if j is -1 (0, 1), respectively.
        # The value w gives the width of the text as computed by the library.
        tokens = s.split()
        x, y, j, w = tokens[0:4]
        n = int(tokens[4])
        tmp = sum(map(len,tokens[0:5]))+7
        text = s[tmp:tmp+n]
        didx = len(text)+tmp
        return didx, [c, x, y, j, w, text]

    cmdlist = []
    stat = {}
    idx = 0
    s = drawstring.strip()
    while idx < len(s)-1:
        didx = 1
        c = s[idx]
        stat[c] = stat.get(c,0)+1
        try:
            if c in ('e','E'):
                didx, cmd = doeE(c,s[idx+1:])
                cmdlist.append(cmd)
            elif c in ('p','P','L','b','B'):
                didx, cmd = doPLB(c, s[idx+1:])
                cmdlist.append(cmd)
            elif c in ('c','C','S'):
                didx, cmd = doCS(c, s[idx+1:])
                cmdlist.append(cmd)
            elif c == 'F':
                didx, cmd = doFont(c, s[idx+1:])
                cmdlist.append(cmd)
            elif c == 'T':
                didx, cmd = doText(c, s[idx+1:])
                cmdlist.append(cmd)
                
        except:
            pass
            
        idx += didx
    return cmdlist,stat



def getGraphList(gg, l = []):
    """Traverse a graph with subgraphs and return them as a list"""
    if not l:
        outer = True
    else:
        outer = False
    l.append(gg)
    if gg.subgraph_list:
        for g in gg.subgraph_list:
            getGraphList(g,l)
    if outer: return l

class EndOfGraphElement:
    def __init__(self):
        pass

def getAllGraphElements(graph, l=[]):
    """Return all nodes and edges, including elements in subgraphs"""
    if not l:
        outer = True
        l.append(graph)
    else:
        outer = False
    for element in graph.sorted_graph_elements:
        if isinstance(element, pydot.Node):
            l.append(element)
        elif isinstance(element,pydot.Edge):
            l.append(element)
        elif isinstance(element, pydot.Graph):
            l.append(element)
            getAllGraphElements(element,l)
        else:
            log.warning('Unknown graph element')
            
    if outer:
        return l
    else:
        l.append(EndOfGraphElement())


class DotConvBase:
    """Dot2TeX converter base"""
    def __init__(self, options = {}):
        self.color = ""
        self.template = options.get('template','')
        self.textencoding = options.get('encoding',DEFAULT_TEXTENCODING)
        self.templatevars = {}
        self.body = ""
        if options.get('templatefile',''):
            self.loadTemplate(options['templatefile'])

        self.options = options
        if options.get('texpreproc',False) or options.get('autosize',False):
            self.dopreproc = True
        else:
            self.dopreproc = False

    def loadTemplate(self, templatefile):
        try:
            self.template = open(templatefile).read()
        except:
            pass
        
    def convertFile(self, filename):
        """Load dot file and convert"""
        pass
    
    def startFig(self):
        return ""
    
    def endFig(self):
        return ""
    
    def drawEllipse(self, drawop, style = None):
        return ""

    def drawBezier(self, drawop, style = None):
        return ""
    
    def drawPolygon(self, drawop, style = None):
        return ""
    
    def drawPolyLine(self, drawop, style = None):
        return ""
    
    def drawText(self, drawop, style = None):
        return ""
    
    def outputNodeComment(self, node):
        return "  %% Node: %s\n" % node.name
    
    def outputEdgeComment(self, edge):
        src = edge.get_source()
        dst = edge.get_destination()
        if self.directedgraph:
            edge = '->'
        else:
            edge = '--'
        return "  %% Edge: %s %s %s\n" % (src, edge, dst)
    
    def setColor(self, node):
        return ""
    
    def setStyle(self, node):
        return ""
    
    def drawEdge(self, edge):
        return ""
    
    def startNode(self, node):
        return ""
    def endNode(self,node):
        return ""
    def startGraph(self, graph):
        return ""
    def endGraph(self,graph):
        return ""
    
    def startEdge(self):
        return ""
    
    def endEdge(self):
        return ""
    
    def filterStyles(self, style):
        return style
    
    def convertColor(self, drawopcolor,pgf=False):
        """Convert color to a format usable by LaTeX and XColor"""
        # Graphviz uses the following color formats:
        #   "#%2x%2x%2x"    Red-Green-Blue (RGB)
        #   "#%2x%2x%2x%2x" Red-Green-Blue-Alpha (RGBA)
        #   H[, ]+S[, ]+V   Hue-Saturation-Value (HSV) 0.0 <= H,S,V <= 1.0
        #   string  color name
        
        # Is the format RBG(A)?
        if drawopcolor.startswith('#'):
            t = list(chunks(drawopcolor[1:],2))
            # parallell lines not yet supported
            if len(t) > 6:
                t = t[0:3]
            rgb = [(round((int(n,16)/255.0),2)) for n in t]
            if pgf:
                colstr = "{rgb}{%s,%s,%s}" % tuple(rgb[0:3])
                opacity = "1"
                if len(rgb)==4:
                    opacity = rgb[3]
                return (colstr, opacity)
            else:
                return "[rgb]{%s,%s,%s}" % tuple(rgb[0:3])
            
        elif (len(drawopcolor.split(' '))==3) or (len(drawopcolor.split(','))==3):
            # are the values space or comma separated?
            hsb = drawopcolor.split(',')
            if not len(hsb) == 3:
                hsb = drawopcolor.split(' ')
            if pgf:
                return "{hsb}{%s,%s,%s}" % tuple(hsb)
            else:
                return "[hsb]{%s,%s,%s}" % tuple(hsb)
        else:
            drawopcolor = drawopcolor.replace('grey','gray')
            drawopcolor = drawopcolor.replace('_','')
            drawopcolor = drawopcolor.replace(' ','')
            return drawopcolor

    

    def doDrawString(self, drawstring, drawobj):
        """Parse and draw drawsting

        Just a wrapper around doDrawOp.
        """
        drawoperations,stat = parseDrawString(drawstring)
        return self.doDrawOp(drawoperations, drawobj,stat)
    
    def doDrawOp(self, drawoperations, drawobj,stat):
        """Excecute the operations in drawoperations"""
        s = ""
        for drawop in drawoperations:
            op = drawop[0]
            style = getattr(drawobj, 'style',None)
            # styles are not passed to the draw operations in the
            # duplicate mode
            if style and not self.options.get('duplicate', False):
                # map Graphviz styles to backend styles
                style = self.filterStyles(style)
                styles = [self.styles.get(key.strip(),key.strip()) \
                            for key in style.split(',') if key]
                style = ','.join(styles)
            else:
                style = None

            if op in ['e','E']:
                s += self.drawEllipse(drawop, style)
            elif op in ['p','P']:
                s += self.drawPolygon(drawop, style)
            elif op == 'L':
                s += self.drawPolyLine(drawop, style)
            elif op in ['C','c']:
                s += self.setColor(drawop)
            elif op == 'S':
                s += self.setStyle(drawop)
            elif op in ['B']:
                s += self.drawBezier(drawop, style)
            elif op in ['T']:
                # Need to decide what to do with the text
                # Note that graphviz removes the \ character from the draw
                # string. Use \\ instead
                # Todo: Use text from node|edge.label or name
                # Todo: What about multiline labels?
                text = drawop[5]
##                label = getattr(drawobj,'label','\N')
##                multiline = False
##                if label:
##                    if label.find(r'\n') >= 0:
##                        multiline = True
##                        #print label
##                else:
##                    label = "\N"
##                if not multiline and label <> '\N':
##                    text =  drawobj.label
                texmode = self.options.get('texmode','verbatim')
                if getattr(drawobj,'texmode', ''):
                    texmode = drawobj.texmode
                if getattr(drawobj,'texlbl', ''):
                    # the texlbl overrides everything
                    text = drawobj.texlbl
                elif texmode == 'verbatim':
                    # verbatim mode
                    text = escapeTeXChars(text)
                    pass
                elif texmode == 'math':
                    # math mode
                    text = "$%s$" % text

                drawop[5] = text
                if self.options.get('alignstr',''):
                    drawop.append(self.options.get('alignstr'))
                if stat['T'] == 1 and \
                    self.options.get('valignmode','center')=='center':
                    # do this for single line only
                    # Todo: Make this optional
                    pos = getattr(drawobj,'lp',None) or \
                          getattr(drawobj,'pos',None)
                    if pos:
                        coord = pos.split(',')
                        if len(coord)==2:
                            drawop[1] = coord[0]
                            drawop[2] = coord[1]
                        pass
                lblstyle = getattr(drawobj,'lblstyle',None)
                exstyle = getattr(drawobj,'exstyle','')
                if exstyle:
                    if lblstyle:
                        lblstyle += ',' +exstyle
                    else:
                        lblstyle = exstyle
                s += self.drawText(drawop,lblstyle)
        return s

    def doNodes(self):
        s = ""
        for node in self.nodes:
            self.currentnode = node
            dstring = getattr(node,'_draw_',"")
            lstring = getattr(node,'_ldraw_',"")
            
            
            drawstring = dstring+" "+lstring
            
            if not drawstring.strip(): continue
            # detect node type
            shape = node.shape
            if not shape:
                shape = 'ellipse' # default
            # extract size information
            x,y = node.pos.split(',')
            
            # width and height are in inches. Convert to bp units
            w = float(node.width)*in2bp
            h = float(node.height)*in2bp
            
            s += self.outputNodeComment(node)
            s += self.startNode(node)
            #drawoperations = parseDrawString(drawstring)
            s += self.doDrawString(drawstring, node)
            s += self.endNode(node)
        self.body += s
        
    def getEdgePoints(self, edge):
        points = edge.pos.split(' ')
        # check direction
        arrowstyle = '--'
        i = 0
        if points[i].startswith('s'):
            p = points[0].split(',')
            tmp = "%s,%s" % (p[1],p[2])
            if points[1].startswith('e'):
                points[2] =tmp
            else:
                points[1] = tmp
            del points[0]
            arrowstyle = '<-'
            i += 1
        if points[0].startswith('e'):
            p = points[0].split(',')
            points.pop()
            points.append("%s,%s" % (p[1],p[2]))
            del points[0]
            arrowstyle = '->'
            i += 1
        if i>1: arrowstyle = '<->'
        return arrowstyle, points

    def doEdges(self):
        s = ""
        s += self.setColor(('cC',"black"))
        for edge in self.edges:
            dstring = getattr(edge,'_draw_',"")
            lstring = getattr(edge,'_ldraw_',"")
            hstring = getattr(edge,'_hdraw_',"")
            tstring = getattr(edge,'_tdraw_',"")
            tlstring = getattr(edge,'_tldraw_',"")
            hlstring = getattr(edge,'_hldraw_',"")
            
            # Note that the order of the draw strings should be the same
            # as in the xdot output.
            drawstring = dstring + " " + hstring + " " + tstring \
                            + " " + lstring + " " + tlstring + " " + hlstring
            drawop,stat = parseDrawString(drawstring);
            if not drawstring.strip():
                continue
            s += self.outputEdgeComment(edge)
            if self.options.get('duplicate', False):
                s += self.startEdge()
                s += self.doDrawOp(drawop, edge,stat)
                s += self.endEdge()
            else:
                s += self.drawEdge(edge)
                s += self.doDrawString(lstring+" "+tlstring+" "+hlstring, edge)
        self.body += s
        
    def doGraph(self):
        dstring = getattr(self.graph,'_draw_',"")
        lstring = getattr(self.graph,'_ldraw_',"")
        # print lstring
        # Avoid filling background of graphs with white
        if dstring.startswith('c 5 -white C 5 -white') \
            and not getattr(self.graph,'style'):
            dstring = ''
        if getattr(self.graph,'_draw_',None):
            # bug
            dstring = "c 5 -black " + dstring #self.graph._draw_
            pass
        drawstring = dstring+" "+lstring
        if drawstring.strip(): 
            s = self.startGraph(self.graph)
            g = self.doDrawString(drawstring, self.graph)
            e = self.endGraph(self.graph)
            if g.strip():
                self.body += s +g + e

    def setOptions(self):
        # process options
        # Warning! If graph attribute is true and command line option is false,
        # the graph attribute will be used. Command line option should have
        # precedence.
        self.options['alignstr'] = self.options.get('alignstr','') \
            or getattr(self.maingraph,'d2talignstr','')

        # Todo: bad!
        self.options['valignmode'] = getattr(self.maingraph,'d2tvalignmode','')\
            or self.options.get('valignmode','center')


    def convert(self, dotdata):
        # parse data processed by dot.
        log.debug('Start conversion')
        try:
            try:
                maingraph = parseDotData(dotdata)
            except:
                log.info('Failed first attempt to parse graph')
                if not self.dopreproc:
                    log.info('Could not parse input dotdata directly. '
                             'Trying to create xdot data.')
                    try:
                        tmpdata = createXdot(dotdata,self.options.get('prog','dot'))
                        log.debug('xdotdata:\n'+tmpdata)
                        maingraph = parseDotData(tmpdata)
                    except:
                        raise

            if not self.dopreproc and not hasattr(maingraph,'xdotversion'):
                # Older versions of Graphviz does not include the xdotversion
                # attribute
                if not (dotdata.find('_draw_') > 0 or dotdata.find('_ldraw_') > 0):
                    # need to convert to xdot format
                    # Warning. Pydot will not include custom attributes
                    log.debug('Trying to create xdotdata')
                    
                    tmpdata = createXdot(dotdata,self.options.get('prog','dot'))
                    log.debug('xdotdata:\n'+tmpdata)
                    if tmpdata == None or not tmpdata.strip():
                        log.error('Failed to create xdotdata. Is Graphviz installed?')
                        sys.exit(1)
                    maingraph = parseDotData(tmpdata)
                else:
                    # old version
                    pass
               
            self.maingraph = maingraph
            self.pencolor = ""
            self.fillcolor = ""
            self.linewidth = 1
            # Detect graph type
            if maingraph.graph_type == 'digraph':
                self.directedgraph = True
            else:
                self.directedgraph = False
        except:
            log.error(helpmsg)
            sys.exit(1)
            raise
        if self.dopreproc:
            return self.doPreviewPreproc()
        
        # Romove annoying square
        # Todo: Remove squares from subgraphs. See pgram.dot
        dstring = getattr(self.maingraph,'_draw_',"")
        if dstring:
            self.maingraph._draw_ = ""

        setDotAttr(self.maingraph)
        self.setOptions()
            
        # A graph can consists of nested graph. Extract all graphs
        graphlist = getGraphList(self.maingraph, [])
    
        self.body += self.startFig()

        # To get correct drawing order we need to iterate over the graphs
        # multiple times. First we draw the graph graphics, then nodes and
        # finally the edges.

        # todo: support the outputorder attribute
        for graph in graphlist:
            self.graph = graph
            self.doGraph()

        if not self.options.get('flattengraph',False):
            for graph in graphlist:
                self.graph = graph
                self.nodes = cleanDotNodes(graph)
                self.edges = graph.edge_list
                if not self.options.get('switchdraworder',False):
                    self.doEdges() # tmp
                    self.doNodes()
                else:
                    self.doNodes()
                    self.doEdges()
        else:
            nodelist = []
            edgelist = []
            for graph in graphlist:
                self.graph = graph
                nodelist.extend(cleanDotNodes(graph))
                edgelist.extend(graph.edge_list)
            self.nodes = nodelist
            self.edges = edgelist
            if not self.options.get('switchdraworder',False):
                self.doEdges() # tmp
                self.doNodes()
            else:
                self.doNodes()
                self.doEdges()
            
        self.body += self.endFig()
        return self.output()
    
    def cleanTemplate(self, template):
        """Remove preprocsection or outputsection"""
        if not self.dopreproc and self.options.get('codeonly',False):
            r = re.compile('<<startcodeonlysection>>(.*?)<<endcodeonlysection>>',
                    re.DOTALL | re.MULTILINE)
            m = r.search(template)
            if m:
                return m.group(1).strip()
        if not self.dopreproc and self.options.get('figonly',False):
            r = re.compile('<<startfigonlysection>>(.*?)<<endfigonlysection>>',
                    re.DOTALL | re.MULTILINE)
            m = r.search(template)
            if m:
                return m.group(1)

        
        if self.dopreproc:
            r = re.compile('<<startoutputsection>>.*?<<endoutputsection>>',
                    re.DOTALL | re.MULTILINE)
        else:
            r = re.compile('<<startpreprocsection>>.*?<<endpreprocsection>>',
                    re.DOTALL | re.MULTILINE)
        # remove codeonly and figonly section
        r2 = re.compile('<<startfigonlysection>>.*?<<endfigonlysection>>',
                    re.DOTALL | re.MULTILINE)
        tmp = r2.sub('',template)
        r2 = re.compile('<<startcodeonlysection>>.*?<<endcodeonlysection>>',
                    re.DOTALL | re.MULTILINE)
        tmp = r2.sub('',tmp)
        return r.sub('',tmp)

    def initTemplateVars(self):
        vars = {}
        # get bounding box
        bbstr = self.maingraph.bb
        if bbstr:
            bb = bbstr.split(',')
            vars['<<bbox>>'] = "(%sbp,%sbp)(%sbp,%sbp)\n" % (bb[0],bb[1],bb[2],bb[3])
            vars['<<bbox.x0>>'] = bb[0]
            vars['<<bbox.y0>>'] = bb[1]
            vars['<<bbox.x1>>'] = bb[2]
            vars['<<bbox.y1>>'] = bb[3]
        vars['<<figcode>>'] = self.body.strip()
        vars['<<drawcommands>>'] = self.body.strip()
        vars['<<textencoding>>'] = self.textencoding
        docpreamble = self.options.get('docpreamble','') \
            or getattr(self.maingraph, 'd2tdocpreamble','')
##        if docpreamble:
##            docpreamble = docpreamble.replace('\\n','\n')
        vars['<<docpreamble>>'] = docpreamble
        vars['<<figpreamble>>'] = self.options.get('figpreamble','') \
            or getattr(self.maingraph, 'd2tfigpreamble','%')
        vars['<<figpostamble>>'] = self.options.get('figpostamble','') \
            or getattr(self.maingraph, 'd2tfigpostamble','')
        vars['<<graphstyle>>'] = self.options.get('graphstyle','') \
            or getattr(self.maingraph, 'd2tgraphstyle','')
        vars['<<margin>>'] = self.options.get('margin','0pt')
        vars['<<startpreprocsection>>'] = vars['<<endpreprocsection>>'] = ''
        vars['<<startoutputsection>>'] = vars['<<endoutputsection>>'] = ''
        if self.options.get('gvcols',False):
            vars['<<gvcols>>'] = "\input{gvcols.tex}"
        else:
            vars['<<gvcols>>'] = ""
        self.templatevars = vars
            
    def output(self):
        self.initTemplateVars()
        template = self.cleanTemplate(self.template)
        code = replaceTags(template ,self.templatevars.keys(),
                           self.templatevars)
        #code = self.template.replace('<<figcode>>', self.body)
        return code
    
    def getLabel(self, drawobj):
        text = ""
        texmode = self.options.get('texmode','verbatim')
        if getattr(drawobj,'texmode', ''):
            texmode = drawobj.texmode
        text = getattr(drawobj,'label',None)
        
        #log.warning('text %s %s',text,drawobj.to_string())
        
        if text == None or text.strip() == '\N':
            
            if not isinstance(drawobj, pydot.Edge):
                text = getattr(drawobj,'name',None) or \
                    getattr(drawobj,'graph_name','')
            else:
                text = ''
        elif text.strip() == '\N':
            text =  ''
        else:
            text = text.replace("\\\\","\\")
        
        if getattr(drawobj,'texlbl', ''):
            # the texlbl overrides everything
            text = drawobj.texlbl
        elif texmode == 'verbatim':
            # verbatim mode
            text = escapeTeXChars(text)
            pass
        elif texmode == 'math':
            # math mode
            text = "$%s$" % text
        
        return text

    # temp
    def getLabeld(self, drawobj):
        text = ""
        texmode = self.options.get('texmode','verbatim')
        if drawobj.get('texmode', ''):
            texmode = drawobj["texmode"]
        text = drawobj.get('label',None)
        if text == None or text.strip() == '\N':
            text = drawobj.get('name',None) or \
                drawobj.get('graph_name','')
        else:
            text = text.replace("\\\\","\\")

        if drawobj.get('texlbl', ''):
            # the texlbl overrides everything
            text = drawobj["texlbl"]
        elif texmode == 'verbatim':
            # verbatim mode
            text = escapeTeXChars(text)
            pass
        elif texmode == 'math':
            # math mode
            text = "$%s$" % text
        return text

    def getNodePreprocCode(self, node):
        return node['texlbl']

    def getEdgePreprocCode(self,edge):
        return edge.texlbl

    def getGraphPreprocCode(self,graph):
        return graph.texlbl
        

    def getMargins(self, element):
        """Return element margins"""
        margins = element.__dict__.get('margin',None)
        #print margins
        #print type(margins)
        if margins:
            margins = margins.split(',')
            if len(margins) == 1:
                xmargin = ymargin = float(margins[0])
            else:
                xmargin = float(margins[0])
                ymargin = float(margins[1])
        else:
            # use default values
            if isinstance(element,pydot.Edge):
                xmargin = DEFAULT_EDGELABEL_XMARGIN
                ymargin = DEFAULT_EDGELABEL_YMARGIN
            else:
                xmargin = DEFAULT_LABEL_XMARGIN
                ymargin = DEFAULT_LABEL_YMARGIN
        return (xmargin, ymargin)

    # Todo: Add support for head and tail labels!
    # Todo: Support rect nodes if possible.
    def doPreviewPreproc(self):
        setDotAttr(self.maingraph)
        self.initTemplateVars()
        template = self.cleanTemplate(self.template)
        template = replaceTags(template ,self.templatevars.keys(),
                           self.templatevars)
        pp = TeXDimProc(template, self.options)
        processednodes = {}
        processededges = {}
        processedgraphs = {}
        
        usednodes = {}
        usededges = {}
        usedgraphs = {}
        # iterate over every element in the graph
        counter = 0
        for element in getAllGraphElements(self.maingraph,[]):
            if isinstance(element, pydot.Node):
                # is it a node statement?
                node = element
                if node.name.startswith('"'):
                    node_stmt = True
                else:
                    # node defined in a edge statement (edge_stmt)
                    node_stmt = False
                name = node.name.replace('"','')
                if node_stmt:
                    node.name=name
                #print node.texmode
                if name=='node' or name=='edge' or name=='graph': continue
                
                label = self.getLabel(node)
                tmpnode = processednodes.get(name,None)
                
                    
                # has the node been defined before?
                if tmpnode:
                    pass
##                    # is it a new label?
##                    if node.label or node.texlbl:
##                        #if tmpnode['texlbl'] <> label and node_stmt:
##                        tmpnode['texlbl'] = label
                else:
                    tmpnode = dict(texlbl=None, width=None, height=None,
                                    margin=None, style=None, fixedsize=None,
                                    shape=None, texmode=None,label=None,
                                    lblstyle=None)
                    processednodes[name]= tmpnode
                if node.width:
                    tmpnode['width'] = node.width
                if node.height:
                    tmpnode['height'] = node.height
                if node.margin:
                    tmpnode['margin'] = node.margin
                if node.style:
                    tmpnode['style'] = node.style
                if node.texmode:
                    tmpnode['texmode'] = node.texmode
                if node.label or node.label=='':
                    tmpnode['label'] = node.label
                if node.texlbl:
                    tmpnode['texlbl'] = node.texlbl
                if node.lblstyle:
                    tmpnode['lblstyle'] = node.lblstyle
                if node.shape:
                    tmpnode['shape'] = node.shape
                if node.fixedsize:
                    tmpnode['fixedsize'] = node.fixedsize.lower()
                    #log.debug('nodeinfo %s %s',name, node.fixedsize)
                if node.shape:
                    tmpnode['shape'] = node.shape
            elif isinstance(element, pydot.Edge):
                if not element.label: continue
                # Ensure that the edge name is unique.
                name = element.src + element.dst +str(counter)
                label = self.getLabel(element)
                element.texlbl = label
                processededges[name]=element
            elif isinstance(element, pydot.Graph):
                if not getattr(element,'label',None) and \
                    not getattr(element,'texlbl',None): continue
                name = element.graph_name
                label = self.getLabel(element)
                element.texlbl = label
                processedgraphs[name]=element
                
            else:
                pass
            counter += 1
 
        for name, item in processednodes.items():
            if item['fixedsize'] == 'true' or item['style'] == 'invis':
                continue
            if item['shape'] == 'record':
                log.warning('Record nodes not supported in preprocessing mode: %s',name)
                continue
            item['name'] = name
            texlbl = self.getLabeld(item)
            if texlbl:
                item['texlbl'] = texlbl
                code = self.getNodePreprocCode(item)
                pp.addSnippet(name,code)
            #log.warning(item['texlbl'])
            usednodes[name] = item
        for name, item in processededges.items():
            code = self.getEdgePreprocCode(item)
            pp.addSnippet(name,code)
            usededges[name] = item
        for name, item in processedgraphs.items():
            code = self.getGraphPreprocCode(item)
            pp.addSnippet(name,code)
            usedgraphs[name] = item
            
        
        ok = pp.process()
        
        if not ok:
            errormsg = """\
Failed to preprocess the graph.
Is the preview LaTeX package installed? ((Debian package preview-latex-style)
To see what happened, run dot2tex with the --debug option.
"""
            log.error(errormsg)
            sys.exit(1)
        
        for name,item in usednodes.items():
            if not item['texlbl']:continue
            node = pydot.Node('"'+name+'"',texlbl=item['texlbl'],margin=item['margin'])
            hp,dp,wt = pp.texdims[name]
            if self.options.get('rawdim',False):
                # use dimesions from preview.sty directly
                node.width = wt
                node.height = hp+dp
                node.label=" "
                node.fixedsize='true'
                self.maingraph.add_node(node)
                continue
            xmargin, ymargin = self.getMargins(node)
            #print xmargin, ymargin
            ht = hp+dp
            minwidth = float(item['width'] or DEFAULT_NODE_WIDTH)
            minheight = float(item['height'] or DEFAULT_NODE_HEIGHT)
            if self.options.get('nominsize',False):
                width = wt+2*xmargin
                height = ht+2*ymargin
            else:
                
                if (wt+2*xmargin) < minwidth:
                    width = minwidth
                    #log.warning("%s %s %s %s %s",minwidth,wt,width,name,tmp)
                    pass
                else:
                    width = wt+2*xmargin
                height = ht
                if ((hp+dp)+2*ymargin) < minheight:
                    height = minheight
                else:
                    height = ht+ 2*ymargin
            # Treat shapes with equal widht and height differently
            # Warning! Rectangles will not alway fit inside a circle
            #          Should use the diagonal.
            if item['shape'] in ['circle','Msquare','doublecircle','Mcircle']:
                #log.warning('%s %s', name, item['shape'])
                if  wt< height and width < height:
                    width = height
                else:
                    height=width
                    pass

            node.width = width
            node.height = height
            node.label=" "
            
            node.fixedsize='true'
            self.maingraph.add_node(node)
        for name,item in usededges.items():
            
            edge = item
            hp,dp,wt = pp.texdims[name]
            xmargin, ymargin = self.getMargins(edge)
            labelcode = '<<<table border="0" cellborder="0" cellpadding="0">'\
                        '<tr><td fixedsize="true" width="%s" height="%s">a</td>'\
                        '</tr></table>>>'
            edge.label=labelcode % ((wt + 2*xmargin)*72, (hp+dp+2*ymargin)*72)
        for name,item in usedgraphs.items():
            graph = item
            hp,dp,wt = pp.texdims[name]
            xmargin, ymargin = self.getMargins(graph)
            labelcode = '<<<table border="0" cellborder="0" cellpadding="0">'\
                        '<tr><td fixedsize="true" width="%s" height="%s">a</td>'\
                        '</tr></table>>>'
            graph.label=labelcode % ((wt + 2*xmargin)*72, (hp+dp+2*ymargin)*72)
            
        self.maingraph.d2toutputformat = self.options.get('format',
                                             DEFAULT_OUTPUT_FORMAT)
        graphcode = self.maingraph.to_string()
        graphcode = graphcode.replace('"<<<','<<')
        graphcode = graphcode.replace('>>>"','>>')
        return graphcode

            


PSTRICKS_TEMPLATE = r"""\documentclass{article}
% <<bbox>>
\usepackage[x11names]{xcolor}
\usepackage[<<textencoding>>]{inputenc}
\usepackage{graphicx}
\usepackage{pstricks}
\usepackage{amsmath}
<<startpreprocsection>>%
\usepackage[active,auctex]{preview}
<<endpreprocsection>>%
<<gvcols>>%
<<docpreamble>>%


\begin{document}
\pagestyle{empty}
<<startpreprocsection>>%
<<preproccode>>%
<<endpreprocsection>>%
<<startoutputsection>>%
\enlargethispage{100cm}

% Start of code
\begin{pspicture}[linewidth=1bp<<graphstyle>>]<<bbox>>
  \pstVerb{2 setlinejoin} % set line join style to 'mitre'
<<figpreamble>>%
<<drawcommands>>
<<figpostamble>>%
\end{pspicture}
% End of code
<<endoutputsection>>%
\end{document}
%
<<startfigonlysection>>
\begin{pspicture}[linewidth=1bp<<graphstyle>>]<<bbox>>
  \pstVerb{2 setlinejoin} % set line join style to 'mitre'
<<figpreamble>>%
<<drawcommands>>
<<figpostamble>>%
\end{pspicture}
<<endfigonlysection>>
%
<<startcodeonlysection>>
<<figpreamble>>%
<<drawcommands>>
<<figpostamble>>%
<<endcodeonlysection>>
"""

class Dot2PSTricksConv(DotConvBase):
    """PSTricks converter backend"""
    def __init__(self, options = {}):
        DotConvBase.__init__(self, options)
        if not self.template:
            self.template = PSTRICKS_TEMPLATE
        self.styles = dict(
            dotted = "linestyle=dotted",
            dashed = "linestyle=dashed",
            bold   = "linewidth=2pt",
            solid = "",
            filled = "",
          )

    def doGraphtmp(self):
        self.pencolor = "";
        self.fillcolor = ""
        self.color = ""
        self.body += '{\n'
        DotConvBase.doGraph(self)
        self.body += '}\n'
    
    def startFig(self):
        # get bounding box
        bbstr = self.maingraph.bb
        if bbstr:
            bb = bbstr.split(',')
        #fillcolor=black,
        s = "\\begin{pspicture}[linewidth=1bp](%sbp,%sbp)(%sbp,%sbp)\n" % \
                (bb[0],bb[1],bb[2],bb[3])
        # Set line style to mitre
        s += "  \pstVerb{2 setlinejoin} % set line join style to 'mitre'\n"
        #return s
        return ""

    def endFig(self):
        #return '\end{pspicture}\n'
        return ""
    
    def drawEllipse(self, drawop, style = None):
        op, x,y,w,h = drawop
        s = ""
        #s =  "  %% Node: %s\n" % node.name
        if op == 'E':
            if style:
                style = style.replace('filled','')
            stylestr = 'fillstyle=solid'
        else:
            stylestr = ""

        if style:
            if stylestr:
                stylestr += ','+ style
            else:
                stylestr = style
            
        s += "  \psellipse[%s](%sbp,%sbp)(%sbp,%sbp)\n" % (stylestr,x,y, \
                # w+self.linewidth,h+self.linewidth)
                w,h)
        

        return s
    
    def drawPolygon(self, drawop, style = None):
        op, points = drawop
        pp = ['(%sbp,%sbp)' % (p[0],p[1]) for p in points]
        stylestr = ""
        if op == 'P':
            if style:
                style = style.replace('filled','')
            stylestr = "fillstyle=solid"
        if style:
            if stylestr:
                stylestr += ','+ style
            else:
                stylestr = style

        s = "  \pspolygon[%s]%s\n" % (stylestr, "".join(pp))
        return s
        
    def drawPolyLine(self, drawop, style = None):
        op, points = drawop
        pp = ['(%sbp,%sbp)' % (p[0],p[1]) for p in points]
        s = "  \psline%s\n" % "".join(pp)
        return s
    
    def drawBezier(self, drawop, style = None):
        op, points = drawop
        pp= []
        for point in points:
            pp.append("(%sbp,%sbp)" % (point[0],point[1]))

        #points = ['(%sbp, %sbp)' % (p[0],p[1]) for p in points]
        arrowstyle = ""
        return "  \psbezier{%s}%s\n" % (arrowstyle, "".join(pp))
    
        

    def drawText(self, drawop, style=None):
        
        if len(drawop)==7:
            c, x, y, align, w, text, valign = drawop
        else:
            c, x, y, align, w, text = drawop
            valign=""
        if align == "-1" :
            alignstr = 'l' # left aligned
        elif align == "1":
            alignstr = 'r' # right aligned
        else:
            alignstr = ""  # centered (default)
        if alignstr or valign:
            alignstr = '['+alignstr+valign+']'
        s = "  \\rput%s(%sbp,%sbp){%s}\n" % (alignstr, x,y,text)
        return s
        
    def setColor(self, drawop):
        c, color = drawop
        #color = color.replace('grey','gray')
        #self.pencolor = "";
        #self.fillcolor = ""
        #self.color = ""
        color = self.convertColor(color)
        s = ""
        if c == 'c':
            # set pen color
            if self.pencolor <> color:
                self.pencolor = color
                s = "  \psset{linecolor=%s}\n" % color
            else: return ""
        elif c == 'C':
            # set fill color
            if self.fillcolor <> color:
                self.fillcolor = color
                s = "  \psset{fillcolor=%s}\n" % color
            else: return ""
        return s
    
    def setStyle(self, drawop):
        c, style = drawop
        psstyle = self.styles.get(style,"")
        if psstyle:
            return "  \psset{%s}\n" % psstyle
        else:
            return ""
        
    def filterStyles(self, style):
        fstyles = []
        for item in style.split(','):
            keyval = item.strip()
            if keyval.find('setlinewidth') < 0:
                fstyles.append(keyval)
        return ', '.join(fstyles)
        
    def startNode(self, node):
        self.pencolor = "";
        self.fillcolor = ""
        self.color = ""
        return "{%\n"
    
    def endNode(self,node):
        return "}%\n"
    
    def startEdge(self):
        self.pencolor = "";
        self.fillcolor = ""
        return "{%\n"

    def endEdge(self):
        return "}%\n"

    def startGraph(self, graph):
        self.pencolor = "";
        self.fillcolor = ""
        self.color = ""
        return "{\n"

    def endGraph(self,node):
        return "}\n"
        

    def drawEllipseNode(self, x,y,w,h,node):
        s =  "  %% Node: %s\n" % node.name
        s += "  \psellipse(%sbp,%sbp)(%sbp,%sbp)\n" % (x,y, \
                 w/2+self.linewidth,h/2+self.linewidth)
        # label
        if node.label:
            label = node.label
        else:
            label = node.name
        s += "  \\rput(%sbp,%sbp){$%s$}\n" % (x,y,label)

        return s
    
    
    
    def drawEdge(self, edge):
        s = ""
        if edge.style == 'invis':
            return ""
        arrowstyle, points = self.getEdgePoints(edge)
        if arrowstyle == '--': arrowstyle=''
        color = getattr(edge,'color','')
        if self.color <> color:
            if color:
                s += self.setColor(('c',color))
            else:
                # reset to default color
                s += self.setColor(('c','black'))
        pp= []
        for point in points:
            p = point.split(',')
            pp.append("(%sbp,%sbp)" % (p[0],p[1]))

        edgestyle = edge.style
        styles = []
        if arrowstyle:
            styles.append('arrows=%s' % arrowstyle)
        if edgestyle:
            edgestyles = [self.styles.get(key.strip(),key.strip()) for key in edgestyle.split(',') if key]
            styles.extend(edgestyles)
        if styles:
            stylestr = ",".join(styles)
        else:
            stylestr = ""
        if not self.options.get('straightedges',False):
            s += "  \psbezier[%s]%s\n" % (stylestr,"".join(pp))
        else:
            s += "  \psline[%s]%s%s\n" % (stylestr,  pp[0], pp[-1])
        #s += "  \psbezier[%s]{%s}%s\n" % (stylestr, arrowstyle,"".join(pp))
##        if edge.label:
##            x,y = edge.lp.split(',')
##            #s += "\\rput(%s,%s){%s}\n" % (x,y,edge.label)
        return s
    
    def initTemplateVars(self):
        DotConvBase.initTemplateVars(self)
        # Put a ',' before <<graphstyle>>
        graphstyle = self.templatevars.get('<<graphstyle>>','')
        if graphstyle:
            graphstyle = graphstyle.strip()
            if not graphstyle.startswith(','):
                graphstyle = ','+graphstyle
                self.templatevars['<<graphstyle>>'] = graphstyle

        
PGF_TEMPLATE = r"""\documentclass{article}
\usepackage[x11names, rgb]{xcolor}
\usepackage[<<textencoding>>]{inputenc}
\usepackage{tikz}
\usetikzlibrary{snakes,arrows,shapes}
\usepackage{amsmath}
<<startpreprocsection>>%
\usepackage[active,auctex]{preview}
<<endpreprocsection>>%
<<gvcols>>%
<<cropcode>>%
<<docpreamble>>%

\begin{document}
\pagestyle{empty}
%
<<startpreprocsection>>%
<<preproccode>>
<<endpreprocsection>>%
%
<<startoutputsection>>
\enlargethispage{100cm}
% Start of code
% \begin{tikzpicture}[anchor=mid,>=latex',join=bevel,<<graphstyle>>]
\begin{tikzpicture}[>=latex',join=bevel,<<graphstyle>>]
  \pgfsetlinewidth{1bp}
<<figpreamble>>%
<<drawcommands>>
<<figpostamble>>%
\end{tikzpicture}
% End of code
<<endoutputsection>>
%
\end{document}
%
<<startfigonlysection>>
\begin{tikzpicture}[>=latex,join=bevel,<<graphstyle>>]
  \pgfsetlinewidth{1bp}
<<figpreamble>>%
<<drawcommands>>
<<figpostamble>>%
\end{tikzpicture}
<<endfigonlysection>>
<<startcodeonlysection>>
<<figpreamble>>%
<<drawcommands>>
<<figpostamble>>%
<<endcodeonlysection>>
"""

class Dot2PGFConv(DotConvBase):
    """PGF/TikZ converter backend"""
    def __init__(self, options={}):
        DotConvBase.__init__(self, options)
        if not self.template:
            self.template = PGF_TEMPLATE
        self.styles = dict(dashed='dashed', dotted='dotted',
                            bold='very thick', filled='fill', invis="",
                            rounded='rounded corners', )
        self.dashstyles = dict(
            dashed = '\pgfsetdash{{3pt}{3pt}}{0pt}',
            dotted='\pgfsetdash{{\pgflinewidth}{2pt}}{0pt}',
            bold = '\pgfsetlinewidth{1.2pt}')

    def startFig(self):
        # get bounding box
        # get bounding box
        s = ""
##        bbstr = self.maingraph.bb
##        if bbstr:
##            bb = bbstr.split(',')
##            s += "%%(%sbp,%sbp)(%sbp,%sbp)\n" % \
##                (bb[0],bb[1],bb[2],bb[3])
        
        return s

    def endFig(self):
        #return '\end{tikzpicture}'
        return ""
    
    def startNode(self, node):
        # Todo: Should find a more elgant solution
        self.pencolor = "";
        self.fillcolor = ""
        self.color = ""
        return "\\begin{scope}\n"
    
    def endNode(self,node):
        return "\\end{scope}\n"
    
    def startEdge(self):
        # Todo: Should find a more elgant solution
        #self.pencolor = "";
        #self.fillcolor = ""
        #self.color = ""
        return "\\begin{scope}\n"

    def endEdge(self):
        return "\\end{scope}\n"
    
    def startGraph(self, graph):
        # Todo: Should find a more elgant solution
        self.pencolor = "";
        self.fillcolor = ""
        self.color = ""
        return "\\begin{scope}\n"

    def endGraph(self,graph):
        return "\\end{scope}\n"
        #return "\\end{scope}"
    
    def setColor(self, drawop):
        c, color = drawop
        # Todo: Should find a more elgant solution
        #self.pencolor = "";
        #self.fillcolor = ""
        #self.color = ""
        res = self.convertColor(color, True)
        opacity = None
        if len(res)==2:
            ccolor, opacity = res
        else:
            ccolor = res
        s = ""
        if c == 'cC':
            #self.pencolor = color
            #self.fillcolor = color
            if self.color <> color:
                self.color = color
                self.pencolor=color
                self.fillcolor=color
                if ccolor.startswith('{'):
                    # rgb or hsb
                    s += "  \definecolor{newcol}%s;\n" % ccolor
                    ccolor = 'newcol'
                s += "  \pgfsetcolor{%s}\n" % ccolor
                #s += "  \pgfsetfillcolor{%s}\n" % ccolor
        elif c == 'c':
            # set pen color
            if self.pencolor <> color:
                self.pencolor = color
                self.color = ''
                if ccolor.startswith('{'):
                    # rgb or hsb
                    s += "  \definecolor{strokecol}%s;\n" % ccolor
                    ccolor = 'strokecol'
                s += "  \pgfsetstrokecolor{%s}\n" % ccolor
            else: return ""
        elif c == 'C':
            # set fill color
            if self.fillcolor <> color:
                self.fillcolor = color
                self.color = ''
                if ccolor.startswith('{'):
                    # rgb
                    s += "  \definecolor{fillcol}%s;\n" % ccolor
                    ccolor = 'fillcol'
                s += "  \pgfsetfillcolor{%s}\n" % ccolor
                if not opacity == None:
                    self.opacity = opacity
                    # Todo: The opacity should probably be set directly when drawing
                    # The \pgfsetfillcopacity cmd affects text as well
                    #s += "  \pgfsetfillopacity{%s};\n" % opacity
                else:
                    self.opacity = None
            else: return ""
        return s
    
    def setStyle(self, drawop):
        c, style = drawop
        pgfstyle = self.dashstyles.get(style,"")
        if pgfstyle:
            return "  %s\n" % pgfstyle
        else:
            return ""
    
    def filterStyles(self, style):
        fstyles = []
        for item in style.split(','):
            keyval = item.strip()
            if keyval.find('setlinewidth') < 0 and not keyval=='filled':
                fstyles.append(keyval)
        return ', '.join(fstyles)


    def drawEllipse(self, drawop, style = None):
        op, x,y,w,h = drawop
        s = ""
        #s =  "  %% Node: %s\n" % node.name
        if op == 'E':
            if self.opacity <> None:
                # Todo: Need to know the state of the current node
                cmd = 'filldraw [opacity=%s]' % self.opacity
            else:
                cmd = 'filldraw'
        else:
            cmd = "draw"

        if style:
            stylestr = " [%s]" % style
        else:
            stylestr = ''
        s += "  \%s%s (%sbp,%sbp) ellipse (%sbp and %sbp);\n" % (cmd, stylestr, x,y, \
                # w+self.linewidth,h+self.linewidth)
                w,h)
        return s
    
    def drawPolygon(self, drawop, style = None):
        op, points = drawop
        pp = ['(%sbp,%sbp)' % (p[0],p[1]) for p in points]
        cmd = "draw"
        if op == 'P':
            cmd = "filldraw"
            
        if style:
            stylestr = " [%s]" % style
        else:
            stylestr = ''
        s = "  \%s%s %s -- cycle;\n" % (cmd, stylestr, " -- ".join(pp))
        return s
    
    def drawPolyLine(self, drawop, style = None):
        op, points = drawop
        pp = ['(%sbp,%sbp)' % (p[0],p[1]) for p in points]
        ##if style:
##            stylestr = " [%s]" % style
##        else:
##            stylestr = ''
        stylestr = ''
        return "  \draw%s %s;\n" %(stylestr, " -- ".join(pp))
        
    
    def drawText(self, drawop, style = None):
        # The coordinates given by drawop are not the same as the node
        # coordinates! This may give som odd results if graphviz' and
        # LaTeX' fonts are very different.
        if len(drawop)==7:
            c, x, y, align, w, text, valign = drawop
        else:
            c, x, y, align, w, text = drawop
            valign=""
        styles = []
        if align == "-1" :
            alignstr = 'right' # left aligned
        elif align == "1":
            alignstr = 'left' # right aligned
        else:
            alignstr = ""  # centered (default)
        styles.append(alignstr)
        styles.append(style)
##        if alignstr:
##            alignstr = "[" + alignstr+", anchor=mid" + "]"
##        else:
##            alignstr = "[anchor=mid]"
        lblstyle = ",".join([i for i in styles if i])
        if lblstyle:
            lblstyle = '['+lblstyle+']'
        s = "  \draw (%sbp,%sbp) node%s {%s};\n" % (x,y,lblstyle,text)
        return s
    
    def drawBezier(self, drawop, style = None):
        s = ""
        c, points = drawop
        arrowstyle = '--'

        pp= []
        for point in points:
            pp.append("(%sbp,%sbp)" % (point[0],point[1]))

        #points = ['(%sbp, %sbp)' % (p[0],p[1]) for p in points]
        #quadp = nsplit(pp, 4)
        pstrs = ["%s .. controls %s and %s " % p for p in nsplit(pp, 3)]
        ##if style:
##            stylestr = " [%s]" % style
##        else:
##            stylestr = ''
        stylestr = ''
##        if arrowstyle == '--':
##            style = ''
##        else:
##            style = '[%s]' % arrowstyle

        s += "  \draw%s %s .. %s;\n" % (stylestr, " .. ".join(pstrs), pp[-1])
        
        return s
    

    def doEdges(self):
        s = ""
        s += self.setColor(('cC',"black"))
        for edge in self.edges:
            dstring = getattr(edge,'_draw_',"")
            lstring = getattr(edge,'_ldraw_',"")
            hstring = getattr(edge,'_hdraw_',"")
            tstring = getattr(edge,'_tdraw_',"")
            tlstring = getattr(edge,'_tldraw_',"")
            hlstring = getattr(edge,'_hldraw_',"")

            # Note that the order of the draw strings should be the same
            # as in the xdot output.
            drawstring = dstring + " " + hstring + " " + tstring \
                            + " " + lstring + " " + tlstring + " " + hlstring
            drawop,stat = parseDrawString(drawstring);
            if not drawstring.strip():
                continue
            s += self.outputEdgeComment(edge)
            if self.options.get('duplicate', False):
                s += self.startEdge()
                s += self.doDrawOp(drawop, edge,stat)
                s += self.endEdge()
            else:
                topath = getattr(edge,'topath',None)
                s += self.drawEdge(edge)
                if not self.options.get('tikzedgelabels',False) and not topath:
                    s += self.doDrawString(lstring+" "+tlstring+" "+hlstring, edge)
                else:
                    s += self.doDrawString(tlstring+" "+hlstring, edge)
                #s += self.drawEdge(edge)
                #s += self.doDrawString(lstring+" "+tlstring+" "+hlstring, edge)
        self.body += s

     
    def drawEdge(self, edge):
        s = ""
        if edge.style == 'invis':
            return ""
        arrowstyle, points = self.getEdgePoints(edge)
        # PGF uses the fill style when drawing some arrowheads. We have to
        # ensure that the fill color is the same as the pen color.
        color = getattr(edge,'color','')
        
        if self.color <> color:
            if color:
                s += self.setColor(('cC',color))
            else:
                # reset to default color
                s += self.setColor(('cC','black'))
            
        pp= []
        for point in points:
            p = point.split(',')
            pp.append("(%sbp,%sbp)" % (p[0],p[1]))

        edgestyle = edge.style
            
        styles = []
        if arrowstyle <> '--':
            #styles.append(arrowstyle)
            styles = [arrowstyle]

        if edgestyle:
            edgestyles = [self.styles.get(key.strip(),key.strip()) for key in edgestyle.split(',') if key]
            styles.extend(edgestyles)
        
        stylestr = ",".join(styles)
        topath = getattr(edge,'topath',None)

        pstrs = ["%s .. controls %s and %s " % p for p in nsplit(pp, 3)]
        extra = ""
        if self.options.get('tikzedgelabels',False) or topath:
            edgelabel = self.getLabel(edge)
            #log.warning('label: %s', edgelabel)
            lblstyle = getattr(edge,'lblstyle','')
            if lblstyle:
                lblstyle = '['+lblstyle+']'
            else:
                lblstyle = ''
            if edgelabel:
                extra = " node%s {%s}" % (lblstyle,edgelabel)
        src = pp[0]
        dst = pp[-1]
        if topath:
                s += "  \draw [%s] %s to[%s]%s %s;\n" % (stylestr, src,
                                                             topath, extra,dst)
        elif not self.options.get('straightedges',False):
            #s += "  \draw [%s] %s .. %s;\n" % (stylestr, " .. ".join(pstrs), pp[-1])
            s += "  \draw [%s] %s ..%s %s;\n" % (stylestr, " .. ".join(pstrs), extra,pp[-1])
        else:
            s += "  \draw [%s] %s --%s %s;\n" % (stylestr, pp[0],extra, pp[-1])
        
        return s
    
    def initTemplateVars(self):
        DotConvBase.initTemplateVars(self)
        if self.options.get('crop',False):
            cropcode = "\usepackage[active,tightpage]{preview}\n" + \
                "\PreviewEnvironment{tikzpicture}\n" + \
                "\setlength\PreviewBorder{%s}" % self.options.get('margin','0pt')
        else:
            cropcode = ""
        vars = {}
        vars['<<cropcode>>'] = cropcode
        self.templatevars.update(vars)

    def getNodePreprocCode(self,node):
        lblstyle = node.get('lblstyle','')
        text = node.get('texlbl','')
        if lblstyle:
            return "  \\tikz \\node[%s] {%s};\n" % (lblstyle, text)
        else:
            return r"\tikz \node {" + text +"};"

    def getEdgePreprocCode(self,edge):
        lblstyle = getattr(edge,'lblstyle','')
        if lblstyle:
            return "  \\tikz \\node[%s] {%s};\n" % (lblstyle, edge.texlbl)
        else:
            return r"\tikz \node " + "{"+edge.texlbl +"};"

    def getGraphPreprocCode(self,graph):
        lblstyle = getattr(graph,'lblstyle','')
        if lblstyle:
            return "  \\tikz \\node[%s] {%s};\n" % (lblstyle, graph.texlbl)
        else:
            return r"\tikz \node " + graph.texlbl +"};"
        



        

TIKZ_TEMPLATE = r"""\documentclass{article}
\usepackage[x11names, rgb]{xcolor}
\usepackage[<<textencoding>>]{inputenc}
\usepackage{tikz}
\usetikzlibrary{snakes,arrows,shapes}
\usepackage{amsmath}
<<startpreprocsection>>%
\usepackage[active,auctex]{preview}
<<endpreprocsection>>%
<<gvcols>>%
<<cropcode>>%
<<docpreamble>>%

\begin{document}
\pagestyle{empty}
%
<<startpreprocsection>>%
<<preproccode>>
<<endpreprocsection>>%
%
<<startoutputsection>>
\enlargethispage{100cm}
% Start of code
\begin{tikzpicture}[>=latex',join=bevel,<<graphstyle>>]
<<figpreamble>>%
<<drawcommands>>
<<figpostamble>>%
\end{tikzpicture}
% End of code
<<endoutputsection>>
%
\end{document}
%
<<startfigonlysection>>
\begin{tikzpicture}[>=latex,join=bevel,<<graphstyle>>]
<<figpreamble>>%
<<drawcommands>>
<<figpostamble>>%
\end{tikzpicture}
<<endfigonlysection>>
<<startcodeonlysection>>
<<figpreamble>>%
<<drawcommands>>
<<figpostamble>>%
<<endcodeonlysection>>
"""

class Dot2TikZConv(Dot2PGFConv):
    """A backend that utilizes the node and edge mechanism of PGF/TikZ"""
    shapemap = {'doublecircle' : 'circle, double',
                'box' : 'rectangle',
                'rect' : 'rectangle',
                'none' :'draw=none',
                'plaintext' : 'draw=none',
                'polygon' : 'regular polygon, regular polygon sides=7',
                'triangle' : 'regular polygon, regular polygon sides=3',
                'pentagon' : 'regular polygon, regular polygon sides=5',
                'hexagon' : 'regular polygon, regular polygon sides=5',
                'septagon' : 'regular polygon, regular polygon sides=7',
                'octagon' : 'regular polygon, regular polygon sides=8',
                }

    def __init__(self, options={}):
        # to connect nodes they have to defined. Therefore we have to ensure
        # that code for generating nodes is outputted first.
        options['switchdraworder'] = True
        options['flattengraph'] = True
        options['rawdim'] = True
        DotConvBase.__init__(self, options)
        if not self.template:
            self.template = TIKZ_TEMPLATE

        self.styles = dict(dashed='dashed', dotted='dotted',
                            bold='very thick', filled='fill', invis="",
                            rounded='rounded corners', )
        self.dashstyles = dict(
            dashed = '\pgfsetdash{{3pt}{3pt}}{0pt}',
            dotted='\pgfsetdash{{\pgflinewidth}{2pt}}{0pt}',
            bold = '\pgfsetlinewidth{1.2pt}')

    def setOptions(self):
        Dot2PGFConv.setOptions(self)
        self.options['tikzedgelabels'] = self.options.get('tikzedgelabels','') \
            or getboolattr(self.maingraph,'d2ttikzedgelabels','')
        self.options['styleonly'] = self.options.get('styleonly','') \
            or getboolattr(self.maingraph,'d2tstyleonly','')
        self.options['nodeoptions'] = self.options.get('nodeoptions','') \
            or getattr(self.maingraph,'d2tnodeoptions','')
        self.options['edgeoptions'] = self.options.get('edgeoptions','') \
            or getattr(self.maingraph,'d2tedgeoptions','')
            
    def outputNodeComment(self, node):
        # With the node syntax comments are unnecessary
        return ""

    def getNodePreprocCode(self,node):
        lblstyle = node.get('lblstyle','')
        
        shape = node.get('shape','ellipse')
        shape = self.shapemap.get(shape, shape)
        #s += "%% %s\n" % (shape)
        label = node.get('texlbl','')
        style = node.get('style'," ") or " ";
        if lblstyle:
            if style.strip():
                style += ','+lblstyle
            else:
                style = lblstyle

        sn = ""
        if self.options.get('styleonly'):
            sn += "\\tikz  \\node (%s) [%s] {%s};\n" % \
                (style, label)
        else:
            sn += "\\tikz  \\node [draw,%s,%s] {%s};\n" % \
                        (shape, style, label)
        return sn

    def doNodes(self):
        s = ""
        nodeoptions=  self.options.get('nodeoptions',None)
        if nodeoptions:
            s += "\\begin{scope}[%s]\n" % nodeoptions
        for node in self.nodes:
            self.currentnode = node
            # detect node type
            shape = getattr(node,'shape','ellipse')
            shape = self.shapemap.get(shape, shape)
            if shape == None:
                shape='ellipse'
            
            pos = getattr(node,'pos',None)
            if not pos:
                continue
            x,y = pos.split(',')
            label = self.getLabel(node)

            pos = "%sbp,%sbp" % (x,y)
            style = node.style or "";
            if node.lblstyle:
                if style:
                    style += ','+node.lblstyle
                else:
                    style = node.lblstyle
            if node.exstyle:
                if style:
                    style += ','+node.exstyle
                else:
                    style = node.exstyle
            sn = ""
            sn += self.outputNodeComment(node)
            sn += self.startNode(node)
            if self.options.get('styleonly'):
                sn += "  \\node (%s) at (%s) [%s] {%s};\n" % \
                    (node.name, pos, style, label)
            else:
                color = getattr(node,'color','')
                drawstr = 'draw'
                if style.strip() == 'filled':
                    drawstr='fill,draw'
                    style = ''
                    if color:
                        drawstr += ','+color
                elif color:
                    drawstr += '='+color
                    
                if style.strip():
                    sn += "  \\node (%s) at (%s) [%s,%s,%s] {%s};\n" % \
                            (node.name, pos, drawstr, shape, style, label)
                else:
                    sn += "  \\node (%s) at (%s) [%s,%s] {%s};\n" % \
                            (node.name, pos, drawstr, shape,  label)
            sn += self.endNode(node)
            
                    
            s += sn
        if nodeoptions:
            s += "\\end{scope}\n"
        self.body += s
    
    def doEdges(self):
        s = ""
        edgeoptions = self.options.get('edgeoptions',None)
        if edgeoptions:
            s += "\\begin{scope}[%s]\n" % edgeoptions
        for edge in self.edges:
            dstring = getattr(edge,'_draw_',"")
            lstring = getattr(edge,'_ldraw_',"")
            hstring = getattr(edge,'_hdraw_',"")
            tstring = getattr(edge,'_tdraw_',"")
            tlstring = getattr(edge,'_tldraw_',"")
            hlstring = getattr(edge,'_hldraw_',"")
            topath = getattr(edge,'topath',None)
            s += self.drawEdge(edge)
            if not self.options.get('tikzedgelabels',False) and not topath:
                s += self.doDrawString(lstring+" "+tlstring+" "+hlstring, edge)
            else:
                s += self.doDrawString(tlstring+" "+hlstring, edge)
                
        if edgeoptions:
            s += "\\end{scope}\n"
        self.body += s
        
    def drawEdge(self, edge):
        s = ""
        if edge.style == 'invis':
            return ""
        arrowstyle, points = self.getEdgePoints(edge)
        # PGF uses the fill style when drawing some arrowheads. We have to
        # ensure that the fill color is the same as the pen color.
        color = getattr(edge,'color','')
        pp= []
        for point in points:
            p = point.split(',')
            pp.append("(%sbp,%sbp)" % (p[0],p[1]))

        edgestyle = edge.style
        #print edgestyle

        styles = []
        if arrowstyle <> '--':
            #styles.append(arrowstyle)
            styles = [arrowstyle]

        if edgestyle:
            edgestyles = [self.styles.get(key.strip(),key.strip()) for key in edgestyle.split(',') if key]
            styles.extend(edgestyles)

        stylestr = ",".join(styles)
        if color:
            stylestr = color+','+stylestr
        src = edge.get_source()
        dst = edge.get_destination()
        topath = getattr(edge,'topath',None)

        pstrs = ["%s .. controls %s and %s " % p for p in nsplit(pp, 3)]
        pstrs[0] = "(%s) ..controls %s and %s " % (src, pp[1], pp[2])
        extra = ""
        if self.options.get('tikzedgelabels',False) or topath:
            edgelabel = self.getLabel(edge)
            #log.warning('label: %s', edgelabel)
            lblstyle = getattr(edge,'lblstyle','')
            exstyle = getattr(edge,'exstyle','')
            if exstyle:
                if lblstyle:
                    lblstyle += ',' +exstyle
                else:
                    lblstyle = exstyle
            if lblstyle:
                lblstyle = '['+lblstyle+']'
            else:
                lblstyle = ''
            if edgelabel:
                extra = " node%s {%s}" % (lblstyle,edgelabel)
            
        if topath:
            s += "  \draw [%s] (%s) to[%s]%s (%s);\n" % (stylestr, src,
                                                         topath, extra,dst)
        elif not self.options.get('straightedges',False):
            s += "  \draw [%s] %s ..%s (%s);\n" % (stylestr,
                " .. ".join(pstrs), extra,dst)
        else:
            s += "  \draw [%s] (%s) --%s (%s);\n" % (stylestr, src, extra,dst)

        return s
    
    def startNode(self, node):
        return ""
    
    def endNode(self,node):
        return ""
  
dimext = r"""
^\!\s Preview:\s Snippet\s
(?P<number>\d*)\s ended.
\((?P<ht>\d*)\+(?P<dp>\d*)x(?P<wd>\d*)\)"""

class TeXDimProc:
    """Helper class for for finding the size of TeX snippets

    Uses preview.sty
    """
    # Produce document
    # Create a temporary directory
    # Compile file with latex
    # Parse log file
    # Update graph with with and height parameters
    # Clean up
    def __init__(self,template,options):
        self.template = template
        self.snippets_code=[]
        self.snippets_id=[]
        self.options = options
        self.dimext_re = re.compile(dimext,re.MULTILINE|re.VERBOSE)
        pass
    def addSnippet(self,id, code):
        """A a snippet of code to be processed"""
        self.snippets_id.append(id)
        self.snippets_code.append(code)

    def process(self):
        """Process all snippets of code with TeX and preview.sty

        Results are stored in the texdimlist and texdims class attributes.
        Returns False if preprocessing fails
        """
        import shutil
        if len(self.snippets_code) == 0:
            log.warning('No labels to preprocess')
            return True
        self.tempdir = tempfile.mkdtemp(prefix='dot2tex')
        log.debug('Creating temporary directroy %s' % self.tempdir)
        self.tempfilename = os.path.join(self.tempdir,'dot2tex.tex')
        log.debug('Creating temporary file %s' % self.tempfilename)
        f = open(self.tempfilename,'w')
        s = ""
        for n in self.snippets_code:
            s += "\\begin{preview}%\n"
            s += n.strip()+"%\n"
            s += "\end{preview}%\n"

        f.write(self.template.replace('<<preproccode>>',s))
        #f.flush()
        f.close()
        s = open(self.tempfilename,'r').read()
        log.debug('Code written to %s\n' % self.tempfilename + s)
        self.parseLogFile()
        shutil.rmtree(self.tempdir)
        log.debug('Temporary directory and files deleted')
        if self.texdims:
            return True
        else:
            return False
        # cleanup

    def parseLogFile(self):
        logfilename = os.path.splitext(self.tempfilename)[0]+'.log'
        tmpdir = os.getcwd()
        os.chdir(os.path.split(logfilename)[0])
        if self.options.get('usepdflatex',False):
            command = 'pdflatex -interaction=nonstopmode %s' % self.tempfilename
        else:
            command = 'latex -interaction=nonstopmode %s' % self.tempfilename
        log.debug('Running command: %s' % command)
        sres = os.popen(command)
        resdata =  sres.read()
        #log.debug('resdata: %s' % resdata)
        errcode = sres.close()
        log.debug('errcode: %s' % errcode)
        f = open(logfilename,'r')
        logdata = f.read()
        log.debug('Logfile from LaTeX run: \n'+logdata)
        f.close()
        os.chdir(tmpdir)

        texdimdata = self.dimext_re.findall(logdata)
        log.debug('Texdimdata: '+ str(texdimdata))
        if len(texdimdata)== 0:
            log.error('No dimension data could be extracted from dot2tex.tex.')
            self.texdims = None
            return

        c = 1/(100.0*7227)
        c = 1.0/4736286
        self.texdims = {}
        self.texdimlist = [(float(i[1])*c,float(i[2])*c,float(i[3])*c) for i in texdimdata]
        #for i in range(len(self.snippets_id)):
        #    self.texdims[self.snippets_id[i]] = self.texdimlist[i]
        self.texdims = dict(zip(self.snippets_id,self.texdimlist))
    

def cleanDotNodes(graph):
    """Remove unnecessary data from node list"""
    nodes = graph.get_node_list()
    tmp = [node for node in nodes if node.name.startswith('"')]
    for node in nodes:
        node.name = node.name.replace('"','')
    # There are some strange issues with what nodes are returned
    # across different operating systems and versions of pydot, pyparsing,
    # and Graphviz. This is just a quick fix. Need to investigate this further
    if tmp:
        return tmp
    else:
        return nodes


# todo: Should also support graph attributes
def setDotAttr(graph):
    """Distribute default attributes to nodes and edges"""
    elements = getAllGraphElements(graph,[])
    stack = []
    definednodes = {}
    defattrs = {}
    defedgeattrs = {}
    for element in elements:
        if isinstance(element,pydot.Node):
            node = element
            nodeattrs = node.__dict__
            # is it an attribute statement? (attr_stmt)
            if node.name == 'node':
                # The node attributes are stored in node.__dict__. Extract all
                # items that are not None or functions
                defattrs.update([a for a in nodeattrs.items()
                                 if (a[1] or a[1]=='') and not callable(a[1])])
            elif node.name == 'edge':
                defedgeattrs.update([a for a in nodeattrs.items()
                                 if a[1] and not callable(a[1])])
                continue
            elif node.name == 'graph':
                continue
            else:
                name = node.name.replace('"','')
                if definednodes.get(name,False):
                    continue
                    #pass
                else:
                    definednodes[name] = True
                for key,value in defattrs.items():
                    if value=='\N':continue
                    if not node.__dict__.get(key):
                        node.__dict__[key]=value
        elif isinstance(element,pydot.Edge):
            edge = element
            for key,value in defedgeattrs.items():
                if not edge.__dict__.get(key):
                    edge.__dict__[key]=value
        elif isinstance(element,pydot.Graph):
            # push current set of attributes on the stack
            stack.append((defattrs,defedgeattrs))
            defattrs = defattrs.copy()
            defedgeattrs = defedgeattrs.copy()
        elif isinstance(element,EndOfGraphElement):
            defattrs,defedgeattrs = stack.pop()
    

def convertDot(data, backend='pstricks', options = {}):
    """Convert xdot data to a backend compatible format

    Input:
        data - dot
        backend - pstricks, pgf, eepic
    
    """
    graph = pydot.graph_from_dot_data(data)
    nodes = cleanDotNodes(graph)
    edges = graph.edge_list
    # Detect graph type
    if graph.graph_type == 'digraph':
        directedgraph = True
    else:
        directedgraph = False
    # process edges and nodes
    for node in nodes:
        pass
        

def debug(filename = 'd:/pycode/algs/t.dot'):
    dotdata = open(filename).read()
    r = convertDot(dotdata)
    print r


def processCmdLine():
    """Set up and parse command line options"""
    usage = "Usage: %prog [options] <files>"
    parser = OptionParser(usage)
    parser.add_option("-f", "--format",
                  action="store", dest="format",
                  choices = ('pstricks','pgf','pst','tikz'),
                  help="Set output format to 'v' (pstrics, pgf) ", metavar="v")
    parser.add_option('-t','--texmode', dest='texmode', default = 'verbatim',
                  choices = ('math','verbatim', 'raw'),
                  help = "Set text mode (verbatim, math, raw).")
    parser.add_option('-d', '--duplicate', dest = 'duplicate', action='store_true',
                        default=False, help='Try to duplicate Graphviz graphics')
    parser.add_option('-s', '--straightedges', dest = 'straightedges', action='store_true',
                        default=False, help='Force straight edges')
    parser.add_option('--template', dest = 'templatefile', action = 'store',
                  metavar = "FILE")
    parser.add_option('-o','--output', dest = 'outputfile', action = 'store',
                  metavar = "FILE", default='',help="Write output to FILE")
    parser.add_option('-e','--encoding', dest = 'encoding', action = 'store',
                  choices = ('utf8','latin1'), default=DEFAULT_TEXTENCODING,
                  help="Set text encoding to utf8 or latin1")
    parser.add_option('-V','--version', dest = 'printversion', action='store_true',
                  help="Print version information and exit", default=False),
    parser.add_option('-w','--switchdraworder', dest = 'switchdraworder',
                  action="store_true", help = "Switch draw order", default=False),
    parser.add_option('-p','-c','--preview', '--crop', dest = 'crop', action = 'store_true',
                  help="Use preview.sty to crop graph", default=False),
    parser.add_option('--margin', dest = 'margin', action = 'store',
                  help="Set preview margin", default="0pt"),
    parser.add_option('--docpreamble', dest = 'docpreamble', action = 'store',
                  help="Insert TeX code in document preamble", metavar="TEXCODE"),
    parser.add_option('--figpreamble', dest = 'figpreamble', action = 'store',
                  help="Insert TeX code in figure preamble", metavar="TEXCODE"),
    parser.add_option('--figpostamble', dest = 'figpostamble', action = 'store',
                  help="Insert TeX code in figure postamble", metavar="TEXCODE"),
    parser.add_option('--graphstyle', dest = 'graphstyle', action = 'store',
                  help="Insert graph style", metavar="STYLE"),
    parser.add_option('--gvcols', dest='gvcols', action ="store_true",
                  default=False, help="Include gvcols.tex"),
    parser.add_option('--figonly', dest='figonly', action ="store_true",
                  help="Output graph with no preamble", default=False)
    parser.add_option('--codeonly', dest='codeonly', action ="store_true",
                  help="Output only drawing commands", default=False)
    parser.add_option('--styleonly', dest='styleonly', action ="store_true",
                  help="Use style parameter only", default=False)
    parser.add_option('--debug',dest='debug', action="store_true",
                  help="Show additional debugging information", default=False)
    parser.add_option('--preproc', dest='texpreproc', action="store_true",
                  help = 'Preprocess graph through TeX', default=False)
    parser.add_option('--alignstr',dest='alignstr',action='store')
    parser.add_option('--valignmode', dest='valignmode', default = 'center',
                  choices = ('center','dot'),
                  help = "Set vertical alginment mode  (center, dot).")
    parser.add_option('--nominsize', dest='nominsize', action ="store_true",
                  help="No minimum node sizes", default=False)
    parser.add_option('--usepdflatex', dest='usepdflatex', action ="store_true",
                  help="Use PDFLaTeX for preprocessing", default=False)
    parser.add_option('--tikzedgelabels', dest='tikzedgelabels', action ="store_true",
                  help="Let TikZ place edge labels", default=False)
    parser.add_option('--nodeoptions', dest = 'nodeoptions', action = 'store',
                  help="Set options for nodes", metavar="OPTIONS"),
    parser.add_option('--edgeoptions', dest = 'edgeoptions', action = 'store',
                  help="Set options for edges", metavar="OPTIONS"),
    parser.add_option('--runtests',dest='runtests',
                  help="Run testes", action="store_true",default=False)

    parser.add_option("--prog", action="store", dest="prog", default='dot',
                  choices = ('dot','neato','circo','fdp','twopi'),
                  help="Use v to process the graph", metavar="v"),
    parser.add_option('--autosize',dest='autosize',
                  help="Preprocess graph and then run Graphviz", action="store_true",default=False)

    #parser.add_option("--var", action="append", dest="uservars")

    (options, args) = parser.parse_args()
    
    return options,args,parser

def _runtests():
    import doctest
    doctest.testmod()


def printVersionInfo():
    print "Dot2tex version % s" % __version__

def main():
    import platform
    options, args,parser = processCmdLine()
    if options.runtests:
        log.warning('running tests')
        _runtests()
        sys.exit(0)
    
    if options.debug:
        # initalize log handler
        hdlr = logging.FileHandler('dot2tex.log')
        log.addHandler(hdlr)
        formatter = logging.Formatter('%(asctime)s %(name)s %(levelname)s %(message)s')
        hdlr.setFormatter(formatter)
        log.setLevel(logging.DEBUG)
        nodebug = False
    else:
        nodebug = True

    log.info('------- Start of run -------')
    log.info("Dot2tex version % s" % __version__)
    log.info("System information:\n"
             "  Python: %s \n"
             "  Platform: %s\n"
             "  Pydot: %s\n"
             "  Pyparsing: %s",
        sys.version_info, platform.platform(),
        pydot.__version__,pydot.dot_parser.pyparsing_version)
    log.info('dot2tex called with: %s' % sys.argv)
    log.info('Program started in %s' % os.getcwd())

    if options.printversion:
        #print options.hest
        printVersionInfo()
        sys.exit(0)
    if len(args) == 0:
        log.info('Data read from standard input')
        dotdata = sys.stdin.readlines()
    elif len(args) == 1:
        try:
            dotdata = open(args[0], 'rU').readlines()
        except:
            log.error("Could not open input file %s" % args[0])
            sys.exit(1)
        log.info('Data read from %s' % args[0])

    # I'm not quite sure why this is necessary, but some files
    # produces data with line endings that confuses pydot/pyparser.
    # Note: Whitespace at end of line is sometimes significant
    log.debug('Input data:\n'+"".join(dotdata))
    lines = [line for line in dotdata if line.strip()]
    dotdata = "".join(lines)
    #dotdata = convert_line_endings(dotdata,0)
    #optparse.check_choice()
    
    # check for output format attribute
    fmtattr = re.findall(r'd2toutputformat=(.*?);',dotdata)
    extraoptions = re.findall(r'd2toptions\s*=\s*"(.*?)"\s*;?',dotdata)
    if fmtattr:
        log.info('Found outputformat attribute: %s',fmtattr[0])
        gfmt = fmtattr[0]
    else:
        gfmt = None
    if extraoptions:
        #log.warning('Found d2toptions attribute in graph: %s',extraoptions[0])
        (options, args) = parser.parse_args(extraoptions[0].split(),options)
        if options.debug and nodebug:
            # initalize log handler
            hdlr = logging.FileHandler('dot2tex.log')
            log.addHandler(hdlr)
            formatter = logging.Formatter('%(asctime)s %(name)s %(levelname)s %(message)s')
            hdlr.setFormatter(formatter)
            log.setLevel(logging.DEBUG)
            nodebug = False
            
    
    output_format = options.format or gfmt or DEFAULT_OUTPUT_FORMAT
    options.format = output_format
    
    if output_format in ('pstricks', 'pst'):
        conv = Dot2PSTricksConv(options.__dict__)
    elif output_format == 'pgf':
        conv = Dot2PGFConv(options.__dict__)
    elif output_format == 'tikz':
        conv = Dot2TikZConv(options.__dict__)
    else:
        log.error("Unknown output format %s" % options.format)
        sys.exit(1)
    try:
        s =  conv.convert(dotdata)
        log.debug('Output:\n'+s)
        if options.autosize:
            conv.dopreproc = False
            s = conv.convert(s)
            log.debug('Output:\n'+s)
        if options.outputfile:
            f = open(options.outputfile, 'w')
            f.write(s)
            f.close()
        else:
            print s
        #if options.texpreproc:
        #    print conv.preproc.writeTempFile()
    except SystemExit:
        pass
    except Exception:
        #log.error("Could not convert the xdot input.")
        log.exception('Failed to process input')
        
    log.info('------- End of run -------')



if __name__ == '__main__':
    main()