#  Copyright (c) 1997-2015
#  Ewgenij Gawrilow, Michael Joswig (Technische Universitaet Berlin, Germany)
#  http://www.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.
#-------------------------------------------------------------------------------

# @topic category property_types/Graph Types
# This contains all property types that are related to graphs.

# @topic category functions/Graph Operations
# Operations on graphs.

# @category Artificial
# Type tag for an __undirected__ [[Graph]].
declare property_type Undirected : c++ (special => 'Undirected', include => "polymake/Graph.h");

# @category Artificial
# Type tag for a __directed__ [[Graph]].
declare property_type Directed : c++ (special => 'Directed', include => "polymake/Graph.h");

# @category Artificial
# Type tag for an __undirected multigraph__.
declare property_type UndirectedMulti : c++ (special => 'UndirectedMulti', include => "polymake/Graph.h");

# @category Artificial
# Type tag for a __directed multigraph__.
declare property_type DirectedMulti : c++ (special => 'DirectedMulti', include => "polymake/Graph.h");

# @category Artificial
declare property_type EdgeList<*> : c++;

# @category Artificial
declare property_type EdgeIterator<*> : Iterator : c++ {

   method from_node() : c++;

   method to_node() : c++;
}

function entire(EdgeList:anchor) : c++ : returns(EdgeIterator);

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

