—

              
#############################################################################
# output the graph in dot-format text
#
#############################################################################
package Graph::Easy::As_graphviz;
$VERSION = '0.76';
#############################################################################
#############################################################################
package Graph::Easy;
use strict;
use warnings;
use Graph::Easy::Util qw(ord_values);
my $remap = {
  node => {
    'align' => undef,
    'background' => undef,   # need a way to simulate that on non-rect nodes
    'basename' => undef,
    'bordercolor' => \&_remap_color,
    'borderstyle' => \&_graphviz_remap_border_style,
    'borderwidth' => undef,
    'border' => undef,
    'color' => \&_remap_color,
    'fill' => \&_remap_color,
    'label' => \&_graphviz_remap_label,
    'pointstyle' => undef,
    'pointshape' => undef,
    'rotate' => \&_graphviz_remap_node_rotate,
    'shape' => \&_graphviz_remap_node_shape,
    'title' => 'tooltip',
    'rows' => undef,
    'columns' => undef,
    },
  edge => {
    'align' => undef,
    'arrowstyle' => \&_graphviz_remap_arrow_style,
    'background' => undef,
    'color' => \&_graphviz_remap_edge_color,
    'end' => \&_graphviz_remap_port,
    'headtitle' => 'headtooltip',
    'headlink' => 'headURL',
    'labelcolor' => \&_graphviz_remap_label_color,
    'start' => \&_graphviz_remap_port,
    'style' => \&_graphviz_remap_edge_style,
    'tailtitle' => 'tailtooltip',
    'taillink' => 'tailURL',
    'title' => 'tooltip',
    'minlen' => \&_graphviz_remap_edge_minlen,
    },
  graph => {
    align => \&_graphviz_remap_align,
    background => undef,
    bordercolor => \&_remap_color,
    borderstyle => \&_graphviz_remap_border_style,
    borderwidth => undef,
    color => \&_remap_color,
    fill => \&_remap_color,
    gid => undef,
    label => \&_graphviz_remap_label,
    labelpos => 'labelloc',
    output => undef,
    type => undef,
    },
  group => {
    align => \&_graphviz_remap_align,
    background => undef,
    bordercolor => \&_remap_color,
    borderstyle => \&_graphviz_remap_border_style,
    borderwidth => undef,
    color => \&_remap_color,
    fill => \&_remap_color,
    labelpos => 'labelloc',
    rank => undef,
    title => 'tooltip',
    },
  all => {
    arrowshape => undef,
    autolink => undef,
    autotitle => undef,
    autolabel => undef,
    class => undef,
    colorscheme => undef,
    flow => undef,
    fontsize => \&_graphviz_remap_fontsize,
    font => \&_graphviz_remap_font,
    format => undef,
    group => undef,
    link => \&_graphviz_remap_link,
    linkbase => undef,
    textstyle => undef,
    textwrap => undef,
    },
  always => {
    node        => [ qw/borderstyle label link rotate color fill/ ],
    'node.anon' => [ qw/bordercolor borderstyle label link rotate color/ ],
    edge        => [ qw/labelcolor label link color/ ],
    graph       => [ qw/labelpos borderstyle label link color/ ],
    },
  # this routine will handle all custom "x-dot-..." attributes
  x => \&_remap_custom_dot_attributes,
  };
sub _remap_custom_dot_attributes
  {
  my ($self, $name, $value) = @_;
  # drop anything that is not starting with "x-dot-..."
  return (undef,undef) unless $name =~ /^x-dot-/;
  $name =~ s/^x-dot-//;                 # "x-dot-foo" => "foo"
  ($name,$value);
  }
my $color_remap = {
  bordercolor => 'color',
  color => 'fontcolor',
  fill => 'fillcolor',
  };
sub _remap_color
  {
  # remap one color value
  my ($self, $name, $color, $object) = @_;
  # guard against always doing the remap even when the attribute is not set
  return (undef,undef) unless defined $color;
  if (!ref($object) && $object eq 'graph')
    {
    # 'fill' => 'bgcolor';
    $name = 'bgcolor' if $name eq 'fill';
    }
  $name = $color_remap->{$name} || $name;
  $color = $self->_color_as_hex_or_hsv($object,$color);
  ($name, $color);
  }
