1. Chris Mutel
  2. brightway2-analyzer

Commits

Chris Mutel  committed d52549f

Initial graph traversal manipulator. All basic functions are well-tested. However, we still need to add better defaults (number of processes instead of percentages?), and treemap needs to do LCA calculations for each leaf node, giving biosphere flows (plus variance), in addition to adding 'other' nodes (with their own LCA calculations?).

  • Participants
  • Parent commits 54fa90b
  • Branches default

Comments (0)

Files changed (5)

File bw2analyzer/__init__.py

View file
  • Ignore whitespace
 from .contribution import ContributionAnalysis
 from .page_rank import PageRank
 from .explorer import DatabaseExplorer
+from .sc_graph import GTManipulator
 from .report import SerializedLCAReport
 
-__version__ = (0, 3, 3)
+__version__ = (0, 4)

File bw2analyzer/report.py

View file
  • Ignore whitespace
 # -*- coding: utf-8 -*-
 from __future__ import division
-from . import ContributionAnalysis
+from . import ContributionAnalysis, GTManipulator
 from brightway2 import JsonWrapper, methods, config
-from bw2calc import ParallelMonteCarlo, LCA, node_pruner, GraphTraversal, \
-    edge_cutter, d3_fd_graph_formatter
+from bw2calc import ParallelMonteCarlo, LCA, GraphTraversal
 from scipy.stats import gaussian_kde
 import numpy as np
 import os
         """Get graph traversal results"""
         gt = GraphTraversal()
         traversal = gt.calculate(self.activity, self.method)
-        edges = edge_cutter(traversal["nodes"], traversal["edges"],
-            traversal["lca"].score, 0.01)
-        nodes = node_pruner(traversal["nodes"], edges)
-        return d3_fd_graph_formatter(nodes, edges, traversal["lca"].score)
+        nodes, edges = GTManipulator.simplify_naive(
+            traversal['nodes'],
+            traversal['edges'],
+            traversal['lca'].score
+        )
+        nodes = GTManipulator.add_metadata(nodes, traversal['lca'])
+        return GTManipulator.reformat_d3(nodes, edges, traversal['lca'].score)
 
     def write(self):
         """Write report data to file"""

File bw2analyzer/sc_graph.py

View file
  • Ignore whitespace