# @category Graph Types
# @tparam Dir one of [[Undirected]], [[Directed]], [[UndirectedMulti]] or [[DirectedMulti]], default: [[Undirected]]
declare property_type Graph<Dir=Undirected> : c++ (include => "polymake/Graph.h", operators => '@sets:wary == !=') {

   # Returns the total number of nodes.
   # @return Int
   user_method nodes() : c++;

   # Returns the total number of edges.
   # @return Int
   user_method edges() : c++;

   # Adds a new node without incident edes, returns its index.
   # @return Int
   user_method add_node() : non_const : c++;

   # Checks whether the node with given index exists.
   # @param Int node
   # @return Bool
   user_method node_exists($) : wary : c++;

   # Returns true if the given node index is either out of valid range or points to a formerly deleted node.
   # @param Int node
   # @return Bool
   user_method invalid_node($) : c++;

   # Returns true if the given node index is out of valid range.
   # @param Int node
   # @return Bool
   user_method node_out_of_range($) : c++;

   # Deletes all edges incident to the given node and marks it as invalid.
   # The numeration of other nodes stays unchanged.
   # @param Int node
   user_method delete_node($) : non_const : wary : void : c++;

   # Returns the index of the edge connecting two given nodes.
   # The edge is created if was not there.
   # In a multigraph, an arbitrary edge from the parallel bundle will be picked.
   # @param Int tail_node
   # @param Int head_node
   # @return Int
   user_method edge($$) : non_const : wary : c++;

   # In a multigraph, creates a new edge connecting two given nodes.
   # In a normal graph, creates a new edge only if the nodes were not connected yet.
   # Returns the index of the (new) edge.
   # @param Int tail_node
   # @param Int head_node
   # @return Int
   user_method add_edge($$) : non_const : wary : c++;

   # Checks whether two given nodes are connected by (at least) one edge.
   # @param Int tail_node
   # @param Int head_node
   # @return Bool
   user_method edge_exists($$) : wary : c++;

   # Returns an iterator visiting all (parallel) edges connecting two given nodes.
   # @param Int tail_node
   # @param Int head_node
   # @return Iterator
   user_method all_edges($$) : wary : lvalue_opt : c++ : returns(Iterator);

   # Deletes the edge connecting two given nodes, if there was one.
   # In a multigraph, deletes one arbitrary edge from the parallel bundle.
   # @param Int tail_node
   # @param Int head_node
   user_method delete_edge($$) : non_const : void : wary : c++;

   # Delete the edge in a multigraph pointed to by the given iterator
   # @param Iterator iterator as returned by [[all_edges]].
   user_method delete_edge(*) : non_const : void : wary : c++;

   # Deletes all edges in a multigraph connecting two given nodes.
   # @param Int tail_node
   # @param Int head_node
   user_method delete_all_edges($$) : non_const : void : wary : c++;

   # Contract the edge(s) between //node1// and //node2//. Reconnects all edges from //node2// to //node1//,
   # deleting the edge(s) between them and, finally, deleting //node2//.
   # @param Int node1
   # @param Int node2
   user_method contract_edge($$) : non_const : void : wary : c++;

   # Renumbers the valid nodes as to eliminate all gaps left after deleting.
   user_method squeeze() : non_const : void : c++;

   # Deletes all nodes of degree 0,
   # then renumbers the remaining nodes without gaps.
   user_method squeeze_isolated() : non_const : void : c++;

   # Returns a sequence of edges heading to (in Directed case) or incident to (in Undirected case) //node//.
   # @param Int node
   # @return EdgeList
   user_method in_edges($) : wary : anchor : c++ : returns(EdgeList);

   # Returns a sequence of edges leaving (in Directed case) or incident to (in Undirected case) //node//.
   # @param Int node
   # @return EdgeList
   user_method out_edges($) : wary : anchor : c++ : returns(EdgeList);


   # Returns the set of indices of nodes adjacent to //node//.
   # @param Int node
   # @return Set
   user_method adjacent_nodes($) : wary : lvalue_opt : c++;

   # Returns the set of indices of the nodes that have an edge heading to //node//.
   # @param Int node
   # @return Set
   user_method in_adjacent_nodes($) : wary : lvalue_opt : c++;

   # Returns the set of indices of the nodes with an edge arriving from //node//.
   # @param Int node
   # @return Set
   user_method out_adjacent_nodes($) : wary : lvalue_opt : c++;

   # Returns the number of edges heading to //node//.
   # @param Int node
   # @return Int
   user_method in_degree($) : wary : c++;

   # Returns the number of edges leaving //node//.
   # @param Int node
   # @return Int
   user_method out_degree($) : wary : c++;

   # Returns the number of edges incident to //node//.
   # @param Int node
   # @return Int
   user_method degree($) : wary : c++;

   # Returns true if some nodes have been deleted since the last [[squeeze]] operation.
   # @return Bool
   user_method has_gaps() : c++;

   # Returns the maximal node index + 1.
   # If the graph does not have gaps caused by node deletion, the result is equivalent to [[nodes]]().
   # @return Int
   user_method dim() : c++;

   # Create a graph with //n// isolated nodes.
   # @param Int n
   method construct(Int) : c++;

   # Create a (non-multi) graph with adjacency relation between nodes dictated by the given matrix.
   method construct(IncidenceMatrix) : c++;

   type_method toXML {
      my ($proto, $g)=splice @_, 0, 2;
      if ($g->has_gaps) {
         my ($writer, @attr)=@_;
         $writer->startTag("m", @attr, dim => $g->dim);
         local $writer->{"!dim"}=1;
         my $row_type;
         for (my $n=entire(common::nodes($g)); $n; ++$n) {
            my $nodelist=$n->out_adjacent_nodes;
            ($row_type //= $nodelist->type)->toXML->($nodelist, $writer, i=>$$n);
         }
         $writer->endTag("m");
      } else {
         my $am=adjacency_matrix($g);
         $am->type->toXML->($am, @_);
      }
   }

   method init_node_map(*:lvalue:wary) : void : c++;

   method init_edge_map(*:lvalue:wary) : void : c++;

   method enumerate_edges() : void : c++;
}


# @category Graph Operations
# Returns the adjacency matrix of graph nodes.
# For a normal graph, it will be a kind of [[IncidenceMatrix]],
# for multigraph, it will be a [[SparseMatrix<Int>]], with entries encoding the number of parallel edges between two nodes.
# @param Graph graph
# @return IncidenceMatrix both rows and columns correspond to the nodes
user_function adjacency_matrix(Graph:lvalue_opt:anchor) : c++;

function permuted_nodes(Graph, *) : c++;

function renumber_nodes(Graph:anchor) : c++;


# @category Graph Operations
# Returns the sequence of all edges of a graph.
# The edges will appear in ascending order of their tail and head nodes.
# In the Undirected case, the edges will appear once, ordered by the larger index of their incident nodes.
# @param Graph graph
# @return EdgeList
user_function edges(Graph) : c++ : returns(EdgeList);

# @category Artificial
declare property_type NodeSet<*> : c++;

# @category Artificial
declare property_type NodeIterator<*> : Iterator : c++ {

   method out_edges() : c++ : anchor : returns(EdgeList);

   method in_edges() : c++ : anchor : returns(EdgeList);

   method adjacent_nodes() : c++ : anchor;

   method out_adjacent_nodes() : c++ : anchor;

   method in_adjacent_nodes() : c++ : anchor;

   method degree() : c++;

   method in_degree() : c++;

   method out_degree() : c++;
}


# @category Graph Operations
# Returns the sequence of all valid nodes of a graph.
# @param Graph graph
# @return NodeSet
# @example > print nodes(cycle_graph(5)->ADJACENCY);
# {0 1 2 3 4}

user_function nodes(Graph:anchor) : c++ : returns(NodeSet);

function entire(NodeSet:anchor) : c++ : returns(NodeIterator);

# @category Graph Types
# The common abstract base class for all kinds of associative containers that can be attached to a [[Graph]].
# @tparam Dir kind of the host graph: [[Undirected]], [[Directed]], [[UndirectedMulti]], or [[DirectedMulti]]
# @tparam Element data associated with nodes or edges

declare property_type GraphMap<Dir,Element> {

   method construct(Graph<Dir>) : c++;

   method construct(Graph<Dir>, $@) {
      my ($proto, $graph)=splice @_,0,2;
      Core::CPlusPlus::assign_any($proto->construct->($graph), @_);
   }

   type_method equal {
      # the maps may contain gaps, hence got to use iterators
      my ($proto, $m1, $m2)=@_;
      my $elem_proto=$proto->params->[1];
      @$m1==@$m2 and do {
         for (my ($it1, $it2)=(entire($m1), entire($m2)); $it1; ++$it1, ++$it2) {
            $elem_proto->equal->($$it1, $$it2) or return 0;
         }
         1
      }
   }
}

# @category Graph Types
# Dense mapping of nodes to data items.
# @tparam Dir kind of the host graph, [[Undirected]], [[Directed]], [[UndirectedMulti]], or [[DirectedMulti]]
# @tparam Element data associated with nodes
declare property_type NodeMap<Dir,Element> : GraphMap<Dir,Element> \
   : c++ ( include => "polymake/Graph.h", operators => '@eq' );

# @category Graph Types
# Dense mapping of edges to data items.
# @tparam Dir kind of the host graph, [[Undirected]], [[Directed]], [[UndirectedMulti]], or [[DirectedMulti]]
# @tparam Element data associated with edges
declare property_type EdgeMap<Dir,Element> : GraphMap<Dir,Element> \
   : c++ ( include => "polymake/Graph.h", operators => '@eq' ) {

   # Access the data associated with an edge between two given nodes.
   # @param Int from source node
   # @param Int to target node
   user_method edge(Int,Int) : lvalue_opt : wary : c++(name => '()');
}

# @category Graph Types
# Sparse mapping of nodes to data items.
# @tparam Dir one of [[Undirected]], [[Directed]], [[UndirectedMulti]] or [[DirectedMulti]]
# @tparam Element data associated with nodes
declare property_type NodeHashMap<Dir,Element> : GraphMap<Dir,Element> \
   : c++ ( include => "polymake/Graph.h", operators => '@eq' );

# @category Graph Types
# Sparse mapping of edges to data items.
# @tparam Dir one of [[Undirected]], [[Directed]], [[UndirectedMulti]] or [[DirectedMulti]]
# @tparam Element data associated with edges
declare property_type EdgeHashMap<Dir,Element> : GraphMap<Dir,Element> \
   : c++ ( include => "polymake/Graph.h", operators => '@eq' ) {

   # Access the data associated with an edge between two given nodes.
   # The new data element is created on demand.
   # @param Int from source node
   # @param Int to target node
   user_method edge(Int,Int) : lvalue : wary : c++(name => '()');

   # Access the data associated with an edge between two given nodes.
   # @param Int from source node
   # @param Int to target node
   # @return Iterator pointing to the data element (must be dereferenced as ${...}) or undef if the element does not exist.
   user_method find(Int,Int) : wary : c++;

   # Delete the data associated with an edge between two given nodes.
   # @param Int from source node
   # @param Int to target node
   user_method erase(Int,Int) : non_const : void : wary : c++;
}

function createNodeMap<Element,Dir>(Graph<Dir>) { new NodeMap<Dir,Element>(@_) }

function createEdgeMap<Element,Dir>(Graph<Dir>) { new EdgeMap<Dir,Element>(@_) }

function createNodeHashMap<Element,Dir>(Graph<Dir>) { new NodeHashMap<Dir,Element>(@_) }

function createEdgeHashMap<Element,Dir>(Graph<Dir>) { new EdgeHashMap<Dir,Element>(@_) }


# @category Graph Operations
# Creates an induced subgraph for the given subset of nodes.
# @param Graph graph
# @param Set set indices of selected nodes
# @return Graph
# @example $g = new props::Graph(cycle_graph(5)->ADJACENCY);
# > $s1 = new Set(1,2,3);
# > print induced_subgraph($g,$s1);
# | {2}
# | {1 3}
# | {2}

user_function induced_subgraph(Graph:wary:anchor, *:anchor) : c++ ( include => "polymake/IndexedSubgraph.h" );


# @category Graph Operations
# Returns the node-edge incidence matrix of a graph.
# @param Graph graph
# @tparam Coord coordinate type for the resulting matrix, default: [[Int]]
# @return SparseMatrix<Coord>
# @example > print node_edge_incidences(cycle_graph(5)->ADJACENCY);
# | (5) (0 1) (3 1)
# | (5) (0 1) (1 1)
# | (5) (1 1) (2 1)
# | (5) (2 1) (4 1)
# | (5) (3 1) (4 1)

user_function node_edge_incidences<Coord=Int>(Graph) : c++ ( include => "polymake/node_edge_incidences.h" );


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