path: root/egraph/egraph.c

#include <err.h>
#include <Efx.h>
#include <Edje.h>

#include "Egraph.h"

#define DEBUG 0

#define TYPE_MAXLEN 30

static void _smart_add(Evas_Object *obj);
static void _smart_del(Evas_Object *obj);
static void _smart_move(Evas_Object *obj, Evas_Coord x, Evas_Coord y);
static void _smart_resize(Evas_Object *obj, Evas_Coord w, Evas_Coord h);
static void _edge_v2_add(Egraph *eg, Egraph_Edge *e);
static void _edge_add(Egraph *eg, Egraph_Edge *e);
static void _edge_signal(Egraph *eg, Egraph_Edge *e, const char *signal);
static void _edge_v2_del(Egraph *eg, Egraph_Edge *e);
static void _edge_del(Egraph *eg, Egraph_Edge *e);
static void _vertice_v2_add(Egraph *eg, Egraph_Vertice *v);
static void _vertice_add(Egraph *eg, Egraph_Vertice *v);
static void _vertice_v2_del(Egraph *eg, Egraph_Vertice *v);
static void _vertice_del(Egraph *eg, Egraph_Vertice *v);
static void _vertice_update_status(Egraph *eg, Egraph_Vertice *v);
static void _vertice_signal(Egraph *eg, Egraph_Vertice *v, const char *signal);
static void _vertice_geometry_update(Egraph *eg, Egraph_Vertice *v);
static void _v2_update(Egraph *eg);
static void _v3_update(Egraph *eg);
static void _coords2_copy(Egraph *eg);
static void _cb_blob_arrived(void *data, Efx_Map_Data *e, Evas_Object *obj);
static void _blob_send(Evas_Object *blob,
                       Egraph_Vertice *v, Evas_Coord x, Evas_Coord y);
static void _layouting_schedule(Egraph *eg);
static Eina_Bool _cb_layouting_start(void *data);
static void _cb_layouting_run(void *data, Ecore_Thread *thread);
static void _cb_layouting_end(void *data, Ecore_Thread *thread);
static void _cb_layouting_cancel(void *data, Ecore_Thread *thread);
static int  _igraph_query_vid(igraph_t *g, int g_len, int id);
static void _cb_vertice_move(void *data,
                             Evas *evas, Evas_Object *obj, void *event_info);
static void _reposition(Egraph *eg, int no_animation);
static void _matrix_minmax_2v(const igraph_matrix_t *m, int row_count,
                              float *c1min, float *c1max,
                              float *c2min, float *c2max);
static Evas_Object *_edje_obj_new(Egraph *eg, const char *group);
static Evas_Object *_edje_obj_set(Egraph *eg, Evas_Object *o, const char *group);

static const Evas_Smart_Cb_Description _smart_callbacks[] = {{NULL, NULL}};
#define EGRAPH_DATA_GET(o, ptr) \
  Egraph * ptr = evas_object_smart_data_get(o)
/* defines _egraph_parent_sc and _egraph_smart_class_new */
EVAS_SMART_SUBCLASS_NEW("Egraph", _egraph,
                        Evas_Smart_Class, Evas_Smart_Class,
                        evas_object_smart_clipped_class_get, _smart_callbacks);

static void
_egraph_smart_set_user(Evas_Smart_Class *sc)
{
   /* specializing these two */
   sc->add = _smart_add;
   sc->del = _smart_del;
   sc->move = _smart_move;
   /* clipped smart object has no hook on resizes or calculations */
   sc->resize = _smart_resize;
}

static void
_smart_add(Evas_Object *obj)
{
  EVAS_SMART_DATA_ALLOC(obj, Egraph);

  priv->evas = evas_object_evas_get(obj);

  _egraph_parent_sc->add(obj);
}

static void
_smart_del(Evas_Object *obj)
{
  EGRAPH_DATA_GET(obj, eg);

  igraph_destroy(&eg->graph);
  if (eg->layouting.running == 2)
    ecore_thread_cancel(eg->layouting.thread);

  _egraph_parent_sc->del(obj);
}

static void
_smart_move(Evas_Object *obj, Evas_Coord x, Evas_Coord y)
{
  EGRAPH_DATA_GET(obj, eg);

  _reposition(eg, 1);

  _egraph_parent_sc->move(obj, x, y);
}

static void
_smart_resize(Evas_Object *obj, Evas_Coord w, Evas_Coord h)
{
  EGRAPH_DATA_GET(obj, eg);

  _reposition(eg, 1);
}

Evas_Object *
egraph_new(Evas *evas, int directed)
{
  Evas_Object *obj = NULL;
  Evas_Object *rect;
  Egraph *eg;
  int i;

  EINA_SAFETY_ON_NULL_RETURN_VAL(evas, NULL);

  efx_init();
  eina_log_domain_level_set("efx", EINA_LOG_LEVEL_WARN);

  obj = evas_object_smart_add(evas, _egraph_smart_class_new());
  eg = evas_object_smart_data_get(obj);
  if (!eg) goto err;
  eg->obj = obj;
  rect = evas_object_rectangle_add(eg->evas);
  evas_object_color_set(rect, 0, 0, 0, 0);
  evas_object_smart_member_add(rect, obj);
  eg->split_vertice_edge = rect;

  eg->graph_directed = directed;
  eg->display_vertices = 1;
  eg->display_names = 1;
  eg->display_edges = 1;
  eg->use_animations = 1;
  eg->do_improvements = 1;
  egraph_theme_file_set(obj, NULL);
  eg->theme_edges = 1;
  eg->layout = EGRAPH_LAYOUT_DEFAULT;

  /* needed for igraph attribute handling */
  igraph_i_set_attribute_table(&igraph_cattribute_table);

  eg->vertices = eina_hash_int32_new(NULL);
	for (i=0; i<EGRAPH_VERTICES_MAX-1; i++)
		eg->vertices_freeids[i] = i;
  if (igraph_empty(&eg->graph, 0, directed))
    goto err;
  if (igraph_empty(&eg->graph2, 0, directed))
    goto err;
  igraph_matrix_init(&eg->coords, 0, 2);
  igraph_matrix_init(&eg->coords2, 0, 2);
  eg->graph_wmin = 0;
  eg->graph_wmax = 200;
  eg->graph_hmin = 0;
  eg->graph_hmax = 200;
  eg->vertice_max_w = 0;
  eg->vertice_max_h = 0;

  return obj;

err:
  if (obj)
    evas_object_del(obj);
  return NULL;
}

