21
$\begingroup$

We have been reading about algorithms for MST, strong-connectivity, routing, etc. in directed graphs.

Also recently people have been doing research for dynamic and fault tolerant algorithms for directed graphs.

But I was wondering if there are any practical applications where the underlining graph network is "Directed". Other than social-networks all problems that I could think of like rail/road network, Internet network, etc. deal with undirected graphs only.

Edit 1: I understand that these can be used to model some scenarios where links are directed but I was wondering how often these scenarios occur in real-world, and how important is study of fault tolerance for directed graphs.

Improve this question
$\endgroup$
7
  • 6
    $\begingroup$ Two of the most famous classes of directed graphs in all of computer science are the tree and DAG (Directed Acyclic Graph). The tree is used in many things (e.g. family trees, hierarchies); The DAG can do more sophisticated versions of those. DAGs are used essentially whenever you have a set of entities that have dependencies on one another. When your problem has a "time" or "step-by-step" component, directedness represents that inexorable march of progress. You see DAGs in such things as flowchart diagrams, package management software and compilers' intermediate-representation SSA forms. $\endgroup$
    – Iwillnotexist Idonotexist
    Commented Jan 2, 2017 at 11:02
  • 2
    $\begingroup$ OK, what's your actual question? Do you want to know why directed graphs are important or why fault tolerance in directed graphs is important? Those are two completely separate questions. $\endgroup$
    – David Richerby
    Commented Jan 2, 2017 at 16:32
  • 2
    $\begingroup$ Your examples, while physically "undirected" in implementation, still frequently have directed graphs operating logically over them. For instance, trains do not travel bidirectionally - they go one way, or the other, on a schedule. Let's say one doesn't schedule the trains, but only schedules passengers. Then, that person is interested in a directed graph, despite the arbitrary fact that trains can theoretically travel either way on a rail. $\endgroup$
    – Darren Ringer
    Commented Jan 2, 2017 at 19:19
  • 5
    $\begingroup$ chyle: Networks can most certainly benefit from being represented by a directed graph. Most household internet connections are asymmetric. The upstream and downstream links can have completely different properties (bandwidth, latency, packet loss, etc.) $\endgroup$
    – Alexander
    Commented Jan 3, 2017 at 3:51
  • 1
    $\begingroup$ I don't know about everyone else, but my family tree is a digraph. I am not my mother's parent. $\endgroup$
    – user16765
    Commented Jan 3, 2017 at 15:53

4 Answers 4

Reset to default
38
$\begingroup$

Recalling that a directed graph is a graph where the edges have an associated direction with them.

Using a directed graph you can represent asymmetrical relationships between nodes, while in undirected graph we can represent only symmetrical relationships.

Practically, using a directed graph you can represent:

  • Road networks (using a directed graph you can represent streets' direction);
  • hyperlinks connecting web pages;
  • dependencies in software modules;
  • prey-predator relationships;
  • deterministic finite automaton.

Besides these classical examples, you can depict many other real-world scenarios (financial trade, scheduling, infectious disease, citation, control flow, etc) that needs an ordered relationship [1].

Improve this answer
$\endgroup$
4
  • 4
    $\begingroup$ Great answer. I think OP is forgetting that when you have a street, you actually have two streets (one for each direction, usually perfectly parallel). They can be represented as a simple graph, but directed graphs add essential information to the model. $\endgroup$
    – ecc
    Commented Jan 2, 2017 at 13:56
  • $\begingroup$ I like this, and I notice that this answer is careful to say hyperlink connected web pages - which excludes the use of the Back function. ;-) $\endgroup$
    – SDsolar
    Commented Jan 2, 2017 at 16:10
  • $\begingroup$ To put @ecc's comment in the vernacular, you have two nodes connected by two edges. Each edge is directed opposite to the other. It is seen often in deterministic state diagrams. For streets, it would reduce to a single edge, whether directed (one-way) or undirected. $\endgroup$
    – SDsolar
    Commented Jan 2, 2017 at 17:36
  • 4
    $\begingroup$ @ecc also, where I'm from (California), we have one way streets $\endgroup$
    – k_g
    Commented Jan 2, 2017 at 19:55
5
$\begingroup$

Directed graphs do exist. As mentioned in the comments, Directed Acyclic Graphs (DAGs), in particular, are tremendously useful in many computational tasks such as the compiling of code.

Also, its worth noting that most directed graph algorithms can be used in the undirected case simply by replacing each undirected edge with two directed edges. The dual of this, trying to make a directed graph out of an undirected graph, cannot be done for most algorithms.

Improve this answer
$\endgroup$
3
$\begingroup$

The beginnings of topological sorting (a fundamental operation on directed acyclic graphs) lie in networks of dependencies in project management, specifically the PERT method. Kahn and Lasser both cite PERT in their papers and base their examples on it, eg

A PERT network of 30,000 activities can be ordered in less than one hour of machine time.

Online job scheduling is still done with this type of network; for instance an ETL system schedules jobs to run only after the jobs that provide their input data have run.

Improve this answer
$\endgroup$
2
$\begingroup$

Answer: From the OP I deduce that the question is actually related to SDGs (Signed Directed Graphs). So here is my answer which addresses basic directed graphs then leads on to SDGs.

Directed graphs are widely utilized in fault-tree analysis in industrial systems. As you eliminate causes of a fault you follow the directed graph to explore other possibilities.

Directed graphs are utilized to prevent counterproductive revisiting of nodes which have been effectively eliminated. In fault diagnosis, often time to restoration of service is critical. In complex industrial systems there is always a parallel tree based on time which can lead to total system shutdown if the fault is not corrected within various time limitations. Going back and forth would be more likely to lead to total failure, which can cause restoration operations which are much more time-consuming (like draining tanks and pipelines in order to restart a refinery).

It is like trimming a tree branch - no need to go back to the trunk when you are trying to find a single twig.

SDGs have the additional property of giving guidance based on probabilities or thresholds in order to help make decisions as the tree is traversed.

Here is a link to a good book on the subject, called Fault Detection and Diagnosis in Industrial Systems (page 224), where it describes the benefits of SDG-based diagnosis:

https://books.google.com/books?id=KFLlBwAAQBAJ&pg=PA224

Improve this answer
$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.