#  Copyright (c) 1997-2006
#  Ewgenij Gawrilow, Michael Joswig (Technische Universitaet Berlin, Germany)
#  http://www.math.tu-berlin.de/polymake,  mailto:polymake@math.tu-berlin.de
#
#  This program is free software; you can redistribute it and/or modify it
#  under the terms of the GNU General Public License as published by the
#  Free Software Foundation; either version 2, or (at your option) any
#  later version: http://www.gnu.org/licenses/gpl.txt.
#
#  This program is distributed in the hope that it will be useful,
#  but WITHOUT ANY WARRANTY; without even the implied warranty of
#  MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
#  GNU General Public License for more details.
#-----------------------------------------------------------------------------
#  $Project: polymake $$Id: visual_graph.rules 7533 2006-12-20 23:55:58Z gawrilow $


package Visual::PolytopeGraph;

use Struct (
   [ '@ISA' => 'Visual::Container' ],
   '$Polytope',
   [ '@VertexSubset' => 'undef' ],
);

method basis_graph { $_[0]->elements->[0] }


# In the spring embedding of the graph with a superposed linear objective function,
# controls the relative force magnitude along the z-axis
custom $embedding_objective_factor=1;


# Illustrate the behavior of a linear objective function on the polytope.
# Color the nodes according to the value the objective function takes
# on the vertices (@see Polytope.VERTEX_COLORS)
# 
# The spring embedder applies an additional force, which tries to arrange the nodes in the z-axis direction
# corresponding to the objective function values.

user_method VERTEX_COLORS {
   my ($self)=@_;
   my $lp=$self->Polytope;
   my $G=$self->basis_graph;
   $G->NodeColor= $self->VertexSubset ? subset($lp->VERTEX_COLORS, @{$self->VertexSubset}) : $lp->VERTEX_COLORS;
   if (detect_dynamic(my $coord=$G->Coord)) {
      $coord->push('z-ordering' => $lp->lookup_pv("LINEAR_OBJECTIVE | ABSTRACT_OBJECTIVE")->property->name,
		   'z-factor' => $embedding_objective_factor);
   }
   visualize($self);
}


# Illustrate the behavior of a linear objective function on the polytope.
# The vertices belonging to @see MINIMAL_FACE and @see MAXIMAL_FACE are drawn in distinct colors
# 
# The spring embedder applies an additional force, which tries to arrange the nodes in the z-axis direction
# corresponding to the objective function values.
#
# option: min => minimal face color (default: yellow)
# option: max => maximal face color (default: red)

user_method MIN_MAX_FACE({ min => $Visual::Color::min, max => $Visual::Color::max }) {
   my ($self, $decor)=@_;
   my $lp=$self->Polytope;
   my $G=$self->basis_graph;
   my ($maximal_face, $minimal_face)=($lp->MAXIMAL_FACE, $lp->MINIMAL_FACE);
   my %colors;
   if ($self->VertexSubset) {
      my $i=0;
      my %renumber=map { $_ => $i++ } @{$self->VertexSubset};
      $colors{$_}=$decor->{min} for grep { defined($_) } @renumber{$minimal_face =~ /\d+/g};
      $colors{$_}=$decor->{max} for grep { defined($_) } @renumber{$maximal_face =~ /\d+/g};
   } else {
      $colors{$_}=$decor->{min} for $minimal_face =~ /\d+/g;
      $colors{$_}=$decor->{max} for $maximal_face =~ /\d+/g;
   }
   $G->merge(NodeColor => \%colors);
   if (detect_dynamic(my $coord=$G->Coord)) {
      $coord->push('z-ordering' => $lp->lookup_pv("LINEAR_OBJECTIVE | ABSTRACT_OBJECTIVE")->property->name,
		   'z-factor' => $embedding_objective_factor);
   }
   visualize($self);
}

# Show the growth direction of a linear objective function via arrowed edges.

user_method DIRECTED_GRAPH {
   my ($self)=@_;
   my $lp=$self->Polytope;
   if ($self->VertexSubset) {
      my @dg;
      client("induced_subgraph", $lp, "DIRECTED_GRAPH", [ "{".join(" ", @{$self->VertexSubset})."}\n" ], \@dg, "-nol");
      $self->basis_graph->Graph=\@dg;
   } else {
      $self->basis_graph->Graph=$lp->DIRECTED_GRAPH;
   }
   $self->Name="DIRECTED_GRAPH of ".$lp->name;
   $self->basis_graph->Directed=1;
   visualize($self);
}


###########################################################################################
object Polytope;

# category: Visualization
# Visualize the @see GRAPH of a polyhedron.
# option: seed => random seed value for the string embedder
# return: Visual::PolytopeGraph

user_method VISUAL_GRAPH(%Visual::Graph::decorations, { seed => undef }) {
   my ($this, $decor, $seed)=@_;
   my $G=new Visual::Graph(
			   Name => $this->name,
			   Graph => $this->GRAPH,
			   NodeLabels => $this->lookup("VERTEX_LABELS"),
			   Coord => spring_embedding_3d($this, "GRAPH", %$seed),
			   $decor,
			  );
   visualize( new Visual::PolytopeGraph(
					Name => "GRAPH of " . $this->name,
					Polytope => $this,
					$G
				       ));
}


# category: Visualization
# Visualize the @see DUAL_GRAPH of a polyhedron.
# option: seed => random seed value for the string embedder
# return: Visual::Graph

user_method VISUAL_DUAL_GRAPH(%Visual::Graph::decorations, { seed => undef }) {
   my ($this, $decor, $seed)=@_;
   visualize( new Visual::Graph(
				Name => $this->name,
				Title => "DUAL_GRAPH of ".$this->name,
				Graph => $this->DUAL_GRAPH,
				NodeLabels => $this->lookup("FACET_LABELS"),
				Coord => spring_embedding_3d($this, "DUAL_GRAPH", %$seed),
				$decor,
			       ));
}


# category: Visualization
# Visualize the @see BOUNDED_GRAPH of a polyhedron.
# option: seed => random seed value for the string embedder
# return: Visual::PolytopeGraph

user_method VISUAL_BOUNDED_GRAPH(%Visual::Graph::decorations, { seed => undef }) {
   my ($this, $decor, $seed)=@_;
   my $labels=$this->lookup("VERTEX_LABELS");
   my @indices=map { /\((\d+)/ } @{$this->BOUNDED_GRAPH};

   my $G=new Visual::Graph(
			   Name => $this->name,
			   Graph => $this->BOUNDED_GRAPH,
			   NodeLabels => $labels ? subset(split_labels($labels), @indices) : \@indices,
			   Coord => spring_embedding_3d($this, "BOUNDED_GRAPH", "skip-node-attr", undef, %$seed),
			   $decor,
			  );
   visualize( new Visual::PolytopeGraph(
					Name => "BOUNDED_GRAPH of " . $this->name,
					Polytope => $this,
					VertexSubset => \@indices,
					$G
				       ));
}


#########################################################################################
#
#  Face lattice visualization
#
package Visual::PolytopeLattice;

use Struct (
   [ '@ISA' => 'Visual::Lattice' ],
   '$Polytope',
);

# Illustrate the behavior of a linear objective function on the polytope.
# Draw the filters of the @see MAXIMAL_FACE and @see MINIMAL_FACE in distinct colors.
#
# option: min => minimal face color (default: yellow)
# option: max => maximal face color (default: red)

user_method MIN_MAX_FACE({ min => $Visual::Color::min, max => $Visual::Color::max }) {
   my ($self, $decor)=@_;
   my $lp=$self->Polytope;
   if (defined (my $min_face=$lp->MINIMAL_FACE)) {
      $self->add_subcomplex($self->Polytope->HASSE_DIAGRAM, [ $min_face ],
			    { NodeColor => "border $decor->{min}",  EdgeColor => $decor->{min}, show_filter=>1 });
   }
   if (defined (my $max_face=$lp->MAXIMAL_FACE)) {
      $self->add_subcomplex($self->Polytope->HASSE_DIAGRAM, [ $max_face ],
			    { NodeColor => "border $decor->{max}",  EdgeColor => $decor->{max}, show_filter=>1 });
   }
   visualize($self);
}

#########################################################################################

object Polytope;

# category: Visualization
# Visualize the @see HASSE_DIAGRAM of a polyhedron as a multi-layer graph.
# option: seed => random seed value for the node placement
# return: Visual::PolytopeLattice

user_method VISUAL_FACE_LATTICE(%Visual::Lattice::decorations, { seed => undef }) {
   my ($this, $decor, $seed)=@_;
   my ($dims, @graph)=@{$this->HASSE_DIAGRAM};
   $graph[0] =~ s/^\s*<//;  pop @graph;
   my ($bottom_node, $top_node)= $graph[0] =~ /\Q({}\E/ ? (0, $#graph) : ($#graph, 0);

   my @vertex_labels=Visual::Lattice::prepare_vertex_labels($this, "VERTEX_LABELS");
   my @labels=("")x@graph;

   my $n=1;
   foreach (@graph[1..$#graph-1]) {	# unless top/bottom node
      s/\{(.*?)\}\s+//;  my $label=$1;
      if (@vertex_labels) {
	 $label =~ s/(\d+)/$vertex_labels[$1]/g;
      }
      $labels[$n]=$label;
      ++$n;
   }

   $labels[$top_node]=$labels[$bottom_node]=" ";
   $graph[$top_node]="";

   visualize( new Visual::PolytopeLattice(
      Name => $this->name,
      Title => "Face lattice of ".$this->name,
      Polytope => $this,
      Graph => \@graph,
      top_node => $top_node,
      Directed => 1,
      Mode => "primal",
      NodeLabels => \@labels,
      NodeColor => { $top_node => "0 0 0" },
      NodeStyle => "face",
      Coord => hd_embedding($this, "HASSE_DIAGRAM", %$seed),
      $decor
   ));
}


# category: Visualization
# Visualize the @see DUAL_FACE_LATTICE of a polyhedron as a multi-layer graph.
# option: seed => random seed value for the node placement
# return: Visual::PolytopeLattice

user_method VISUAL_DUAL_FACE_LATTICE(%Visual::Lattice::decorations, { seed => undef }) {
   my ($this, $decor, $seed)=@_;
   my ($dims, @graph)=@{$this->HASSE_DIAGRAM};
   $graph[0] =~ s/^\s*<//;  pop @graph;
   my @dims=split /\s+/, $dims;

   my @facet_labels=Visual::Lattice::prepare_vertex_labels($this, "FACET_LABELS");
   my @dual_labels=(undef)x@graph;
   my @labels=("")x@graph;

   my ($d_first, $d_last, $d_step, $bottom_node, $top_node)= $graph[0] =~ /\Q({}\E/
    ? (  -2,    -$#dims-2,  -1,        0,         $#graph)
    : (   0,     $#dims,     1,     $#graph,         0);

   for (my $d=$d_first; $d != $d_last;  $d+=$d_step) {
      foreach my $n ($dims[$d] .. $dims[$d+1]-1) {
	 $graph[$n] =~ s/\{.*?\}\s+//;
	 foreach my $to ($graph[$n] =~ /\d+/g) {
	    @{$dual_labels[$n]}{keys %{$dual_labels[$to]}}=();
	 }
         if (! keys %{$dual_labels[$n]}) {
	    $dual_labels[$n]->{$n-$dims[$d_first]}=1;
	 }
	 my $label=join(" ", sort { $a <=> $b } keys %{$dual_labels[$n]});
	 if (@facet_labels) {
	    $label =~ s/(\d+)/$facet_labels[$1]/g;
	 }
	 $labels[$n]=$label;
      }
   }

   $labels[$top_node]=$labels[$bottom_node]=" ";
   $graph[$top_node]="";
   visualize( new Visual::PolytopeLattice(
      Name => $this->name,
      Title => "Dual face lattice of ".$this->name,
      Polytope => $this,
      Graph => \@graph,
      top_node => $top_node,
      Directed => 1,
      Mode => "dual",
      NodeLabels => \@labels,
      NodeColor => { $top_node => "0 0 0" },
      NodeStyle => "face",
      Coord => hd_embedding($this, "HASSE_DIAGRAM", %$seed),
      $decor
   ));
}


# Local Variables:
# mode: perl
# c-basic-offset:3
# End: