Graph comparison

.block

license: mit

README.md

A simple method for comparing small, similar graphs. Two linked views are presented, showing differences as "phantom" nodes and links. The views share the same layout, ensuring comparability.

forked from nitaku's block: Graph comparison

index.coffee

graph = {
  nodes: [
    {id: 'A', graphs:['I','II']},
    {id: 'B', graphs:['II']},
    {id: 'C', graphs:['I','II']},
    {id: 'D', graphs:['I']},
    {id: 'E', graphs:['II']},
    {id: 'F', graphs:['I','II']},
    {id: 'G', graphs:['I','II']},
    {id: 'H', graphs:['I','II']},
    {id: 'I', graphs:['I','II']},
    {id: 'J', graphs:['I']}
  ],
  links: [
    {id:  1, source: 'A', target: 'B', graphs:['II']},
    {id:  2, source: 'A', target: 'C', graphs:['I','II']},
    {id:  3, source: 'A', target: 'D', graphs:['I']},
    {id:  4, source: 'B', target: 'E', graphs:['II']},
    {id:  5, source: 'B', target: 'F', graphs:['II']},
    {id:  6, source: 'C', target: 'G', graphs:['I','II']},
    {id:  7, source: 'C', target: 'F', graphs:['I','II']},
    {id:  8, source: 'F', target: 'G', graphs:['I','II']},
    {id:  9, source: 'G', target: 'H', graphs:['I','II']},
    {id: 10, source: 'G', target: 'I', graphs:['I','II']},
    {id: 11, source: 'H', target: 'I', graphs:['I','II']},
    {id: 12, source: 'I', target: 'J', graphs:['I']}
  ]}


### objectify the graph ###
### resolve node IDs (not optimized at all!) ###
for l in graph.links
  for n in graph.nodes
    if l.source is n.id
      l.source = n

    if l.target is n.id
      l.target = n
  
R = 18

svg = d3.select('svg')
width = svg.node().getBoundingClientRect().width
height = svg.node().getBoundingClientRect().height

defs = svg.append('defs')

### define arrow markers for graph links ###
defs.append('marker')
  .attr
    id: 'end-arrow'
    viewBox: '0 0 10 10'
    refX: 4+R
    refY: 5
    orient: 'auto'
.append('path')
  .attr
    d: 'M0,0 L0,10 L10,5 z'
    
defs.append('marker')
  .attr
    id: 'phantom-end-arrow'
    viewBox: '0 0 10 10'
    refX: 4+R
    refY: 5
    orient: 'auto'
.append('path')
  .attr
    d: 'M0,0 L0,10 L10,5 z'

### create views ###
defs.append('clipPath')
  .attr
    id: 'square_window'
.append('rect')
  .attr
    x: 0
    y: 0
    width: width/2
    height: height
    
views_data = ['I','II']
views = svg.selectAll('.view')
  .data(views_data)
  
enter_views = views.enter().append('g')
  .attr
    class: 'view'
    'clip-path': 'url(#square_window)'
    transform: (d) -> if d is 'II' then "translate(#{width/2},0)" else 'translate(0,0)'
      
svg.append('line')
  .attr
    class: 'separator'
    x1: width/2
    y1: 0
    x2: width/2
    y2: height
    
### create phantom nodes and links ###
phantom_links_layer = enter_views.append('g')
phantom_links = phantom_links_layer.selectAll('.link')
  .data(((v) -> graph.links.filter((l) -> v not in l.graphs)), (d) -> d.id)
  
phantom_links
  .enter().append('line')
    .attr('class', 'phantom link')


phantom_nodes_layer = enter_views.append('g')
phantom_nodes = phantom_nodes_layer.selectAll('.node')
  .data(((v) -> graph.nodes.filter((n) -> v not in n.graphs)), (d) -> d.id)
        
enter_phantom_nodes = phantom_nodes.enter().append('g')
  .attr('class', 'phantom node')

enter_phantom_nodes.append('circle')
  .attr('r', R)
  
### create nodes and links ###
links_layer = enter_views.append('g')
links = links_layer.selectAll('.link')
  .data(((v) -> graph.links.filter((l) -> v in l.graphs)), (d) -> d.id)
  
links
  .enter().append('line')
    .attr('class', 'link')

nodes_layer = enter_views.append('g')
nodes = nodes_layer.selectAll('.node')
  .data(((v) -> graph.nodes.filter((n) -> v in n.graphs)), (d) -> d.id)
        
enter_nodes = nodes.enter().append('g')
  .attr('class', 'node')

enter_nodes.append('circle')
  .attr('r', R)

### draw the label ###
enter_nodes.append('text')
  .text((d) -> d.id)
  .attr('dy', '0.35em')
  
