/****************************************************************************
 * Copyright (C) 2009-2015 EPAM Systems
 * 
 * This file is part of Indigo toolkit.
 * 
 * This file may be distributed and/or modified under the terms of the
 * GNU General Public License version 3 as published by the Free Software
 * Foundation and appearing in the file LICENSE.GPL included in the
 * packaging of this file.
 * 
 * This file is provided AS IS with NO WARRANTY OF ANY KIND, INCLUDING THE
 * WARRANTY OF DESIGN, MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE.
 ***************************************************************************/

#include <stdarg.h>
#include <stdio.h>

#include "base_c/defs.h"
#include "base_cpp/tlscont.h"
#include "graph/graph.h"
#include "graph/spanning_tree.h"
#include "graph/cycle_basis.h"
#include "graph/graph_decomposer.h"

using namespace indigo;

NeighborsAuto Vertex::neighbors() const
{
   return NeighborsAuto(*this);
}

int Vertex::findNeiVertex (int idx) const
{
   for (int i = neighbors_list.begin(); i < neighbors_list.end(); i = neighbors_list.next(i))
      if (neighbors_list[i].v == idx)
         return i;

   return -1;
}

int Vertex::findNeiEdge (int idx) const
{
   for (int i = neighbors_list.begin(); i < neighbors_list.end(); i = neighbors_list.next(i))
      if (neighbors_list[i].e == idx)
         return i;

   return -1;
}

IMPL_ERROR(Graph, "graph");

Graph::Graph ()
{
   _vertices = new ObjPool<Vertex>();
   _neighbors_pool = new Pool<List<VertexEdge>::Elem>();
   _sssr_pool = 0;
   _components_valid = false;
}

Graph::~Graph ()
{
   delete _vertices;
   delete _neighbors_pool;
   if (_sssr_pool != 0)
   {
      _sssr_vertices.clear();
      _sssr_edges.clear();
      delete _sssr_pool;
   }
}

int Graph::addVertex ()
{
   return _vertices->add(*_neighbors_pool);
}

int Graph::findEdgeIndex (int beg, int end) const
{
   const Vertex &vbeg = getVertex(beg);

   for (int i = vbeg.neiBegin(); i != vbeg.neiEnd(); i = vbeg.neiNext(i))
      if (vbeg.neiVertex(i) == end)
         return vbeg.neiEdge(i);

   return -1;
}

bool Graph::haveEdge (int beg, int end) const 
{
   return findEdgeIndex(beg, end) != -1;
}

bool Graph::hasEdge(int idx) const
{
   return _edges.hasElement(idx);
}

bool Graph::hasVertex(int idx) const
{
   return _vertices->hasElement(idx);
}

int Graph::getEdgeEnd (int beg, int edge) const
{
   const Edge &e = getEdge(edge);
   if (e.beg == beg)
      return e.end;
   if (e.end == beg)
      return e.beg;
   return -1;
}

int Graph::addEdge (int beg, int end)
{
   if (beg == end)
      throw Error("can't have loop-edge on vertex %d", beg);

   if (findEdgeIndex(beg, end) != -1)
      throw Error("already have edge between vertices %d and %d", beg, end);
   
   int edge_idx = _edges.add();

   Vertex &vbeg = _vertices->at(beg);
   Vertex &vend = _vertices->at(end);

   int ve1_idx = vbeg.neighbors_list.add();
   int ve2_idx = vend.neighbors_list.add();

   VertexEdge &ve1 = vbeg.neighbors_list[ve1_idx];
   VertexEdge &ve2 = vend.neighbors_list[ve2_idx];

   ve1.v = end;
   ve2.v = beg;
   ve1.e = edge_idx;
   ve2.e = edge_idx;

   _edges[edge_idx].beg = beg;
   _edges[edge_idx].end = end;

   _topology_valid = false;
   _sssr_valid = false;
   _components_valid = false;

   return edge_idx;
}

