Repository: LLNL/hatchet

Issue:
To_Literal Generates a Tree with Duplicate Nodes from Graph
There exists a problem with to_literal where nodes with multiple parents, and cycles are duplicated and not recognized as the same node when read in by another program. See this example of the following outputs of the same graphs. 

![To Literal](https://user-images.githubusercontent.com/10066043/90822397-3acd1e80-e2e9-11ea-9e17-d9af5855c179.png)
![To dot](https://user-images.githubusercontent.com/10066043/90822398-3acd1e80-e2e9-11ea-8cf5-0982cdbd1f3d.png)

The fix for this should be to write out node-ids with each node and ensure that a reader looks for them.

Discussion:
bhatele: We should make sure that this works if we hit the a node with duplicate first and then the "first" clone of the node.
slabasan: Agreed, that'll be a good test, I'll work on adding that as well.

Patch:
diff --git a/docs/index.rst b/docs/index.rst
index 6d127a6..814134c 100644
--- a/docs/index.rst
+++ b/docs/index.rst
@@ -64,6 +64,12 @@ following `paper <http://www.cs.umd.edu/~bhatele/pubs/pdf/2019/sc2019.pdf>`_:
 
    basic_tutorial
 
+.. toctree::
+    :maxdepth: 2
+    :caption: Reference
+
+    publications
+
 .. toctree::
    :maxdepth: 2
    :caption: API Docs
diff --git a/docs/publications.rst b/docs/publications.rst
new file mode 100644
index 0000000..513b03f
--- /dev/null
+++ b/docs/publications.rst
@@ -0,0 +1,27 @@
+.. Copyright 2020 Lawrence Livermore National Security, LLC and other
+   Hatchet Project Developers. See the top-level LICENSE file for details.
+
+   SPDX-License-Identifier: MIT
+
+******************************
+Publications and Presentations
+******************************
+
+Publications
+============
+
+- Stephanie Brink, Ian Lumsden, Connor Scully-Allison, Katy Williams, Olga Pearce, Todd Gamblin, Michela Taufer, Katherine Isaacs, Abhinav Bhatele. `Usability and Performance Improvements in Hatchet <https://pssg.cs.umd.edu/assets/papers/2020-11-hatchet-protools.pdf>`_. Presented at the `ProTools 2020 Workshop <https://protools20.github.io/>`_, held in conjunction with the International Conference for High Performance Computing, Networking, Storage and Analysis (SC '20), held virtually.
+
+- Abhinav Bhatele, Stephanie Brink, and Todd Gamblin. `Hatchet: Pruning the Overgrowth in Parallel Profiles <https://doi.org/10.1145/3295500.3356219>`_. In Proceedings of the International Conference for High Performance Computing, Networking, Storage and Analysis (SC '19), Denver, CO.
+
+Posters
+=======
+
+- Ian Lumsden. `Graph-Based Profiling Analysis using Hatchet <https://globalcomputing.group/assets/img/sc20/posters/ian.pdf>`_. Presented at SC '20. `Slides <https://globalcomputing.group/assets/img/sc20/bestposters/ian.pdf>`_ | `Video Presentation <https://www.youtube.com/watch?v=j-FRGnLBo4U&feature=youtu.be>`_
+
+- Suraj P. Kesavan, Harsh Bhatia, Abhinav Bhatele, Stephanie Brink, Olga Pearce, Todd Gamblin, Peer-Timo Bremer, and Kwan-Liu Ma. `Scalable Comparative Visualization of Ensembles of Call Graphs Using CallFlow`. Presented at SC '20.
+
+Tutorials
+=========
+
+- Performance Analysis using Hatchet, LLNL, July 29/31, 2020.
diff --git a/hatchet/graphframe.py b/hatchet/graphframe.py
index 083ce58..8be16b8 100644
--- a/hatchet/graphframe.py
+++ b/hatchet/graphframe.py
@@ -134,116 +134,11 @@ class GraphFrame:
 
     @staticmethod
     def from_literal(graph_dict):
-        """Create a GraphFrame from a list of dictionaries.
-
-        TODO: calculate inclusive metrics automatically.
-
-        Example:
-
-        .. code-block:: console
-
-            dag_ldict = [
-                {
-                    "name": "A",
-                    "type": "function",
-                    "metrics": {"time (inc)": 130.0, "time": 0.0},
-                    "children": [
-                        {
-                            "name": "B",
-                            "type": "function",
-                            "metrics": {"time (inc)": 20.0, "time": 5.0},
-                            "children": [
-                                {
-                                    "name": "C",
-                                    "type": "function",
-                                    "metrics": {"time (inc)": 5.0, "time": 5.0},
-                                    "children": [
-                                        {
-                                            "name": "D",
-                                            "type": "function",
-                                            "metrics": {"time (inc)": 8.0, "time": 1.0},
-                                        }
-                                    ],
-                                }
-                            ],
-                        },
-                        {
-                            "name": "E",
-                            "type": "function",
-                            "metrics": {"time (inc)": 55.0, "time": 10.0},
-                            "children": [
-                                {
-                                    "name": "H",
-                                    "type": "function",
-                                    "metrics": {"time (inc)": 1.0, "time": 9.0}
-                                }
-                            ],
-                        },
-                    ],
-                }
-            ]
-
-        Return:
-            (GraphFrame): graphframe containing data from dictionaries
-        """
-
-        def parse_node_literal(child_dict, hparent):
-            """Create node_dict for one node and then call the function
-            recursively on all children.
-            """
-
-            hnode = Node(
-                Frame({"name": child_dict["name"], "type": child_dict["type"]}), hparent
-            )
-
-            node_dicts.append(
-                dict(
-                    {"node": hnode, "name": child_dict["name"]}, **child_dict["metrics"]
-                )
-            )
-            hparent.add_child(hnode)
-
-            if "children" in child_dict:
-                for child in child_dict["children"]:
-                    parse_node_literal(child, hnode)
-
-        list_roots = []
-        node_dicts = []
-
-        # start with creating a node_dict for each root
-        for i in range(len(graph_dict)):
-            graph_root = Node(
-                Frame({"name": graph_dict[i]["name"], "type": graph_dict[i]["type"]}),
-                None,
-            )
-
-            node_dict = {"node": graph_root, "name": graph_dict[i]["name"]}
-            node_dict.update(**graph_dict[i]["metrics"])
-            node_dicts.append(node_dict)
-
-            list_roots.append(graph_root)
-
-            # call recursively on all children of root
-            if "children" in graph_dict[i]:
-                for child in graph_dict[i]["children"]:
-                    parse_node_literal(child, graph_root)
-
-        graph = Graph(list_roots)
-        graph.enumerate_traverse()
-
-        exc_metrics = []
-        inc_metrics = []
-        for key in graph_dict[i]["metrics"].keys():
-            if "(inc)" in key:
-                inc_metrics.append(key)
-            else:
-                exc_metrics.append(key)
-
-        dataframe = pd.DataFrame(data=node_dicts)
-        dataframe.set_index(["node"], inplace=True)
-        dataframe.sort_index(inplace=True)
+        """Create a GraphFrame from a list of dictionaries."""
+        # import this lazily to avoid circular dependencies
+        from .readers.literal_reader import LiteralReader
 
-        return GraphFrame(graph, dataframe, exc_metrics, inc_metrics)
+        return LiteralReader(graph_dict).read()
 
     @staticmethod
     def from_lists(*lists):
diff --git a/hatchet/readers/literal_reader.py b/hatchet/readers/literal_reader.py
new file mode 100644
index 0000000..c7a6a7e
--- /dev/null
+++ b/hatchet/readers/literal_reader.py
@@ -0,0 +1,147 @@
+# Copyright 2017-2020 Lawrence Livermore National Security, LLC and other
+# Hatchet Project Developers. See the top-level LICENSE file for details.
+#
+# SPDX-License-Identifier: MIT
+
+import pandas as pd
+
+import hatchet.graphframe
+from hatchet.node import Node
+from hatchet.graph import Graph
+from hatchet.frame import Frame
+
+
+class LiteralReader:
+    """Create a GraphFrame from a list of dictionaries.
+
+    TODO: calculate inclusive metrics automatically.
+
+    Example:
+
+    .. code-block:: console
+
+        dag_ldict = [
+            {
+                "name": "A",
+                "type": "function",
+                "metrics": {"time (inc)": 130.0, "time": 0.0},
+                "children": [
+                    {
+                        "name": "B",
+                        "type": "function",
+                        "metrics": {"time (inc)": 20.0, "time": 5.0},
+                        "children": [
+                            {
+                                "name": "C",
+                                "type": "function",
+                                "metrics": {"time (inc)": 5.0, "time": 5.0},
+                                "children": [
+                                    {
+                                        "name": "D",
+                                        "type": "function",
+                                        "metrics": {"time (inc)": 8.0, "time": 1.0},
+                                    }
+                                ],
+                            }
+                        ],
+                    },
+                    {
+                        "name": "E",
+                        "type": "function",
+                        "metrics": {"time (inc)": 55.0, "time": 10.0},
+                        "children": [
+                            {
+                                "name": "H",
+                                "type": "function",
+                                "metrics": {"time (inc)": 1.0, "time": 9.0}
+                            }
+                        ],
+                    },
+                ],
+            }
+        ]
+
+    Return:
+        (GraphFrame): graphframe containing data from dictionaries
+    """
+
+    def __init__(self, graph_dict):
+        """Read from list of dictionaries.
+
+        graph_dict (dict): List of dictionaries encoding nodes.
+        """
+        self.graph_dict = graph_dict
+
+    def parse_node_literal(self, frame_to_node_dict, node_dicts, child_dict, hparent):
+        """Create node_dict for one node and then call the function
+        recursively on all children.
+        """
+        frame = None
+        if "duplicate" not in child_dict:
+            frame = Frame({"name": child_dict["name"]})
+            hnode = Node(frame, hparent)
+
+            node_dict = dict(
+                {"node": hnode, "name": child_dict["name"]}, **child_dict["metrics"]
+            )
+
+            node_dicts.append(node_dict)
+            frame_to_node_dict[frame] = hnode
+        elif "duplicate" in child_dict:
+            frame = Frame({"name": child_dict["name"]})
+            hnode = frame_to_node_dict.get(frame)
+            if not hnode:
+                hnode = Node(frame, hparent)
+                node_dict = dict(
+                    {"node": hnode, "name": child_dict["name"]}, **child_dict["metrics"]
+                )
+                node_dicts.append(node_dict)
+                frame_to_node_dict[frame] = hnode
+
+        hparent.add_child(hnode)
+
+        if "children" in child_dict:
+            for child in child_dict["children"]:
+                self.parse_node_literal(frame_to_node_dict, node_dicts, child, hnode)
+
+    def read(self):
+        list_roots = []
+        node_dicts = []
+        frame_to_node_dict = {}
+        frame = None
+
+        # start with creating a node_dict for each root
+        for i in range(len(self.graph_dict)):
+            frame = Frame({"name": self.graph_dict[i]["name"]})
+            graph_root = Node(frame, None)
+
+            node_dict = {"node": graph_root, "name": self.graph_dict[i]["name"]}
+            node_dict.update(**self.graph_dict[i]["metrics"])
+            node_dicts.append(node_dict)
+
+            list_roots.append(graph_root)
+            frame_to_node_dict[frame] = graph_root
+
+            # call recursively on all children of root
+            if "children" in self.graph_dict[i]:
+                for child in self.graph_dict[i]["children"]:
+                    self.parse_node_literal(
+                        frame_to_node_dict, node_dicts, child, graph_root
+                    )
+
+        graph = Graph(list_roots)
+        graph.enumerate_traverse()
+
+        exc_metrics = []
+        inc_metrics = []
+        for key in self.graph_dict[i]["metrics"].keys():
+            if "(inc)" in key:
+                inc_metrics.append(key)
+            else:
+                exc_metrics.append(key)
+
+        dataframe = pd.DataFrame(data=node_dicts)
+        dataframe.set_index(["node"], inplace=True)
+        dataframe.sort_index(inplace=True)
+
+        return hatchet.graphframe.GraphFrame(graph, dataframe, exc_metrics, inc_metrics)


Test patch:
diff --git a/hatchet/tests/caliper.py b/hatchet/tests/caliper.py
index d30e40c..27f518c 100644
--- a/hatchet/tests/caliper.py
+++ b/hatchet/tests/caliper.py
@@ -195,4 +195,6 @@ def test_graphframe_to_literal(lulesh_caliper_json):
     gf = GraphFrame.from_caliper_json(str(lulesh_caliper_json))
     graph_literal = gf.to_literal()
 
-    assert len(graph_literal) == len(gf.graph.roots)
+    gf2 = GraphFrame.from_literal(graph_literal)
+
+    assert len(gf.graph) == len(gf2.graph)
diff --git a/hatchet/tests/conftest.py b/hatchet/tests/conftest.py
index ffbbf55..71a9634 100644
--- a/hatchet/tests/conftest.py
+++ b/hatchet/tests/conftest.py
@@ -717,3 +717,124 @@ def mock_dag_literal_module_more_complex():
     ]
 
     return dag_ldict
+
+
+@pytest.fixture
+def mock_graph_literal_duplicates():
+    """Creates a mock tree with duplicate nodes."""
+    graph_dict = [
+        {
+            "name": "a",
+            "type": "function",
+            "metrics": {"time (inc)": 130.0, "time": 0.0},
+            "children": [
+                {
+                    "name": "b",
+                    "type": "function",
+                    "metrics": {"time (inc)": 20.0, "time": 5.0},
+                    "children": [
+                        {
+                            "name": "d",
+                            "type": "function",
+                            "metrics": {"time (inc)": 20.0, "time": 5.0},
+                            "children": [
+                                {
+                                    "name": "e",
+                                    "type": "function",
+                                    "metrics": {"time (inc)": 20.0, "time": 5.0},
+                                },
+                                {
+                                    "name": "f",
+                                    "type": "function",
+                                    "metrics": {"time (inc)": 20.0, "time": 5.0},
+                                },
+                            ],
+                        }
+                    ],
+                },
+                {
+                    "name": "c",
+                    "type": "function",
+                    "metrics": {"time (inc)": 20.0, "time": 5.0},
+                    "children": [
+                        {
+                            "name": "a",
+                            "duplicate": "True",
+                            "type": "function",
+                            "metrics": {"time (inc)": 20.0, "time": 5.0},
+                        },
+                        {
+                            "name": "d",
+                            "duplicate": "True",
+                            "type": "function",
+                            "metrics": {"time (inc)": 20.0, "time": 5.0},
+                        },
+                    ],
+                },
+            ],
+        }
+    ]
+
+    return graph_dict
+
+
+@pytest.fixture
+def mock_graph_literal_duplicate_first():
+    """Creates a mock tree with node with duplicate first."""
+    graph_dict = [
+        {
+            "name": "a",
+            "duplicate": True,
+            "type": "function",
+            "metrics": {"time (inc)": 130.0, "time": 0.0},
+            "children": [
+                {
+                    "name": "b",
+                    "duplicate": True,
+                    "type": "function",
+                    "metrics": {"time (inc)": 20.0, "time": 5.0},
+                    "children": [
+                        {
+                            "name": "d",
+                            "duplicate": True,
+                            "type": "function",
+                            "metrics": {"time (inc)": 20.0, "time": 5.0},
+                            "children": [
+                                {
+                                    "name": "e",
+                                    "type": "function",
+                                    "metrics": {"time (inc)": 20.0, "time": 5.0},
+                                },
+                                {
+                                    "name": "f",
+                                    "type": "function",
+                                    "metrics": {"time (inc)": 20.0, "time": 5.0},
+                                },
+                            ],
+                        }
+                    ],
+                },
+                {
+                    "name": "c",
+                    "type": "function",
+                    "metrics": {"time (inc)": 20.0, "time": 5.0},
+                    "children": [
+                        {
+                            "name": "a",
+                            "duplicate": "True",
+                            "type": "function",
+                            "metrics": {"time (inc)": 20.0, "time": 5.0},
+                        },
+                        {
+                            "name": "d",
+                            "duplicate": "True",
+                            "type": "function",
+                            "metrics": {"time (inc)": 20.0, "time": 5.0},
+                        },
+                    ],
+                },
+            ],
+        }
+    ]
+
+    return graph_dict
diff --git a/hatchet/tests/graph_literal.py b/hatchet/tests/graph_literal.py
index 09f39cd..837a90e 100644
--- a/hatchet/tests/graph_literal.py
+++ b/hatchet/tests/graph_literal.py
@@ -17,4 +17,25 @@ def test_graphframe_to_literal(mock_graph_literal):
     gf = GraphFrame.from_literal(mock_graph_literal)
     graph_literal = gf.to_literal()
 
-    assert len(graph_literal) == len(mock_graph_literal) == len(gf.graph.roots)
+    test_literal_output = gf.from_literal(graph_literal)
+
+    assert len(test_literal_output.graph.roots) == len(gf.graph.roots)
+    assert len(test_literal_output.graph) == len(gf.graph)
+
+
+def test_with_duplicates(mock_graph_literal_duplicates):
+    gf = GraphFrame.from_literal(mock_graph_literal_duplicates)
+
+    assert len(gf.graph) == 6
+
+    graph_literal = gf.to_literal()
+    assert mock_graph_literal_duplicates.sort() == graph_literal.sort()
+
+
+def test_with_duplicate_in_first_node(mock_graph_literal_duplicate_first):
+    gf = GraphFrame.from_literal(mock_graph_literal_duplicate_first)
+
+    assert len(gf.graph) == 6
+
+    graph_literal = gf.to_literal()
+    assert mock_graph_literal_duplicate_first.sort() == graph_literal.sort()
diff --git a/hatchet/tests/graphframe.py b/hatchet/tests/graphframe.py
index 67e644e..ff859f6 100644
--- a/hatchet/tests/graphframe.py
+++ b/hatchet/tests/graphframe.py
@@ -976,11 +976,11 @@ def test_output_with_cycle_graphs():
     assert "d" in a_c_children
     assert "d" in a_b_children
 
-    # check certian edges are in dot
+    # check certain edges are in dot
     for edge in dot_edges:
         assert edge in dotout
 
-    # check that a certian number of occurences
+    # check that a certain number of occurences
     # of same node are in tree indicating multiple
     # edges
     assert treeout.count("a") == 2
diff --git a/hatchet/tests/hpctoolkit.py b/hatchet/tests/hpctoolkit.py
index 25f6766..98a0c98 100644
--- a/hatchet/tests/hpctoolkit.py
+++ b/hatchet/tests/hpctoolkit.py
@@ -198,11 +198,15 @@ def test_graphframe_to_literal(data_dir, calc_pi_hpct_db):
     gf = GraphFrame.from_hpctoolkit(str(calc_pi_hpct_db))
     graph_literal = gf.to_literal()
 
-    assert len(graph_literal) == len(gf.graph.roots)
+    gf2 = GraphFrame.from_literal(graph_literal)
+
+    assert len(gf.graph) == len(gf2.graph)
 
 
 def test_graphframe_to_literal_with_threads(data_dir, osu_allgather_hpct_db):
     gf = GraphFrame.from_hpctoolkit(str(osu_allgather_hpct_db))
     graph_literal = gf.to_literal()
 
-    assert len(graph_literal) == len(gf.graph.roots)
+    gf2 = GraphFrame.from_literal(graph_literal)
+
+    assert len(gf.graph) == len(gf2.graph)
diff --git a/hatchet/tests/pyinstrument.py b/hatchet/tests/pyinstrument.py
index 3eb6e30..9bef9a4 100644
--- a/hatchet/tests/pyinstrument.py
+++ b/hatchet/tests/pyinstrument.py
@@ -117,4 +117,6 @@ def test_graphframe_to_literal(hatchet_pyinstrument_json):
     gf = GraphFrame.from_pyinstrument(str(hatchet_pyinstrument_json))
     graph_literal = gf.to_literal()
 
-    assert len(graph_literal) == len(gf.graph.roots)
+    gf2 = GraphFrame.from_literal(graph_literal)
+
+    assert len(gf.graph) == len(gf2.graph)