### cola layout ###
graph.nodes.forEach (v) ->
  v.width = 2.5*R
  v.height = 2.5*R

d3cola = cola.d3adaptor()
  .size([width/2, height])
  .linkDistance(70)
  .avoidOverlaps(true)
  .nodes(graph.nodes)
  .links(graph.links)
  .on 'tick', () ->
    ### update nodes and links  ###
    views.selectAll('.node')
      .attr('transform', (d) -> "translate(#{d.x},#{d.y})")

    views.selectAll('.link')
      .attr('x1', (d) -> d.source.x)
      .attr('y1', (d) -> d.source.y)
      .attr('x2', (d) -> d.target.x)
      .attr('y2', (d) -> d.target.y)
      
enter_nodes
  .call(d3cola.drag)

enter_phantom_nodes
  .call(d3cola.drag)
  
d3cola.start(30,30,30)

index.css

.node > circle {
  fill: #DDD;
  stroke: #777;
  stroke-width: 2px;
}

.node > text {
  font-family: sans-serif;
  text-anchor: middle;
  pointer-events: none;
  user-select: none;
  -webkit-user-select: none;
}

.link {
  stroke: #88A;
  stroke-width: 4px;  
  marker-end: url(#end-arrow);
}
#end-arrow {
  fill: #88A;
}

.separator {
  stroke: #dfd7c4;
  shape-rendering: crispEdges;
}

.phantom.node > circle {
  fill: #EEE;
  stroke: #EEE;
}

.phantom.link {
  stroke: #EEE;
  marker-end: url(#phantom-end-arrow);
}
#phantom-end-arrow {
  fill: #EEE;
}

index.html

<!doctype html>
<html lang="en">
  <head>
    <meta charset="utf-8">
    <title>Graph comparison</title>
    <link rel="stylesheet" href="index.css">
    <script src="http://d3js.org/d3.v3.min.js"></script>
    <script src="http://marvl.infotech.monash.edu/webcola/cola.v3.min.js"></script>
  </head>
  <body>
    <svg width="960px" height="500px"></svg>
    <script src="index.js"></script>
  </body>
</html>

index.js