void
egraph_clear(Evas_Object *obj)
{
  EGRAPH_DATA_GET(obj, eg);
  Eina_Iterator *it;
  Egraph_Vertice *v;
  void *data;

  it = eina_hash_iterator_tuple_new(eg->vertices);
  while (eina_iterator_next(it, &data)) {
    Eina_Hash_Tuple *t = data;
    v = t->data;
    egraph_vertice_del(obj, v);
  }
}

void
egraph_theme_file_set(Evas_Object *obj, char *path)
{
  EGRAPH_DATA_GET(obj, eg);

  if (eg->theme_path)
    free(eg->theme_path);

  if (!path) {
    char buf[256];

    snprintf(buf, sizeof(buf),
            "%s/egraph.edj",
            "/usr/local/share/egraph"); /* XXX use eina_prefix */
    path = buf;
  }
  eg->theme_path = strndup(path, 256);
}

void
egraph_theme_edges_set(Evas_Object *obj, int set)
{
  EGRAPH_DATA_GET(obj, eg);

  eg->theme_edges = set;
}

void
egraph_layout_set(Evas_Object *obj, Egraph_Layout layout)
{
  EGRAPH_DATA_GET(obj, eg);

  eg->layout = layout;
  _layouting_schedule(eg);
}

void
egraph_display_vertices_set(Evas_Object *obj, int set)
{
  EGRAPH_DATA_GET(obj, eg);
  Eina_Iterator *it;
  Egraph_Vertice *v;
  void *data;

  eg->display_vertices = set;

  it = eina_hash_iterator_tuple_new(eg->vertices);
  while (eina_iterator_next(it, &data)) {
    Eina_Hash_Tuple *t = data;
    v = t->data;
    if (v->o) {
      if (set == 0)
        evas_object_hide(v->o);
      else
        evas_object_show(v->o);
    }
  }

  _reposition(eg, 0);
}

void
egraph_display_names_set(Evas_Object *obj, int set)
{
  EGRAPH_DATA_GET(obj, eg);
  Eina_Iterator *it;
  Egraph_Vertice *v;
  void *data;

  eg->display_names = set;

  it = eina_hash_iterator_tuple_new(eg->vertices);
  while (eina_iterator_next(it, &data)) {
    Eina_Hash_Tuple *t = data;
    v = t->data;
    egraph_vertice_rename(obj, v, set ? v->name : NULL);
  }
}

void
egraph_display_edges_set(Evas_Object *obj, int set)
{
  EGRAPH_DATA_GET(obj, eg);
  Eina_List *l;
  Egraph_Edge *e;

  eg->display_edges = set;

  EINA_LIST_FOREACH(eg->edges, l, e) {
    if (e->o) {
      if (set == 0)
        evas_object_hide(e->o);
      else
        evas_object_show(e->o);
    }
  }
}

void
egraph_use_animations_set(Evas_Object *obj, int set)
{
  EGRAPH_DATA_GET(obj, eg);
  
  eg->use_animations = set;
}

void
egraph_do_improvements_set(Evas_Object *obj, int set)
{
  EGRAPH_DATA_GET(obj, eg);
  
  eg->do_improvements = set;
}

Egraph_Edge *
egraph_edge_add(Evas_Object *obj, Egraph_Vertice *a, Egraph_Vertice *b,
                void *data)
{
  EGRAPH_DATA_GET(obj, eg);
  Egraph_Edge *e;

  e = calloc(1, sizeof(Egraph_Edge));
  if (!e)
    err(1, "egraph_edge_add: cannot calloc");
  e->v3_new = 1;
  e->a = a;
  e->b = b;
  e->data = data;
  eg->edges = eina_list_append(eg->edges, e);
  if (DEBUG)
    printf("egraph_edge_add %d %d\n", e->a->id, e->b->id);

  egraph_edge_type_set(obj, e, "edge_normal");

  _layouting_schedule(eg);
  return e;
}

static void
_edge_v2_add(Egraph *eg, Egraph_Edge *e)
{
  int a_pos, b_pos;

  if (DEBUG)
    printf("_edge_v2_add %d %d\n", e->a->id, e->b->id);

  e->v2_new = 1;
  e->v3_new = 0;

  a_pos = _igraph_query_vid(&eg->graph2, eg->graph2_vcount, e->a->id);
  b_pos = _igraph_query_vid(&eg->graph2, eg->graph2_vcount, e->b->id);
  igraph_add_edge(&eg->graph2, a_pos, b_pos);
}

