Skip to content

Instantly share code, notes, and snippets.

@inscapist

inscapist/gist:143cddbe08c0c17418893ba147ab1b3f

Forked from lirenlin/gist:013bc9fae7acfc48cc92cf40993cc772
Created July 5, 2024 14:53
Show Gist options

  • Select an option

    Learn more about clone URLs
  • Save inscapist/143cddbe08c0c17418893ba147ab1b3f to your computer and use it in GitHub Desktop.

Select an option

Learn more about clone URLs
Save inscapist/143cddbe08c0c17418893ba147ab1b3f to your computer and use it in GitHub Desktop.
Download ZIP

Revisions

  1. @lirenlin lirenlin revised this gist Apr 8, 2018. 1 changed file with 5 additions and 0 deletions.
    5 changes: 5 additions & 0 deletions gistfile1.txt
    View file
    Original file line number Diff line number Diff line change
    @@ -17,4 +17,9 @@ topological ordering/sorting is a concept for directed graph which has no direct
    Travesal method is for graph. This includes tree as it is a rectricted form of graph.
    RPO (Reverse Post Order) of a DAG has another name: topological sort.

    tree edge
    back edge
    forward edge
    cross edge

    https://eli.thegreenplace.net/2015/directed-graph-traversal-orderings-and-applications-to-data-flow-analysis/
  2. @lirenlin lirenlin created this gist Apr 5, 2018.
    20 changes: 20 additions & 0 deletions gistfile1.txt
    View file
    Original file line number Diff line number Diff line change
    @@ -0,0 +1,20 @@
    A Tree is just a restricted form of a Graph.

    Trees have direction (parent / child relationships) and don't contain cycles.
    It has only one path between any two vertices

    They fit with in the category of Directed Acyclic Graphs (or a DAG).
    So Trees are DAGs with the restriction that a child can only have one parent.

    Directed Acyclic Graphs is a kind of directed graph that have no cycles.

    DFS will create a spanning tree of a graph. So does flooding.

    control-flow graph --> DFS --> spanning tree --> tree travesal (pre-order, post-order, in-order)
    CFG may contains loops, nodes with multiple incoming path.

    topological ordering/sorting is a concept for directed graph which has no directed cycles, that is, DAG.
    Travesal method is for graph. This includes tree as it is a rectricted form of graph.
    RPO (Reverse Post Order) of a DAG has another name: topological sort.

    https://eli.thegreenplace.net/2015/directed-graph-traversal-orderings-and-applications-to-data-flow-analysis/