Directed Graph

Directed #202204112045 or digraph recognises the ordering of vertices in a pair. This means that the edge \((u, v)\) is different from the edge \((v, u)\) as in the first case \(u\) is pointing to \(v\) and in the second case, \(v\) is pointing to \(u\) instead. It is useful to represent a dense graph.

If \((v, v)\) exists in the graph, this means that the graph is a loop.

A directed graph is acyclic if it has no cycle. Sometimes it will be referred to as DAG (Directed Acyclic Graph).

A directed graph is strongly connected if there is a path from every vertex to every other vertex. It is weakly connected if the graph is connected with the edges (strip off the direction and treat it as an 202204112129).

To calculate the shortest path for each vertex to each other vertices, see 202204141149#.

Links to this page
  • Topological Sort

    Topological sort is an algorithm that sort the vertices of a #directed acyclic graph in such that it respect the ordering of the vertices in this original graph. We could use the indegree (the incoming edges) to determine the order of the vertices.

  • Shortest-Path Algorithm

    Shortest-Path Algorithm is an algorithm that calculate the shortest path of one vertex to all other vertices in a #202204112118. The path could be unweighted or weighted. It is similar to level-order traversal. Sometimes, it is wise to 202204151111# in order to store path information for later usage.

  • Residual Graph

    Residual Graph is a #202204112118 which include #202206091453 and 202206091616#.

  • Observer Pattern

    If the updates become too complicated to handle, especially when observer is subscribing to multiple subjects, a change manager class is needed to manage the hassle so in the case when multiple subjects changes, the observer will be notified only once. Such class should be in Mediator Pattern# and Singleton Pattern#. It can be with simple approach or directed-acyclic graphs (DAG) approach. Simple change manager will update all the registered observers of each subject. DAG change manager instead handles the DAG of dependencies between subjects and their observers which is usually preferable if an observer subscribes to multiple subjects as it will update once to observer upon a change of multiple subjects.

  • Minimum Spanning Tree

    We can find the minimum #202207081445 in 202204112129# and 202204112118#. However, the solution for digraph appears to be more difficult.

  • Graph
  • Git Relative Positioning

    ^ means moving up to one commit or its nearest parent from the current commit. If followed by number, let’s say \(x\), it will point to the \(x\)th parent of the commit in the Git DAG. You can visualise it in git log --graph. This could be useful when dealing with repository that use #202204261123 often.

  • Flow Graph

    Flow Graph is a #202204112118 that depicts the networking flow. The starting node is called a source (denoted \(s\)) whereas the ending node is called a sink (denoted \(t\)). Each edge has flow value (how many have flowed through) and maximum capacity (how much can flowed through), usually written in the format flow value/maximum capacity.

  • Dijkstra’s Algorithm with Vertex Selection Rule

    #202204151059 could be used alongside with vertex selection rule, that is to select vertices in topological order# which in turn they will be declared known. It is useful on dealing with known #directed acyclic graph.

  • Depth First Search (DFS)
    If using against an #202204112129 which is not connected or #202204112118 that is not strongly connected, repeatedly call DFS on the unvisited nodes in order to visit all nodes in the graph.
  • Critical Path Analysis

    Critical Path Analysis is used to schedule project activities without delay. It is useful in variety of fields such as construction, software engineering and facility expansion. Such analysis usually displayed as a 202204112118.

  • A Review on Android Malware: Attacks, Countermeassures and Challenges

    Heavyweight static analysis uses various graph based data structures, such as API Call Graph (CG), Control Flow Graph (CFG), and Data Flow Graph (DFG), to analysis a structure of a program. API CG depicts a Directed Graph# with denotes links between callee and caller using edge. CFG represents the set of all paths traversed during program execution. DFG visualises the flow of sensitive information across the application between different entities. These techniques require heavy use of computer resources.

#graph