sub _color_as_hex_or_hsv
  {
  # Given a color in hex, hsv, hsl or rgb, will return either a hex or hsv
  # color to preserve as much precision as possible:
  my ($graph, $self, $color) = @_;
  if ($color !~ /^#/)
    {
    # HSV colors with an alpha channel are not supported by graphviz, and
    # hence converted to RGB here:
    if ($color =~ /^hsv\(([0-9\.]+),([0-9\.]+),([0-9\.]+)\)/)
      {
      # hsv(1.0,1.0,1.0) => 1.0 1.0 1.0
      $color = "$1 $2 $3";
      }
    else
      {
      my $cs = ref($self) ? $self->attribute('colorscheme') :
                        $graph->attribute($self,'colorscheme');
      # red => hex
      $color = $graph->color_as_hex($color, $cs);
      }
    }
  $color;
  }
sub _graphviz_remap_align
  {
  my ($self, $name, $style) = @_;
  my $s = lc(substr($style,0,1));               # 'l', 'r', or 'c'
  ('labeljust', $s);
  }
sub _graphviz_remap_edge_minlen
  {
  my ($self, $name, $len) = @_;
  $len = int(($len + 1) / 2);
  ($name, $len);
  }
sub _graphviz_remap_edge_color
  {
  my ($self, $name, $color, $object) = @_;
  my $style = ref($object) ?
    $object->attribute('style') :
    $self->attribute('edge','style');
  if (!defined $color)
    {
    $color = ref($object) ?
      $object->attribute('color') :
      $self->attribute('edge','color');
    }
  $color = '#000000' unless defined $color;
  $color = $self->_color_as_hex_or_hsv($object, $color);
  $color = $color . ':' . $color        # 'red:red'
    if $style =~ /^double/;
  ($name, $color);
  }
sub _graphviz_remap_edge_style
  {
  my ($self, $name, $style) = @_;
  # valid output styles are: solid dashed dotted bold invis
  $style = 'solid' unless defined $style;
  $style = 'dotted' if $style =~ /^dot-/;       # dot-dash, dot-dot-dash
  $style = 'dotted' if $style =~ /^wave/;       # wave
  # double lines will be handled in the color attribute as "color:color"
  $style = 'solid' if $style eq 'double';       # double
  $style = 'dashed' if $style =~ /^double-dash/;
  $style = 'invis' if $style eq 'invisible';    # invisible
  # XXX TODO: These should be (2, 0.5em, 1em) instead of 2,5,11
  $style = 'setlinewidth(2), dashed' if $style =~ /^bold-dash/;
  $style = 'setlinewidth(5)' if $style =~ /^broad/;
  $style = 'setlinewidth(11)' if $style =~ /^wide/;
  return (undef, undef) if $style eq 'solid';   # default style can be suppressed
  ($name, $style);
  }
sub _graphviz_remap_node_rotate
  {
  my ($graph, $name, $angle, $self) = @_;
  # do this only for objects, not classes
  return (undef,undef) unless ref($self) && defined $angle;
  return (undef,undef) if $angle == 0;
  # despite what the manual says, dot rotates counter-clockwise, so fix that
  $angle = 360 - $angle;
  ('orientation', $angle);
  }
sub _graphviz_remap_port
  {
  my ($graph, $name, $side, $self) = @_;
  # do this only for objects, not classes
  return (undef,undef) unless ref($self) && defined $side;
  # XXX TODO
  # remap relative ports (front etc) to "south" etc
  # has a specific port, aka shared a port with another edge
  return (undef, undef) if $side =~ /,/;
  $side = $graph->_flow_as_side($self->flow(),$side);
  $side = substr($side,0,1);    # "south" => "s"
  my $n = 'tailport'; $n = 'headport' if $name eq 'end';
  ($n, $side);
  }
sub _graphviz_remap_font
  {
  # Remap the font names
  my ($self, $name, $style) = @_;
  # XXX TODO: "times" => "Times.ttf" ?
  ('fontname', $style);
  }
sub _graphviz_remap_fontsize
  {
  # make sure the fontsize is in pixel or percent
  my ($self, $name, $style) = @_;
  # XXX TODO: This should be actually 1 em
  my $fs = '11';
  if ($style =~ /^([\d\.]+)em\z/)
    {
    $fs = $1 * 11;
    }
  elsif ($style =~ /^([\d\.]+)%\z/)
    {
    $fs = ($1 / 100) * 11;
    }
  # this is discouraged:
  elsif ($style =~ /^([\d\.]+)px\z/)
    {
    $fs = $1;
    }
  else
    {
    $self->_croak("Illegal font-size '$style'");
    }
  # font-size => fontsize
  ('fontsize', $fs);
  }
sub _graphviz_remap_border_style
  {
  my ($self, $name, $style, $node) = @_;
  my $shape = '';
  $shape = ($node->attribute('shape') || '') if ref($node);
  # some shapes don't need a border:
  return (undef,undef) if $shape =~ /^(none|invisible|img|point)\z/;
  $style = $node->attribute('borderstyle') unless defined $style;
  # valid styles are: solid dashed dotted bold invis
  $style = '' unless defined $style;
  $style = 'dotted' if $style =~ /^dot-/;       # dot-dash, dot-dot-dash
  $style = 'dashed' if $style =~ /^double-/;    # double-dash
  $style = 'dotted' if $style =~ /^wave/;       # wave
  # borderstyle double will be handled extra with peripheries=2 later
  $style = 'solid' if $style eq 'double';
  # XXX TODO: These should be (2, 0.5em, 1em) instead of 2,5,11
  $style = 'setlinewidth(2)' if $style =~ /^bold/;
  $style = 'setlinewidth(5)' if $style =~ /^broad/;
  $style = 'setlinewidth(11)' if $style =~ /^wide/;
  # "solid 0px" => "none"
  my $w = 0; $w = $node->attribute('borderwidth') if (ref($node) && $style ne 'none');
  $style = 'none' if $w == 0;
  my @rc;
  if ($style eq 'none')
    {
    my $fill = 'white'; $fill = $node->color_attribute('fill') if ref($node);
    $style = 'filled'; @rc = ('color', $fill);
    }
  # default style can be suppressed
  return (undef, undef) if $style =~ /^(|solid)\z/ && $shape ne 'rounded';
  # for graphviz v2.4 and up
  $style = 'filled' if $style eq 'solid';
  $style = 'filled,'.$style unless $style eq 'filled';
  $style = 'rounded,'.$style if $shape eq 'rounded' && $style ne 'none';
  $style =~ s/,\z//;            # "rounded," => "rounded"
  push @rc, 'style', $style;
  @rc;
  }
sub _graphviz_remap_link
  {
  my ($self, $name, $l, $object) = @_;
  # do this only for objects, not classes
  return (undef,undef) unless ref($object);
  $l = $object->link() unless defined $l;
  ('URL', $l);
  }
sub _graphviz_remap_label_color
  {
  my ($graph, $name, $color, $self) = @_;
  # do this only for objects, not classes
  return (undef,undef) unless ref($self);
  # no label => no color nec.
  return (undef, $color) if ($self->label()||'') eq '';
  $color = $self->raw_attribute('labelcolor') unless defined $color;
  # the label color falls back to the edge color
  $color = $self->attribute('color') unless defined $color;
  $color = $graph->_color_as_hex_or_hsv($self,$color);
  ('fontcolor', $color);
  }
sub _graphviz_remap_node_shape
  {
  my ($self, $name, $style, $object) = @_;
  # img needs no shape, and rounded is handled as style
  return (undef,undef) if $style =~ /^(img|rounded)\z/;
  # valid styles are: solid dashed dotted bold invis
  my $s = $style;
  $s = 'plaintext' if $style =~ /^(invisible|none|point)\z/;
  if (ref($object))
    {
    my $border = $object->attribute('borderstyle');
    $s = 'plaintext' if $border eq 'none';
    }
  ($name, $s);
  }
sub _graphviz_remap_arrow_style
  {
  my ($self, $name, $style) = @_;
  my $s = 'normal';
  $s = $style if $style =~ /^(none|open)\z/;
  $s = 'empty' if $style eq 'closed';
  my $n = 'arrowhead';
  $n = 'arrowtail' if $self->{_flip_edges};
  ($n, $s);
  }
sub _graphviz_remap_label
  {
  my ($self, $name, $label, $node) = @_;
  my $s = $label;
  # call label() to handle thinks like "autolabel: 15" properly
  $s = $node->label() if ref($node);
  if (ref($node))
    {
    # remap all "\n" and "\c" to either "\l" or "\r", depending on align
    my $align = $node->attribute('align');
    my $next_line = '\n';
    # the align of the line-ends counts for the line _before_ them, so
    # add one more to fix the last line
    $next_line = '\l', $s .= '\l' if $align eq 'left';
    $next_line = '\r', $s .= '\r' if $align eq 'right';
    $s =~ s/(^|[^\\])\\n/$1$next_line/g;        # \n => align
    }
  $s =~ s/(^|[^\\])\\c/$1\\n/g;                 # \c => \n (for center)
  my $shape = 'rect';
  $shape = ($node->attribute('shape') || '') if ref($node);
  # only for nodes and when they have a "shape: img"
  if ($shape eq 'img')
    {
    my $s = '<<TABLE BORDER="0"><TR><TD><IMG SRC="##url##" /></TD></TR></TABLE>>';
    my $url = $node->label();
    $url =~ s/\s/\+/g;                          # space
    $url =~ s/'/%27/g;                          # replace quotation marks
    $s =~ s/##url##/$url/g;
    }
  ($name, $s);
  }
#############################################################################
sub _att_as_graphviz
  {
  # convert a hash with attribute => value mappings to a string
  my ($self, $out) = @_;
  my $att = '';
  for my $atr (sort keys %$out)
    {
    my $v = $out->{$atr};
    $v =~ s/\n/\\n/g;
    $v = '"' . $v . '"' if $v !~ /^[a-z0-9A-Z]+\z/;     # quote if nec.
    # convert "x-dot-foo" to "foo". Special case "K":
    my $name = $atr; $name =~ s/^x-dot-//; $name = 'K' if $name eq 'k';
    $att .= "  $name=$v,\n";
    }
  $att =~ s/,\n\z/ /;                   # remove last ","
  if ($att ne '')
    {
    # the following makes short, single definitions to fit on one line
    if ($att !~ /\n.*\n/ && length($att) < 40)
      {
      $att =~ s/\n/ /; $att =~ s/( )+/ /g;
      }
    else
      {
      $att =~ s/\n/\n  /g;
      $att = "\n  $att";
      }
    }
  $att;
  }
use Graph::Easy::Util qw(first_kv);
sub _generate_group_edge
  {
  # Given an edge (from/to at least one group), generate the graphviz code
  my ($self, $e, $indent) = @_;
  my $edge_att = $e->attributes_as_graphviz();
  my $a = ''; my $b = '';
  my $from = $e->{from};
  my $to = $e->{to};
  ($from,$to) = ($to,$from) if $self->{_flip_edges};
  if ($from->isa('Graph::Easy::Group'))
    {
    # find an arbitray node inside the group
        my ($n, $v) = first_kv($from->{nodes});
    $a = 'ltail="cluster' . $from->{id}.'"'; # ltail=cluster0
    $from = $v;
    }
  # XXX TODO:
  # this fails for empty groups
  if ($to->isa('Graph::Easy::Group'))
    {
    # find an arbitray node inside the group
    my ($n, $v) = first_kv($to->{nodes});
    $b = 'lhead="cluster' . $to->{id}.'"';   # lhead=cluster0
    $to = $v;
    }
  my $other = $to->_graphviz_point();
  my $first = $from->_graphviz_point();
  $e->{_p} = undef;                          # mark as processed
  my $att = $a;
  $att .= ', ' . $b if $b ne ''; $att =~ s/^,//;
  if ($att ne '')
    {
    if ($edge_att eq '')
      {
      $edge_att = " [ $att ]";
      }
    else
      {
      $edge_att =~ s/ \]/, $att \]/;
      }
    }
  "$indent$first $self->{edge_type} $other$edge_att\n";              # return edge text
  }