+import copy
+import itertools
+from heapq import heappush, heappop
+from bw2data import Database
+
+
+def tupify(o):
+    """Transform edge from dict to tuples. Multiply impact by -1 because sort by min, not max"""
+    return (-1 * o['impact'], o['from'], o['to'], o['amount'], o['exc_amount'])
+
+
+class GTManipulator(object):
+    """Manipulate ``GraphTraversal`` results."""
+    @staticmethod
+    def unroll_graph(nodes, edges, score, cutoff=0.005, max_links=2500):
+        """Unroll a ``GraphTraversal`` result, allowing the same activity to appear in the graph multiple times."""
+        input_nodes, input_edges = copy.deepcopy(nodes), copy.deepcopy(edges)
+        counter = itertools.count()
+        edges_dict = {}
+        heap, edges, links, cutoff_score = [], [], 0, cutoff * score
+        nodes = {-1: copy.deepcopy(input_nodes[-1])}
+
+        for edge in input_edges:
+            edges_dict.setdefault(edge['to'], []).append(edge)
+
+        for edge in edges_dict[-1]:
+            heappush(heap, tupify(edge))
+            links += 1
+
+        while heap and links < max_links:
+            score, from_, to, cum_amount, exc_amount = heappop(heap)
+
+            if (-1 * score) < cutoff_score:
+                continue
+
+            # ``from_`` is old-style indexing, ``to`` is new-style indexing
+            from_node = input_nodes[from_]
+            to_node = nodes[to]
+            new_amount = exc_amount * to_node['amount']
+
+            node_id = counter.next()
+            # Only node that doesn't have a ``row`` attribute is the
+            # functional unit, which by definition has no outgoing links
+            nodes[node_id] = {
+                'amount': new_amount,
+                'row': from_,
+                'cum': from_node['cum'] * new_amount / from_node['amount'],
+                'ind': from_node['ind']
+            }
+            edges.append({
+                'to': to,
+                'from': node_id,
+                'amount': new_amount,
+                'exc_amount': exc_amount,
+                'impact': nodes[node_id]['cum']
+            })
+
+            frommer = lambda x: x['from']
+            # Include all edges for now; ignore minor ones when popping heap
+            for edge in sorted(edges_dict.get(from_, []), key=frommer):
+                from_edge_node = input_nodes[from_]
+                heappush(heap, tupify({
+                   'amount': new_amount * edge['exc_amount'],
+                   'from': edge['from'],
+                   'to': node_id,
+                   'exc_amount': edge['exc_amount'],
+                   'impact': from_edge_node['cum'] / from_edge_node['amount'] \
+                        * new_amount * edge['exc_amount']
+                }))
+                links += 1
+        return nodes, edges, links
+
+    @staticmethod
+    def add_metadata(nodes, lca):
+        """Add metadata to nodes, like name, unit, and category."""
+        rt, rb = lca.reverse_dict()
+        new_nodes = {}
+        for key, value in nodes.iteritems():
+            new_value = copy.deepcopy(value)
+            if key == -1:
+                new_value.update({
+                    'name': "Functional unit",
+                    'unit': "unit",
+                    'categories': ["Functional unit"]
+                })
+            else:
+                if 'row' in value:
+                    index = value['row']
+                else:
+                    index = key
+                code = rt[index]
+                ds = Database(code[0]).load()[code]
+                new_value.update({
+                    'name': ds['name'],
+                    'categories': ds['categories'],
+                    'unit': ds['unit'],
+                    'key': code
+                })
+            new_nodes[key] = new_value
+        return new_nodes
+
+    @staticmethod
+    def d3_force_directed(nodes, edges, score):
+        """Reformat to D3 style, which is a list of nodes, and edge ids are node list indices."""
+        # Sort node ids by highest cumulative score first
+        node_ids = [x[1] for x in sorted(
+            [(v["cum"], k) for k, v in nodes.iteritems()])]
+        new_nodes = [nodes[i] for i in node_ids]
+        lookup = dict([(key, index) for index, key in enumerate(node_ids)])
+        new_edges = [{
+            "source": lookup[e["to"]],
+            "target": lookup[e["from"]],
+            "amount": e["impact"]
+        } for e in edges]
+        return {
+            "edges": new_edges,
+            "nodes": new_nodes,
+            "total": score
+        }
+
+    @staticmethod
+    def simplify(nodes, edges, score, limit=0.005):
+        """Simplify supply chain to include only nodes which individually contribute ``limit * score``.
+
+        Only removes and combines edges; doesn't check to make sure amounts add up correctly."""
+        if isinstance(limit, int) and limit > 1:
+            nodes_to_delete = sorted([
+                (value['amount'] * value['ind'], key)
+                for key, value in nodes.iteritems()
+                ], reverse=True)[limit:]
+        else:
+            nodes_to_delete = [
+                key for key, value in nodes.iteritems()
+                if key != -1
+                and (value['amount'] * value['ind']) < (score * limit)
+            ]
+        edges_dict = {(edge['to'], edge['from']): edge
+            for edge in copy.deepcopy(edges)}
+        for node in nodes_to_delete:
+            p_edges = [key for key in edges_dict if key[1] == node]
+            c_edges = [key for key in edges_dict if key[0] == node]
+            total_amount = sum([edges_dict[k]['amount'] for k in p_edges])
+            total_impact = sum([edges_dict[k]['impact'] for k in p_edges])
+            for p_key, c_key in itertools.product(
+                    p_edges, c_edges):
+                key = (p_key[0], c_key[1])
+                if p_key[0] == c_key[1]:
+                    continue
+                p_edge = edges_dict[p_key]
+                c_edge = edges_dict[c_key]
+                e_amount = c_edge['amount'] * p_edge['amount'] / total_amount
+                e_impact = c_edge['impact'] * p_edge['impact'] / total_impact
+                e_eamount = p_edge['exc_amount'] * c_edge['exc_amount']
+                if key in edges_dict:
+                    edges_dict[key]['amount'] += e_amount
+                    edges_dict[key]['exc_amount'] += e_eamount
+                    edges_dict[key]['impact'] += e_impact
+                else:
+                    edges_dict[key] = {
+                        'to': p_edge['to'],
+                        'from': c_edge['from'],
+                        'amount': e_amount,
+                        'exc_amount': e_eamount,
+                        'impact': e_impact
+                    }
+            # Remove obsolete edges
+            for key in p_edges:
+                del edges_dict[key]
+            for key in c_edges:
+                del edges_dict[key]
+        nodes = {key: value for key, value in nodes.iteritems()
+            if key not in set(nodes_to_delete)}
+        return nodes, edges_dict.values()
+
+    @staticmethod
+    def simplify_naive(nodes, edges, score, limit=0.0025):
+        """Naive simplification which simplifies removes links below an LCA score cutoff. Orphan nodes are also deleted."""
+        edges = [e for e in edges if e["impact"] >= (score * limit)]
+        good_nodes = set([e["from"] for e in edges]).union(
+            set([e["to"] for e in edges]))
+        nodes = dict([(k, v) for k, v in nodes.iteritems() if k in good_nodes])
+        return nodes, edges
+
+    @staticmethod
+    def d3_treemap(nodes, edges, lca, add_biosphere=False):
+        """Add node data by traversing the graph; assign different metadata to leaf nodes."""
+        rt, rb = lca.reverse_dict()
+
+        child_nodes = lambda node, edges: [e['from'] for e in edges if e['to'] == node]
+
+        def format_node(node_key, node_data, rt):
+            if node_key == -1:
+                return {
+                    'name': 'Functional unit',
+                    'unit': 'unit',
+                    'location': 'GLO',
+                    'categories': "",
+                    'id': node_key,
+                    'amount': 1.
+                }
+
+            if 'row' in node_data:
+                node_key = node_data['row']
+            key = rt[node_key]
+            ds = Database(key[0]).load()[key]
+            return {
+                'name': ds['name'],
+                'unit': ds['unit'],
+                'location': ds['location'],
+                'categories': ", ".join(ds['categories']),
+                'id': node_key,
+                'amount': node_data['amount']
+            }
+
+        def format_child_node(node_key, node_data, rt, add_biosphere):
+            ds = format_node(node_key, node_data, rt)
+            ds['size'] = node_data['cum']
+            ds['variance'] = 0.5
+            return ds
+
+        def process_node(node):
+            cn = child_nodes(node, edges)
+            if cn:
+                ds = format_node(node, nodes[node], rt)
+                ds['children'] = [process_node(o) for o in cn]
+                return ds
+            else:
+                return format_child_node(node, nodes[node], rt, False)
+
+        return process_node(-1)

File bw2analyzer/tests/__init__.py

View file
  • Ignore whitespace
 from .econ import EconometricsTestCase
-from .utils import GroupingTest
+# from .utils import GroupingTest
+from .sc_graph import UnrollGraphTestCase, MetadataTestCase, SimplifyTestCase

File bw2analyzer/tests/sc_graph.py

View file
  • Ignore whitespace
+from __future__ import division
+from ..sc_graph import GTManipulator
+from bw2data import databases, Database
+from bw2data.tests import BW2DataTest
+import unittest
+import copy
+
+
+class UnrollGraphTestCase(unittest.TestCase):
+    def test_simple_chain(self):
+        nodes = {
+            -1: {'amount': 1, 'cum': 1, 'ind': 0},
+            10: {'amount': 1, 'cum': 1, 'ind': 1},
+            11: {'amount': 0.5, 'cum': 0.5, 'ind': 1},
+            12: {'amount': 0.1, 'cum': 0.1, 'ind': 1},
+        }
+        edges = [
+            {'to': -1, 'from': 10, 'amount': 1, 'exc_amount': 1, 'impact': 1},
+            {'to': 10, 'from': 11, 'amount': 0.5, 'exc_amount': 0.5, 'impact': 0.5},
+            {'to': 11, 'from': 12, 'amount': 0.1, 'exc_amount': 0.2, 'impact': 0.1}
+        ]
+        nodes, edges, count = GTManipulator.unroll_graph(nodes, edges, 1)
+        ref_nodes = {
+            -1: {'ind': 0, 'amount': 1, 'cum': 1},
+            0: {'ind': 1, 'amount': 1, 'cum': 1, 'row': 10},
+            1: {'ind': 1, 'amount': 0.5, 'cum': 0.5, 'row': 11},
+            2: {'ind': 1, 'amount': 0.1, 'cum': 0.10000000000000002, 'row': 12}
+        }
+        ref_edges = [
+            {'impact': 1, 'to': -1, 'amount': 1, 'exc_amount': 1, 'from': 0},
+            {'impact': 0.5, 'to': 0, 'amount': 0.5, 'exc_amount': 0.5, 'from': 1},
+            {'impact': 0.10000000000000002, 'to': 1, 'amount': 0.1, 'exc_amount': 0.2, 'from': 2}
+        ]
+        self.assertEqual(count, 3)
+        self.assertEqual(nodes, ref_nodes)
+        self.assertEqual(edges, ref_edges)
+
+    def test_multiple_inputs(self):
+        nodes = {
+            -1: {'amount': 1, 'cum': 1, 'ind': 0},
+            10: {'amount': 1, 'cum': 1, 'ind': 1},
+            11: {'amount': 0.5, 'cum': 0.5, 'ind': 1},
+            12: {'amount': 0.5, 'cum': 0.5, 'ind': 1},
+        }
+        edges = [
+            {'to': -1, 'from': 10, 'amount': 1, 'exc_amount': 1, 'impact': 1},
+            {'to': 10, 'from': 11, 'amount': 0.5, 'exc_amount': 0.5, 'impact': 0.5},
+            {'to': 10, 'from': 12, 'amount': 0.5, 'exc_amount': 0.5, 'impact': 0.5}
+        ]
+        nodes, edges, count = GTManipulator.unroll_graph(nodes, edges, 1)
+        ref_nodes = {
+            -1: {'ind': 0, 'amount': 1, 'cum': 1},
+            0: {'ind': 1, 'amount': 1, 'cum': 1, 'row': 10},
+            1: {'ind': 1, 'amount': 0.5, 'cum': 0.5, 'row': 11},
+            2: {'ind': 1, 'amount': 0.5, 'cum': 0.5, 'row': 12}
+        }
+        ref_edges = [
+            {'impact': 1, 'to': -1, 'amount': 1, 'exc_amount': 1, 'from': 0},
+            {'impact': 0.5, 'to': 0, 'amount': 0.5, 'exc_amount': 0.5, 'from': 1},
+            {'impact': 0.5, 'to': 0, 'amount': 0.5, 'exc_amount': 0.5, 'from': 2}
+        ]
+        self.assertEqual(count, 3)
+        self.assertEqual(nodes, ref_nodes)
+        self.assertEqual(edges, ref_edges)
+
+    def test_pruning(self):
+        nodes = {
+            -1: {'amount': 1, 'cum': 1, 'ind': 0},
+            10: {'amount': 1, 'cum': 1, 'ind': 1},
+            11: {'amount': 0.5, 'cum': 0.5, 'ind': 1},
+            12: {'amount': 0.001, 'cum': 0.001, 'ind': 1},
+        }
+        edges = [
+            {'to': -1, 'from': 10, 'amount': 1, 'exc_amount': 1, 'impact': 1},
+            {'to': 10, 'from': 11, 'amount': 0.5, 'exc_amount': 0.5, 'impact': 0.5},
+            {'to': 10, 'from': 12, 'amount': 0.001, 'exc_amount': 0.002, 'impact': 0.001}
+        ]
+        nodes, edges, count = GTManipulator.unroll_graph(nodes, edges, 1)
+        ref_nodes = {
+            -1: {'ind': 0, 'amount': 1, 'cum': 1},
+            0: {'ind': 1, 'amount': 1, 'cum': 1, 'row': 10},
+            1: {'ind': 1, 'amount': 0.5, 'cum': 0.5, 'row': 11},
+        }
+        ref_edges = [
+            {'impact': 1, 'to': -1, 'amount': 1, 'exc_amount': 1, 'from': 0},
+            {'impact': 0.5, 'to': 0, 'amount': 0.5, 'exc_amount': 0.5, 'from': 1},
+        ]
+        self.assertEqual(count, 3)
+        self.assertEqual(nodes, ref_nodes)
+        self.assertEqual(edges, ref_edges)
+
+    def test_unroll_circular(self):
+        nodes = {
+            -1: {'amount': 1, 'cum': 1, 'ind': 0},
+            10: {'amount': 1, 'cum': 1, 'ind': 1},
+            11: {'amount': 1, 'cum': 1, 'ind': 1}
+        }
+        edges = [
+            {'to': -1, 'from': 10, 'amount': 1, 'exc_amount': 1, 'impact': 1},
+            {'to': 10, 'from': 11, 'amount': 1, 'exc_amount': 0.8, 'impact': 1},
+            {'to': 11, 'from': 10, 'amount': 1, 'exc_amount': 0.8, 'impact': 1}
+        ]
+        nodes, edges, count = GTManipulator.unroll_graph(nodes, edges, 1, cutoff=0.4)
+        ref_nodes = {
+            -1: {'ind': 0, 'amount': 1, 'cum': 1},
+            0: {'ind': 1, 'amount': 1, 'cum': 1, 'row': 10},
+            1: {'ind': 1, 'amount': 0.8, 'cum': 0.8, 'row': 11},
+            2: {'ind': 1, 'amount': 0.6400000000000001, 'cum': 0.6400000000000001, 'row': 10},
+            3: {'ind': 1, 'amount': 0.5120000000000001, 'cum': 0.5120000000000001, 'row': 11},
+            4: {'ind': 1, 'amount': 0.40960000000000013, 'cum': 0.40960000000000013, 'row': 10}
+        }
+        ref_edges = [
+            {'impact': 1, 'to': -1, 'amount': 1, 'exc_amount': 1, 'from': 0},
+            {'impact': 0.8, 'to': 0, 'amount': 0.8, 'exc_amount': 0.8, 'from': 1},
+            {'impact': 0.6400000000000001, 'to': 1, 'amount': 0.6400000000000001, 'exc_amount': 0.8, 'from': 2},
+            {'impact': 0.5120000000000001, 'to': 2, 'amount': 0.5120000000000001, 'exc_amount': 0.8, 'from': 3},
+            {'impact': 0.40960000000000013, 'to': 3, 'amount': 0.40960000000000013, 'exc_amount': 0.8, 'from': 4}
+        ]
+        self.assertEqual(count, 6)
+        self.assertEqual(nodes, ref_nodes)
+        self.assertEqual(edges, ref_edges)
+
+    def test_max_links(self):
+        nodes = {
+            -1: {'amount': 1, 'cum': 1, 'ind': 0},
+            10: {'amount': 1, 'cum': 1, 'ind': 1},
+            11: {'amount': 1, 'cum': 1, 'ind': 1}
+        }
+        edges = [
+            {'to': -1, 'from': 10, 'amount': 1, 'exc_amount': 1, 'impact': 1},
+            {'to': 10, 'from': 11, 'amount': 1, 'exc_amount': 0.999, 'impact': 1},
+            {'to': 11, 'from': 10, 'amount': 1, 'exc_amount': 0.999, 'impact': 1}
+        ]
+        nodes, edges, count = GTManipulator.unroll_graph(nodes, edges, 1, max_links=100)
+        self.assertEqual(count, 100)
+
+    def test_diamond(self):
+        nodes = {
+            -1: {'amount': 1, 'cum': 1, 'ind': 0},
+            10: {'amount': 1, 'cum': 1, 'ind': 0},
+            11: {'amount': 1, 'cum': 0.2, 'ind': 0},
+            12: {'amount': 1, 'cum': 0.8, 'ind': 0},
+            13: {'amount': 1, 'cum': 1, 'ind': 1},
+        }
+        edges = [
+            {'to': -1, 'from': 10, 'amount': 1, 'exc_amount': 1, 'impact': 1},
+            {'to': 10, 'from': 11, 'amount': 1, 'exc_amount': 1, 'impact': 0.2},
+            {'to': 10, 'from': 12, 'amount': 1, 'exc_amount': 1, 'impact': 0.8},
+            {'to': 11, 'from': 13, 'amount': 0.2, 'exc_amount': 0.2, 'impact': 0.2},
+            {'to': 12, 'from': 13, 'amount': 0.8, 'exc_amount': 0.8, 'impact': 0.8}
+        ]
+        nodes, edges, count = GTManipulator.unroll_graph(nodes, edges, 1)
+        ref_nodes = {
+            -1: {'ind': 0, 'amount': 1, 'cum': 1},
+            0: {'ind': 0, 'amount': 1, 'cum': 1, 'row': 10},
+            1: {'ind': 0, 'amount': 1, 'cum': 0.2, 'row': 11},
+            2: {'ind': 0, 'amount': 1, 'cum': 0.8, 'row': 12},
+            3: {'ind': 1, 'amount': 0.8, 'cum': 0.8, 'row': 13},
+            4: {'ind': 1, 'amount': 0.2, 'cum': 0.2, 'row': 13}
+        }
+        ref_edges = [
+            {'impact': 1, 'to': -1, 'amount': 1, 'exc_amount': 1, 'from': 0},
+            {'impact': 0.2, 'to': 0, 'amount': 1, 'exc_amount': 1, 'from': 1},
+            {'impact': 0.8, 'to': 0, 'amount': 1, 'exc_amount': 1, 'from': 2},
+            {'impact': 0.8, 'to': 2, 'amount': 0.8, 'exc_amount': 0.8, 'from': 3},
+            {'impact': 0.2, 'to': 1, 'amount': 0.2, 'exc_amount': 0.2, 'from': 4}
+        ]
+        self.assertEqual(count, 5)
+        self.assertEqual(nodes, ref_nodes)
+        self.assertEqual(edges, ref_edges)
+
+    def test_circle_with_branches(self):
+        pass
+
+
+class MetadataTestCase(BW2DataTest):
+    class LCAMock(object):
+        def reverse_dict(self):
+            return {1: ("A", "a"), 2: ("A", "b"), 3: ("A", "c")}, {}
+
+    def extra_setup(self):
+        data = {
+            ("A", "a"): {
+                "name": "a",
+                "categories": [],
+                "unit": "kilogram"
+                },
+            ("A", "b"): {
+                "name": "b",
+                "categories": [],
+                "unit": "kilogram"
+                },
+            ("A", "c"): {
+                "name": "c",
+                "categories": [],
+                "unit": "kilogram"
+                }
+        }
+        d = Database("A")
+        d.register("Tests", [], len(data))
+        d.write(data)
+        self.assertEqual(len(databases), 1)
+
+    def test_without_row(self):
+        nodes = {1: {}, 3: {}}
+        old_nodes = copy.deepcopy(nodes)
+        new_nodes = GTManipulator.add_metadata(nodes, self.LCAMock())
+        self.assertEqual(old_nodes, nodes)
+        self.assertEqual(
+            new_nodes,
+            {
+                1: {'categories': [], 'unit': 'kilogram', 'key': ('A', 'a'), 'name': 'a'},
+                3: {'categories': [], 'unit': 'kilogram', 'key': ('A', 'c'), 'name': 'c'}
+            })
+
+    def test_with_functional_unit(self):
+        nodes = {-1: {}, 1: {}, 3: {}}
+        old_nodes = copy.deepcopy(nodes)
+        new_nodes = GTManipulator.add_metadata(nodes, self.LCAMock())
+        self.assertEqual(old_nodes, nodes)
+        self.assertEqual(
+            new_nodes,
+            {
+                -1: {'name': "Functional unit", 'unit': "unit", 'categories': ["Functional unit"]},
+                1: {'categories': [], 'unit': 'kilogram', 'key': ('A', 'a'), 'name': 'a'},
+                3: {'categories': [], 'unit': 'kilogram', 'key': ('A', 'c'), 'name': 'c'}
+            })
+
+    def test_with_row(self):
+        nodes = {1000: {'row': 1}, 3000: {'row': 3}}
+        old_nodes = copy.deepcopy(nodes)
+        new_nodes = GTManipulator.add_metadata(nodes, self.LCAMock())
+        self.assertEqual(old_nodes, nodes)
+        self.assertEqual(
+            new_nodes,
+            {
+                1000: {'categories': [], 'unit': 'kilogram', 'key': ('A', 'a'), 'name': 'a', 'row': 1},
+                3000: {'categories': [], 'unit': 'kilogram', 'key': ('A', 'c'), 'name': 'c', 'row': 3}
+            })
+
+
+class SimplifyTestCase(unittest.TestCase):
+    def test_nodes_dont_change(self):
+        nodes = {
+            1: {'amount': 1, 'ind': 1},
+            2: {'amount': 2, 'ind': 0.0001},
+            3: {'amount': 4, 'ind': 1},
+        }
+        old_nodes = copy.deepcopy(nodes)
+        edges = [
+            {'to': 1, 'from': 2, 'amount': 3, 'exc_amount': 2, 'impact': 4},
+            {'to': 2, 'from': 3, 'amount': 3, 'exc_amount': 2, 'impact': 5},
+        ]
+        GTManipulator.simplify(nodes, edges, 2, 0.1)
+        self.assertEqual(old_nodes, nodes)
+
+    def test_linear(self):
+        """Test supply chain graph like this:
+
+            o
+            |    o
+            x => |
+            |    o
+            o
+
+        """
+        nodes = {
+            1: {'amount': 1, 'ind': 1},
+            2: {'amount': 2, 'ind': 0.0001},
+            3: {'amount': 4, 'ind': 1},
+        }
+        edges = [
+            {'to': 1, 'from': 2, 'amount': 3, 'exc_amount': 2, 'impact': 4},
+            {'to': 2, 'from': 3, 'amount': 3, 'exc_amount': 2, 'impact': 5},
+        ]
+        new_nodes, new_edges = GTManipulator.simplify(nodes, edges, 2, 0.1)
+        self.assertEqual(
+            new_nodes,
+            {key: value for key, value in nodes.iteritems() if key in (1, 3)}
+        )
+        self.assertEqual(
+            new_edges,
+            [{'to': 1, 'from': 3, 'amount': 3, 'exc_amount': 4, 'impact': 5}]
+        )
+
+    def test_y(self):
+        """Test supply chain graph like this:
+
+            o   o     o   o
+             \ /       \ /
+              x   =>    o
+              |
+              o
+
+        """
+        nodes = {
+            1: {'amount': 1, 'ind': 1},
+            2: {'amount': 4, 'ind': 2},
+            3: {'amount': 1, 'ind': 0.001},
+            4: {'amount': 2, 'ind': 1.5},
+        }
+        edges = [
+            {'to': 1, 'from': 3, 'amount': 0.2, 'exc_amount': 0.2, 'impact': 1},
+            {'to': 2, 'from': 3, 'amount': 0.8, 'exc_amount': 0.2, 'impact': 2},
+            {'to': 3, 'from': 4, 'amount': 2, 'exc_amount': 2, 'impact': 3},
+        ]
+        new_nodes, new_edges = GTManipulator.simplify(nodes, edges, 9, 0.1)
+        expected_nodes = {key: value for key, value in nodes.iteritems()
+            if key in (1, 2, 4)}
+        self.assertEqual(expected_nodes, new_nodes)
+        expected_edges = [
+            {'to': 2, 'from': 4, 'amount': 1.6, 'exc_amount': 0.4, 'impact': 2},
+            {'to': 1, 'from': 4, 'amount': 0.4, 'exc_amount': 0.4, 'impact': 1},
+        ]
+        self.assertEqual(expected_edges, new_edges)
+
+    def test_no_self_edge(self):
+        """Test that collapsed edges from a -> a are deleted."""
+        nodes = {
+            1: {'amount': 1, 'ind': 1},
+            2: {'amount': 4, 'ind': 2},
+            3: {'amount': 1, 'ind': 0.001},
+            4: {'amount': 2, 'ind': 1.5},
+        }
+        edges = [
+            {'to': 1, 'from': 3, 'amount': 0.2, 'exc_amount': 0.2, 'impact': 1},
+            {'to': 2, 'from': 3, 'amount': 0.8, 'exc_amount': 0.2, 'impact': 2},
+            {'to': 3, 'from': 4, 'amount': 2, 'exc_amount': 2, 'impact': 3},
+        ]
+        new_nodes, new_edges = GTManipulator.simplify(nodes, edges, 9, 0.1)
+        expected_nodes = {key: value for key, value in nodes.iteritems()
+            if key in (1, 2, 4)}
+        self.assertEqual(expected_nodes, new_nodes)
+        expected_edges = [
+            {'to': 2, 'from': 4, 'amount': 1.6, 'exc_amount': 0.4, 'impact': 2},
+            {'to': 1, 'from': 4, 'amount': 0.4, 'exc_amount': 0.4, 'impact': 1},
+        ]
+        self.assertEqual(expected_edges, new_edges)
+
+    def test_diamond(self):
+        """Test supply chain graph like this:
+
+              o
+             / \      o
+            x   x =>  |
+             \ /      o
+              o
+
+        """
+        nodes = {
+            1: {'amount': 1, 'ind': 1},
+            2: {'amount': 2, 'ind': 0},
+            3: {'amount': 3, 'ind': 0},
+            4: {'amount': 5, 'ind': 1},
+        }
+        edges = [
+            {'to': 1, 'from': 2, 'amount': 2, 'exc_amount': 1, 'impact': 2},
+            {'to': 1, 'from': 3, 'amount': 3, 'exc_amount': 1, 'impact': 3},
+            {'to': 2, 'from': 4, 'amount': 2, 'exc_amount': 1, 'impact': 2},
+            {'to': 3, 'from': 4, 'amount': 3, 'exc_amount': 1, 'impact': 3},
+        ]
+        new_nodes, new_edges = GTManipulator.simplify(nodes, edges, 5, 0.1)
+        expected_nodes = {key: value for key, value in nodes.iteritems()
+            if key in (1, 4)}
+        self.assertEqual(expected_nodes, new_nodes)
+        expected_edges = [
+            {'to': 1, 'from': 4, 'amount': 5, 'exc_amount': 2, 'impact': 5}
+        ]
+        self.assertEqual(expected_edges, new_edges)
+
+    def test_x(self):
+        """Test supply chain graph like this:
+
+            o   o
+             \ /      o  o
+              x   =>  |\/|
+             / \      |/\|
+            o   o     o  o
+        """
+        nodes = {
+            1: {'amount': 1, 'ind': 1},
+            2: {'amount': 1, 'ind': 1},
+            3: {'amount': 3, 'ind': 0},
+            4: {'amount': 9, 'ind': 3},
+            5: {'amount': 12, 'ind': 2},
+        }
+        edges = [
+            {'to': 1, 'from': 3, 'amount': 1, 'exc_amount': 1, 'impact': 17},
+            {'to': 2, 'from': 3, 'amount': 2, 'exc_amount': 2, 'impact': 34},
+            {'to': 3, 'from': 4, 'amount': 9, 'exc_amount': 3, 'impact': 27},
+            {'to': 3, 'from': 5, 'amount': 12, 'exc_amount': 4, 'impact': 24},
+        ]
+        new_nodes, new_edges = GTManipulator.simplify(nodes, edges, 53, 0.01)
+        expected_nodes = {key: value for key, value in nodes.iteritems()
+            if key in (1, 2, 4, 5)}
+        self.assertEqual(expected_nodes, new_nodes)
+        expected_edges = [
+            {'to': 1, 'from': 4, 'amount': 3, 'exc_amount': 3, 'impact': 9},
+            {'to': 1, 'from': 5, 'amount': 4, 'exc_amount': 4, 'impact': 8},
+            {'to': 2, 'from': 5, 'amount': 8, 'exc_amount': 8, 'impact': 16},
+            {'to': 2, 'from': 4, 'amount': 6, 'exc_amount': 6, 'impact': 18},
+        ]
+        self.assertEqual(expected_edges, new_edges)
+