void Graph::swapEdgeEnds (int edge_idx)
{
   int tmp;

   __swap(_edges[edge_idx].beg, _edges[edge_idx].end, tmp);
}

void Graph::removeEdge (int idx)
{
   Edge edge = _edges[idx];

   Vertex &beg = _vertices->at(edge.beg);
   Vertex &end = _vertices->at(edge.end);

   _edges.remove(idx);

   beg.neighbors_list.remove(beg.findNeiEdge(idx));
   end.neighbors_list.remove(end.findNeiEdge(idx));

   _topology_valid = false;
   _sssr_valid = false;
   _components_valid = false;
}

void Graph::removeAllEdges ()
{
   for (int i = _vertices->begin(); i != _vertices->end(); i = _vertices->next(i))
      _vertices->at(i).neighbors_list.clear();

   _edges.clear();
   _topology_valid = false;
   _sssr_valid = false;
   _components_valid = false;
}

void Graph::removeVertex (int idx)
{
   QS_DEF(Array<int>, edges);

   const Vertex &vertex = getVertex(idx);

   int i;

   edges.clear();

   for (i = vertex.neiBegin(); i != vertex.neiEnd(); i = vertex.neiNext(i))
      edges.push(vertex.neiEdge(i));

   for (i = 0; i < edges.size(); i++)
      removeEdge(edges[i]);

   _vertices->remove(idx);

   _topology_valid = false;
   _sssr_valid = false;
   _components_valid = false;
}


const Vertex & Graph::getVertex (int idx) const
{
   return _vertices->at(idx);
}

const Edge & Graph::getEdge (int idx) const
{
   return _edges[idx];
}

bool Graph::isConnected (Graph &graph)
{
   return graph.countComponents() == 1;
}

struct BfsState
{
   int state;
   int prev;
   int edge;
};


/* Finds path, writes edge indices into path_out. Returns false if no path. */
bool Graph::findPath (int from, int where, Array<int> &path_out) const
{
   path_out.clear();

   QS_DEF(Array<int>, queue);
   QS_DEF(Array<BfsState>, states);

   queue.clear_resize(_vertices->size());
   states.clear_resize(_vertices->end());

   states.zerofill();

   int top = 1, bottom = 0;
   bool have_path = false;

   states[where].state = 1;
   queue[0] = where;

   while (top != bottom)
   {
      if (queue[bottom] == from)
      {
         have_path = true;
         break;
      }

      const Vertex &vertex = getVertex(queue[bottom]);

      states[queue[bottom]].state = 2;

      for (int i = vertex.neiBegin(); i != vertex.neiEnd(); i = vertex.neiNext(i))
      {
         int other = vertex.neiVertex(i);

         if (states[other].state == 0)
         {
            queue[top++] = other;
            states[other].state = 1;
            states[other].prev = queue[bottom];
            states[other].edge = vertex.neiEdge(i);
         }
      }
      bottom++;
   }

   if (have_path)
   {
      while (from != where)
      {
         path_out.push(states[from].edge);
         from = states[from].prev;
      }
      return true;
   }

   return false;
}

VerticesAuto Graph::vertices ()
{
   return VerticesAuto(*this);
}

EdgesAuto Graph::edges ()
{
   return EdgesAuto(*this);
}

void Graph::clear ()
{
   _vertices->clear();
   _edges.clear();
   _topology_valid = false;
   _sssr_valid = false;
   _components_valid = false;
}

bool Graph::isChain_AssumingConnected (const Graph &graph)
{
   // ensure it is a tree
   if (graph.vertexCount() - graph.edgeCount() != 1)
      return false;

   for (int i = graph.vertexBegin(); i < graph.vertexEnd(); i = graph.vertexNext(i))
      if (graph.getVertex(i).degree() > 2)
         return false;

   return true;
}

bool Graph::isTree (Graph &graph)
{
   if (!Graph::isConnected(graph))
      return false;

   if (graph.vertexCount() != graph.edgeCount() + 1)
      return false;

   return true;
}

void Graph::filterVertices (const Graph &graph, const int *filter, int filter_type, int filter_value, Array<int> &result)
{
   result.clear();

   for (int i = graph.vertexBegin(); i != graph.vertexEnd(); i = graph.vertexNext(i))
   {
      if (filter != 0)
      {
         if (filter_type == FILTER_EQ && filter_value != filter[i])
            continue;
         if (filter_type == FILTER_NEQ && filter_value == filter[i])
            continue;
      }
      result.push(i);
   }
}

void Graph::filterEdges (const Graph &graph, const int *filter, int filter_type, int filter_value, Array<int> &result)
{
   result.clear();

   for (int i = graph.edgeBegin(); i != graph.edgeEnd(); i = graph.edgeNext(i))
   {
      if (filter != 0)
      {
         if (filter_type == FILTER_EQ && filter_value != filter[i])
            continue;
         if (filter_type == FILTER_NEQ && filter_value == filter[i])
            continue;
      }
      result.push(i);
   }
}

void Graph::_mergeWithSubgraph (const Graph &other, const Array<int> &vertices, const Array<int> *edges,
                                Array<int> *vertex_mapping, Array<int> *edge_mapping)
{
   QS_DEF(Array<int>, tmp_mapping);
   int i;

   if (vertex_mapping == 0)
      vertex_mapping = &tmp_mapping;

   vertex_mapping->clear_resize(other.vertexEnd());
   vertex_mapping->fffill();

   if (edge_mapping != 0)
   {
      edge_mapping->clear_resize(other.edgeEnd());
      edge_mapping->fffill();
   }

   for (i = 0; i < vertices.size(); i++)
   {
      int idx = vertices[i];

      if (vertex_mapping->at(idx) != -1)
         throw Error("makeSubgraph(): repeated vertex #%d", idx);

      vertex_mapping->at(idx) = addVertex();
   }

   if (edges != 0)
   {
      for (i = 0; i != edges->size(); i++)
      {
         const Edge &edge = other.getEdge(edges->at(i));

         int beg = vertex_mapping->at(edge.beg);
         int end = vertex_mapping->at(edge.end);

         if (beg == -1 || end == -1)
            throw Error("_mergeWithSubgraph: edge %d maps to (%d, %d)", edges->at(i), beg, end);
         
         int idx = addEdge(beg, end);

         if (edge_mapping != 0)
            edge_mapping->at(edges->at(i)) = idx;

      }
   }
   else for (i = other.edgeBegin(); i < other.edgeEnd(); i = other.edgeNext(i))
   {
      const Edge &edge = other.getEdge(i);
      int beg = vertex_mapping->at(edge.beg);
      int end = vertex_mapping->at(edge.end);

      if (beg != -1 && end != -1)
      {
         int idx = addEdge(beg, end);
         if (edge_mapping != 0)
            edge_mapping->at(i) = idx;
      }
   }
}

void Graph::buildEdgeMapping (const Graph &other, Array<int> *mapping, Array<int> *edge_mapping)
{
   for (int i = other.edgeBegin(); i < other.edgeEnd(); i = other.edgeNext(i))
   {
      const Edge &edge = other.getEdge(i);
      int beg = mapping->at(edge.beg);
      int end = mapping->at(edge.end);

      if (beg != -1 && end != -1)
      {
         int idx = findEdgeIndex(beg, end);
         if (edge_mapping != 0)
            edge_mapping->at(i) = idx;
      }
   }
}

void Graph::mergeWith (const Graph &other, Array<int> *mapping)
{
   QS_DEF(Array<int>, vertices);
   int i;

   vertices.clear();

   for (i = other.vertexBegin(); i != other.vertexEnd(); i = other.vertexNext(i))
      vertices.push(i);

   _mergeWithSubgraph(other, vertices, 0, mapping, 0);
}

void Graph::makeSubgraph (const Graph &other, const Array<int> &vertices, Array<int> *vertex_mapping)
{
   clear();
   _mergeWithSubgraph(other, vertices, 0, vertex_mapping, 0);
}

void Graph::makeSubgraph (const Graph &other, const Array<int> &vertices, Array<int> *vertex_mapping, const Array<int> *edges, Array<int> *edge_mapping)
{
   clear();
   _mergeWithSubgraph(other, vertices, edges, vertex_mapping, edge_mapping);
}

void Graph::makeSubgraph (const Graph &other, const Filter &filter,
                             Array<int> *mapping_out, Array<int> *inv_mapping)
{
   QS_DEF(Array<int>, vertices);

   if (mapping_out == 0)
      mapping_out = &vertices;

   filter.collectGraphVertices(other, *mapping_out);

   makeSubgraph(other, *mapping_out, inv_mapping);
}

void Graph::cloneGraph (const Graph &other, Array<int> *mapping)
{
   QS_DEF(Array<int>, vertices);
   vertices.clear();

   for (int i = other.vertexBegin(); i < other.vertexEnd(); i = other.vertexNext(i))
      vertices.push(i);
   makeSubgraph(other, vertices, mapping);
}

void Graph::makeEdgeSubgraph (const Graph &other,
              const Array<int> &vertices, const Array<int> &edges,
              Array<int> *v_mapping, Array<int> *e_mapping)
{
   QS_DEF(Array<int>, tmp_mapping);
   int i;

   if (v_mapping == 0)
      v_mapping = &tmp_mapping;

   v_mapping->clear_resize(other.vertexEnd());

   for (i = other.vertexBegin(); i < other.vertexEnd(); i = other.vertexNext(i))
      v_mapping->at(i) = -1;

   if (e_mapping != 0)
      e_mapping->clear_resize(other.edgeEnd());

   clear();

   for (i = 0; i < vertices.size(); i++)
   {
      int idx = vertices[i];

      if (v_mapping->at(idx) != -1)
         throw Error("makeEdgeSubgraph(): repeated vertex #%d", idx);

      v_mapping->at(idx) = addVertex();
   }

   for (i = 0; i < edges.size(); i++)
   {
      int edge_idx = edges[i];
      const Edge &edge = other.getEdge(edge_idx);
      int beg = v_mapping->at(edge.beg);
      int end = v_mapping->at(edge.end);

      int new_edge_idx = addEdge(beg, end);
      if (e_mapping != 0)
         e_mapping->at(edge_idx) = new_edge_idx;
   }
}

int Graph::findMappedEdge (const Graph &graph, const Graph &mapped_graph,
                           int edge_idx, const int *mapping)
{
   const Edge &edge = graph.getEdge(edge_idx);

   int beg = mapping[edge.beg];
   int end = mapping[edge.end];

   if (beg == -1 || end == -1)
      return -1;

   return mapped_graph.findEdgeIndex(beg, end);
}

int Graph::getEdgeTopology (int idx)
{
   if (!_topology_valid)
      _calculateTopology();

   return _topology[idx];
}

bool Graph::vertexInRing (int idx)
{
   const Vertex &vertex = getVertex(idx);
   int i;

   for (i = vertex.neiBegin(); i != vertex.neiEnd(); i = vertex.neiNext(i))
      if (getEdgeTopology(vertex.neiEdge(i)) == TOPOLOGY_RING)
         return true;

   return false;
}

void Graph::_calculateTopology ()
{
   SpanningTree spt(*this, 0);
   int i;

   _topology.clear_resize(_edges.end());

   for (i = _edges.begin(); i != _edges.end(); i = _edges.next(i))
      _topology[i] = TOPOLOGY_CHAIN;

   spt.markAllEdgesInCycles(_topology.ptr(), TOPOLOGY_RING);
   _topology_valid = true;
}

void Graph::setEdgeTopology (int idx, int topology)
{
   _topology.expandFill(idx + 1, -1);
   _topology[idx] = topology;
}

void Graph::validateEdgeTopologies ()
{
   _topology_valid = true;
}

int Graph::vertexCountSSSR (int idx)
{
   if (!_sssr_valid)
      _calculateSSSR();

   return _v_sssr_count[idx];

}

int Graph::vertexSmallestRingSize (int idx)
{
   if (!_sssr_valid)
      _calculateSSSR();

   return _v_smallest_ring_size[idx];
}

int Graph::edgeSmallestRingSize (int idx)
{
   if (!_sssr_valid)
      _calculateSSSR();

   return _e_smallest_ring_size[idx];
}

void Graph::_calculateSSSRInit ()
{
   _v_smallest_ring_size.clear_resize(vertexEnd());
   _e_smallest_ring_size.clear_resize(edgeEnd());
   _v_sssr_count.clear_resize(vertexEnd());

   _v_smallest_ring_size.fffill();
   _e_smallest_ring_size.fffill();
   _v_sssr_count.zerofill();

   if (_sssr_pool == 0)
      _sssr_pool = new Pool<List<int>::Elem>();

   _sssr_vertices.clear();
   _sssr_edges.clear();
}


void Graph::_calculateSSSRByCycleBasis (CycleBasis &basis)
{
   _calculateSSSRInit();

   for (int i = 0; i < basis.getCyclesCount(); i++)
   {
      const Array<int> &cycle = basis.getCycle(i);

      List<int> &vertices = _sssr_vertices.push(*_sssr_pool);
      List<int> &edges = _sssr_edges.push(*_sssr_pool);

      _calculateSSSRAddEdgesAndVertices(cycle, edges, vertices);

      for (int j = vertices.begin(); j != vertices.end(); j = vertices.next(j))
      {
         int idx = vertices[j];

         if (_v_smallest_ring_size[idx] == -1 || _v_smallest_ring_size[idx] > cycle.size())
            _v_smallest_ring_size[idx] = cycle.size();
         
         _v_sssr_count[idx]++;
      }

      for (int j = edges.begin(); j != edges.end(); j = edges.next(j))
      {
         int idx = edges[j];

         if (_e_smallest_ring_size[idx] == -1 || _e_smallest_ring_size[idx] > cycle.size())
            _e_smallest_ring_size[idx] = cycle.size();
      }
   }

   for (int i = 0; i < _v_smallest_ring_size.size(); i++)
      if (_v_smallest_ring_size[i] == -1)
         _v_smallest_ring_size[i] = 0;
   
   for (int i = 0; i < _e_smallest_ring_size.size(); i++)
      if (_e_smallest_ring_size[i] == -1)
         _e_smallest_ring_size[i] = 0;
   
   _sssr_valid = true;
}

void Graph::_calculateSSSR ()
{
   // Note: function was split into smaller functions to reduce stack usage
   QS_DEF(CycleBasis, basis);
   basis.create(*this);
   _calculateSSSRByCycleBasis(basis);
}

void Graph::_calculateComponents ()
{
   GraphDecomposer decomposer(*this);
   int i;

   decomposer.decompose();
   
   _component_numbers.clear_resize(vertexEnd());

   for (i = vertexBegin(); i != vertexEnd(); i = vertexNext(i))
      _component_numbers[i] = decomposer.getComponent(i);

   _components_count = decomposer.getComponentsCount();

   _component_vcount.clear_resize(_components_count);
   _component_ecount.clear_resize(_components_count);

   for (i = 0; i < _components_count; i++)
   {
      _component_vcount[i] = decomposer.getComponentVerticesCount(i);
      _component_ecount[i] = decomposer.getComponentEdgesCount(i);
   }

   _components_valid = true;
}

int Graph::vertexComponent (int v_idx)
{
   if (!_components_valid)
      _calculateComponents();

   return _component_numbers[v_idx];
}

int Graph::countComponents ()
{
   if (!_components_valid)
      _calculateComponents();

   return _components_count;
}

