#  Copyright (c) 1997-2024
#  Ewgenij Gawrilow, Michael Joswig, and the polymake team
#  Technische Universität Berlin, Germany
#  https://polymake.org
#
#  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.
#-------------------------------------------------------------------------------

object Graph {

rule N_NODES : ADJACENCY {
   $this->N_NODES=$this->ADJACENCY->nodes;
}
weight 0.1;

rule N_EDGES : ADJACENCY {
   $this->N_EDGES=$this->ADJACENCY->edges;
}
weight 0.10;

rule NODE_DEGREES : ADJACENCY {
   $this->NODE_DEGREES(temporary)=[ map { $this->ADJACENCY->degree($_) } 0..($this->ADJACENCY->nodes-1) ];
}
weight 1.10;

# @category Combinatorics
# Explore the graph as a sequence of its edges.
# @return Array<Set<Int>>
user_method EDGES {
  my $g = shift;
  my $a = new Array<Set<Int> >($g->N_EDGES);
  my $i = 0;
  for ( my $e=entire(edges($g->ADJACENCY)); $e; ++$e, ++$i ) { 
     $a->[$i] = new Set<Int>([$e->from_node,$e->to_node]);
  }
  return $a;
}

}

object Graph<Undirected> {

rule CONNECTED : ADJACENCY {
   $this->CONNECTED=is_connected($this->ADJACENCY);
}
weight 1.10;

rule CONNECTED_COMPONENTS : ADJACENCY {
   $this->CONNECTED_COMPONENTS=connected_components($this->ADJACENCY);
}
weight 1.10;

rule N_CONNECTED_COMPONENTS : CONNECTED_COMPONENTS {
   $this->N_CONNECTED_COMPONENTS=$this->CONNECTED_COMPONENTS->rows;
}
weight 0.1;

rule CONNECTED : N_CONNECTED_COMPONENTS {
   $this->CONNECTED = $this->N_CONNECTED_COMPONENTS <= 1;
}
weight 0.1;

rule BICONNECTED_COMPONENTS : ADJACENCY {
   $this->BICONNECTED_COMPONENTS=biconnected_components($this->ADJACENCY);
}
weight 1.10;

rule CONNECTED_COMPONENTS : NodePerm.CONNECTED_COMPONENTS, NodePerm.PERMUTATION {
   $this->CONNECTED_COMPONENTS=permuted_cols($this->NodePerm->CONNECTED_COMPONENTS, $this->NodePerm->PERMUTATION);
};

rule BICONNECTED_COMPONENTS : NodePerm.BICONNECTED_COMPONENTS, NodePerm.PERMUTATION {
   $this->BICONNECTED_COMPONENTS=permuted_cols($this->NodePerm->BICONNECTED_COMPONENTS, $this->NodePerm->PERMUTATION);
};

rule DIAMETER : ADJACENCY {
   $this->DIAMETER=diameter($this->ADJACENCY);
}
precondition : CONNECTED;

rule BIPARTITE, SIGNATURE : ADJACENCY {
   bipartite_signature($this);
}
precondition : N_NODES;
weight 1.10;


rule TRIANGLE_FREE : ADJACENCY {
   $this->TRIANGLE_FREE=triangle_free($this->ADJACENCY);
}

rule TRIANGLE_FREE : { $this->TRIANGLE_FREE=1 }
precondition : BIPARTITE;
weight 0.1;

rule CONNECTIVITY : ADJACENCY {
   $this->CONNECTIVITY=connectivity($this->ADJACENCY);
}

rule MAX_CLIQUES : ADJACENCY {
   $this->MAX_CLIQUES=max_cliques($this->ADJACENCY);
}

rule MAX_INDEPENDENT_SETS : ADJACENCY {
   $this->MAX_INDEPENDENT_SETS=max_independent_sets($this->ADJACENCY);
}

rule DEGREE_SEQUENCE, AVERAGE_DEGREE : ADJACENCY {
   degree_sequence($this);
}

rule CHARACTERISTIC_POLYNOMIAL : N_NODES, ADJACENCY {
   my $x = monomials(1);
   my $u = new UniPolynomial(-1);
   my $n = $this->N_NODES;
   my $m = new Matrix<UniPolynomial>($n, $n); # don't use unit_matrix because it will get full
   
   for (my $i=0; $i<$n; ++$i) {
      $m->[$i]->[$i] = $x;
   }
   
   for ( my $e=entire(edges($this->ADJACENCY)); $e; ++$e ) { 
      $m->[$e->from_node]->[$e->to_node] = $u;
      $m->[$e->to_node]->[$e->from_node] = $u;
   }

   $this->CHARACTERISTIC_POLYNOMIAL = det($m);
}

}