static void
_edge_add(Egraph *eg, Egraph_Edge *e)
{
  Evas_Object *eobj = NULL;
  int a_pos, b_pos;

  e->new = 1;
  e->v2_new = 0;

  a_pos = _igraph_query_vid(&eg->graph, eg->graph_vcount, e->a->id);
  b_pos = _igraph_query_vid(&eg->graph, eg->graph_vcount, e->b->id);
  igraph_add_edge(&eg->graph, a_pos, b_pos);

  if (eg->theme_edges) {
    eobj = _edje_obj_new(eg, e->type);
    if (eobj) {
      e->o_usetheme = 1;
      evas_object_resize(eobj, eg->vertice_max_w, eg->vertice_max_h); // XXX rm
    }
  }
  if (!eobj) {
    eobj = evas_object_line_add(eg->evas);
    evas_object_color_set(eobj, 255, 0, 0, 255);
  }
  evas_object_smart_member_add(eobj, eg->obj);
  evas_object_stack_below(eobj, eg->split_vertice_edge);
  e->o = eobj;
  _edge_signal(eg, e, "become_active");

  e->a->edges = eina_list_append(e->a->edges, e);
  e->b->edges = eina_list_append(e->b->edges, e);
  _vertice_update_status(eg, e->a);
  _vertice_update_status(eg, e->b);
}

void
egraph_edge_type_set(Evas_Object *obj, Egraph_Edge *e, const char *type)
{
  EGRAPH_DATA_GET(obj, eg);

  if (e->type)
    free(e->type);

  e->type = strndup(type, TYPE_MAXLEN);
  if (eg->theme_edges && e->o) {
    _edje_obj_set(eg, e->o, type);
  }
}

static void
_edge_signal(Egraph *eg, Egraph_Edge *e, const char *signal)
{
  if (eg->theme_edges && e->o);
    edje_object_signal_emit(e->o, signal, "");
}

void
egraph_edge_del(Evas_Object *obj, Egraph_Edge *e)
{
  EGRAPH_DATA_GET(obj, eg);

  // XXX DEBUG find mem corrupt, del already del edge
  if (!egraph_edge_find(obj, e->a, e->b))
    printf("XXX DEBUG: egraph_edge_del on unknown edge !!!\n");
  if (DEBUG)
    printf("egraph_edge_del: %d %d\n", e->a->id, e->b->id);
  
  e->v3_del = 1;
  _layouting_schedule(eg);
}

static void
_edge_v2_del(Egraph *eg, Egraph_Edge *e)
{
  igraph_es_t es;
  int a_pos, b_pos;
 
  if (e->v2_del == 1)
    return;

  if (DEBUG)
    printf("_edge_v2_del %d %d\n", e->a->id, e->b->id);

  e->v2_del = 1;
  e->v3_del = 0;

  if (!e->v3_new) {
    a_pos = _igraph_query_vid(&eg->graph2, eg->graph2_vcount, e->a->id);
    b_pos = _igraph_query_vid(&eg->graph2, eg->graph2_vcount, e->b->id);
    igraph_es_pairs_small(&es, eg->graph_directed, a_pos, b_pos, -1);
    igraph_delete_edges(&eg->graph2, es);
  }
}

static void
_edge_del(Egraph *eg, Egraph_Edge *e)
{
  igraph_es_t es;
  int a_pos, b_pos;

  if (!e->v3_new && !e->v2_new) {
    a_pos = _igraph_query_vid(&eg->graph, eg->graph_vcount, e->a->id);
    b_pos = _igraph_query_vid(&eg->graph, eg->graph_vcount, e->b->id);
    igraph_es_pairs_small(&es, eg->graph_directed, a_pos, b_pos, -1);
    igraph_delete_edges(&eg->graph, es);

    e->a->edges = eina_list_remove(e->a->edges, e);
    e->b->edges = eina_list_remove(e->b->edges, e);
    _vertice_update_status(eg, e->a);
    _vertice_update_status(eg, e->b);

    evas_object_del(e->o);
  }
  eg->edges = eina_list_remove(eg->edges, e);
  free(e);
}

Egraph_Edge *
egraph_edge_find(Evas_Object *obj, Egraph_Vertice *a, Egraph_Vertice *b)
{
  EGRAPH_DATA_GET(obj, eg);
  Egraph_Edge *e;
  Eina_List *l;

  EINA_LIST_FOREACH(eg->edges, l, e)
    if (!(e->v3_del || e->v2_del) &&
        ((e->a == a && e->b == b) ||
         (e->a == b && e->b == a)))
      return e;
  return NULL;
}

Egraph_Vertice *
egraph_vertice_add(Evas_Object *obj, const char *name, void *data)
{
  EGRAPH_DATA_GET(obj, eg);
  Egraph_Vertice *v;
  u_int32_t id;

  if (eg->vertices_count == EGRAPH_VERTICES_MAX) {
    printf("egraph error: maximum number of vertices reached !\n");
    return NULL;
  }
  v = calloc(1, sizeof(Egraph_Vertice));
  if (!v)
    err(1, "egraph_vertice_add: cannot calloc");
  id = eg->vertices_freeids[eg->vertices_count];
  v->id = id;
  eina_hash_add(eg->vertices, &id, v);
  eg->vertices_count++;
  v->v3_new = 1;
  if (DEBUG)
    printf("egraph_vertice_add %d\n", id);

	if (name)
    v->name = strndup(name, EGRAPH_VERTICE_NAME_MAXLEN);
  egraph_vertice_type_set(obj, v, "vertice_normal");

  v->data = data;

  _layouting_schedule(eg);
  return v;
}

