path: root/examples/graph.c

#if 0 /*
#/  ================================================================
#/
#/    graph.c
#/
#/  ================================================================
#/
#/    Self-compilation shell script
#/
SRC=${0##*./}
BIN=${SRC%.*}
gcc                                         \
  -Wall -Wextra -Werror -pedantic           \
  -Wno-old-style-declaration                \
  -Wno-missing-braces                       \
  -Wno-unused-variable                      \
  -Wno-unused-but-set-variable              \
  -Wno-unused-parameter                     \
  -Wno-overlength-strings                   \
  -O3                                       \
  -fsanitize=undefined,address,leak -mshstk \
  -lX11 -lm                                 \
  -o $BIN $SRC &&                           \
  ./$BIN $@ && rm $BIN
exit $? # */
#endif

#include "../graphics.c"

enum {
  MAX_NUM_NODES = 1024,
  MAX_NUM_EDGES = 1024,
};

typedef struct {
  b8  enabled;
  f64 x;
  f64 y;
  f64 radius;
  b8  hover;
  b8  highlight;
  f64 distance;
} Node;

typedef struct {
  b8  enabled;
  i64 src;
  i64 dst;
  f64 width;
  b8  hover;
  b8  highlight;
} Edge;

typedef struct {
  Node nodes[MAX_NUM_NODES];
  Edge edges[MAX_NUM_EDGES];
} World;

World world = {0};

b8 check_node_index(i64 node_index) {
  return
       node_index >= 0 && node_index < MAX_NUM_NODES
    && world.nodes[node_index].enabled;
}

b8 check_edge_index(i64 edge_index) {
  return
       edge_index >= 0 && edge_index < MAX_NUM_EDGES
    && world.edges[edge_index].enabled
    && check_node_index(world.edges[edge_index].src)
    && check_node_index(world.edges[edge_index].dst);
}

void draw_node(i64 node_index) {
  assert(check_node_index(node_index));

  Node n = world.nodes[node_index];

  u32 color = 0; // black color

  if (n.highlight)
    color = 0xff00ff; // pink color
  if (n.hover)
    color = 0x007f00; // green color

  fill_ellipse(
    OP_SET, // set pixels
    color,
    n.x - n.radius,
    n.y - n.radius,
    n.radius * 2,
    n.radius * 2
  );
}

void draw_edge(i64 edge_index) {
  assert(check_edge_index(edge_index));

  Edge e  = world.edges[edge_index];
  Node n0 = world.nodes[e.src];
  Node n1 = world.nodes[e.dst];

  u32 color = 0x7f7f7f; // grey color

  if (e.highlight)
    color = 0xff00ff; // pink color
  if (e.hover)
    color = 0x007f00; // green color

  fill_line(
    OP_SET, // set pixels
    color,
    n0.x,
    n0.y,
    n1.x,
    n1.y,
    e.width
  );
}

void draw_graph(void) {
  //  draw all edges
  for (i64 i = 0; i < MAX_NUM_EDGES; ++i)
    if (world.edges[i].enabled)
      draw_edge(i);

  //  draw all nodes
  for (i64 i = 0; i < MAX_NUM_NODES; ++i)
    if (world.nodes[i].enabled)
      draw_node(i);
}

void update_node(i64 node_index) {
  assert(check_node_index(node_index));

  Node n = world.nodes[node_index];

  world.nodes[node_index].hover = ellipse_contains(
    n.x - n.radius,
    n.y - n.radius,
    n.radius * 2,
    n.radius * 2,
    platform.cursor_x,
    platform.cursor_y
  );
}

void update_edge(i64 edge_index) {
  assert(check_edge_index(edge_index));

  Edge e  = world.edges[edge_index];
  Node n0 = world.nodes[e.src];
  Node n1 = world.nodes[e.dst];

  world.edges[edge_index].hover = line_contains(
    n0.x,
    n0.y,
    n1.x,
    n1.y,
    e.width,
    platform.cursor_x,
    platform.cursor_y
  );
}

void remove_edge(i64 edge_index) {
  assert(check_edge_index(edge_index));

  world.edges[edge_index].enabled = 0;
}

void remove_node(i64 node_index) {
  assert(check_node_index(node_index));

  for (i64 i = 0; i < MAX_NUM_EDGES; ++i)
    if (world.edges[i].enabled && (world.edges[i].src == node_index || world.edges[i].dst == node_index))
      remove_edge(i);

  world.nodes[node_index].enabled = 0;
}

void add_node(f64 x, f64 y) {
  i64 node_index = 0;

  while (node_index < MAX_NUM_NODES && world.nodes[node_index].enabled)
    ++node_index;

  assert(node_index < MAX_NUM_NODES);

  world.nodes[node_index] = (Node) {
    .enabled = 1,
    .x       = x,
    .y       = y,
    .radius  = 50,
  };
}

void add_edge(i64 src, i64 dst) {
  assert(check_node_index(src));
  assert(check_node_index(dst));

  if (src == dst)
    return;

  for (i64 i = 0; i < MAX_NUM_EDGES; ++i)
    if (world.edges[i].enabled && world.edges[i].src == src && world.edges[i].dst == dst)
      return;

  i64 edge_index = 0;

  while (edge_index < MAX_NUM_EDGES && world.edges[edge_index].enabled)
    ++edge_index;

  assert(edge_index < MAX_NUM_EDGES);

  world.edges[edge_index] = (Edge) {
    .enabled = 1,
    .src     = src,
    .dst     = dst,
    .width   = 30,
  };
}

f64 distance_between(f64 x0, f64 y0, f64 x1, f64 y1) {
  f64 dx = x1 - x0;
  f64 dy = y1 - y0;

  return sqrt(dx * dx + dy * dy);
}

void highlight_path(i64 src, i64 dst) {
  if (!check_node_index(src)) return;
  if (!check_node_index(dst)) return;

  for (i64 i = 0; i < MAX_NUM_NODES; ++i) {
    world.nodes[i].highlight = 0;
    world.nodes[i].distance  = -1;
  }

  for (i64 i = 0; i < MAX_NUM_EDGES; ++i)
    world.edges[i].highlight = 0;

  world.nodes[src].highlight = 1;
  world.nodes[dst].highlight = 1;

  world.nodes[src].distance = 0;

  //  Dijkstra
  //

  for (;;) {
    //  Find a node with minimum path distance
    //

    i64 min_index    = -1;
    f64 min_distance = -1;

    for (i64 i = 0; i < MAX_NUM_EDGES; ++i)
      if (check_edge_index(i)) {
        Edge e  = world.edges[i];
        Node n0 = world.nodes[e.src];
        Node n1 = world.nodes[e.dst];

        f64 l = distance_between(n0.x, n0.y, n1.x, n1.y);

        //  Assume bi-directional graph

        if (n0.distance >= 0 && n1.distance < 0)
          if (min_index < 0 || n0.distance + l < min_distance) {
            min_index    = e.dst;
            min_distance = n0.distance + l;
          }

        if (n1.distance >= 0 && n0.distance < 0)
          if (min_index < 0 || n1.distance + l < min_distance) {
            min_index    = e.src;
            min_distance = n1.distance + l;
          }
      }

    //  If not found, stop the search
    //

    if (min_index < 0)
      break;

    //  Save the distance for the found node
    //

    world.nodes[min_index].distance = min_distance;

    //  Repeat until we got the destination node
    //

    if (min_index == dst)
      break;
  }

  //  If path not found, stop
  //

  if (world.nodes[dst].distance < 0) {
    printf("Path not found\n");
    return;
  }

  //  Reconstruct the path
  //

  f64 min_distance = world.nodes[dst].distance;

  for (i64 node_index = dst; node_index != src;) {
    //  Repeat until we got the source node

    //  Find neighbor node with minimal path distance
    //

    i64 min_node_index = -1;
    i64 min_edge_index = -1;

    for (i64 i = 0; i < MAX_NUM_EDGES; ++i)
      if (check_edge_index(i)) {
        Edge e  = world.edges[i];
        Node n0 = world.nodes[e.src];
        Node n1 = world.nodes[e.dst];

        //  Assume bi-directional graph

        if (e.src == node_index && n1.distance >= 0 && n1.distance < min_distance) {
          min_node_index = e.dst;
          min_edge_index = i;
          min_distance   = n1.distance;
        }

        if (e.dst == node_index && n0.distance >= 0 && n0.distance < min_distance) {
          min_node_index = e.src;
          min_edge_index = i;
          min_distance   = n0.distance;
        }
      }

    //  If not found, stop
    //

    if (min_node_index < 0) {
      printf("Internal error\n");
      break;
    }

    //  Highlight found node and edge
    //

    world.nodes[min_node_index].highlight = 1;
    world.edges[min_edge_index].highlight = 1;

    //  Repeat for the found node
    //

    node_index = min_node_index;
  }
}

i32 main(i32 argc, c8 **argv) {
  (void) argc;
  (void) argv;

  platform = (Platform) {
    .title        = "Graph",
    .frame_width  = 960,
    .frame_height = 720,
  };

  p_init();

  add_node(100, 100);
  add_node(300, 100);
  add_node(120, 300);

  add_edge(0, 1);
  add_edge(0, 2);
  add_edge(1, 2);

  b8  adding_edge = 0;
  i64 adding_src  = 0;
  i64 adding_dst  = 0;

  b8  path_changed = 0;
  i64 path_src     = -1;
  i64 path_dst     = -1;

  while (!platform.done) {
    p_wait_events();

    //  Input events

    b8 hover_node = 0;

    for (i64 i = 0; i < MAX_NUM_NODES; ++i)
      if (world.nodes[i].enabled) {
        update_node(i);
        if (world.nodes[i].hover)
          hover_node = 1;
      }

    for (i64 i = 0; i < MAX_NUM_EDGES; ++i)
      if (world.edges[i].enabled) {
        if (hover_node)
          world.edges[i].hover = 0;
        else
          update_edge(i);
      }

    if (platform.key_pressed[KEY_DELETE]) {
      for (i64 i = 0; i < MAX_NUM_EDGES; ++i)
        if (world.edges[i].enabled && world.edges[i].hover)
          remove_edge(i);

      for (i64 i = 0; i < MAX_NUM_NODES; ++i)
        if (world.nodes[i].enabled && world.nodes[i].hover)
          remove_node(i);
    }

    if (platform.key_pressed['1']) {

      for (i64 i = 0; i < MAX_NUM_NODES; ++i)
        if (world.nodes[i].enabled && world.nodes[i].hover) {
          path_src     = i;
          path_changed = 1;
          break;
        }
    }

    if (platform.key_pressed['2'])
      for (i64 i = 0; i < MAX_NUM_NODES; ++i)
        if (world.nodes[i].enabled && world.nodes[i].hover) {
          path_dst     = i;
          path_changed = 1;
          break;
        }

    if (path_changed) {
      highlight_path(path_src, path_dst);
      path_changed = 0;
    }

    if (platform.key_pressed[BUTTON_LEFT])
      add_node(platform.cursor_x, platform.cursor_y);

    if (platform.key_pressed[BUTTON_RIGHT])
      for (i64 i = 0; i < MAX_NUM_NODES; ++i)
        if (world.nodes[i].enabled && world.nodes[i].hover) {
          adding_edge = 1;
          adding_src  = i;
          adding_src  = i;
          break;
        }

    if (adding_edge)
      for (i64 i = 0; i < MAX_NUM_NODES; ++i)
        if (world.nodes[i].enabled && world.nodes[i].hover) {
          adding_dst = i;
          break;
        }

    if (adding_edge && !platform.key_down[BUTTON_RIGHT]) {
      adding_edge = 0;
      add_edge(adding_src, adding_dst);
    }

    //  Render

    fill_rectangle(OP_SET, 0xffffff, 0, 0, platform.frame_width, platform.frame_height);

    if (adding_edge) {
      f64 x0 = world.nodes[adding_src].x;
      f64 y0 = world.nodes[adding_src].y;
      f64 x1 = platform.cursor_x;
      f64 y1 = platform.cursor_y;

      if (adding_src != adding_dst) {
        x1 = world.nodes[adding_dst].x;
        y1 = world.nodes[adding_dst].y;
      }

      fill_line(OP_SET, 0x7f007f, x0, y0, x1, y1, 30);
    }

    draw_graph();

    p_render_frame();
  }

  p_cleanup();
  return 0;
}