object Graph<Directed> {

rule WEAKLY_CONNECTED : ADJACENCY {
   $this->WEAKLY_CONNECTED=is_weakly_connected($this->ADJACENCY);
}
weight 1.10;

rule WEAKLY_CONNECTED_COMPONENTS : ADJACENCY {
   $this->WEAKLY_CONNECTED_COMPONENTS=weakly_connected_components($this->ADJACENCY);
}
weight 1.10;

rule WEAKLY_CONNECTED : WEAKLY_CONNECTED_COMPONENTS {
   $this->WEAKLY_CONNECTED = $this->WEAKLY_CONNECTED_COMPONENTS->rows <= 1;
}
weight 0.1;

rule STRONGLY_CONNECTED : ADJACENCY {
   $this->STRONGLY_CONNECTED=is_strongly_connected($this->ADJACENCY);
}
weight 1.10;

rule STRONG_COMPONENTS : ADJACENCY {
   $this->STRONG_COMPONENTS=strong_components($this->ADJACENCY);
}
weight 1.10;

rule STRONGLY_CONNECTED : STRONG_COMPONENTS {
   $this->STRONGLY_CONNECTED = $this->STRONG_COMPONENTS->rows <= 1;
}
weight 0.1;

rule WEAKLY_CONNECTED_COMPONENTS : NodePerm.WEAKLY_CONNECTED_COMPONENTS, NodePerm.PERMUTATION {
   $this->WEAKLY_CONNECTED_COMPONENTS=permuted_cols($this->NodePerm->WEAKLY_CONNECTED_COMPONENTS, $this->NodePerm->PERMUTATION);
};

rule STRONG_COMPONENTS : NodePerm.STRONG_COMPONENTS, NodePerm.PERMUTATION {
   $this->STRONG_COMPONENTS=permuted_cols($this->NodePerm->STRONG_COMPONENTS, $this->NodePerm->PERMUTATION);
};

rule CONNECTED : ADJACENCY, STRONG_COMPONENTS {
   $this->CONNECTED=is_totally_ordered(component_connectivity($this->ADJACENCY, $this->STRONG_COMPONENTS));
}
weight 1.10;

rule CONNECTED : {
   $this->CONNECTED=1;
}
precondition : STRONGLY_CONNECTED;
weight 0.1;

rule DIAMETER : ADJACENCY {
   $this->DIAMETER=diameter($this->ADJACENCY);
}
precondition : STRONGLY_CONNECTED;

rule NODE_OUT_DEGREES : ADJACENCY {
   $this->NODE_OUT_DEGREES(temporary)=[ map { $this->ADJACENCY->out_degree($_) } 0..($this->ADJACENCY->nodes-1) ];
}
weight 1.10;
rule NODE_IN_DEGREES : ADJACENCY {
   $this->NODE_IN_DEGREES(temporary)=[ map { $this->ADJACENCY->in_degree($_) } 0..($this->ADJACENCY->nodes-1) ];
}
weight 1.10;

}

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

# @category Other
# Creates a graph from a given list of //edges//.
# @param Array<Set<Int>> edges
# @return Graph
# @example
# > $g = graph_from_edges([[1,2],[1,3],[1,4]]);
# > print $g->ADJACENCY;
# | {}
# | {2 3 4}
# | {1}
# | {1}
# | {1}

