require(igraph)

getWeight = function(A, B, graphA, graphB) {
  sim <- graph.intersection(graphA, graphB)
  adj <- get.adjacency(sim, type="both")
  return (adj[A,B]);
}

getSimilarity <- function(graphA, graphB) {
  # Create a new graph, where each node represents a possible pairing of:
  #         --a node from graph A    (x)
  #         --to a node from graph B (y)
  ig <- graph(n=0, edges=NULL, directed=FALSE)
  thresh <- 0.2
  for (i in 1:length(V(graphA))){
    for (j in 1:length(V(graphB))) {
      # If two nodes (x,y) are dissimilar (use association indices), remove the node in the new graph.
      # If similar, give node in new graph weight between [0,1]
      w <- getWeight(V(graphA)[i], V(graphB)[j], graphA, graphB)
      if (w>thresh) {
        ig <- add.vertices(ig, 1, name=sprintf("A:%s<->B:%s", V(graphA)[i], V(graphB)[j]), weight=w)
      }
    }
  }
  # Connect nodes in new graph if they do not contradict each other. (x,y) and (x,t) contradict each other
  first <- list()
  second <- list()
  for (i in 1:length(V(ig)$name)) {
    item <- strsplit(V(ig)$name[i], '<->')
    first[i] <- item[1]
    second[i] <- item[2]
  }
  for (i in 1:length(first)) {
    for (j in 1:length(second)) {
      if (??INSERT CONTRADICTION CHECK HERE!!) {
        ig <- add.edges(ig, c(first, second))
      }
    }
  }

  # Find a clique in the new graph which has the maximum amount of nodes, or
  # The clique which has the maximum node weights (sum)
  cliq.ig <- maximal.cliques(ig)
  maxNodes <- max(sapply(cliq.ig, length);

  # Similarity between graphs A and B final calculation
  #         = size of maximum clique OR total weight of maximum clique
  #           DIVIDED BY
  #           average clique sizes of A and B OR average weights of A and B
  mnCliqSize <- 0
  for (i in 1:length(cliquesA)) {
    mnCliqSize <- mnCliqSize + length(cliquesA[[i]])
  }
  for (i in 1:length(cliquesB)) {
    mnCliqSize <- mnCliqSize + length(cliquesB[[i]])
  }
  mnCliqSize <- mnCliqSize / (length(cliquesA)+length(cliquesB))
  return (maxNodes/mnCliqSize);
}

ig <- graph(n=0, edges=NULL, directed=FALSE)
ig <- add.vertices(ig, 10, name=sprintf("%d", 1:10))
ig <- add.edges(ig, c(1,3, 3,5, 5,7, 7,9, 2,4, 4,6, 6,8, 8,10))
ig2 <- graph(n=0, edges=NULL, directed=FALSE)
ig2 <- add.vertices(ig2, 2, name=sprintf("%d", seq(1,3,2)))
ig2 <- add.edges(ig2, c(1,2))
test <- getSimilarity(ig, ig2)