Talk:Directed graph

Scientific context

I feel this page does not contain enough information about the context of its subject. It is not made clear in what scientific or mathematical fields one is likely to encounter a digraph, nor is any information presented about how they are useful. 75.162.233.85 (talk) 05:56, 15 October 2008 (UTC)

I came here specifically to ask why there is nothing in the page about the uses of graphs. Finding a comment from 2008 with no replies is perplexing to say the least. Netscr1be (talk) 15:11, 30 April 2021 (UTC)

It's so huge a topic that it's difficult to know even where to begin. It's like you're on the page for real numbers and you're asking that the article say something about how numbers are used in science. —David Eppstein (talk) 16:16, 30 April 2021 (UTC)

The Use of "Arcs" instead of "Edges"

I don't know about anyone else, but most of the academic literature I have encountered uses the word "edge" instead of "arc" or "arrow". In the context of the english version, I think this makes even more sense because using the symmetric name for the set "E" is not likely to be confused with a word, unlike the set name "A" (which is easily confused with the word "a" when it is being used at the beginning of a sentence). This has even more value in improving clarity if the article includes the use of the upper-case letter to name the set and the lower-case to name an edge from the set of edges.

I have never seen the term "arrow", but I have seen "arc", especially in older literature. However, every use of "arc" I have so far encountered referred to a directed edge. I think the definition should be cleared up a bit: removing the mentions of "arrows" and "lines" (or at least "directed lines"); defining "arcs" as directed edges and removing "directed arcs". 147.229.208.56 (talk) 23:55, 12 February 2020 (UTC)

Three pieces of data?

Why is the third of these needed? Seems to me that it is superfluous; a digraph is a set of nodes, and a (multi)set of ordered pairs (arcs) node→node. I guess the nodes need to all be connected too, but that does't follow from the article, which says:

• a set V, whose elements are called vertices or nodes,
• a set A of ordered pairs of vertices, called arcs, directed edges, or arrows, and
• two maps from A to V that associate to an arc its head and its tail.

JöG (talk) 12:22, 22 November 2008 (UTC)

You are right: "two maps" is not part of the mathematical definition. Although they may appear useful in some computer representations of digraphs. Twri (talk) 00:10, 25 November 2008 (UTC)

Either you have a set A of ordered pairs of vertices, or you have just a set A plus two maps 'head' and 'tail'. The two maps GIVE each arrow a direction, namely from the head to the tail. The difference is this option (a plain set plus two maps) allows multiple (or none at all) arrows between two vertices. This gives the notion of a 'directed multigraph'.145.97.197.129 (talk) 14:19, 30 July 2010 (UTC)

definition of directed graphs

Definitions of Directed graph on the Web: • A directed graph or digraph is an ordered pair with * is a set, whose elements are called vertices or nodes, * is a set of ordered pairs of vertices, called directed edges, arcs, or arrows. •

A graph in which the edges are ordered pairs, so that, if the edge (a, b) is in the graph, the edge (b, a) need not be in the graph and is ...

