Difference between revisions of "TADM2E 7.3"

From Algorithm Wiki
Jump to: navigation, search
(Blanked the page)
(→‎Algorithm)
 
(2 intermediate revisions by the same user not shown)
Line 1: Line 1:
  
 +
== Algorithm ==
 +
 +
Given two graphs G1 and G2:
 +
 +
* compare the nos. of vertices in G1 and G2 for equality;
 +
* compare the nos. of edges in G1 and G2 for equality;
 +
* sort the vertices of G1 and G2 by degree and compare the degrees of each pair of vertices from G1 and G2 for equality;
 +
* use back-tracking to generate a mapping of vertices: for each vertex, v1, in G1 pick a vertex, v2, from G2 of the same degree and check that if v2 is adjacent to any vertices that have already been mapped they have been mapped to vertices adjacent to v1; if all vertices can be successfully mapped, G1 and G2 are isomorphic.
 +
 +
== Implementation in C with Examples ==
 +
 +
Each of the example graphs below is specified as a list of strings where each
 +
string comprises the label of a vertex followed by the labels of vertices
 +
adjacent to it.  The strings are sorted by decreasing length, which is to say
 +
that the vertices are sorted by decreasing degree.
 +
 +
We compare the first graph, G1, to the remaining five, G2 - G6.  G2 is
 +
isomorphic to G1; the others are not.
 +
 +
Expected output:
 +
 +
  isomorphic: 1
 +
  g1[2] -> g2[0]
 +
  g1[1] -> g2[1]
 +
  g1[0] -> g2[2]
 +
  g1[3] -> g2[3]
 +
  g1[5] -> g2[4]
 +
  g1[4] -> g2[5]
 +
  g1[6] -> g2[6]
 +
  isomorphic: 0
 +
  isomorphic: 0
 +
  isomorphic: 0
 +
  isomorphic: 0
 +
 +
Code:
 +
 +
#include <assert.h>
 +
#include <limits.h>
 +
#include <stdint.h>
 +
#include <stdio.h>
 +
#include <stdlib.h>
 +
#include <string.h>
 +
 +
typedef struct vertex_
 +
  {
 +
  size_t index;    /* Index of the vertex in the graph */
 +
  size_t nr_edges; /* No. of edges incident on this vertex */
 +
  size_t edges[];  /* Array of indices of vertices adjacent to this vertex */
 +
  }
 +
vertex;
 +
 +
typedef struct graph_
 +
  {
 +
  size_t  nr_vertices;  /* No. of vertices in this graph */
 +
  size_t  nr_edges;    /* No. of edges in this graph */
 +
  vertex *vertices[];  /* Array of vertices in this graph */
 +
  }
 +
graph;
 +
 +
static int
 +
map_vertices (const graph *g1, const graph *g2, size_t *mappings, size_t i)
 +
  {
 +
  if (i == g2->nr_vertices)
 +
    return 1;
 +
 +
  const vertex *v1 = g1->vertices[i];
 +
 +
  /*
 +
    * Given a vertex, v1, in g1, find a vertex, v2, in g2 which has the same
 +
    * degree and has not already been mapped to a previous vertex in g1.
 +
    */
 +
  for (size_t j = 0; j < g2->nr_vertices; ++j)
 +
    {
 +
    const vertex *v2 = g2->vertices[j];
 +
 +
    if (v1->nr_edges == v2->nr_edges && mappings[v2->index] == SIZE_MAX)
 +
      {
 +
      /*
 +
        * Ensure that if a vertex, u2, adjacent to v2, has already been mapped,
 +
        * it is mapped to a vertex, u1, adjacent to v1.
 +
        */
 +
      int mapped = 1;
 +
 +
      for (size_t l = 0; mapped && l < v2->nr_edges; ++l)
 +
        {
 +
        const vertex *u2 = g2->vertices[v2->edges[l]];
 +
 +
        if (mappings[u2->index] != SIZE_MAX)
 +
          {
 +
          int found = 0;
 +
 +
          for (size_t k = 0; !found && k < v1->nr_edges; ++k)
 +
            {
 +
            const vertex *u1 = g1->vertices[v1->edges[k]];
 +
 +
            if (mappings[u2->index] == u1->index)
 +
              found = 1;
 +
            }
 +
 +
          if (!found)
 +
            mapped = 0;
 +
          }
 +
        }
 +
 +
      if (mapped)
 +
        {
 +
        mappings[v2->index] = v1->index;
 +
        if (map_vertices (g1, g2, mappings, i + 1))
 +
          return 1;
 +
        else
 +
          mappings[v2->index] = SIZE_MAX;
 +
        }
 +
      }
 +
    }
 +
 +
  return 0;
 +
  }
 +
 +
static void
 +
compare_graphs (graph *g1, graph *g2)
 +
  {
 +
  size_t *mappings = malloc (g1->nr_vertices * sizeof *mappings);
 +
  assert (mappings != NULL);
 +
  for (size_t i = 0; i < g1->nr_vertices; ++i)
 +
    mappings[i] = SIZE_MAX;
 +
 +
  int isomorphic;
 +
 +
  if (g1->nr_vertices != g2->nr_vertices)
 +
    isomorphic = 0;
 +
  else if (g1->nr_edges != g2->nr_edges)
 +
    isomorphic = 0;
 +
  else
 +
    {
 +
    isomorphic = 1;
 +
    for (size_t i = 0; isomorphic && i < g1->nr_vertices; i++)
 +
      isomorphic = g1->vertices[i]->nr_edges == g2->vertices[i]->nr_edges;
 +
 +
    if (isomorphic)
 +
      isomorphic = map_vertices (g1, g2, mappings, 0);
 +
    }
 +
 +
  fprintf (stderr, "isomorphic: %d\n", isomorphic);
 +
 +
  if (isomorphic)
 +
    for (size_t i = 0; i < g2->nr_vertices; ++i)
 +
      fprintf (stderr, "g1[%zu] -> g2[%zu]\n", mappings[i], i);
 +
 +
  free (mappings);
 +
  }
 +
 +
/*******************************************************************************
 +
  *
 +
  *    a---b
 +
  *  / |  |
 +
  * +  c---d
 +
  *  \ |  |
 +
  *    e---f  g
 +
  *
 +
  */
 +
char *G1[] =
 +
  {
 +
  "abce",
 +
  "cade",
 +
  "dbcf",
 +
  "eacf",
 +
  "bad",
 +
  "fde",
 +
  "g",
 +
  };
 +
 +
/*******************************************************************************
 +
  *
 +
  *    a---b
 +
  *    |  | \
 +
  *    c---d  +
 +
  *    |  | /
 +
  * g  e---f
 +
  *
 +
  */
 +
char *G2[] =
 +
  {
 +
  "cade",
 +
  "dbcf",
 +
  "fbde",
 +
  "badf",
 +
  "abc",
 +
  "ecf",
 +
  "g",
 +
  };
 +
 +
/*******************************************************************************
 +
  *
 +
  *    +--+
 +
  *  /    \
 +
  *  +  a---b
 +
  *  |  |  |
 +
  *  +  c---d
 +
  *  \ |  |
 +
  *    e---f
 +
  *
 +
  */
 +
char *G3[] =
 +
  {
 +
  "bade",
 +
  "cade",
 +
  "dbcf",
 +
  "ebcf",
 +
  "abc",
 +
  "fbd",
 +
  };
 +
 +
/*******************************************************************************
 +
  *
 +
  *    +--+
 +
  *  /    \
 +
  *  +  a---b
 +
  *  |  |  |
 +
  *  +  c---d
 +
  *  \ |  |
 +
  *    e---f---g
 +
  *
 +
  */
 +
char *G4[] =
 +
  {
 +
  "bade",
 +
  "cade",
 +
  "dbcf",
 +
  "ebcf",
 +
  "fbdg",
 +
  "abc",
 +
  "gf",
 +
  };
 +
 +
/*******************************************************************************
 +
  *
 +
  *    a---b
 +
  *    |  |
 +
  *    c---d
 +
  *    |  |
 +
  * g---e---f
 +
  *
 +
  */
 +
char *G5[] =
 +
  {
 +
  "cade",
 +
  "dbcf",
 +
  "ecfg",
 +
  "abc",
 +
  "bad",
 +
  "fbd",
 +
  "ge",
 +
  };
 +
 +
/*******************************************************************************
 +
  *
 +
  *    +--+
 +
  *  /    \
 +
  *  +  a---b
 +
  *  |  |  |
 +
  *  +  c---d
 +
  *  \ |  |
 +
  *    e---f  g
 +
  *
 +
  */
 +
char *G6[] =
 +
  {
 +
  "bade",
 +
  "cade",
 +
  "dbcf",
 +
  "ebcf",
 +
  "abc",
 +
  "fbd",
 +
  "g",
 +
  };
 +
 +
static graph *
 +
init_graph (char **in, size_t nr_vertices)
 +
  {
 +
  graph *g = malloc (sizeof *g + nr_vertices * sizeof *g->vertices);
 +
 +
  assert (g != NULL);
 +
 +
  g->nr_vertices = nr_vertices;
 +
 +
  size_t indices[UCHAR_MAX + 1] = { 0 };
 +
 +
  for (size_t i = 0; i < nr_vertices; ++i)
 +
    {
 +
    g->vertices[i] = malloc (sizeof *g->vertices[i]
 +
                            + sizeof *g->vertices[i]->edges * in[i][0]);
 +
 +
    assert (g->vertices[i] != NULL);
 +
 +
    g->vertices[i]->index    = i;
 +
    g->vertices[i]->nr_edges = strlen (in[i]) - 1;
 +
 +
    g->nr_edges += g->vertices[i]->nr_edges;
 +
 +
    indices[(unsigned char) in[i][0]] = i;
 +
    }
 +
 +
  for (size_t i = 0; i < nr_vertices; ++i)
 +
    for (size_t j = 0; j < g->vertices[i]->nr_edges; ++j)
 +
      g->vertices[i]->edges[j] = indices[(unsigned char) in[i][j + 1]];
 +
 +
  return g;
 +
  }
 +
 +
int main (void)
 +
  {
 +
  graph *g1 = init_graph (G1, sizeof G1 / sizeof G1[0]);
 +
  graph *g2 = init_graph (G2, sizeof G2 / sizeof G2[0]);
 +
  graph *g3 = init_graph (G3, sizeof G3 / sizeof G3[0]);
 +
  graph *g4 = init_graph (G4, sizeof G4 / sizeof G4[0]);
 +
  graph *g5 = init_graph (G5, sizeof G5 / sizeof G5[0]);
 +
  graph *g6 = init_graph (G6, sizeof G6 / sizeof G6[0]);
 +
 +
  compare_graphs (g1, g2);
 +
  compare_graphs (g1, g3);
 +
  compare_graphs (g1, g4);
 +
  compare_graphs (g1, g5);
 +
  compare_graphs (g1, g6);
 +
 +
  exit (EXIT_SUCCESS);
 +
  }

Latest revision as of 17:18, 18 December 2016

Algorithm

Given two graphs G1 and G2:

  • compare the nos. of vertices in G1 and G2 for equality;
  • compare the nos. of edges in G1 and G2 for equality;
  • sort the vertices of G1 and G2 by degree and compare the degrees of each pair of vertices from G1 and G2 for equality;
  • use back-tracking to generate a mapping of vertices: for each vertex, v1, in G1 pick a vertex, v2, from G2 of the same degree and check that if v2 is adjacent to any vertices that have already been mapped they have been mapped to vertices adjacent to v1; if all vertices can be successfully mapped, G1 and G2 are isomorphic.

Implementation in C with Examples

Each of the example graphs below is specified as a list of strings where each string comprises the label of a vertex followed by the labels of vertices adjacent to it. The strings are sorted by decreasing length, which is to say that the vertices are sorted by decreasing degree.

We compare the first graph, G1, to the remaining five, G2 - G6. G2 is isomorphic to G1; the others are not.

Expected output: 

 isomorphic: 1
 g1[2] -> g2[0]
 g1[1] -> g2[1]
 g1[0] -> g2[2]
 g1[3] -> g2[3]
 g1[5] -> g2[4]
 g1[4] -> g2[5]
 g1[6] -> g2[6]
 isomorphic: 0
 isomorphic: 0
 isomorphic: 0
 isomorphic: 0

Code: 

#include <assert.h>
#include <limits.h>
#include <stdint.h>
#include <stdio.h>
#include <stdlib.h>
#include <string.h>

typedef struct vertex_
  {
  size_t index;    /* Index of the vertex in the graph */
  size_t nr_edges; /* No. of edges incident on this vertex */
  size_t edges[];  /* Array of indices of vertices adjacent to this vertex */
  }
vertex;

typedef struct graph_
  {
  size_t  nr_vertices;  /* No. of vertices in this graph */
  size_t  nr_edges;     /* No. of edges in this graph */
  vertex *vertices[];   /* Array of vertices in this graph */
  }
graph;

static int
map_vertices (const graph *g1, const graph *g2, size_t *mappings, size_t i)
  {
  if (i == g2->nr_vertices)
    return 1;

  const vertex *v1 = g1->vertices[i];

  /*
   * Given a vertex, v1, in g1, find a vertex, v2, in g2 which has the same
   * degree and has not already been mapped to a previous vertex in g1.
   */
  for (size_t j = 0; j < g2->nr_vertices; ++j)
    {
    const vertex *v2 = g2->vertices[j];

    if (v1->nr_edges == v2->nr_edges && mappings[v2->index] == SIZE_MAX)
      {
      /*
       * Ensure that if a vertex, u2, adjacent to v2, has already been mapped,
       * it is mapped to a vertex, u1, adjacent to v1.
       */
      int mapped = 1;

      for (size_t l = 0; mapped && l < v2->nr_edges; ++l)
        {
        const vertex *u2 = g2->vertices[v2->edges[l]];

        if (mappings[u2->index] != SIZE_MAX)
          {
          int found = 0;

          for (size_t k = 0; !found && k < v1->nr_edges; ++k)
            {
            const vertex *u1 = g1->vertices[v1->edges[k]];

            if (mappings[u2->index] == u1->index)
              found = 1;
            }

          if (!found)
            mapped = 0;
          }
        }

      if (mapped)
        {
        mappings[v2->index] = v1->index;
        if (map_vertices (g1, g2, mappings, i + 1))
          return 1;
        else
          mappings[v2->index] = SIZE_MAX;
        }
      }
    }

  return 0;
  }

static void
compare_graphs (graph *g1, graph *g2)
  {
  size_t *mappings = malloc (g1->nr_vertices * sizeof *mappings);
  assert (mappings != NULL);
  for (size_t i = 0; i < g1->nr_vertices; ++i)
    mappings[i] = SIZE_MAX;

  int isomorphic;

  if (g1->nr_vertices != g2->nr_vertices)
    isomorphic = 0;
  else if (g1->nr_edges != g2->nr_edges)
    isomorphic = 0;
  else
    {
    isomorphic = 1;
    for (size_t i = 0; isomorphic && i < g1->nr_vertices; i++)
      isomorphic = g1->vertices[i]->nr_edges == g2->vertices[i]->nr_edges;

    if (isomorphic)
      isomorphic = map_vertices (g1, g2, mappings, 0);
    }

  fprintf (stderr, "isomorphic: %d\n", isomorphic);

  if (isomorphic)
    for (size_t i = 0; i < g2->nr_vertices; ++i)
      fprintf (stderr, "g1[%zu] -> g2[%zu]\n", mappings[i], i);

  free (mappings);
  }

/*******************************************************************************
 *
 *    a---b
 *  / |   |
 * +  c---d
 *  \ |   |
 *    e---f   g
 *
 */
char *G1[] =
  {
  "abce",
  "cade",
  "dbcf",
  "eacf",
  "bad",
  "fde",
  "g",
  };

/*******************************************************************************
 *
 *     a---b
 *     |   | \
 *     c---d  +
 *     |   | /
 * g   e---f
 *
 */
char *G2[] =
  {
  "cade",
  "dbcf",
  "fbde",
  "badf",
  "abc",
  "ecf",
  "g",
  };

/*******************************************************************************
 *
 *    +--+
 *   /    \
 *  +  a---b
 *  |  |   |
 *  +  c---d
 *   \ |   |
 *     e---f
 *
 */
char *G3[] =
  {
  "bade",
  "cade",
  "dbcf",
  "ebcf",
  "abc",
  "fbd",
  };

/*******************************************************************************
 *
 *    +--+
 *   /    \
 *  +  a---b
 *  |  |   |
 *  +  c---d
 *   \ |   |
 *     e---f---g
 *
 */
char *G4[] =
  {
  "bade",
  "cade",
  "dbcf",
  "ebcf",
  "fbdg",
  "abc",
  "gf",
  };

/*******************************************************************************
 *
 *     a---b
 *     |   |
 *     c---d
 *     |   |
 * g---e---f
 *
 */
char *G5[] =
  {
  "cade",
  "dbcf",
  "ecfg",
  "abc",
  "bad",
  "fbd",
  "ge",
  };

/*******************************************************************************
 *
 *    +--+
 *   /    \
 *  +  a---b
 *  |  |   |
 *  +  c---d
 *   \ |   |
 *     e---f   g
 *
 */
char *G6[] =
  {
  "bade",
  "cade",
  "dbcf",
  "ebcf",
  "abc",
  "fbd",
  "g",
  };

static graph *
init_graph (char **in, size_t nr_vertices)
  {
  graph *g = malloc (sizeof *g + nr_vertices * sizeof *g->vertices);

  assert (g != NULL);

  g->nr_vertices = nr_vertices;

  size_t indices[UCHAR_MAX + 1] = { 0 };

  for (size_t i = 0; i < nr_vertices; ++i)
    {
    g->vertices[i] = malloc (sizeof *g->vertices[i]
                           + sizeof *g->vertices[i]->edges * in[i][0]);

    assert (g->vertices[i] != NULL);

    g->vertices[i]->index    = i;
    g->vertices[i]->nr_edges = strlen (in[i]) - 1;

    g->nr_edges += g->vertices[i]->nr_edges;

    indices[(unsigned char) in[i][0]] = i;
    }

  for (size_t i = 0; i < nr_vertices; ++i)
    for (size_t j = 0; j < g->vertices[i]->nr_edges; ++j)
      g->vertices[i]->edges[j] = indices[(unsigned char) in[i][j + 1]];

  return g;
  }

int main (void)
  {
  graph *g1 = init_graph (G1, sizeof G1 / sizeof G1[0]);
  graph *g2 = init_graph (G2, sizeof G2 / sizeof G2[0]);
  graph *g3 = init_graph (G3, sizeof G3 / sizeof G3[0]);
  graph *g4 = init_graph (G4, sizeof G4 / sizeof G4[0]);
  graph *g5 = init_graph (G5, sizeof G5 / sizeof G5[0]);
  graph *g6 = init_graph (G6, sizeof G6 / sizeof G6[0]);

  compare_graphs (g1, g2);
  compare_graphs (g1, g3);
  compare_graphs (g1, g4);
  compare_graphs (g1, g5);
  compare_graphs (g1, g6);

  exit (EXIT_SUCCESS);
  }
Retrieved from "https://algorist.com/algowiki_v2/index.php?title=TADM2E_7.3&oldid=472"