int Graph::countComponentEdges (int comp_idx)
{
   if (!_components_valid)
      _calculateComponents();

   return _component_ecount[comp_idx];
}

int Graph::countComponentVertices (int comp_idx)
{
   if (!_components_valid)
      _calculateComponents();

   return _component_vcount[comp_idx];
}

const Array<int> & Graph::getDecomposition ()
{
   if (!_components_valid)
      _calculateComponents();

   return _component_numbers;
}

List<int> & Graph::sssrEdges (int idx)
{
   if (!_sssr_valid)
      _calculateSSSR();
   return _sssr_edges[idx];
}

List<int> & Graph::sssrVertices (int idx)
{
   if (!_sssr_valid)
      _calculateSSSR();
   return _sssr_vertices[idx];
}

int Graph::sssrCount ()
{
   if (!_sssr_valid)
      _calculateSSSR();
   return _sssr_vertices.size();
}

void Graph::_cloneGraph_KeepIndices (const Graph &other)
{
   if (vertexCount() > 0 || edgeCount() > 0)
      throw Error("can not _clone_KeepIndices into a non-empty graph");

   int i, j, i_prev;
   int max_vertex_idx = -1;
   int max_edge_idx = -1;

   for (i = other.vertexBegin(); i != other.vertexEnd(); i = other.vertexNext(i))
      if (max_vertex_idx < i)
         max_vertex_idx = i;

   for (i = other.edgeBegin(); i != other.edgeEnd(); i = other.edgeNext(i))
      if (max_edge_idx < i)
         max_edge_idx = i;

   for (i = 0; i <= max_vertex_idx; i++)
      if (addVertex() != i)
         throw Error("_clone_KeepIndices: unexpected vertex index");

   i_prev = -1;

   for (i = other.vertexBegin(); i != other.vertexEnd(); i = other.vertexNext(i))
   {
      for (j = i_prev + 1; j < i; j++)
         removeVertex(j);
      i_prev = i;
   }

   if (vertexCount() != other.vertexCount())
      throw Error("_clone_KeepIndices: internal");

   for (i = 0; i <= max_edge_idx; i++)
      if (_edges.add() != i)
         throw Error("_clone_KeepIndices: unexpected edge index");

   i_prev = -1;

   for (i = other.edgeBegin(); i != other.edgeEnd(); i = other.edgeNext(i))
   {
      for (j = i_prev + 1; j < i; j++)
         _edges.remove(j);

      _edges[i].beg = other._edges[i].beg;
      _edges[i].end = other._edges[i].end;

      Vertex &vbeg = _vertices->at(_edges[i].beg);
      Vertex &vend = _vertices->at(_edges[i].end);

      int ve1_idx = vbeg.neighbors_list.add();
      int ve2_idx = vend.neighbors_list.add();

      VertexEdge &ve1 = vbeg.neighbors_list[ve1_idx];
      VertexEdge &ve2 = vend.neighbors_list[ve2_idx];

      ve1.v = _edges[i].end;
      ve2.v = _edges[i].beg;
      ve1.e = i;
      ve2.e = i;

      i_prev = i;
   }

   if (edgeCount() != other.edgeCount())
      throw Error("_clone_KeepIndices: internal");

   _topology_valid = false;
   _sssr_valid = false;
   _components_valid = false;
}

void Graph::_calculateSSSRAddEdgesAndVertices (const Array<int> &cycle, List<int> &edges, List<int> &vertices)
{
   int prev_beg = -1;
   int prev_end = -1;

   for (int j = 0; j < cycle.size(); j++)
   {
      const Edge &edge = getEdge(cycle[j]);

      edges.add(cycle[j]);

      if (j != cycle.size() - 1)
      {
         if (edge.beg != prev_beg && edge.beg != prev_end)
            vertices.add(edge.beg);
         if (edge.end != prev_beg && edge.end != prev_end)
            vertices.add(edge.end);
      }
      prev_beg = edge.beg;
      prev_end = edge.end;
   }
}