• • A graph with signed edges. For example, in a protein interaction network, we have excitatory interactions (which might be represented by an edge ...

• A graph with one-way edges. See also directed acyclic graph (DAG).

• (digraph):The edges are ordered pairs of V (ie the binary relation is not necessarily symmetric).

• A graph in which information flows between vertices unidirectionally.

• A graph is a directed graph if the edges have a direction, ieif they are arrows with a head and a tail.

(Jabihul Quamar Jugnu & Shailendra Pratap) —Preceding unsigned comment added by 59.180.153.186 (talk) 07:07, 27 April 2009 (UTC)

A graph with signed edges is not a directed graph. Signs on edges are independent of whether the graph is directed or not. Zaslav (talk) 16:18, 16 January 2016 (UTC)

File:Directed.svg Nominated for Deletion

An image used in this article, File:Directed.svg, has been nominated for deletion at Wikimedia Commons in the following category: Deletion requests September 2011 What should I do? Don't panic; a discussion will now take place over on Commons about whether to remove the file. This gives you an opportunity to contest the deletion, although please review Commons guidelines before doing so. If the image is non-free then you may need to upload it to Wikipedia (Commons does not allow fair use) If the image isn't freely licensed and there is no fair use rationale then it cannot be uploaded or used. This notification is provided by a Bot --CommonsNotificationBot (talk) 19:45, 6 September 2011 (UTC)

Confusing sentence in definition

The last sentence of the introduction is confusing:

"On the other hand, some texts allow loops, multiple arcs, or both in a digraph."

What is a "text" in this context?

166.111.70.36 (talk) 05:55, 1 November 2012 (UTC)

Definition of Networks as Digraphs

"A network is a tuple (G,u) where G=(V,E) is a directed graph and u:E→ℝ>0∪{∞}. For e∈E, we call u(e) the capacity of that edge. [..] I would go as far as to say that a network really has to be a directed graph."

says http://math.stackexchange.com/questions/222114/what-is-the-definition-of-a-network-in-graph-theory --Gunnar (talk) 20:52, 30 June 2016 (UTC)

I've reported the definition of directed network and undirected network by Chartrand, p.19 in the section "Types of directed graphs". --Esponenziale (talk) 11:23, 15 August 2016 (UTC)

Software tools for creating, editing, and drawing directed graphs

Are there any software tools, analogous to those provided for mind mapping, that are useful for creating, editing, and drawing directed graphs? Thanks! --Lbeaumont (talk) 11:42, 13 December 2016 (UTC)

I see a list of software tools in the article on Graph Drawing. Would it be helpful to add Graph Drawing to the See Also section of this article, or would it be better to create a list of software specific to directed graphs and add that new section here directly? --Lbeaumont (talk) 12:02, 13 December 2016 (UTC)

External links modified

Hello fellow Wikipedians,

I have just modified one external link on Directed graph. Please take a moment to review my edit. If you have any questions, or need the bot to ignore the links, or the page altogether, please visit this simple FaQ for additional information. I made the following changes:

• Added archive https://web.archive.org/web/20100413104345/http://www.ecp6.jussieu.fr/pageperso/bondy/books/gtwa/gtwa.html to http://www.ecp6.jussieu.fr/pageperso/bondy/books/gtwa/gtwa.html

When you have finished reviewing my changes, you may follow the instructions on the template below to fix any issues with the URLs.

This message was posted before February 2018. After February 2018, "External links modified" talk page sections are no longer generated or monitored by InternetArchiveBot. No special action is required regarding these talk page notices, other than regular verification using the archive tool instructions below. Editors have permission to delete these "External links modified" talk page sections if they want to de-clutter talk pages, but see the RfC before doing mass systematic removals. This message is updated dynamically through the template {{source check}} (last update: 18 January 2022).

• If you have discovered URLs which were erroneously considered dead by the bot, you can report them with this tool.
• If you found an error with any archives or the URLs themselves, you can fix them with this tool.

Cheers.—InternetArchiveBot (Report bug) 04:19, 11 September 2017 (UTC)

Missing nomenclature for self-reference?

Is there an English term for an edge connecting a node to itself? In Italian it's called "autoanello" ("self-ring"). Thanks. 2A02:C7D:DA0A:DB00:7199:6F1B:2084:365F (talk) 20:29, 20 September 2019 (UTC)

It is a "loop". — Preceding unsigned comment added by 82.69.43.178 (talk) 15:49, 11 March 2020 (UTC)

Or sometimes a "self-loop". —David Eppstein (talk) 21:39, 11 March 2020 (UTC)

Main diagram

The main diagram (which is used elsewhere to illustrate this concept) of the page does not show a directed graph!

One of the arrows is double-headed. I appreciate this my be shorthand for two oppositely directed edges, but I feel that complicates the presentation greatly. Especially since people coming to this article may be meeting the concept for the first time, and there is no accompanying explanation. With the inclusion of directed multigraphs, I feel this could easily lead to confusion as to whether there are 3 types of edge, directed each way and directed both ways. I suggest the removal of this diagram from the wiki anywhere it is the primary image reference for this topic. I suggest an alternative where the double headed arrow is replaced with two oppositely directed arrows would be ideal. — Preceding unsigned comment added by 62.30.151.181 (talk) 15:24, 4 March 2020 (UTC)

No, to my knowledge double-headed arrows are possible within the definition of digraph, because arrows are ordered pairs, and therefore arrow (x,y) is different from arrow (y,x).–Esponenziale (talk) 15:38, 4 March 2020 (UTC)

Thank you for your comment Esponenziale. I appreciate that both (a,b) and (b,a) can be present in the same graph. Sorry, I think my original comment was not very clear. My concern is that a reader new to the concept may think that 3 kinds of edges are allowed: 'forward' pointing arrows, 'backwards' pointing arrows and double headed arrows. I appreciate, the text says this is not the case. But a user who is not familiar with formal definitions may not understand the text and relevance of ordered pairs. In the section "Basic Terminology", edges are implicitly identified with arrows. I think most people, especially non-mathematicians, would consider a double headed arrow to be a single arrow, not two arrows. ie. an "arrow" being the whole entity, not just the head. The diagram could have 2 separate, single headed arrows between the right most and bottom most nodes. As shown in this diagram https://en.wikipedia.org/wiki/File:DirectedDegrees.svg . As it stands I feel it could be confusing or even misleading for non-mathematical readers, and there is no need. — Preceding unsigned comment added by 62.30.151.181 (talk) 17:18, 4 March 2020 (UTC)

Ok I see what you mean. Feel free to go ahead and edit the image (you can either upload the modified image as a new one or, possibly, upload it as a new revision of the old one). –Esponenziale (talk) 17:26, 4 March 2020 (UTC)

No, it must be a new image under a new name. The existing image is used on far too many articles on far too many different-language versions of Wikipedia to be sure that its replacement by something else would be safe. —David Eppstein (talk) 17:37, 4 March 2020 (UTC)

I edited the description under the main diagram to clarify the meaning of the double-headed arrow. I do agree that it should be replaced by a less confusing image, though. –Vocchi —Preceding undated comment added 15:16, 16 March 2020 (UTC)

I have made the diagram but unfortunately I can't upload it because I don't have a wikipedia account. Since I have made it programmatically anyone can recreate it so I hope someone else will be kind enough to generate and upload it. To make it save the following code into a text file called directed_graph.gv

digraph G {
  node [label="", shape="circle", style="filled", fillcolor="lightblue", width=0.3];
  a -> b;
  b -> c;
  c -> a;
  a -> c;
}

Then in the same folder run this command-line command:

neato -Tsvg -odirected_graph.svg directed_graph.gv

You need to have the "graphviz" program "neato" installed.

If you don't want to run this program, there is an online tool that can make a worse version of the diagram. Go to this web page: https://graphs.grevian.org/graph . Into the text box paste the code I put for the file directed_graph.gv above. Then in the dropdown menu select "neato". Finally click the "Generate" button and it will make the graph for you. — Preceding unsigned comment added by 82.69.43.178 (talk) 03:07, 4 July 2020 (UTC)

The diagram is definitely bad. The double-headed line is a bidirected edge, not a directed edge, in the definition given at Bidirected graph. It needs to be fixed soon. Zaslav (talk) 23:04, 10 August 2022 (UTC)

Here I agree with you. Directed graphs may have two edges connecting pairs of vertices in opposite directions, but a single bidirected edge is not something that belongs in a directed graph. The caption says it's two edges, but that's not what it looks like and it seems more likely to confuse or misinform readers than help them. Commons:Category:Directed graphs has many possible replacement images. —David Eppstein (talk) 23:52, 10 August 2022 (UTC)

Thanks. Finally someone took action. Zaslav (talk) 22:51, 12 August 2022 (UTC)