static void
_vertice_v2_add(Egraph *eg, Egraph_Vertice *v)
{
  v->v2_new = 1;
  v->v3_new = 0;

  igraph_add_vertices(&eg->graph2, 1, 0);
  SETVAN(&eg->graph2, "id", eg->graph2_vcount, v->id);
  eg->graph2_vcount++;
}

static void
_vertice_add(Egraph *eg, Egraph_Vertice *v)
{
  Evas_Object *vobj = NULL;

  v->new = 1;
  v->v2_new = 0;

  vobj = _edje_obj_new(eg, v->type);
  if (!vobj) {
    printf("egraph: could not load theme for vertice !");
    v->v2_new = 1;
    v->new = 0;
    _vertice_v2_del(eg, v);
    return;
  }
  evas_object_smart_member_add(vobj, eg->obj);
  evas_object_stack_above(vobj, eg->split_vertice_edge);
  evas_object_event_callback_add(vobj, EVAS_CALLBACK_MOVE, _cb_vertice_move, v);
  v->o = vobj;
  _vertice_geometry_update(eg, v);

  igraph_add_vertices(&eg->graph, 1, 0);
  SETVAN(&eg->graph, "id", eg->graph_vcount, v->id);
  eg->graph_vcount++;

  if (v->name)
    egraph_vertice_rename(eg->obj, v, v->name);
}

void
egraph_vertice_del(Evas_Object *obj, Egraph_Vertice *v)
{
  EGRAPH_DATA_GET(obj, eg);
  Egraph_Edge *e;
  Eina_List *l;

  v->v3_del = 1;

  EINA_LIST_FOREACH(eg->edges, l, e)
    if (e->a == v || e->b == v)
      egraph_edge_del(obj, e);

  _layouting_schedule(eg);
}

static void
_vertice_v2_del(Egraph *eg, Egraph_Vertice *v)
{
  Egraph_Edge *e;
  Eina_List *l;
  int pos;

  if (v->v2_del == 1)
    return;

  v->v2_del = 1;
  v->v3_del = 0;

  if (DEBUG)
    printf("_vertice_v2_del %d\n", v->id);
  EINA_LIST_FOREACH(eg->edges, l, e)
    if (e->a == v || e->b == v)
      _edge_v2_del(eg, e);

  if (!v->v3_new) {
    pos = _igraph_query_vid(&eg->graph2, eg->graph2_vcount, v->id);
    igraph_delete_vertices(&eg->graph2, igraph_vss_1(pos));
    eg->graph2_vcount--;
  }
}

static void
_vertice_del(Egraph *eg, Egraph_Vertice *v)
{
  Egraph_Edge *e;
  Eina_List *l, *lprev;
  Evas_Object *blob;
  int pos;

  if (!v->v3_new && !v->v2_new) {
    EINA_LIST_FOREACH_SAFE(eg->edges, l, lprev, e)
      if (e->a == v || e->b == v)
        _edge_del(eg, e);
    eina_list_free(v->edges);

    pos = _igraph_query_vid(&eg->graph, eg->graph_vcount, v->id);
    igraph_delete_vertices(&eg->graph, igraph_vss_1(pos));
    eg->graph_vcount--;

    EINA_LIST_FOREACH(v->blobs_incoming, l, blob)
      evas_object_del(blob);
    eina_list_free(v->blobs_incoming);

    evas_object_del(v->o);
  }

  eina_hash_del(eg->vertices, &v->id, NULL);
	eg->vertices_count--;
	eg->vertices_freeids[eg->vertices_count] = v->id;

  free(v);
}

void
egraph_vertice_type_set(Evas_Object *obj, Egraph_Vertice *v, const char *type)
{
  EGRAPH_DATA_GET(obj, eg);

  if (v->type)
    free(v->type);

  v->type = strndup(type, TYPE_MAXLEN);
  if (v->o)
    _edje_obj_set(eg, v->o, type);
}

static void
_vertice_update_status(Egraph *eg, Egraph_Vertice *v)
{
  Eina_List *l;
  Egraph_Edge *e;
  int status = 0;

  if (v->is_group && (eina_list_count(v->edges) >= 1)) {
    status = 1; /* we are a group with childs */
  } else {
    EINA_LIST_FOREACH(v->edges, l, e) {
      if ((v == e->a && !e->b->is_group) ||
          (v == e->b && !e->a->is_group)) {
        status = 1; /* we are connected to at least on other non group node */
        break;
      }
    }
  }

  if (status != v->status) {
    if (status)
      _vertice_signal(eg, v, "become_active");
    else
      _vertice_signal(eg, v, "become_inactive");
    v->status = status;
  }
}

static void
_vertice_signal(Egraph *eg, Egraph_Vertice *v, const char *signal)
{
  if (v->o)
    edje_object_signal_emit(v->o, signal, "");
}

void
egraph_vertice_rename(Evas_Object *obj, Egraph_Vertice *v, const char *name)
{
  EGRAPH_DATA_GET(obj, eg);

  if (eg->display_names == 0)
    return;

  if (name) {
    if (v->name != name) {
      if (v->name)
        free(v->name);
      v->name = strndup(name, EGRAPH_VERTICE_NAME_MAXLEN);
    }
  }
  if (v->o) {
    if (v->name)
      edje_object_part_text_set(v->o, "label", v->name);
    else
      edje_object_part_text_set(v->o, "label", "");
    _vertice_geometry_update(eg, v);
  }
}

static void
_vertice_geometry_update(Egraph *eg, Egraph_Vertice *v)
{
  int w, h;

  edje_object_size_min_calc(v->o, &w, &h);
  if (DEBUG)
    printf("_vertice_geometry_update: %d %d\n", w, h);
  evas_object_resize(v->o, w, h);
  if (w > eg->vertice_max_w)
    eg->vertice_max_w = w;
  if (h > eg->vertice_max_h)
    eg->vertice_max_h = h;
  if (DEBUG)
    printf("_vertice_geometry_update: end %d %d\n",
           eg->vertice_max_w, eg->vertice_max_h);
}

void
_color_int_to_rgb(u_int32_t color, int *r, int *g , int *b)
{
  *r = (color & 0xFF000000) >> 24;
  *g = (color & 0x00FF0000) >> 16;
  *b = (color & 0x0000FF00) >> 8;
}

void
egraph_vertice_send_blob(Evas_Object *obj,
                         Egraph_Vertice *a, Egraph_Vertice *b,
                         int size, u_int32_t color)
{
  EGRAPH_DATA_GET(obj, eg);
  Evas_Object *blob;
  int ax, ay, aw, ah, bx, by, bw, bh;
  int cr, cg, cb;
  
  if (!a->o || !b->o)
    return;
  evas_object_geometry_get(a->o, &ax, &ay, &aw, &ah);
  evas_object_geometry_get(b->o, &bx, &by, &bw, &bh);
  _color_int_to_rgb(color, &cr, &cg, &cb);

  blob = _edje_obj_new(eg, "blob");
  if (!blob)
    blob = evas_object_rectangle_add(eg->evas);
  evas_object_color_set(blob, cr, cg, cb, 255);
  evas_object_smart_member_add(blob, eg->obj);
  evas_object_stack_above(blob, eg->split_vertice_edge);
  evas_object_move(blob, ax, ay);
  evas_object_resize(blob, size, size);
  evas_object_show(blob);
  b->blobs_incoming = eina_list_append(b->blobs_incoming, blob);
  _blob_send(blob, b, bx, by);
}

static void
_cb_blob_arrived(void *data, Efx_Map_Data *e, Evas_Object *obj)
{
  Egraph_Vertice *v;

  v = data;
  v->blobs_incoming = eina_list_remove(v->blobs_incoming, obj);
  evas_object_del(obj);
}

static void
_blob_send(Evas_Object *blob, Egraph_Vertice *v, Evas_Coord x, Evas_Coord y)
{
  if (DEBUG)
    printf("blob_send %d %d\n", x, y);
  efx_move(blob, EFX_EFFECT_SPEED_SINUSOIDAL,
          &(Evas_Point){ x, y }, 0.6, _cb_blob_arrived, v);
}

static void
_layouting_schedule(Egraph *eg)
{
  if (eg->layouting.running > 0) {
    eg->layouting.todo = 1;
    return;
  }

  eg->layouting.running = 1;
  ecore_timer_add(0.0, _cb_layouting_start, eg); /* delayed start */
}

static void
_v2_update(Egraph *eg)
{
  Eina_List *l, *lprev, *todel, *toadd;
  Eina_Iterator *it;
  Egraph_Vertice *v;
  Egraph_Edge *e;
  void *data;

  /* update graph and structs based on v2_add / v2_del */
  it = eina_hash_iterator_tuple_new(eg->vertices);
  todel = NULL; toadd = NULL;
  while (eina_iterator_next(it, &data)) {
    Eina_Hash_Tuple *t = data;
    v = t->data;
    if (v->v2_del)
      todel = eina_list_append(todel, v);
    else if (v->v2_new)
      toadd = eina_list_append(toadd, v);
  }
  eina_iterator_free(it);
  EINA_LIST_FOREACH(todel, l, v)
    _vertice_del(eg, v);
  EINA_LIST_FOREACH(toadd, l, v)
    _vertice_add(eg, v);
  todel = eina_list_free(todel);
  toadd = eina_list_free(toadd);
  EINA_LIST_FOREACH_SAFE(eg->edges, l, lprev, e) {
    if (e->v2_del)
      _edge_del(eg, e);
    else if (e->v2_new)
      _edge_add(eg, e);
  }
}

static void
_v3_update(Egraph *eg)
{
  Eina_List *l, *lprev;
  Eina_Iterator *it;
  Egraph_Vertice *v;
  Egraph_Edge *e;
  void *data;
  float ranx, rany;
  int changes_count = 0;
  int changes_diff = 0;
  int i, id;

  if (DEBUG)
    printf("_v3_update\n");
  /* update graph2 and structs based on v3_add / v3_del */
  it = eina_hash_iterator_tuple_new(eg->vertices);
  while (eina_iterator_next(it, &data)) {
    Eina_Hash_Tuple *t = data;
    v = t->data;
    if (v->v3_del) {
      _vertice_v2_del(eg, v); changes_diff--; changes_count++;
    } else if (v->v3_new) {
      _vertice_v2_add(eg, v); changes_diff++; changes_count++;
    }
  }
  eina_iterator_free(it);
  if (DEBUG)
    printf("_v3_update edges\n");
  EINA_LIST_FOREACH_SAFE(eg->edges, l, lprev, e) {
    if (e->v3_del) {
      _edge_v2_del(eg, e); changes_count++;
    } else if (e->v3_new) {
      _edge_v2_add(eg, e); changes_count++;
    }
  }

  /* set correct coords2 size */
  if (changes_diff > 0) {
    for (i=0; i<changes_diff; i++) {
      id = (eg->graph2_vcount - changes_diff) + i;
      igraph_matrix_add_rows(&eg->coords2, 1);
      ranx = eg->graph_wmin + fmod((float)random() / 1000, (float)((eg->graph_wmax + 1) - eg->graph_wmin));
      rany = eg->graph_hmin + fmod((float)random() / 1000, (float)((eg->graph_hmax + 1) - eg->graph_hmin));
      if (DEBUG)
        printf("ranx %6.3f rany %6.3f\n", ranx, rany);
      igraph_matrix_set(&eg->coords2, id, 0, ranx);
      igraph_matrix_set(&eg->coords2, id, 1, rany);
    }
  } else if (changes_diff < 0) {
    changes_diff = -changes_diff;
    for (i=0; i<changes_diff; i++) {
      id = (eg->graph2_vcount + changes_diff) - i;
      igraph_matrix_remove_row(&eg->coords2, 0);
    }
  }

  if (eg->layout == EGRAPH_LAYOUT_FRUCHTERMANREINGOLD) {
    /* set minimum and maximum for each node */
    /* XXX do that in layouting thread ? */
    if (DEBUG)
      printf("g wmin %d wmax %d hmin %d hmax %d\n",
             eg->graph_wmin, eg->graph_wmax, eg->graph_hmin, eg->graph_hmax);
    igraph_vector_init(&eg->graph2_wmin, eg->graph2_vcount);
    igraph_vector_init(&eg->graph2_wmax, eg->graph2_vcount);
    igraph_vector_init(&eg->graph2_hmin, eg->graph2_vcount);
    igraph_vector_init(&eg->graph2_hmax, eg->graph2_vcount);
    igraph_vector_fill(&eg->graph2_wmin, eg->graph_wmin);
    igraph_vector_fill(&eg->graph2_wmax, eg->graph_wmax);
    igraph_vector_fill(&eg->graph2_hmin, eg->graph_hmin);
    igraph_vector_fill(&eg->graph2_hmax, eg->graph_hmax);
  }

  eg->layouting.changes_diff = changes_diff;
}

static Eina_Bool
_cb_layouting_start(void *data)
{
  Egraph *eg;

  eg = data;

  eg->layouting.todo = 0;

  _v3_update(eg);

  eg->layouting.running = 2;
  eg->layouting.thread = ecore_thread_run(_cb_layouting_run, _cb_layouting_end,
                                          _cb_layouting_cancel, eg);

  return EINA_FALSE; /* no repeat */
}

void
_cb_layouting_run(void *data, Ecore_Thread *thread)
{
  Egraph *eg;
  int niter;

  eg = data;

  if (DEBUG)
    printf("[-] _cb_layouting_run begin (%d)\n", eg->layout);

  switch(eg->layout) {
  case EGRAPH_LAYOUT_KAMADAKAWAI:
    if (eg->layouting.improvement) {
      niter = 300;
    } else {
      if (eg->layouting.changes_diff == 0)
        niter = 1000;
      else
        niter = 1000 * eg->layouting.changes_diff;
      if (niter > 2000)
        niter = 2000;
    }
    /* http://igraph.sourceforge.net/doc/html/ch18s01.html#igraph_layout_kamada_kawai
     * int igraph_layout_kamada_kawai(const igraph_t *g, igraph_matrix_t *res,
     *                    igraph_integer_t niter, igraph_real_t sigma, 
     *                    igraph_real_t initemp, igraph_real_t coolexp,
     *                    igraph_real_t kkconst, igraph_bool_t use_seed,
     *                    const igraph_vector_t *minx,
     *                    const igraph_vector_t *maxx,
     *                    const igraph_vector_t *miny,
     *                    const igraph_vector_t *maxy);
     * Defaults :
     * igraph_layout_kamada_kawai(&eg->graph2, &eg->coords2,
     *                    1000, eg->vertices_count / 4, 10, 0.99,
     *                    eg->vertices_count ^ 2, 1,
     *                    NULL, NULL, NULL, NULL);
     */
    igraph_layout_kamada_kawai(&eg->graph2, &eg->coords2,
                          niter, eg->graph2_vcount, 10, 0.99,
                          eg->vertices_count ^ 2, 1,
                          NULL, NULL, NULL, NULL);
    break;

  case EGRAPH_LAYOUT_GRAPHOPT:
    if (eg->layouting.improvement) {
      niter = 300;
    } else {
      if (eg->layouting.changes_diff == 0)
        niter = 100;
      else
        niter = 50 * eg->layouting.changes_diff;
      if (niter > 500)
        niter = 500;
    }
    /* http://igraph.sourceforge.net/doc/html/ch18s01.html#igraph_layout_graphopt
     * int igraph_layout_graphopt(const igraph_t *g, igraph_matrix_t *res, 
     *          igraph_integer_t niter,
     *          igraph_real_t node_charge, igraph_real_t node_mass,
     *          igraph_real_t spring_length,
     *          igraph_real_t spring_constant, 
     *          igraph_real_t max_sa_movement,
     *          igraph_bool_t use_seed);
     * Defaults :
     * igraph_layout_graphopt(&eg->graph2, &eg->coords2,
     *                    1000, 0.001, 30, 0, 1, 5, 0);
     */
    igraph_layout_graphopt(&eg->graph2, &eg->coords2,
                           niter, 0.003, 10, 10, 1, 5, 1);
    break;

  case EGRAPH_LAYOUT_FRUCHTERMANREINGOLD:
    niter = 1000;
    /* http://igraph.sourceforge.net/doc/html/ch18s01.html#igraph_layout_fruchterman_reingold
     * int igraph_layout_fruchterman_reingold(const igraph_t *graph, igraph_matrix_t *res,
     *          igraph_integer_t niter, igraph_real_t maxdelta,
     *          igraph_real_t area, igraph_real_t coolexp, 
     *          igraph_real_t repulserad, igraph_bool_t use_seed,
     *          const igraph_vector_t *weight, 
     *          const igraph_vector_t *minx,
     *          const igraph_vector_t *maxx,
     *          const igraph_vector_t *miny,
     *          const igraph_vector_t *maxy);
     * Defaults:
     * igraph_layout_fruchterman_reingold(&eg->graph2, &eg->coords2,
     *                                    500, eg->graph2_vcount,
     *                                    sqrt(eg->graph2_vcount) * sqrt(eg->graph2_vcount), 1.5,
     *                                    eg->graph2_vcount, 0,
     *                                    NULL, NULL, NULL, NULL, NULL);
     */
     igraph_layout_fruchterman_reingold(&eg->graph2, &eg->coords2,
                                        niter, 0.05,
                                        sqrt(eg->graph2_vcount), 1.5,
                                        sqrt(eg->graph2_vcount) * eg->graph2_vcount, 1,
                                        NULL, NULL, NULL, NULL, NULL);
                                        //&eg->graph2_wmin, &eg->graph2_wmax,
                                        //&eg->graph2_hmin, &eg->graph2_hmax);
     break;
  }
  if (DEBUG)
    printf("[-] _cb_layouting_run end\n");
}

static void
_coords2_copy(Egraph *eg)
{
  igraph_matrix_copy(&eg->coords, &eg->coords2);
}

void
_cb_layouting_end(void *data, Ecore_Thread *thread)
{
  Egraph *eg;

  eg = data;
  _v2_update(eg);
  _coords2_copy(eg);
  _reposition(eg, 0);
  eg->layouting.running = 0;
  if (eg->layouting.todo) {
    eg->layouting.todo = 0;
    eg->layouting.improvement = 0;
    _layouting_schedule(eg);
  } else {
    if (eg->do_improvements) {
      if (eg->layouting.improvement < EGRAPH_LAYOUTING_IMPROVEMENTS) {
        eg->layouting.improvement++;
        _layouting_schedule(eg);
      } else {
        eg->layouting.improvement = 0;
      }
    }
  }
}

void
_cb_layouting_cancel(void *data, Ecore_Thread *thread)
{
  Egraph *eg;

  eg = data;
  eg->layouting.running = 0;
  eg->layouting.todo = 0;
  /* we are not in a clean state now, but it happends on exit only */
}

/* XXX slow ! possible to do edge/vertice delete on repositionning ? */
static int
_igraph_query_vid(igraph_t *g, int g_len, int id)
{
  int i;

  for (i=0; i<g_len; i++) {
    if (VAN(g, "id", i) == id)
      return i;
  }
  printf("egraph: WARNING: _igraph_query_id %d not found !\n", id);
  return -1;
}

/* Apply vertice move to it's edges */
static void
_cb_vertice_move(void *data, Evas *evas, Evas_Object *obj, void *event_info)
{
  EGRAPH_DATA_GET(evas_object_smart_parent_get(obj), eg);
  Egraph_Vertice *v;
  Egraph_Edge *e;
  Evas_Map *m;
  Eina_List *l;
  int x, y, w, h;
  int ax, ay, bx, by, aw, ah, bw, bh;
  int p0x, p0y, p1x, p1y, p2x, p2y, p3x, p3y;
  float a;

  v = data;
  evas_object_geometry_get(v->o, &x, &y, &w, &h);

  EINA_LIST_FOREACH(v->edges, l, e) {
    if (e->new) {
      if (eg->display_edges)
        evas_object_show(e->o);
      e->new = 0;
    }
    if (e->o_usetheme) {
      /* XXX we map the edges once per node = 2 times ... */
      evas_object_move(e->o, x, y);
      m = evas_map_new(4);
      evas_map_smooth_set(m, 1);
      evas_map_util_points_populate_from_object(m, e->o);
      evas_object_geometry_get(e->a->o, &ax, &ay, &aw, &ah);
      evas_object_geometry_get(e->b->o, &bx, &by, &bw, &bh);
      ax = ax + aw / 2; ay = ay + ah / 2;
      bx = bx + bw / 2; by = by + bh / 2;
      aw = aw / 2; ah = ah / 2;
      bw = bw / 2; bh = bh / 2;
      /* rotate edge endpoints */
      a = atan2(by - ay, bx - ax);
#define ROTX(x, h, a) (-sin(a)*h + x)
#define ROTY(y, h, a) (cos(a)*h + y)
      p0x = ROTX(ax, ah, a); p0y = ROTY(ay, ah, a);
      p1x = ROTX(ax, -ah, a); p1y = ROTY(ay, -ah, a);
      p2x = ROTX(bx, bh, a); p2y = ROTY(by, bh, a);
      p3x = ROTX(bx, -bh, a); p3y = ROTY(by, -bh, a);
      /* set edge endpoints */
      evas_map_point_coord_set(m, 0, p2x, p2y, 0);
      evas_map_point_coord_set(m, 1, p0x, p0y, 0);
      evas_map_point_coord_set(m, 2, p1x, p1y, 0);
      evas_map_point_coord_set(m, 3, p3x, p3y, 0);
      evas_object_map_set(e->o, m);
      evas_object_map_enable_set(e->o, EINA_TRUE); // XXX do at init
      evas_map_free(m);
    } else {
      evas_object_line_xy_get(e->o, &ax, &ay, &bx, &by);
      if (e->a == v) {
        ax = x + w/2;
        ay = y + h/2;
      } else {
        bx = x + w/2;
        by = y + h/2;
      }
      evas_object_line_xy_set(e->o, ax, ay, bx, by);
    }
  }
}