user_function graph_from_edges($) {
   my $edges = shift;
   my $max = 0;
   foreach (@$edges ) {
      ( $#$_ == 1 && $_->[0] != $_->[1] ) or croak("not a list of edges\n");
      assign_max($max, $_->[0]);
      assign_max($max, $_->[1]);
   }

   my $g = new GraphAdjacency($max+1);
   for ( @$edges ) {
      $g->edge(@$_);
   }

   return new Graph(ADJACENCY=>$g);
}

user_function graph_from_cycles($) {
   my $cycles = shift;
   my $max = 0;

   foreach my $cycle (@$cycles){
      foreach my $i (0..scalar(@$cycle)-1) {
         ( $cycle->[$i-1] != $cycle->[$i] ) or croak( $cycle." does not seem to be a cycle (position ".$i.")\n");
         assign_max($max, $cycle->[$i]);
      }
   }

   my $g = new GraphAdjacency($max+1);
   foreach my $cycle (@$cycles) {
      foreach my $i (0..scalar(@$cycle)-1) {
         $g->edge($cycle->[$i-1],$cycle->[$i]);
      }
   }

   return new Graph(ADJACENCY=>$g);
}


# @category Combinatorics
# Creates the __line graph__ of a graph.
# @param Graph G
# @return Graph
# @example The following prints the adjacency matrix of the line graph of the star graph with 4 nodes:
# > $g = new Graph<Undirected>(ADJACENCY=>[[],[0],[0],[0]]);
# > print line_graph($g->ADJACENCY);
# | {1 2}
# | {0 2}
# | {0 1}
user_function line_graph(GraphAdjacency) : c++ (include=>["polymake/graph/line_graph.h"]);

# @category Combinatorics
# Creates the __complement graph__ of a graph.
# @param Graph G
# @return Graph
# @example The following prints the adjancency matrix of the complement graph of the star graph with 4 nodes: 
# > $g = new Graph<Undirected>(ADJACENCY=>[[],[0],[0],[0]]);
# > print complement_graph($g)->ADJACENCY;
# | {}
# | {2 3}
# | {1 3}
# | {1 2}
user_function complement_graph($) {
   my $g = shift;
   my $inv_adj = ~( adjacency_matrix($g->ADJACENCY) )- index_matrix( unit_matrix($g->N_NODES) );
   my $G = new Graph(ADJACENCY=>$inv_adj, N_NODES=>$g->N_NODES);
   if (defined $g->lookup("NODE_LABELS")) {
      $G->NODE_LABELS = $g->NODE_LABELS;
   }
   return $G;
}

# @category Combinatorics
# Compute the unsigned vertex-edge incidence matrix of the graph.
 # @param Graph G
# @return SparseMatrix<Int>
# @example
# > $I = incidence_matrix(cycle_graph(4));
# > print $I
# | 1 0 1 0
# | 1 1 0 0
# | 0 1 0 1
# | 0 0 1 1
user_function incidence_matrix<Dir>(Graph<Dir>): c++ (include=>["polymake/graph/incidence_matrix.h"]);

# @category Combinatorics
# Compute the signed vertex-edge incidence matrix of the graph.
# In case of undirected graphs, the orientation of the edges is induced by the order of the nodes.
# @param Graph G
# @return SparseMatrix<Int>
# @example
# > $I = signed_incidence_matrix(cycle_graph(4));
# > print $I;
# | 1 0 1 0
# | -1 1 0 0
# | 0 -1 0 1
# | 0 0 -1 -1
user_function signed_incidence_matrix<Dir>(Graph<Dir>): c++ (include=>["polymake/graph/incidence_matrix.h"]);
      
# @category Combinatorics
# Compute the unsigned vertex-edge incidence matrix of the graph.
# @param GraphAdjacency G
# @return SparseMatrix<Int>
# @example
# > $I = incidence_matrix(cycle_graph(4)->ADJACENCY);
# > print $I;
# | 1 0 1 0
# | 1 1 0 0
# | 0 1 0 1
# | 0 0 1 1
user_function incidence_matrix(GraphAdjacency) : c++ (include=>["polymake/graph/incidence_matrix.h"]);
      
# @category Combinatorics
# Compute the signed vertex-edge incidence matrix of the graph.
# In case of undirected graphs, the orientation of the edges is induced by the order of the nodes.
# @param GraphAdjacency G
# @return SparseMatrix<Int>
# @example
# > $I = signed_incidence_matrix(cycle_graph(4)->ADJACENCY);
# > print $I;
# | 1 0 1 0
# | -1 1 0 0
# | 0 -1 0 1
# | 0 0 -1 -1
user_function signed_incidence_matrix(GraphAdjacency) : c++ (include=>["polymake/graph/incidence_matrix.h"]);
                               
############################################################################

function is_connected(GraphAdjacency<Undirected>) : c++ (include=>["polymake/graph/connected.h"]);

function connected_components(GraphAdjacency<Undirected>) : c++ (include=>["polymake/graph/connected.h"]);

function is_weakly_connected(GraphAdjacency<Directed>) : c++ (include=>["polymake/graph/connected.h"]);

function weakly_connected_components(GraphAdjacency<Directed>) : c++ (include=>["polymake/graph/connected.h"]);

function is_strongly_connected(GraphAdjacency<Directed>) : c++ (include=>["polymake/graph/strong_connected.h"]);

function strong_components(GraphAdjacency<Directed>) : c++ (include=>["polymake/graph/strong_connected.h"]);

function is_totally_ordered(GraphAdjacency<Directed>) : c++ (include=>["polymake/graph/connected.h"]);

function component_connectivity(GraphAdjacency, IncidenceMatrix) : c++ (include=>["polymake/graph/connected.h"]);

function biconnected_components(GraphAdjacency<Undirected>) : c++ (include=>["polymake/graph/biconnected.h"]);

function max_cliques(GraphAdjacency<Undirected>) : c++ (include=>["polymake/graph/max_cliques.h"]);

function max_independent_sets(GraphAdjacency<Undirected>) : c++ (include=>["polymake/graph/max_cliques.h"]);

function diameter(GraphAdjacency) : c++ (include=>["polymake/graph/diameter.h"]);

# Local Variables:
# mode: perl
# cperl-indent-level:3
# indent-tabs-mode:nil
# End: