adds implementation of SNAP summarization algorithm (#4463)

* adds implementation of SNAP summarization algorithm

Thanks to dschult and rossbar for many much-needed recommendations for refining and optimizing the implementation

* Seed layouts for snap gallery examples.

Make sure the layouts are reproducible.

Co-authored-by: Ross Barnowski <rossbar@berkeley.edu>

4 files changed, 893 insertions, 12 deletions

diff --git a/doc/reference/algorithms/summarization.rst b/doc/reference/algorithms/summarization.rst
index 3efd6237..8b8ebcb0 100644
--- a/doc/reference/algorithms/summarization.rst
+++ b/doc/reference/algorithms/summarization.rst
@@ -7,3 +7,4 @@ Summarization
    :toctree: generated/
 
    dedensify
+   snap_aggregation
diff --git a/examples/algorithms/plot_snap.py b/examples/algorithms/plot_snap.py
new file mode 100644
index 00000000..85ea71de
--- /dev/null
+++ b/examples/algorithms/plot_snap.py
@@ -0,0 +1,108 @@
+"""
+==================
+SNAP Graph Summary
+==================
+An example of summarizing a graph based on node attributes and edge attributes
+using the Summarization by Grouping Nodes on Attributes and Pairwise
+edges (SNAP) algorithm (not to be confused with the Stanford Network
+Analysis Project).  The algorithm groups nodes by their unique
+combinations of node attribute values and edge types with other groups
+of nodes to produce a summary graph.  The summary graph can then be used to
+infer how nodes with different attributes values relate to other nodes in the
+graph.
+"""
+import networkx as nx
+import matplotlib.pyplot as plt
+
+
+nodes = {
+    "A": dict(color="Red"),
+    "B": dict(color="Red"),
+    "C": dict(color="Red"),
+    "D": dict(color="Red"),
+    "E": dict(color="Blue"),
+    "F": dict(color="Blue"),
+    "G": dict(color="Blue"),
+    "H": dict(color="Blue"),
+    "I": dict(color="Yellow"),
+    "J": dict(color="Yellow"),
+    "K": dict(color="Yellow"),
+    "L": dict(color="Yellow"),
+}
+edges = [
+    ("A", "B", "Strong"),
+    ("A", "C", "Weak"),
+    ("A", "E", "Strong"),
+    ("A", "I", "Weak"),
+    ("B", "D", "Weak"),
+    ("B", "J", "Weak"),
+    ("B", "F", "Strong"),
+    ("C", "G", "Weak"),
+    ("D", "H", "Weak"),
+    ("I", "J", "Strong"),
+    ("J", "K", "Strong"),
+    ("I", "L", "Strong"),
+]
+original_graph = nx.Graph()
+original_graph.add_nodes_from(n for n in nodes.items())
+original_graph.add_edges_from((u, v, {"type": label}) for u, v, label in edges)
+
+
+plt.suptitle("SNAP Summarization")
+
+base_options = dict(with_labels=True, edgecolors="black", node_size=500)
+
+ax1 = plt.subplot(1, 2, 1)
+plt.title(
+    "Original (%s nodes, %s edges)"
+    % (original_graph.number_of_nodes(), original_graph.number_of_edges())
+)
+pos = nx.spring_layout(original_graph, seed=7482934)
+node_colors = [d["color"] for _, d in original_graph.nodes(data=True)]
+
+edge_type_visual_weight_lookup = {"Weak": 1.0, "Strong": 3.0}
+edge_weights = [
+    edge_type_visual_weight_lookup[d["type"]]
+    for _, _, d in original_graph.edges(data=True)
+]
+
+nx.draw_networkx(
+    original_graph, pos=pos, node_color=node_colors, width=edge_weights, **base_options
+)
+
+node_attributes = ("color",)
+edge_attributes = ("type",)
+summary_graph = nx.snap_aggregation(
+    original_graph, node_attributes, edge_attributes, prefix="S-"
+)
+
+plt.subplot(1, 2, 2)
+
+plt.title(
+    "SNAP Aggregation (%s nodes, %s edges)"
+    % (summary_graph.number_of_nodes(), summary_graph.number_of_edges())
+)
+summary_pos = nx.spring_layout(summary_graph, seed=8375428)
+node_colors = []
+for node in summary_graph:
+    color = summary_graph.nodes[node]["color"]
+    node_colors.append(color)
+
+edge_weights = []
+for edge in summary_graph.edges():
+    edge_types = summary_graph.get_edge_data(*edge)["types"]
+    edge_weight = 0.0
+    for edge_type in edge_types:
+        edge_weight += edge_type_visual_weight_lookup[edge_type["type"]]
+    edge_weights.append(edge_weight)
+
+nx.draw_networkx(
+    summary_graph,
+    pos=summary_pos,
+    node_color=node_colors,
+    width=edge_weights,
+    **base_options
+)
+
+plt.tight_layout()
+plt.show()
diff --git a/networkx/algorithms/summarization.py b/networkx/algorithms/summarization.py
index f909ee3e..13d7508a 100644
--- a/networkx/algorithms/summarization.py
+++ b/networkx/algorithms/summarization.py
@@ -59,10 +59,10 @@ For more information on graph summarization, see `Graph Summarization Methods
 and Applications: A Survey <https://dl.acm.org/doi/abs/10.1145/3186727>`_
 """
 import networkx as nx
+from collections import Counter, defaultdict
 
-__all__ = [
-    "dedensify",
-]
+
+__all__ = ["dedensify", "snap_aggregation"]
 
 
 def dedensify(G, threshold, prefix=None, copy=True):
@@ -210,3 +210,352 @@ def dedensify(G, threshold, prefix=None, copy=True):
             G.add_edge(compression_node, node)
         compressor_nodes.add(compression_node)
     return G, compressor_nodes
+
+
+def _snap_build_graph(
+    G,
+    groups,
+    node_attributes,
+    edge_attributes,
+    neighbor_info,
+    edge_types,
+    prefix,
+    supernode_attribute,
+    superedge_attribute,
+):
+    """
+    Build the summary graph from the data structures produced in the SNAP aggregation algorithm
+
+    Used in the SNAP aggregation algorithm to build the output summary graph and supernode
+    lookup dictionary.  This process uses the original graph and the data structures to
+    create the supernodes with the correct node attributes, and the superedges with the correct
+    edge attributes
+
+    Parameters
+    ----------
+    G: networkx.Graph
+        the original graph to be summarized
+    groups: dict
+        A dictionary of unique group IDs and their corresponding node groups
+    node_attributes: iterable
+        An iterable of the node attributes considered in the summarization process
+    edge_attributes: iterable
+        An iterable of the edge attributes considered in the summarization process
+    neighbor_info: dict
+        A data structure indicating the number of edges a node has with the
+        groups in the current summarization of each edge type
+    edge_types: dict
+        dictionary of edges in the graph and their corresponding attributes recognized
+        in the summarization
+    prefix: string
+        The prefix to be added to all supernodes
+    supernode_attribute: str
+        The node attribute for recording the supernode groupings of nodes
+    superedge_attribute: str
+        The edge attribute for recording the edge types represented by superedges
+
+    Returns
+    -------
+    summary graph: Networkx graph
+    """
+    output = G.__class__()
+    node_label_lookup = dict()
+    for index, group_id in enumerate(groups):
+        group_set = groups[group_id]
+        supernode = "%s%s" % (prefix, index)
+        node_label_lookup[group_id] = supernode
+        supernode_attributes = {
+            attr: G.nodes[next(iter(group_set))][attr] for attr in node_attributes
+        }
+        supernode_attributes[supernode_attribute] = group_set
+        output.add_node(supernode, **supernode_attributes)
+
+    for group_id in groups:
+        group_set = groups[group_id]
+        source_supernode = node_label_lookup[group_id]
+        for other_group, group_edge_types in neighbor_info[
+            next(iter(group_set))
+        ].items():
+            if group_edge_types:
+                target_supernode = node_label_lookup[other_group]
+                summary_graph_edge = (source_supernode, target_supernode)
+
+                edge_types = [
+                    dict(zip(edge_attributes, edge_type))
+                    for edge_type in group_edge_types
+                ]
+
+                has_edge = output.has_edge(*summary_graph_edge)
+                if output.is_multigraph():
+                    if not has_edge:
+                        for edge_type in edge_types:
+                            output.add_edge(*summary_graph_edge, **edge_type)
+                    elif not output.is_directed():
+                        existing_edge_data = output.get_edge_data(*summary_graph_edge)
+                        for edge_type in edge_types:
+                            if edge_type not in existing_edge_data.values():
+                                output.add_edge(*summary_graph_edge, **edge_type)
+                else:
+                    superedge_attributes = {superedge_attribute: edge_types}
+                    output.add_edge(*summary_graph_edge, **superedge_attributes)
+
+    return output
+
+
+def _snap_eligible_group(G, groups, group_lookup, edge_types):
+    """
+    Determines if a group is eligible to be split.
+
+    A group is eligible to be split if all nodes in the group have edges of the same type(s)
+    with the same other groups.
+
+    Parameters
+    ----------
+    G: graph
+        graph to be summarized
+    groups: dict
+        A dictionary of unique group IDs and their corresponding node groups
+    group_lookup: dict
+        dictionary of nodes and their current corresponding group ID
+    edge_types: dict
+        dictionary of edges in the graph and their corresponding attributes recognized
+        in the summarization
+
+    Returns
+    -------
+    tuple: group ID to split, and neighbor-groups participation_counts data structure
+    """
+    neighbor_info = {node: {gid: Counter() for gid in groups} for node in group_lookup}
+    for group_id in groups:
+        current_group = groups[group_id]
+
+        # build neighbor_info for nodes in group
+        for node in current_group:
+            neighbor_info[node] = {group_id: Counter() for group_id in groups}
+            edges = G.edges(node, keys=True) if G.is_multigraph() else G.edges(node)
+            for edge in edges:
+                neighbor = edge[1]
+                edge_type = edge_types[edge]
+                neighbor_group_id = group_lookup[neighbor]
+                neighbor_info[node][neighbor_group_id][edge_type] += 1
+
+        # check if group_id is eligible to be split
+        group_size = len(current_group)
+        for other_group_id in groups:
+            edge_counts = Counter()
+            for node in current_group:
+                edge_counts.update(neighbor_info[node][other_group_id].keys())
+
+            if not all(count == group_size for count in edge_counts.values()):
+                # only the neighbor_info of the returned group_id is required for handling group splits
+                return group_id, neighbor_info
+
+    # if no eligible groups, complete neighbor_info is calculated
+    return None, neighbor_info
+
+
+def _snap_split(
+    groups,
+    neighbor_info,
+    group_lookup,
+    group_id,
+):
+    """
+    Splits a group based on edge types and updates the groups accordingly
+
+    Splits the group with the given group_id based on the edge types
+    of the nodes so that each new grouping will all have the same
+    edges with other nodes.
+
+    Parameters
+    ----------
+    groups: dict
+        A dictionary of unique group IDs and their corresponding node groups
+    neighbor_info: dict
+        A data structure indicating the number of edges a node has with the
+        groups in the current summarization of each edge type
+    edge_types: dict
+        dictionary of edges in the graph and their corresponding attributes recognized
+        in the summarization
+    group_lookup: dict
+        dictionary of nodes and their current corresponding group ID
+    group_id: object
+        ID of group to be split
+
+    Returns
+    -------
+    dict
+        The updated groups based on the split
+    """
+    new_group_mappings = defaultdict(set)
+    for node in groups[group_id]:
+        signature = tuple(
+            frozenset(edge_types) for edge_types in neighbor_info[node].values()
+        )
+        new_group_mappings[signature].add(node)
+
+    # leave the biggest new_group as the original group
+    new_groups = sorted(new_group_mappings.values(), key=len)
+    for new_group in new_groups[:-1]:
+        # Assign unused integer as the new_group_id
+        # ids are tuples, so will not interact with the original group_ids
+        new_group_id = len(groups)
+        groups[new_group_id] = new_group
+        groups[group_id] -= new_group
+        for node in new_group:
+            group_lookup[node] = new_group_id
+
+    return groups
+
+
+def snap_aggregation(
+    G,
+    node_attributes,
+    edge_attributes=(),
+    prefix="Supernode-",
+    supernode_attribute="group",
+    superedge_attribute="types",
+):
+    """Creates a summary graph based on attributes and connectivity.
+
+    This function uses the Summarization by Grouping Nodes on Attributes
+    and Pairwise edges (SNAP) algorithm for summarizing a given
+    graph by grouping nodes by node attributes and their edge attributes
+    into supernodes in a summary graph.  This name SNAP should not be
+    confused with the Stanford Network Analysis Project (SNAP).
+
+    Here is a high-level view of how this algorithm works:
+
+    1) Group nodes by node attribute values.
+
+    2) Iteratively split groups until all nodes in each group have edges
+    to nodes in the same groups. That is, until all the groups are homogeneous
+    in their member nodes' edges to other groups.  For example,
+    if all the nodes in group A only have edge to nodes in group B, then the
+    group is homogeneous and does not need to be split. If all nodes in group B
+    have edges with nodes in groups {A, C}, but some also have edges with other
+    nodes in B, then group B is not homogeneous and needs to be split into
+    groups have edges with {A, C} and a group of nodes having
+    edges with {A, B, C}.  This way, viewers of the summary graph can
+    assume that all nodes in the group have the exact same node attributes and
+    the exact same edges.
+
+    3) Build the output summary graph, where the groups are represented by
+    super-nodes. Edges represent the edges shared between all the nodes in each
+    respective groups.
+
+    A SNAP summary graph can be used to visualize graphs that are too large to display
+    or visually analyze, or to efficiently identify sets of similar nodes with similar connectivity
+    patterns to other sets of similar nodes based on specified node and/or edge attributes in a graph.
+
+    Parameters
+    ----------
+    G: graph
+        Networkx Graph to be summarized
+    edge_attributes: iterable, optional
+        An iterable of the edge attributes considered in the summarization process.  If provided, unique
+        combinations of the attribute values found in the graph are used to
+        determine the edge types in the graph.  If not provided, all edges
+        are considered to be of the same type.
+    prefix: str
+        The prefix used to denote supernodes in the summary graph. Defaults to 'Supernode-'.
+    supernode_attribute: str
+        The node attribute for recording the supernode groupings of nodes. Defaults to 'group'.
+    superedge_attribute: str
+        The edge attribute for recording the edge types of multiple edges. Defaults to 'types'.
+
+    Returns
+    -------
+    networkx.Graph: summary graph
+
+    Examples
+    --------
+    SNAP aggregation takes a graph and summarizes it in the context of user-provided
+    node and edge attributes such that a viewer can more easily extract and
+    analyze the information represented by the graph::
+
+    >>> nodes = {
+    ...     "A": dict(color="Red"),
+    ...     "B": dict(color="Red"),
+    ...     "C": dict(color="Red"),
+    ...     "D": dict(color="Red"),
+    ...     "E": dict(color="Blue"),
+    ...     "F": dict(color="Blue"),
+    ... }
+    >>> edges = [
+    ...     ("A", "E", "Strong"),
+    ...     ("B", "F", "Strong"),
+    ...     ("C", "E", "Weak"),
+    ...     ("D", "F", "Weak"),
+    ... ]
+    >>> G = nx.Graph()
+    >>> for node in nodes:
+    ...     attributes = nodes[node]
+    ...     G.add_node(node, **attributes)
+    ...
+    >>> for source, target, type in edges:
+    ...     G.add_edge(source, target, type=type)
+    ...
+    >>> node_attributes = ('color', )
+    >>> edge_attributes = ('type', )
+    >>> summary_graph = nx.snap_aggregation(G, node_attributes=node_attributes, edge_attributes=edge_attributes)
+
+    Notes
+    -----
+    The summary graph produced is called a maximum Attribute-edge
+    compatible (AR-compatible) grouping.  According to [1]_, an
+    AR-compatible grouping means that all nodes in each group have the same
+    exact node attribute values and the same exact edges and
+    edge types to one or more nodes in the same groups.  The maximal
+    AR-compatible grouping is the grouping with the minimal cardinality.
+
+    The AR-compatible grouping is the most detailed grouping provided by
+    any of the SNAP algorithms.
+
+    References
+    ----------
+    .. [1] Y. Tian, R. A. Hankins, and J. M. Patel. Efficient aggregation
+       for graph summarization. In Proc. 2008 ACM-SIGMOD Int. Conf.
+       Management of Data (SIGMOD’08), pages 567–580, Vancouver, Canada,
+       June 2008.
+    """
+    edge_types = {
+        edge: tuple(attrs.get(attr) for attr in edge_attributes)
+        for edge, attrs in G.edges.items()
+    }
+    if not G.is_directed():
+        if G.is_multigraph():
+            # list is needed to avoid mutating while iterating
+            edges = [((v, u, k), etype) for (u, v, k), etype in edge_types.items()]
+        else:
+            # list is needed to avoid mutating while iterating
+            edges = [((v, u), etype) for (u, v), etype in edge_types.items()]
+        edge_types.update(edges)
+
+    group_lookup = {
+        node: tuple(attrs[attr] for attr in node_attributes)
+        for node, attrs in G.nodes.items()
+    }
+    groups = defaultdict(set)
+    for node, node_type in group_lookup.items():
+        groups[node_type].add(node)
+
+    eligible_group_id, neighbor_info = _snap_eligible_group(
+        G, groups, group_lookup, edge_types
+    )
+    while eligible_group_id:
+        groups = _snap_split(groups, neighbor_info, group_lookup, eligible_group_id)
+        eligible_group_id, neighbor_info = _snap_eligible_group(
+            G, groups, group_lookup, edge_types
+        )
+    return _snap_build_graph(
+        G,
+        groups,
+        node_attributes,
+        edge_attributes,
+        neighbor_info,
+        edge_types,
+        prefix,
+        supernode_attribute,
+        superedge_attribute,
+    )
diff --git a/networkx/algorithms/tests/test_summarization.py b/networkx/algorithms/tests/test_summarization.py
index 4140a504..dd90d0b9 100644
--- a/networkx/algorithms/tests/test_summarization.py
+++ b/networkx/algorithms/tests/test_summarization.py
@@ -1,9 +1,8 @@
 """
-Unit tests for dedensification/densification
+Unit tests for dedensification and graph summarization
 """
-
+import pytest
 import networkx as nx
-from networkx.algorithms.summarization import dedensify
 
 
 class TestDirectedDedensification:
@@ -45,7 +44,7 @@ class TestDirectedDedensification:
         Verify that an empty directed graph results in no compressor nodes
         """
         G = nx.DiGraph()
-        compressed_graph, c_nodes = dedensify(G, threshold=2)
+        compressed_graph, c_nodes = nx.dedensify(G, threshold=2)
         assert c_nodes == set()
 
     @staticmethod
@@ -92,7 +91,7 @@ class TestDirectedDedensification:
         """
         G = self.build_original_graph()
         compressed_G = self.build_compressed_graph()
-        compressed_graph, c_nodes = dedensify(G, threshold=2)
+        compressed_graph, c_nodes = nx.dedensify(G, threshold=2)
         for s, t in compressed_graph.edges():
             o_s = "".join(sorted(s))
             o_t = "".join(sorted(t))
@@ -108,7 +107,7 @@ class TestDirectedDedensification:
         """
         G = self.build_original_graph()
         original_edge_count = len(G.edges())
-        c_G, c_nodes = dedensify(G, threshold=2)
+        c_G, c_nodes = nx.dedensify(G, threshold=2)
         compressed_edge_count = len(c_G.edges())
         assert compressed_edge_count <= original_edge_count
         compressed_G = self.build_compressed_graph()
@@ -164,7 +163,7 @@ class TestUnDirectedDedensification:
         Verify that an empty undirected graph results in no compressor nodes
         """
         G = nx.Graph()
-        compressed_G, c_nodes = dedensify(G, threshold=2)
+        compressed_G, c_nodes = nx.dedensify(G, threshold=2)
         assert c_nodes == set()
 
     def setup_method(self):
@@ -197,7 +196,7 @@ class TestUnDirectedDedensification:
         correct edges to/from the compressor nodes in an undirected graph
         """
         G = self.build_original_graph()
-        c_G, c_nodes = dedensify(G, threshold=2)
+        c_G, c_nodes = nx.dedensify(G, threshold=2)
         v_compressed_G = self.build_compressed_graph()
         for s, t in c_G.edges():
             o_s = "".join(sorted(s))
@@ -213,10 +212,434 @@ class TestUnDirectedDedensification:
         undirected graph
         """
         G = self.build_original_graph()
-        c_G, c_nodes = dedensify(G, threshold=2, copy=True)
+        c_G, c_nodes = nx.dedensify(G, threshold=2, copy=True)
         compressed_edge_count = len(c_G.edges())
         verified_original_edge_count = len(G.edges())
         assert compressed_edge_count <= verified_original_edge_count
         verified_compressed_G = self.build_compressed_graph()
         verified_compressed_edge_count = len(verified_compressed_G.edges())
         assert compressed_edge_count == verified_compressed_edge_count
+
+
+@pytest.mark.parametrize(
+    "graph_type", [nx.Graph, nx.DiGraph, nx.MultiGraph, nx.MultiDiGraph]
+)
+def test_summarization_empty(graph_type):
+    G = graph_type()
+    summary_graph = nx.snap_aggregation(G, node_attributes=("color",))
+    assert nx.is_isomorphic(summary_graph, G)
+
+
+class AbstractSNAP:
+    node_attributes = ("color",)
+
+    def build_original_graph(self):
+        pass
+
+    def build_summary_graph(self):
+        pass
+
+    def test_summary_graph(self):
+        original_graph = self.build_original_graph()
+        summary_graph = self.build_summary_graph()
+
+        relationship_attributes = ("type",)
+        generated_summary_graph = nx.snap_aggregation(
+            original_graph,
+            self.node_attributes,
+            relationship_attributes,
+        )
+        relabeled_summary_graph = self.deterministic_labels(generated_summary_graph)
+        assert nx.is_isomorphic(summary_graph, relabeled_summary_graph)
+
+    def deterministic_labels(self, G):
+        node_labels = list(G.nodes)
+        node_labels = sorted(node_labels, key=lambda n: sorted(G.nodes[n]["group"])[0])
+        node_labels.sort()
+
+        label_mapping = dict()
+        for index, node in enumerate(node_labels):
+            label = "Supernode-%s" % index
+            label_mapping[node] = label
+
+        return nx.relabel_nodes(G, label_mapping)
+
+
+class TestSNAPNoEdgeTypes(AbstractSNAP):
+    relationship_attributes = ()
+
+    def test_summary_graph(self):
+        original_graph = self.build_original_graph()
+        summary_graph = self.build_summary_graph()
+
+        relationship_attributes = ("type",)
+        generated_summary_graph = nx.snap_aggregation(
+            original_graph, self.node_attributes
+        )
+        relabeled_summary_graph = self.deterministic_labels(generated_summary_graph)
+        assert nx.is_isomorphic(summary_graph, relabeled_summary_graph)
+
+    def build_original_graph(self):
+        nodes = {
+            "A": dict(color="Red"),
+            "B": dict(color="Red"),
+            "C": dict(color="Red"),
+            "D": dict(color="Red"),
+            "E": dict(color="Blue"),
+            "F": dict(color="Blue"),
+            "G": dict(color="Blue"),
+            "H": dict(color="Blue"),
+            "I": dict(color="Yellow"),
+            "J": dict(color="Yellow"),
+            "K": dict(color="Yellow"),
+            "L": dict(color="Yellow"),
+        }
+        edges = [
+            ("A", "B"),
+            ("A", "C"),
+            ("A", "E"),
+            ("A", "I"),
+            ("B", "D"),
+            ("B", "J"),
+            ("B", "F"),
+            ("C", "G"),
+            ("D", "H"),
+            ("I", "J"),
+            ("J", "K"),
+            ("I", "L"),
+        ]
+        G = nx.Graph()
+        for node in nodes:
+            attributes = nodes[node]
+            G.add_node(node, **attributes)
+
+        for source, target in edges:
+            G.add_edge(source, target)
+
+        return G
+
+    def build_summary_graph(self):
+        nodes = {
+            "Supernode-0": dict(color="Red"),
+            "Supernode-1": dict(color="Red"),
+            "Supernode-2": dict(color="Blue"),
+            "Supernode-3": dict(color="Blue"),
+            "Supernode-4": dict(color="Yellow"),
+            "Supernode-5": dict(color="Yellow"),
+        }
+        edges = [
+            ("Supernode-0", "Supernode-0"),
+            ("Supernode-0", "Supernode-1"),
+            ("Supernode-0", "Supernode-2"),
+            ("Supernode-0", "Supernode-4"),
+            ("Supernode-1", "Supernode-3"),
+            ("Supernode-4", "Supernode-4"),
+            ("Supernode-4", "Supernode-5"),
+        ]
+        G = nx.Graph()
+        for node in nodes:
+            attributes = nodes[node]
+            G.add_node(node, **attributes)
+
+        for source, target in edges:
+            G.add_edge(source, target)
+
+        supernodes = {
+            "Supernode-0": set(["A", "B"]),
+            "Supernode-1": set(["C", "D"]),
+            "Supernode-2": set(["E", "F"]),
+            "Supernode-3": set(["G", "H"]),
+            "Supernode-4": set(["I", "J"]),
+            "Supernode-5": set(["K", "L"]),
+        }
+        nx.set_node_attributes(G, supernodes, "group")
+        return G
+
+
+class TestSNAPUndirected(AbstractSNAP):
+    def build_original_graph(self):
+        nodes = {
+            "A": dict(color="Red"),
+            "B": dict(color="Red"),
+            "C": dict(color="Red"),
+            "D": dict(color="Red"),
+            "E": dict(color="Blue"),
+            "F": dict(color="Blue"),
+            "G": dict(color="Blue"),
+            "H": dict(color="Blue"),
+            "I": dict(color="Yellow"),
+            "J": dict(color="Yellow"),
+            "K": dict(color="Yellow"),
+            "L": dict(color="Yellow"),
+        }
+        edges = [
+            ("A", "B", "Strong"),
+            ("A", "C", "Weak"),
+            ("A", "E", "Strong"),
+            ("A", "I", "Weak"),
+            ("B", "D", "Weak"),
+            ("B", "J", "Weak"),
+            ("B", "F", "Strong"),
+            ("C", "G", "Weak"),
+            ("D", "H", "Weak"),
+            ("I", "J", "Strong"),
+            ("J", "K", "Strong"),
+            ("I", "L", "Strong"),
+        ]
+        G = nx.Graph()
+        for node in nodes:
+            attributes = nodes[node]
+            G.add_node(node, **attributes)
+
+        for source, target, type in edges:
+            G.add_edge(source, target, type=type)
+
+        return G
+
+    def build_summary_graph(self):
+        nodes = {
+            "Supernode-0": dict(color="Red"),
+            "Supernode-1": dict(color="Red"),
+            "Supernode-2": dict(color="Blue"),
+            "Supernode-3": dict(color="Blue"),
+            "Supernode-4": dict(color="Yellow"),
+            "Supernode-5": dict(color="Yellow"),
+        }
+        edges = [
+            ("Supernode-0", "Supernode-0", "Strong"),
+            ("Supernode-0", "Supernode-1", "Weak"),
+            ("Supernode-0", "Supernode-2", "Strong"),
+            ("Supernode-0", "Supernode-4", "Weak"),
+            ("Supernode-1", "Supernode-3", "Weak"),
+            ("Supernode-4", "Supernode-4", "Strong"),
+            ("Supernode-4", "Supernode-5", "Strong"),
+        ]
+        G = nx.Graph()
+        for node in nodes:
+            attributes = nodes[node]
+            G.add_node(node, **attributes)
+
+        for source, target, type in edges:
+            G.add_edge(source, target, types=[dict(type=type)])
+
+        supernodes = {
+            "Supernode-0": set(["A", "B"]),
+            "Supernode-1": set(["C", "D"]),
+            "Supernode-2": set(["E", "F"]),
+            "Supernode-3": set(["G", "H"]),
+            "Supernode-4": set(["I", "J"]),
+            "Supernode-5": set(["K", "L"]),
+        }
+        nx.set_node_attributes(G, supernodes, "group")
+        return G
+
+
+class TestSNAPDirected(AbstractSNAP):
+    def build_original_graph(self):
+        nodes = {
+            "A": dict(color="Red"),
+            "B": dict(color="Red"),
+            "C": dict(color="Green"),
+            "D": dict(color="Green"),
+            "E": dict(color="Blue"),
+            "F": dict(color="Blue"),
+            "G": dict(color="Yellow"),
+            "H": dict(color="Yellow"),
+        }
+        edges = [
+            ("A", "C", "Strong"),
+            ("A", "E", "Strong"),
+            ("A", "F", "Weak"),
+            ("B", "D", "Strong"),
+            ("B", "E", "Weak"),
+            ("B", "F", "Strong"),
+            ("C", "G", "Strong"),
+            ("C", "F", "Strong"),
+            ("D", "E", "Strong"),
+            ("D", "H", "Strong"),
+            ("G", "E", "Strong"),
+            ("H", "F", "Strong"),
+        ]
+        G = nx.DiGraph()
+        for node in nodes:
+            attributes = nodes[node]
+            G.add_node(node, **attributes)
+
+        for source, target, type in edges:
+            G.add_edge(source, target, type=type)
+
+        return G
+
+    def build_summary_graph(self):
+        nodes = {
+            "Supernode-0": dict(color="Red"),
+            "Supernode-1": dict(color="Green"),
+            "Supernode-2": dict(color="Blue"),
+            "Supernode-3": dict(color="Yellow"),
+        }
+        edges = [
+            ("Supernode-0", "Supernode-1", [{"type": "Strong"}]),
+            ("Supernode-0", "Supernode-2", [{"type": "Weak"}, {"type": "Strong"}]),
+            ("Supernode-1", "Supernode-2", [{"type": "Strong"}]),
+            ("Supernode-1", "Supernode-3", [{"type": "Strong"}]),
+            ("Supernode-3", "Supernode-2", [{"type": "Strong"}]),
+        ]
+        G = nx.DiGraph()
+        for node in nodes:
+            attributes = nodes[node]
+            G.add_node(node, **attributes)
+
+        for source, target, types in edges:
+            G.add_edge(source, target, types=types)
+
+        supernodes = {
+            "Supernode-0": set(["A", "B"]),
+            "Supernode-1": set(["C", "D"]),
+            "Supernode-2": set(["E", "F"]),
+            "Supernode-3": set(["G", "H"]),
+            "Supernode-4": set(["I", "J"]),
+            "Supernode-5": set(["K", "L"]),
+        }
+        nx.set_node_attributes(G, supernodes, "group")
+        return G
+
+
+class TestSNAPUndirectedMulti(AbstractSNAP):
+    def build_original_graph(self):
+        nodes = {
+            "A": dict(color="Red"),
+            "B": dict(color="Red"),
+            "C": dict(color="Red"),
+            "D": dict(color="Blue"),
+            "E": dict(color="Blue"),
+            "F": dict(color="Blue"),
+            "G": dict(color="Yellow"),
+            "H": dict(color="Yellow"),
+            "I": dict(color="Yellow"),
+        }
+        edges = [
+            ("A", "D", ["Weak", "Strong"]),
+            ("B", "E", ["Weak", "Strong"]),
+            ("D", "I", ["Strong"]),
+            ("E", "H", ["Strong"]),
+            ("F", "G", ["Weak"]),
+            ("I", "G", ["Weak", "Strong"]),
+            ("I", "H", ["Weak", "Strong"]),
+            ("G", "H", ["Weak", "Strong"]),
+        ]
+        G = nx.MultiGraph()
+        for node in nodes:
+            attributes = nodes[node]
+            G.add_node(node, **attributes)
+
+        for source, target, types in edges:
+            for type in types:
+                G.add_edge(source, target, type=type)
+
+        return G
+
+    def build_summary_graph(self):
+        nodes = {
+            "Supernode-0": dict(color="Red"),
+            "Supernode-1": dict(color="Blue"),
+            "Supernode-2": dict(color="Yellow"),
+            "Supernode-3": dict(color="Blue"),
+            "Supernode-4": dict(color="Yellow"),
+            "Supernode-5": dict(color="Red"),
+        }
+        edges = [
+            ("Supernode-1", "Supernode-2", [{"type": "Weak"}]),
+            ("Supernode-2", "Supernode-4", [{"type": "Weak"}, {"type": "Strong"}]),
+            ("Supernode-3", "Supernode-4", [{"type": "Strong"}]),
+            ("Supernode-3", "Supernode-5", [{"type": "Weak"}, {"type": "Strong"}]),
+            ("Supernode-4", "Supernode-4", [{"type": "Weak"}, {"type": "Strong"}]),
+        ]
+        G = nx.MultiGraph()
+        for node in nodes:
+            attributes = nodes[node]
+            G.add_node(node, **attributes)
+
+        for source, target, types in edges:
+            for type in types:
+                G.add_edge(source, target, type=type)
+
+        supernodes = {
+            "Supernode-0": set(["A", "B"]),
+            "Supernode-1": set(["C", "D"]),
+            "Supernode-2": set(["E", "F"]),
+            "Supernode-3": set(["G", "H"]),
+            "Supernode-4": set(["I", "J"]),
+            "Supernode-5": set(["K", "L"]),
+        }
+        nx.set_node_attributes(G, supernodes, "group")
+        return G
+
+
+class TestSNAPDirectedMulti(AbstractSNAP):
+    def build_original_graph(self):
+        nodes = {
+            "A": dict(color="Red"),
+            "B": dict(color="Red"),
+            "C": dict(color="Green"),
+            "D": dict(color="Green"),
+            "E": dict(color="Blue"),
+            "F": dict(color="Blue"),
+            "G": dict(color="Yellow"),
+            "H": dict(color="Yellow"),
+        }
+        edges = [
+            ("A", "C", ["Weak", "Strong"]),
+            ("A", "E", ["Strong"]),
+            ("A", "F", ["Weak"]),
+            ("B", "D", ["Weak", "Strong"]),
+            ("B", "E", ["Weak"]),
+            ("B", "F", ["Strong"]),
+            ("C", "G", ["Weak", "Strong"]),
+            ("C", "F", ["Strong"]),
+            ("D", "E", ["Strong"]),
+            ("D", "H", ["Weak", "Strong"]),
+            ("G", "E", ["Strong"]),
+            ("H", "F", ["Strong"]),
+        ]
+        G = nx.MultiDiGraph()
+        for node in nodes:
+            attributes = nodes[node]
+            G.add_node(node, **attributes)
+
+        for source, target, types in edges:
+            for type in types:
+                G.add_edge(source, target, type=type)
+
+        return G
+
+    def build_summary_graph(self):
+        nodes = {
+            "Supernode-0": dict(color="Red"),
+            "Supernode-1": dict(color="Blue"),
+            "Supernode-2": dict(color="Yellow"),
+            "Supernode-3": dict(color="Blue"),
+        }
+        edges = [
+            ("Supernode-0", "Supernode-1", ["Weak", "Strong"]),
+            ("Supernode-0", "Supernode-2", ["Weak", "Strong"]),
+            ("Supernode-1", "Supernode-2", ["Strong"]),
+            ("Supernode-1", "Supernode-3", ["Weak", "Strong"]),
+            ("Supernode-3", "Supernode-2", ["Strong"]),
+        ]
+        G = nx.MultiDiGraph()
+        for node in nodes:
+            attributes = nodes[node]
+            G.add_node(node, **attributes)
+
+        for source, target, types in edges:
+            for type in types:
+                G.add_edge(source, target, type=type)
+
+        supernodes = {
+            "Supernode-0": set(["A", "B"]),
+            "Supernode-1": set(["C", "D"]),
+            "Supernode-2": set(["E", "F"]),
+            "Supernode-3": set(["G", "H"]),
+        }
+        nx.set_node_attributes(G, supernodes, "group")
+        return G