// Generated by CoffeeScript 1.4.0
(function() {
  var R, d3cola, defs, enter_nodes, enter_phantom_nodes, enter_views, graph, height, l, links, links_layer, n, nodes, nodes_layer, phantom_links, phantom_links_layer, phantom_nodes, phantom_nodes_layer, svg, views, views_data, width, _i, _j, _len, _len1, _ref, _ref1,
    __indexOf = [].indexOf || function(item) { for (var i = 0, l = this.length; i < l; i++) { if (i in this && this[i] === item) return i; } return -1; };

  graph = {
    nodes: [
      {
        id: 'A',
        graphs: ['I', 'II']
      }, {
        id: 'B',
        graphs: ['II']
      }, {
        id: 'C',
        graphs: ['I', 'II']
      }, {
        id: 'D',
        graphs: ['I']
      }, {
        id: 'E',
        graphs: ['II']
      }, {
        id: 'F',
        graphs: ['I', 'II']
      }, {
        id: 'G',
        graphs: ['I', 'II']
      }, {
        id: 'H',
        graphs: ['I', 'II']
      }, {
        id: 'I',
        graphs: ['I', 'II']
      }, {
        id: 'J',
        graphs: ['I']
      }
    ],
    links: [
      {
        id: 1,
        source: 'A',
        target: 'B',
        graphs: ['II']
      }, {
        id: 2,
        source: 'A',
        target: 'C',
        graphs: ['I', 'II']
      }, {
        id: 3,
        source: 'A',
        target: 'D',
        graphs: ['I']
      }, {
        id: 4,
        source: 'B',
        target: 'E',
        graphs: ['II']
      }, {
        id: 5,
        source: 'B',
        target: 'F',
        graphs: ['II']
      }, {
        id: 6,
        source: 'C',
        target: 'G',
        graphs: ['I', 'II']
      }, {
        id: 7,
        source: 'C',
        target: 'F',
        graphs: ['I', 'II']
      }, {
        id: 8,
        source: 'F',
        target: 'G',
        graphs: ['I', 'II']
      }, {
        id: 9,
        source: 'G',
        target: 'H',
        graphs: ['I', 'II']
      }, {
        id: 10,
        source: 'G',
        target: 'I',
        graphs: ['I', 'II']
      }, {
        id: 11,
        source: 'H',
        target: 'I',
        graphs: ['I', 'II']
      }, {
        id: 12,
        source: 'I',
        target: 'J',
        graphs: ['I']
      }
    ]
  };

  /* objectify the graph
  */


  /* resolve node IDs (not optimized at all!)
  */


  _ref = graph.links;
  for (_i = 0, _len = _ref.length; _i < _len; _i++) {
    l = _ref[_i];
    _ref1 = graph.nodes;
    for (_j = 0, _len1 = _ref1.length; _j < _len1; _j++) {
      n = _ref1[_j];
      if (l.source === n.id) {
        l.source = n;
      }
      if (l.target === n.id) {
        l.target = n;
      }
    }
  }

  R = 18;

  svg = d3.select('svg');

  width = svg.node().getBoundingClientRect().width;

  height = svg.node().getBoundingClientRect().height;

  defs = svg.append('defs');

  /* define arrow markers for graph links
  */


  defs.append('marker').attr({
    id: 'end-arrow',
    viewBox: '0 0 10 10',
    refX: 4 + R,
    refY: 5,
    orient: 'auto'
  }).append('path').attr({
    d: 'M0,0 L0,10 L10,5 z'
  });

  defs.append('marker').attr({
    id: 'phantom-end-arrow',
    viewBox: '0 0 10 10',
    refX: 4 + R,
    refY: 5,
    orient: 'auto'
  }).append('path').attr({
    d: 'M0,0 L0,10 L10,5 z'
  });

  /* create views
  */


  defs.append('clipPath').attr({
    id: 'square_window'
  }).append('rect').attr({
    x: 0,
    y: 0,
    width: width / 2,
    height: height
  });

  views_data = ['I', 'II'];

  views = svg.selectAll('.view').data(views_data);

  enter_views = views.enter().append('g').attr({
    "class": 'view',
    'clip-path': 'url(#square_window)',
    transform: function(d) {
      if (d === 'II') {
        return "translate(" + (width / 2) + ",0)";
      } else {
        return 'translate(0,0)';
      }
    }
  });

  svg.append('line').attr({
    "class": 'separator',
    x1: width / 2,
    y1: 0,
    x2: width / 2,
    y2: height
  });

  /* create phantom nodes and links
  */


  phantom_links_layer = enter_views.append('g');

  phantom_links = phantom_links_layer.selectAll('.link').data((function(v) {
    return graph.links.filter(function(l) {
      return __indexOf.call(l.graphs, v) < 0;
    });
  }), function(d) {
    return d.id;
  });

  phantom_links.enter().append('line').attr('class', 'phantom link');

  phantom_nodes_layer = enter_views.append('g');

  phantom_nodes = phantom_nodes_layer.selectAll('.node').data((function(v) {
    return graph.nodes.filter(function(n) {
      return __indexOf.call(n.graphs, v) < 0;
    });
  }), function(d) {
    return d.id;
  });

  enter_phantom_nodes = phantom_nodes.enter().append('g').attr('class', 'phantom node');

  enter_phantom_nodes.append('circle').attr('r', R);

  /* create nodes and links
  */


  links_layer = enter_views.append('g');

  links = links_layer.selectAll('.link').data((function(v) {
    return graph.links.filter(function(l) {
      return __indexOf.call(l.graphs, v) >= 0;
    });
  }), function(d) {
    return d.id;
  });

  links.enter().append('line').attr('class', 'link');

  nodes_layer = enter_views.append('g');

  nodes = nodes_layer.selectAll('.node').data((function(v) {
    return graph.nodes.filter(function(n) {
      return __indexOf.call(n.graphs, v) >= 0;
    });
  }), function(d) {
    return d.id;
  });

  enter_nodes = nodes.enter().append('g').attr('class', 'node');

  enter_nodes.append('circle').attr('r', R);

  /* draw the label
  */


  enter_nodes.append('text').text(function(d) {
    return d.id;
  }).attr('dy', '0.35em');

  /* cola layout
  */


  graph.nodes.forEach(function(v) {
    v.width = 2.5 * R;
    return v.height = 2.5 * R;
  });

  d3cola = cola.d3adaptor().size([width / 2, height]).linkDistance(70).avoidOverlaps(true).nodes(graph.nodes).links(graph.links).on('tick', function() {
    /* update nodes and links
    */
    views.selectAll('.node').attr('transform', function(d) {
      return "translate(" + d.x + "," + d.y + ")";
    });
    return views.selectAll('.link').attr('x1', function(d) {
      return d.source.x;
    }).attr('y1', function(d) {
      return d.source.y;
    }).attr('x2', function(d) {
      return d.target.x;
    }).attr('y2', function(d) {
      return d.target.y;
    });
  });

  enter_nodes.call(d3cola.drag);

  enter_phantom_nodes.call(d3cola.drag);

  d3cola.start(30, 30, 30);

}).call(this);