/* EINA_GRAPH - EFL graph processing library
 * Copyright (C) 2013 Jérémy Zurcher
 *
 * Permission is hereby granted, free of charge, to any person obtaining a copy
 * of this software and associated documentation files (the "Software"), to
 * deal in the Software without restriction, including without limitation the
 * rights to use, copy, modify, merge, publish, distribute, sublicense, and/or
 * sell copies of the Software, and to permit persons to whom the Software is
 * furnished to do so, subject to the following conditions:
 *
 * The above copyright notice and this permission notice shall be included in
 * all copies of the Software and its Copyright notices. In addition publicly
 * documented acknowledgment must be given that this software has been used if no
 * source code of this software is made available publicly. This includes
 * acknowledgments in either Copyright notices, Manuals, Publicity and Marketing
 * documents or any documentation provided with any product containing this
 * software. This License does not apply to any software that links to the
 * libraries provided by this software (statically or dynamically), but only to
 * the software provided.
 *
 * THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND, EXPRESS OR
 * IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF MERCHANTABILITY,
 * FITNESS FOR A PARTICULAR PURPOSE AND NONINFRINGEMENT. IN NO EVENT SHALL
 * THE AUTHORS BE LIABLE FOR ANY CLAIM, DAMAGES OR OTHER LIABILITY, WHETHER
 * IN AN ACTION OF CONTRACT, TORT OR OTHERWISE, ARISING FROM, OUT OF OR IN
 * CONNECTION WITH THE SOFTWARE OR THE USE OR OTHER DEALINGS IN THE SOFTWARE.
 */

#ifdef HAVE_CONFIG_H
# include <config.h>
#endif /* HAVE_CONFIG_H */

#include <eina_graph.h>
#include "eina_graph_private.h"

EAPI Eina_Graph *
eina_graph_new(unsigned int v, unsigned int step, Eina_Bool directed)
{
   unsigned int i;
   _Eina_Graph *_g;

   _g = calloc(1, sizeof(_Eina_Graph) + (v * sizeof(Eina_Array *)));
   if (!_g)
     {
        ERR("calloc failed : %s", strerror(errno));
        return NULL;
     }

   _g->vertices = v;
   _g->directed = directed;
   for (i = 0; i < v; i++)
     _g->adjs[i] = eina_array_new(step);

   return (Eina_Graph *) _g;
}

EAPI void
eina_graph_free(Eina_Graph *g)
{
   unsigned int i;
   _Eina_Graph * _g = (_Eina_Graph *) g;

   for (i = 0; i< _g->vertices; i++)
     eina_array_free(_g->adjs[i]);

   free(_g);
}

EAPI Eina_Bool
eina_graph_directed(const Eina_Graph *g)
{
   _Eina_Graph * _g = (_Eina_Graph *) g;

   return _g->directed;
}

EAPI unsigned int
eina_graph_vertices_count(const Eina_Graph *g)
{
   _Eina_Graph * _g = (_Eina_Graph *) g;

   return _g->vertices;
}

EAPI unsigned int
eina_graph_edges_count(const Eina_Graph *g)
{
   _Eina_Graph * _g = (_Eina_Graph *) g;

   return _g->edges;
}

EAPI unsigned int
eina_graph_degree(const Eina_Graph *g, unsigned int v)
{
   _Eina_Graph * _g = (_Eina_Graph *) g;

   if (v >= _g->vertices)
     {
        ERR("%u is out of [0;%u[", v, _g->vertices);
        return 0;
     }

   return eina_array_count_get(_g->adjs[v]);
}

EAPI unsigned int
eina_graph_degree_max(const Eina_Graph *g)
{
   unsigned int i, n, max;
   _Eina_Graph * _g = (_Eina_Graph *) g;

   max = 0;
   for (i = 0; i< _g->vertices; i++)
     {
        n = eina_array_count_get(_g->adjs[i]);
        if ( n > max ) max = n;
     }

   return max;
}

EAPI float
eina_graph_degree_avg(const Eina_Graph *g)
{
   _Eina_Graph * _g = (_Eina_Graph *) g;

   return (2.0 * _g->edges) / _g->vertices;
}

EAPI unsigned int
eina_graph_self_loops(const Eina_Graph *g)
{
   unsigned int i, j, n, loops;
   Eina_Array *ar;
   _Eina_Graph * _g = (_Eina_Graph *) g;

   loops = 0;
   for (i = 0; i< _g->vertices; i++)
     {
        ar = _g->adjs[i];
        n = eina_array_count_get(ar);
        for (j = 0; j < n; j++)
          {
             if(i == eina_array_uint_nth_get(ar, j)) loops++;
          }
     }

   return loops;
}

EAPI Eina_Bool
eina_graph_edge_add(Eina_Graph *g, unsigned int v, unsigned int w)
{
   _Eina_Graph * _g = (_Eina_Graph *) g;

   if ((v >= _g->vertices) || (w >= _g->vertices))
     {
        ERR("%u->%u is out of [0;%u[", v, w, _g->vertices);
        return EINA_FALSE;
     }

   if (!eina_array_push_uint(_g->adjs[v], w)) return EINA_FALSE;
   if (!_g->directed && (v != w))
     if (!eina_array_push_uint(_g->adjs[w], v)) return EINA_FALSE;

   _g->edges++;

   return EINA_TRUE;
}

EAPI void
eina_graph_dot_write(Eina_Graph *g, FILE *f)
{
   int r;
   char buf[32];
   unsigned int i, j, n;
   Eina_Array *ar;
   _Eina_Graph * _g = (_Eina_Graph *) g;

   if (_g->directed)
     fwrite("digraph {\n", 10, 1, f);
   else
     fwrite("strict graph {\n", 15, 1, f);

   for (i = 0; i< _g->vertices; i++)
     {
        ar = _g->adjs[i];
        n = eina_array_count_get(ar);
        for (j = 0; j < n; j++)
          {
             if (_g->directed)
               r = snprintf(buf, 32, "%u -> %u;\n", i, eina_array_uint_nth_get(ar, j));
             else
               r = snprintf(buf, 32, "%u -- %u;\n", i, eina_array_uint_nth_get(ar, j));
             fwrite(buf, r, 1, f);
          }
     }

   fwrite("}\n", 2, 1, f);
}