import marimo

__generated_with = "0.25.0"
app = marimo.App()


@app.cell
def _():
    import marimo as mo

    return (mo,)


@app.cell(hide_code=True)
def _(mo):
    mo.md(r"""
    # Higher-Order Models for Time-Respecting Paths in Temporal Graphs

    ## Prerequisites

    First, we need to set up our Python environment that has PyTorch, PyTorch Geometric and PathpyG installed. Depending on where you are executing this notebook, this might already be (partially) done. E.g. Google Colab has PyTorch installed by default so we only need to install the remaining dependencies. The DevContainer that is part of our GitHub Repository on the other hand already has all of the necessary dependencies installed.

    In the following, we install the packages for usage in Google Colab using Jupyter magic commands. For other environments comment in or out the commands as necessary. For more details on how to install `pathpyG` especially if you want to install it with GPU-support, we refer to our [documentation](https://www.pathpy.net/dev/getting_started/). Note that `%%capture` discards the full output of the cell to not clutter this tutorial with unnecessary installation details. If you want to print the output, you can comment `%%capture` out.
    """)
    return


@app.cell
def _():
    # magic command not supported in marimo; please file an issue to add support
    # %%capture
    # # !pip install torch
    # # !pip install torch_geometric
    # # !pip install git+https://github.com/pathpy/pathpyG.git
    return


@app.cell(hide_code=True)
def _(mo):
    mo.md(r"""
    ## Motivation and Learning Objectives

    In the tutorial on paths and higher-order models, we have seen how we can use higher-order models to model paths in complex networks. In this example, paths were directly given in terms of sequences of nodes traversed by some process (like a random walk). We have further seen that higher-order De Bruijn graph models can be used to capture patterns that influence the **causal topology** of a complex network, i.e. which nodes can possibly influence each other via paths. The same is true for time-respecting paths in a temporal graph. Due to the fact that time-stamped edges need to occur in the correct temporal ordering (and within a given time interval based on the maximum time difference $\delta$), the causal topology given by time-respecting paths can be very different from what we would expect from the (static) topology of links.

    In the following, we will show how we can easily and efficiently construct higher-order models for time-respecting paths in a temporal graph. To illustrate this, we use the same toy example as in [Time-Respecting Paths, Centralities and Communities](../trp_centralities_communities/):
    """)
    return


@app.cell
def _():
    import pathpyG as pp

    return (pp,)


@app.cell
def _(pp):
    tedges = [('a', 'b', 1),('a', 'b', 2), ('b', 'a', 3), ('b', 'c', 3), ('d', 'c', 4), ('a', 'b', 4), ('c', 'b', 4),
                  ('c', 'd', 5), ('b', 'a', 5), ('c', 'b', 6)]
    t = pp.TemporalGraph.from_edge_list(tedges)
    print(t)
    return (t,)


@app.cell(hide_code=True)
def _(mo):
    mo.md(r"""
    In [Time-Respecting Paths, Centralities and Communities](../trp_centralities_communities/), we have used a directed acyclic event graph to enumerate all time-respecting paths in this temporal graph. For $\delta=1$, there are six different time-respecting paths of length one (i.e. the six edges), six different time-respecting paths of length two (where $a \rightarrow b \rightarrow a$ occurs twice), four time-respecting paths of length three, and two time-respecting paths of length four.
    """)
    return


@app.cell(hide_code=True)
def _(mo):
    mo.md(r"""
    As you can see, these time-respecting paths are actually very similar to the paths data that we have previously represented using the `PathData` object. In fact, we could - in theory - first extract all time-respecting paths of all lengths, add them to a `PathData` object and then use the `MultiOrderModel` class to generate higher-order De Bruijn graph models of all orders. In the example above, since we have paths of length one to four, we could create higher-order models with orders from one to four.

    However, this approach would not be efficient for large temporal graphs, as it is computationally expensive to calculate all possible time-respecting paths as well as subpaths of length $k$, especially for larger values of $\delta$. To avoid this bottleneck, `pathpyG` uses a smarter, GPU-based algorithm to calculate time-respecting paths of length $k$ that are needed for a given order $k$, starting from the event graph introduced in [Event Graphs](../event_graphs/).

    For the example above, we can generate all higher-order models up to order four as follows:
    """)
    return


@app.cell
def _(pp, t):
    m = pp.MultiOrderModel.from_temporal_graph(t, delta=1, max_order=4)

    print(m.layers[3])
    print(m.layers[4])
    return (m,)


@app.cell(hide_code=True)
def _(mo):
    mo.md(r"""
    Each layer `m.layers[k]` is a `HigherOrderGraph`, which we have introduced in [Working with Higher-Order De Bruijn Graphs](../higher_order_graphs/). This is why printing a layer shows its order as well as the number of first-order nodes from which its higher-order nodes are built. Remember that in a $k$-th order model nodes capture paths of length $k-1$, while edges capture paths of length $k$.

    This implies that the first-order model has four nodes and six edges, which simply corresponds to the time-aggregated weighted graph for our example temporal network.
    """)
    return


@app.cell
def _(m, pp):
    print(m.layers[1])
    pp.plot(m.layers[1]);
    return


@app.cell(hide_code=True)
def _(mo):
    mo.md(r"""
    For the second-order model, we have six nodes, which map to the six different edges (each edge trivially being a time-respecting path of length one) of the temporal graph. The six edges in the second-order model represent the six different time-respecting paths of length two (see above). Since the time-respecting path $a \rightarrow b \rightarrow a$  occurs twice at different times, we have one edge with weight two.
    """)
    return


@app.cell
def _(m, pp):
    print(m.layers[2])
    print(m.layers[2].data.edge_weight)
    pp.plot(m.layers[2]);
    return


@app.cell(hide_code=True)
def _(mo):
    mo.md(r"""
    For the third-oder mode, we have four edges representing the four different time-respecting paths of length three in the temporal graph above:
    """)
    return


@app.cell
def _(m, pp):
    print(m.layers[3])
    pp.plot(m.layers[3]);
    return


@app.cell(hide_code=True)
def _(mo):
    mo.md(r"""
    And finally, for the model with order $k=4$ we only have two edges, representing the two time-respecting paths $a \rightarrow b \rightarrow a \rightarrow b \rightarrow a$ and $a \rightarrow b \rightarrow c \rightarrow b \rightarrow a$:
    """)
    return


@app.cell
def _(m, pp):
    print(m.layers[4])
    pp.plot(m.layers[4]);
    return


@app.cell(hide_code=True)
def _(mo):
    mo.md(r"""
    Intuitively, since in our example there are no time-respecting paths longer than four, if we were to generate a multi-order model with De Bruijn graphs with orders larger than four, those graphs cannot contain any edges. We see this in the following example. The first-order graph is simply the time-aggregated weighted graph, i.e. the number of nodes is equal to the number of nodes in the temporal graph and the number of edges is equal to the number of different time-stamped edges. In each graph of order $k>1$, the number of nodes corresponds to the number of edges in the graph with order $k-1$, since each of those nodes corresponds to a time-respecting path of length $k-1$, which are represented by edges in a $k-1$-th order graph. This implies that the graph with order five has two nodes, which are the two time-respecting paths of length four. Those nodes are not connected since there is no time-respecting path with length five.
    """)
    return


@app.cell
def _(pp, t):
    m_1 = pp.MultiOrderModel.from_temporal_graph(t, delta=1, max_order=5)
    print(m_1.layers[4])
    print(m_1.layers[5])
    pp.plot(m_1.layers[5]);
    return (m_1,)


@app.cell(hide_code=True)
def _(mo):
    mo.md(r"""
    If we only need a single order $k$, we can directly create the corresponding `HigherOrderGraph` using the class method `HigherOrderGraph.from_temporal_graph`. Note that each call constructs all lower orders internally, so if we need several orders, it is more efficient to create a `MultiOrderModel` once and access its layers. For the third-order model of our example, we obtain the six different time-respecting paths of length two as nodes and the four time-respecting paths of length three as edges:
    """)
    return


@app.cell
def _(pp, t):
    g3 = pp.HigherOrderGraph.from_temporal_graph(t, order=3, delta=1)
    print(g3)
    print(g3.nodes)
    return


@app.cell(hide_code=True)
def _(mo):
    mo.md(r"""
    ## Constructing Higher-Order De Bruijn Graph Models for Empirical Temporal Networks

    Let us now use `pathpyG` to construct higher-order De Bruijn graph models for time-respecting paths in empirical temporal networks. For this, we first read a number of temporal graphs using `pp.io.read_csv_temporal_graph`. In the following, we use the following three publicly available data sets:

    - Antenna interactions between ants in a colony [(Blonder and Dornhaus, 2011)](https://pubmed.ncbi.nlm.nih.gov/21625450/)
    - E-Mail exchanges in a manufacturing company [(Nurek and Michalski, 2020)](https://www.ii.pwr.edu.pl/~michalski/index.php?content=datasets)
    - Face-to-face interactions in a highschool [(Mastrandrea, Fournet, Barrat, 2015)](http://www.sociopatterns.org/datasets/high-school-contact-and-friendship-networks/)
    """)
    return


@app.cell
def _(pp):
    t_ants = pp.io.read_csv_temporal_graph(pp.io.example_data('ants_1_1.tedges'), header=False)
    print(t_ants)
    return (t_ants,)


@app.cell
def _(pp):
    t_email = pp.io.read_csv_temporal_graph(pp.io.example_data('manufacturing_email.tedges'), header=False)
    print(t_email)
    return (t_email,)


@app.cell
def _(pp):
    t_sp = pp.io.read_csv_temporal_graph(pp.io.example_data('sociopatterns_highschool_2013.tedges'), header=False)
    print(t_sp)
    return (t_sp,)


@app.cell(hide_code=True)
def _(mo):
    mo.md(r"""
    To generate a `MultiOrderModel` consisting of multiple layers of higher-order De Bruijn graph models, we can use the `MultiOrderModel.from_temporal_graph` method. We can further specify the maximum order of the highest-order layer, as well as the maximum time difference $\delta$ for time-respecting paths.

    For the ants, we consider time-respecting paths with a maximum time difference of 30 seconds up to length four. Since we want to compare this to a smaller maximum time difference of 20 seconds below, we first construct an `EventGraph` (see [Event Graphs](../event_graphs/)), from which we can create a `MultiOrderModel` using `MultiOrderModel.from_event_graph`:
    """)
    return


@app.cell
def _(mo, pp, t_ants):
    # Hide the progress output
    with mo.capture_stdout(), mo.capture_stderr():
        eg_ants = pp.EventGraph.from_temporal_graph(t_ants, delta=30)
    m_2 = pp.MultiOrderModel.from_event_graph(eg_ants, max_order=4)
    print(m_2.layers[1])
    print(m_2.layers[2])
    print(m_2.layers[3])
    print(m_2.layers[4])
    return (eg_ants,)


@app.cell(hide_code=True)
def _(mo):
    mo.md(r"""
    Rather than constructing the time-respecting paths for a maximum time difference of 20 seconds from scratch, we can reduce the maximum time difference of the existing event graph. The resulting higher-order models have fewer edges, since fewer pairs of interactions are close enough in time to form a time-respecting path:
    """)
    return


@app.cell
def _(eg_ants, pp):
    m_2_20 = pp.MultiOrderModel.from_event_graph(eg_ants.reduce_delta(10), max_order=4)
    print(m_2_20.layers[2])
    print(m_2_20.layers[4])
    return


@app.cell(hide_code=True)
def _(mo):
    mo.md(r"""
    For the E-Mail communication network, we use time-respecting paths up to length four with a maximum time difference of one hour. Note that the timestamps in this data set are given in microseconds rather than seconds, so we scale $\delta$ accordingly.
    """)
    return


@app.cell
def _(pp, t_email):
    m_3 = pp.MultiOrderModel.from_temporal_graph(t_email, delta=3600 * 1000000, max_order=4)
    print(m_3.layers[1])
    print(m_3.layers[2])
    print(m_3.layers[3])
    print(m_3.layers[4])
    return


@app.cell(hide_code=True)
def _(mo):
    mo.md(r"""
    And finally, for the largest data set from the Sociopatterns collaboration, we use a maximum time difference of 15 minutes. As you can see below, we can efficiently generate a 5-th order model despite using a temporal graph with more than 188,000 time-stamped edges and considering all time-respecting paths up to length five with a large maximum time difference. Thanks to the use of GPU-accelerated operations, creating such a model takes less than 12 seconds on an (old) RTX 2080 GPU.
    """)
    return


@app.cell
def _(pp, t_sp):
    m_4 = pp.MultiOrderModel.from_temporal_graph(t_sp, delta=900, max_order=5)
    print(m_4.layers[1])
    print(m_4.layers[5])
    return


@app.cell(hide_code=True)
def _(mo):
    mo.md(r"""
    How can we use such higher-order graph models for graph learning tasks? We will demonstrate this in the tutorials on causality-aware temporal graph learning, e.g. [De Bruijn Graph Neural Networks](../dbgnn/).
    """)
    return


if __name__ == "__main__":
    app.run()