sub _insert_edge_attribute
  {
  # insert an additional attribute into an edge attribute string
  my ($self, $att, $new_att) = @_;
  return '[ $new_att ]' if $att eq '';          # '' => '[ ]'
  # remove any potential old attribute with the same name
  my $att_name = $new_att; $att_name =~ s/=.*//;
  $att =~ s/$att_name=("[^"]+"|[^\s]+)//;
  # insert the new attribute at the end
  $att =~ s/\s?\]/,$new_att ]/;
  $att;
  }
sub _suppress_edge_attribute
  {
  # remove the named attribute from the edge attribute string
  my ($self, $att, $sup_att) = @_;
  $att =~ s/$sup_att=("(\\"|[^"])*"|[^\s\n,;]+)[,;]?//;
  $att;
  }
sub _generate_edge
  {
  # Given an edge, generate the graphviz code for it
  my ($self, $e, $indent) = @_;
  # skip links from/to groups, these will be done later
  return '' if
    $e->{from}->isa('Graph::Easy::Group') ||
    $e->{to}->isa('Graph::Easy::Group');
  my $invis = $self->{_graphviz_invis};
  # attributes for invisible helper nodes (the color will be filled in from the edge color)
  my $inv       = ' [ label="",shape=none,style=filled,height=0,width=0,fillcolor="';
  my $other = $e->{to}->_graphviz_point();
  my $first = $e->{from}->_graphviz_point();
  my $edge_att = $e->attributes_as_graphviz();
  my $txt = '';
  my $modify_edge = 0;
  my $suppress_start = (!$self->{_flip_edges} ? 'arrowtail=none' : 'arrowhead=none');
  my $suppress_end   = ( $self->{_flip_edges} ? 'arrowtail=none' : 'arrowhead=none');
  my $suppress;
  # if the edge has a shared start/end port
  if ($e->has_ports())
    {
    my @edges = ();
    my ($side,@port) = $e->port('start');
    @edges = $e->{from}->edges_at_port('start',$side,@port) if defined $side && @port > 0;
    if (@edges > 1)                                  # has strict port
      {
      # access the invisible node
      my $sp = $e->port('start');
      my $key = "$e->{from}->{name},start,$sp";
      my $invis_id = $invis->{$key};
      $suppress = $suppress_start;
      if (!defined $invis_id)
        {
        # create the invisible helper node
        # find a name for it, carefully avoiding names of other nodes:
        $self->{_graphviz_invis_id}++ while (defined $self->node($self->{_graphviz_invis_id}));
        $invis_id = $self->{_graphviz_invis_id}++;
        # output the helper node
        my $e_color = $e->color_attribute('color');
        $txt .= $indent . "$invis_id$inv$e_color\" ]\n";
        my $e_att = $self->_insert_edge_attribute($edge_att,$suppress_end);
        $e_att = $self->_suppress_edge_attribute($e_att,'label');
        my $before = ''; my $after = ''; my $i = $indent;
        if ($e->{group})
          {
          $before = $indent . 'subgraph "cluster' . $e->{group}->{id} . "\" {\n";
          $after = $indent . "}\n";
          $i = $indent . $indent;
          }
        if ($self->{_flip_edges})
          {
          $txt .= $before . $i . "$invis_id $self->{_edge_type} $first$e_att\n" . $after;
          }
        else
          {
          $txt .= $before . $i . "$first $self->{_edge_type} $invis_id$e_att\n" . $after;
          }
        $invis->{$key} = $invis_id;          # mark as created
        }
      # "joint0" etc
      $first = $invis_id;
      $modify_edge++;
      }
    ($side,@port) = $e->port('end');
    @edges = ();
    @edges = $e->{to}->edges_at_port('end',$side,@port) if defined $side && @port > 0;
    if (@edges > 1)
      {
      my $ep = $e->port('end');
      my $key = "$e->{to}->{name},end,$ep";
      my $invis_id = $invis->{$key};
      $suppress = $suppress_end;
      if (!defined $invis_id)
        {
        # create the invisible helper node
        # find a name for it, carefully avoiding names of other nodes:
        $self->{_graphviz_invis_id}++ while (defined $self->node($self->{_graphviz_invis_id}));
        $invis_id = $self->{_graphviz_invis_id}++;
        my $e_att = $self->_insert_edge_attribute($edge_att,$suppress_start);
        # output the helper node
        my $e_color = $e->color_attribute('color');
        $txt .= $indent . "$invis_id$inv$e_color\" ]\n";
        my $before = ''; my $after = ''; my $i = $indent;
        if ($e->{group})
          {
          $before = $indent . 'subgraph "cluster' . $e->{group}->{id} . "\" {\n";
          $after = $indent . "}\n";
          $i = $indent . $indent;
          }
        if ($self->{_flip_edges})
          {
          $txt .= $before . $i . "$other $self->{_edge_type} $invis_id$e_att\n" . $after;
          }
        else
          {
          $txt .= $before . $i . "$invis_id $self->{_edge_type} $other$e_att\n" . $after;
          }
        $invis->{$key} = $invis_id;                  # mark as output
        }
      # "joint1" etc
      $other = $invis_id;
      $modify_edge++;
      }
    }
  ($other,$first) = ($first,$other) if $self->{_flip_edges};
  $e->{_p} = undef;                          # mark as processed
  $edge_att = $self->_insert_edge_attribute($edge_att,$suppress)
    if $modify_edge;
  $txt . "$indent$first $self->{_edge_type} $other$edge_att\n";              # return edge text
  }
sub _order_group
  {
  my ($self,$group) = @_;
  $group->{_order}++;
  for my $sg (ord_values( $group->{groups}))
        {
                $self->_order_group($sg);
        }
  }
sub _as_graphviz_group
  {
  my ($self,$group) = @_;
  my $txt = '';
    # quote special chars in group name
    my $name = $group->{name}; $name =~ s/([\[\]\(\)\{\}\#"])/\\$1/g;
   return if $group->{_p};
    # output group attributes first
    my $indent = '  ' x ($group->{_order});
    $txt .= $indent."subgraph \"cluster$group->{id}\" {\n${indent}label=\"$name\";\n";
        for my $sg (ord_values ( $group->{groups} ))
        {
                #print '--'.$sg->{name}."\n";
                $txt .= $self->_as_graphviz_group($sg,$indent);
                $sg->{_p} = 1;
        }
    # Make a copy of the attributes, including our class attributes:
    my $copy = {};
    my $attribs = $group->get_attributes();
    for my $key (sort keys %$attribs)
      {
      $copy->{$key} = $attribs->{$key};
      }
    # set some defaults
    $copy->{'borderstyle'} = 'solid' unless defined $copy->{'borderstyle'};
    my $out = $self->_remap_attributes( $group->class(), $copy, $remap, 'noquote');
    # Set some defaults:
    $out->{fillcolor} = '#a0d0ff' unless defined $out->{fillcolor};
    $out->{labeljust} = 'l' unless defined $out->{labeljust};
    my $att = '';
    # we need to output style first ("filled" and "color" need come later)
    for my $atr (reverse sort keys %$out)
      {
      my $v = $out->{$atr};
      $v = '"' . $v . '"' if $v !~ /^[a-z0-9A-Z]+\z/;   # quote if nec.
      # convert "x-dot-foo" to "foo". Special case "K":
      my $name = $atr; $name =~ s/^x-dot-//; $name = 'K' if $name eq 'k';
      $att .= $indent."$name=$v;\n";
      }
    $txt .= $att . "\n" if $att ne '';
    # output nodes (w/ or w/o attributes) in that group
    for my $n ($group->sorted_nodes())
      {
      # skip nodes that are relativ to others (these are done as part
      # of the HTML-like label of their parent)
      next if $n->{origin};
      my $att = $n->attributes_as_graphviz();
      $n->{_p} = undef;                      # mark as processed
      $txt .= $indent . $n->as_graphviz_txt() . $att . "\n";
      }
    # output node connections in this group
    for my $e (ord_values $group->{edges})
      {
      next if exists $e->{_p};
      $txt .= $self->_generate_edge($e, $indent);
      }
    $txt .= $indent."}\n";
   return $txt;
  }
sub _as_graphviz
  {
  my ($self) = @_;
  # convert the graph to a textual representation
  # does not need a layout() beforehand!
  my $name = "GRAPH_" . ($self->{gid} || '0');
  my $type = $self->attribute('type');
  $type = $type eq 'directed' ? 'digraph' : 'graph';    # directed or undirected?
  $self->{_edge_type} = $type eq 'digraph' ? '->' : '--'; # "a -- b" vs "a -> b"
  my $txt = "$type $name {\n\n" .
            "  // Generated by Graph::Easy $Graph::Easy::VERSION" .
            " at " . scalar localtime() . "\n\n";
  my $flow = $self->attribute('graph','flow');
  $flow = 'east' unless defined $flow;
  $flow = Graph::Easy->_direction_as_number($flow);
  # for LR, BT layouts
  $self->{_flip_edges} = 0;
  $self->{_flip_edges} = 1 if $flow == 270 || $flow == 0;
  my $groups = $self->groups();
  # to keep track of invisible helper nodes
  $self->{_graphviz_invis} = {};
  # name for invisible helper nodes
  $self->{_graphviz_invis_id} = 'joint0';
  # generate the class attributes first
  my $atts =  $self->{att};
  # It is not possible to set attributes for groups in the DOT language that way
  for my $class (qw/edge graph node/)
    {
    next if $class =~ /\./;             # skip subclasses
    my $out = $self->_remap_attributes( $class, $atts->{$class}, $remap, 'noquote');
    # per default, our nodes are rectangular, white, filled boxes
    if ($class eq 'node')
      {
      $out->{shape} = 'box' unless $out->{shape};
      $out->{style} = 'filled' unless $out->{style};
      $out->{fontsize} = '11' unless $out->{fontsize};
      $out->{fillcolor} = 'white' unless $out->{fillcolor};
      }
    elsif ($class eq 'graph')
      {
      $out->{rankdir} = 'LR' if $flow == 90 || $flow == 270;
      $out->{labelloc} = 'top' if defined $out->{label} && !defined $out->{labelloc};
      $out->{style} = 'filled' if $groups > 0;
      }
    elsif ($class eq 'edge')
      {
      $out->{dir} = 'back' if $flow == 270 || $flow == 0;
      my ($name,$style) = $self->_graphviz_remap_arrow_style('',
        $self->attribute('edge','arrowstyle') );
      $out->{$name} = $style;
      }
    my $att = $self->_att_as_graphviz($out);
    $txt .= "  $class [$att];\n" if $att ne '';
    }
  $txt .= "\n" if $txt ne '';           # insert newline
  ###########################################################################
  # output groups as subgraphs
  # insert the edges into the proper group
  $self->_edges_into_groups() if $groups > 0;
  # output the groups (aka subclusters)
  for my $group (ord_values $self->{groups})
  {
   $self->_order_group($group);
  }
  for my $group (sort { $a->{_order} cmp $b->{_order} } values %{$self->{groups}})
  {
    $txt .= $self->_as_graphviz_group($group) || '';
  }
  my $root = $self->attribute('root');
  $root = '' unless defined $root;
  my $count = 0;
  # output nodes with attributes first, sorted by their name
  for my $n (sort { $a->{name} cmp $b->{name} } values %{$self->{nodes}})
    {
    next if exists $n->{_p};
    # skip nodes that are relativ to others (these are done as part
    # of the HTML-like label of their parent)
    next if $n->{origin};
    my $att = $n->attributes_as_graphviz($root);
    if ($att ne '')
      {
      $n->{_p} = undef;                      # mark as processed
      $count++;
      $txt .= "  " . $n->as_graphviz_txt() . $att . "\n";
      }
    }
  $txt .= "\n" if $count > 0;                # insert a newline
  my @nodes = $self->sorted_nodes();
  # output the edges
  foreach my $n (@nodes)
    {
    my @out = $n->successors();
    my $first = $n->as_graphviz_txt();
    if ((@out == 0) && ( (scalar $n->predecessors() || 0) == 0))
      {
      # single node without any connections (unless already output)
      $txt .= "  " . $first . "\n" unless exists $n->{_p} || $n->{origin};
      }
    # for all outgoing connections
    foreach my $other (reverse @out)
      {
      # in case there is more than one edge going from N to O
      my @edges = $n->edges_to($other);
      foreach my $e (@edges)
        {
        next if exists $e->{_p};
        $txt .= $self->_generate_edge($e, '  ');
        }
      }
    }
  # insert now edges between groups (clusters/subgraphs)
  foreach my $e (ord_values $self->{edges})
    {
    $txt .= $self->_generate_group_edge($e, '  ')
     if $e->{from}->isa('Graph::Easy::Group') ||
        $e->{to}->isa('Graph::Easy::Group');
    }
  # clean up
  for my $n ( ord_values( $self->{nodes}), ord_values( $self->{edges} ))
    {
    delete $n->{_p};
    }
  delete $self->{_graphviz_invis};           # invisible helper nodes for joints
  delete $self->{_flip_edges};
  delete $self->{_edge_type};
  $txt .  "\n}\n";                              # close the graph
  }
package Graph::Easy::Node;
sub attributes_as_graphviz
  {
  # return the attributes of this node as text description
  my ($self, $root) = @_;
  $root = '' unless defined $root;
  my $att = '';
  my $class = $self->class();
  return '' unless ref $self->{graph};
  my $g = $self->{graph};
  # get all attributes, excluding the class attributes
  my $a = $self->raw_attributes();
  # add the attributes that are listed under "always":
  my $attr = $self->{att};
  my $base_class = $class; $base_class =~ s/\..*//;
  my $list = $remap->{always}->{$class} || $remap->{always}->{$base_class};
  for my $name (@$list)
    {
    # for speed, try to look it up directly
    # look if we have a code ref:
    if ( ref($remap->{$base_class}->{$name}) ||
         ref($remap->{all}->{$name}) )
      {
      $a->{$name} = $self->raw_attribute($name);
      if (!defined $a->{$name})
        {
        my $b_attr = $g->get_attribute($base_class,$name);
        my $c_attr = $g->get_attribute($class,$name);
        if (defined $b_attr && defined $c_attr && $b_attr ne $c_attr)
          {
          $a->{$name} = $c_attr;
          $a->{$name} = $b_attr unless defined $a->{$name};
          }
        }
      }
    else
      {
      $a->{$name} = $attr->{$name};
      $a->{$name} = $self->attribute($name) unless defined $a->{$name} && $a->{$name} ne 'inherit';
      }
    }
  $a = $g->_remap_attributes( $self, $a, $remap, 'noquote');
  # do not needlessly output labels:
  delete $a->{label} if !$self->isa('Graph::Easy::Edge') &&               # not an edge
        exists $a->{label} && $a->{label} eq $self->{name};
  # generate HTML-like labels for nodes with children, but do so only
  # for the node which is not itself a child
  if (!$self->{origin} && $self->{children} && keys %{$self->{children}} > 0)
    {
    #print "Generating HTML-like label for $self->{name}\n";
    $a->{label} = $self->_html_like_label();
    # make Graphviz avoid the outer border
    $a->{shape} = 'none';
    }
  # bidirectional and undirected edges
  if ($self->{bidirectional})
    {
    delete $a->{dir};
    my ($n,$s) = Graph::Easy::_graphviz_remap_arrow_style(
        $self,'', $self->attribute('arrowstyle'));
    $a->{arrowhead} = $s;
    $a->{arrowtail} = $s;
    }
  if ($self->{undirected})
    {
    delete $a->{dir};
    $a->{arrowhead} = 'none';
    $a->{arrowtail} = 'none';
    }
  if (!$self->isa_cell())
    {
    # borderstyle: double:
    my $style = $self->attribute('borderstyle');
    my $w = $self->attribute('borderwidth');
    $a->{peripheries} = 2 if $style =~ /^double/ && $w > 0;
    }
  # For nodes with shape plaintext, set the fillcolor to the background of
  # the graph/group
  my $shape = $a->{shape} || 'rect';
  if ($class =~ /node/ && $shape eq 'plaintext')
    {
    my $p = $self->parent();
    $a->{fillcolor} = $p->attribute('fill');
    $a->{fillcolor} = 'white' if $a->{fillcolor} eq 'inherit';
    }
  $shape = $self->attribute('shape') unless $self->isa_cell();
  # for point-shaped nodes, include the point as label and set width/height
  if ($shape eq 'point')
    {
    require Graph::Easy::As_ascii;              # for _u8 and point-style
    my $style = $self->_point_style(
        $self->attribute('pointshape'),
        $self->attribute('pointstyle') );
    $a->{label} = $style;
    # for point-shaped invisible nodes, set height/width = 0
    $a->{width} = 0, $a->{height} = 0 if $style eq '';
    }
  if ($shape eq 'invisible')
    {
    $a->{label} = ' ';
    }
  $a->{rank} = '0' if $root ne '' && $root eq $self->{name};
  # create the attributes as text:
  for my $atr (sort keys %$a)
    {
    my $v = $a->{$atr};
    $v =~ s/"/\\"/g;            # '2"' => '2\"'
    # don't quote labels like "<<TABLE.."
    if ($atr eq 'label' && $v =~ /^<<TABLE/)
      {
      my $va = $v; $va =~ s/\\"/"/g;            # unescape \"
      $att .= "$atr=$va, ";
      next;
      }
    $v = '"' . $v . '"' if $v !~ /^[a-z0-9A-Z]+\z/
          || $atr eq 'URL';     # quote if nec.
    # convert "x-dot-foo" to "foo". Special case "K":
    my $name = $atr; $name =~ s/^x-dot-//; $name = 'K' if $name eq 'k';
    $att .= "$name=$v, ";
    }
  $att =~ s/,\s$//;             # remove last ","
  # generate attribute text if nec.
  $att = ' [ ' . $att . ' ]' if $att ne '';
  $att;
  }
sub _html_like_label
  {
  # Generate a HTML-like label from one node with its relative children
  my ($self) = @_;
  my $cells = {};
  my $rc = $self->_do_place(0,0, { cells => $cells, cache => {} } );
  # <TABLE BORDER="0" CELLPADDING="0" CELLSPACING="0"><TR><TD>Name2</TD></TR><TR><TD
  # ALIGN ="LEFT" BALIGN="LEFT" PORT="E4">Somewhere<BR/>test1<BR>test</TD></TR></TABLE>
  my $label = '<<TABLE BORDER="0"><TR>';
  my $old_y = 0; my $old_x = 0;
  # go through all children, and sort them by Y then X coordinate
  my @cells = ();
  for my $cell (sort {
        my ($ax,$ay) = split /,/,$a;
        my ($bx,$by) = split /,/,$b;
        $ay <=> $by or $ax <=> $bx; } keys %$cells )
    {
    #print "cell $cell\n";
    my ($x,$y) = split /,/, $cell;
    if ($y > $old_y)
      {
      $label .= '</TR><TR>'; $old_x = 0;
      }
    my $n = $cells->{$cell};
    my $l = $n->label();
    $l =~ s/\\n/<BR\/>/g;
    my $portname = $n->{autosplit_portname};
    $portname = $n->label() unless defined $portname;
    my $name = $self->{name};
    $portname =~ s/\"/\\"/g;                    # quote "
    $name =~ s/\"/\\"/g;                        # quote "
    # store the "nodename:portname" combination for potential edges
    $n->{_graphviz_portname} = '"' . $name . '":"' . $portname . '"';
    if (($x - $old_x) > 0)
      {
      # need some spacers
      $label .= '<TD BORDER="0" COLSPAN="' . ($x - $old_x) . '"></TD>';
      }
    $label .= '<TD BORDER="1" PORT="' . $portname . '">' . $l . '</TD>';
    $old_y = $y + $n->{cy}; $old_x = $x + $n->{cx};
    }
  # return "<<TABLE.... /TABLE>>"
  $label . '</TR></TABLE>>';
  }
sub _graphviz_point
  {
  # return the node as the target/source of an edge
  # either "name", or "name:port"
  my ($n) = @_;
  return $n->{_graphviz_portname} if exists $n->{_graphviz_portname};
  $n->as_graphviz_txt();
  }
sub as_graphviz_txt
  {
  # return the node itself (w/o attributes) as graphviz representation
  my $self = shift;
  my $name = $self->{name};
  # escape special chars in name (including doublequote!)
  $name =~ s/([\[\]\(\)\{\}"])/\\$1/g;
  # quote if necessary:
  # 2, A, A2, "2A", "2 A" etc
  $name = '"' . $name . '"' if $name !~ /^([a-zA-Z_]+|\d+)\z/ ||
        $name =~ /^(subgraph|graph|node|edge|strict)\z/i;       # reserved keyword
  $name;
  }
1;
__END__
HideShow 47 lines of Pod
=head1 NAME
Graph::Easy::As_graphviz - Generate graphviz description from graph object
=head1 SYNOPSIS
        use Graph::Easy;
        my $graph = Graph::Easy->new();
        my $bonn = Graph::Easy::Node->new(
                name => 'Bonn',
        );
        my $berlin = Graph::Easy::Node->new(
                name => 'Berlin',
        );
        $graph->add_edge ($bonn, $berlin);
        print $graph->as_graphviz();
        # prints something like:
        # digraph NAME { Bonn -> Berlin }
=head1 DESCRIPTION
C<Graph::Easy::As_graphviz> contains just the code for converting a
L<Graph::Easy|Graph::Easy> object to a textual description suitable for
feeding it to Graphviz programs like C<dot>.
=head1 EXPORT
Exports nothing.
=head1 SEE ALSO
L<Graph::Easy>, L<Graph::Easy::Parser::Graphviz>.
=head1 AUTHOR
Copyright (C) 2004 - 2008 by Tels L<http://bloodgate.com>
See the LICENSE file for information.
=cut