static void
_reposition(Egraph *eg, int no_animation)
{
  Egraph_Vertice *v;
  u_int32_t id;
  float gw_min, gw_max, gh_min, gh_max, factor_w, factor_h;
  float x, y;
  int obj_x, obj_y, obj_w, obj_h;
  int vcur;

  if (DEBUG)
    printf("[-] _reposition\n");
  if (eg->graph_vcount == 0)
    return;

  evas_object_geometry_get(eg->obj, &obj_x, &obj_y, &obj_w, &obj_h);
  _matrix_minmax_2v(&eg->coords, eg->graph_vcount,
                    &gw_min, &gw_max, &gh_min, &gh_max);
  eg->graph_wmin = gw_min;
  eg->graph_wmax = gw_max;
  eg->graph_hmin = gh_min;
  eg->graph_hmax = gh_max;
  
  if (DEBUG)
    printf("gw_min %6.3f gw_max %6.3f gh_min %6.3f gh_max %6.3f\n",
           gw_min, gw_max, gh_min, gh_max);
  if (gw_max == gw_min)
    factor_w = 1;
  else
    factor_w = (obj_w - eg->vertice_max_w) / (gw_max - gw_min);
  if (gh_max == gh_min)
    factor_h = 1;
  else
    factor_h = (obj_h - eg->vertice_max_h) / (gh_max - gh_min);
  if (DEBUG)
    printf("factor_w %6.3f factor_h %6.3f\n", factor_w, factor_h);

  for (vcur=0; vcur<eg->graph_vcount; vcur++) {
    id = VAN(&eg->graph, "id", vcur);

    x = MATRIX(eg->coords, vcur, 0);
    y = MATRIX(eg->coords, vcur, 1);
    if (DEBUG)
      printf("%d: %6.3f %6.3f id %d\n", vcur, x, y, id);
    x = obj_x + ((x - gw_min) * factor_w);
    y = obj_y + ((y - gh_min) * factor_h);
    if (DEBUG)
      printf("         inobj: %6.3f %6.3f\n", x, y);

    v = eina_hash_find(eg->vertices, &id);
    if (eg->use_animations && !no_animation) {
      efx_move(v->o, EFX_EFFECT_SPEED_DECELERATE,
              &(Evas_Point){ x, y }, 0.5, NULL, NULL);
    }
    else
      evas_object_move(v->o, x, y);
    /* XXX fix blob repositionning
    Evas_Object *blob;
    Eina_List *l;
    EINA_LIST_FOREACH(v->blobs_incoming, l, blob)
      _blob_send(blob, v, x, y);
    */
    if (v->new) {
      evas_object_show(v->o);
      v->new = 0;
    }
  }
}

/**
 * Compute minimum and maximum of a matrices of 2 colum vectors
 *
 * @note igraph is crazy in the coconut
 */
static void
_matrix_minmax_2v(const igraph_matrix_t *m, int row_count,
                  float *c1min, float *c1max, float *c2min, float *c2max)
{
  float val;
  int row;

  *c1min=MATRIX(*m, 0, 0); *c1max=MATRIX(*m, 0, 0);
  *c2min=MATRIX(*m, 0, 1); *c2max=MATRIX(*m, 0, 1);

  for (row=1; row<row_count; row++) {
    val = MATRIX(*m, row, 0);
    if (val < *c1min) *c1min = val;
    else if (val > *c1max) *c1max = val;
    val = MATRIX(*m, row, 1);
    if (val < *c2min) *c2min = val;
    else if (val > *c2max) *c2max = val;
  }
}

static Evas_Object *
_edje_obj_new(Egraph *eg, const char *group)
{
  Evas_Object *obj;

  obj = edje_object_add(eg->evas);
  return _edje_obj_set(eg, obj, group);
}

static Evas_Object *
_edje_obj_set(Egraph *eg, Evas_Object *obj, const char *group)
{
  if (!obj || !edje_object_file_set(obj, eg->theme_path, group)) {
    int err = edje_object_load_error_get(obj);
    const char *errmsg = edje_load_error_str(err);
    if (DEBUG)
      fprintf(stderr, "Could not load the edje file - reason:%s\n", errmsg);
    return NULL;
  }
  return obj;
}

Egraph_Vertice *
egraph_group_add(Evas_Object *obj, const char *name, void *data)
{
  Egraph_Vertice *g;

  g = egraph_vertice_add(obj, name, data);
  g->is_group = 1;
  egraph_vertice_type_set(obj, g, "vertice_group");
  return g;
}

int
egraph_group_vertice_attach(Evas_Object *obj,
                            Egraph_Vertice *group, Egraph_Vertice *v)
{
  Egraph_Edge *e;

  group->group_vertices = eina_list_append(group->group_vertices, v);
  e = egraph_edge_add(obj, group, v, NULL);
  egraph_edge_type_set(obj, e, "edge_group");
  return 1;
}

void
egraph_group_vertice_detach(Evas_Object *obj,
                            Egraph_Vertice *group, Egraph_Vertice *v)
{
  Egraph_Edge *e;

  group->group_vertices = eina_list_remove(group->group_vertices, v);
  e = egraph_edge_find(obj, group, v);
  egraph_edge_del(obj, e);
}