Directed Graph

A directed graph is a Data Structure containing a vertex set V and an arc set A, where each arc (or edge, or link) is an ordered pair of vertices (or nodes, or sommets). The arcs may be thought of as arrows, each one starting at one vertex and pointing at precisely one other.

There are several variants of this data structure:

The arrowheads may be removed, resulting in an Undirected Graph.

Weights may be put on the arcs, resulting in a Weighted Directed Graph.

If it is not possible, starting from any given vertex and following any positive quantity of arcs to successive vertices, to return to the starting point, the graph is said to contain no circuits and is called a Directed Acyclic Graph.

Of course, there's also Weighted Directed Acyclic Graphs.

A Directed Graph is primarily a Mathematical Notation which can be represented as a Data Structure for programming. You might say Programming Is Math, but Is Programming Math?

Stu Feldman's algorithm (1979) finds a solution to every problem that can be written as a Directed Acyclic Graph. The algorithm finds and traverses a path through the graph. The graph is called a makefile, and his tool is called make (see Make Program). -- Chris Garrod

How does Stu Feldman's algorithm answer this?

Given a Directed Acyclic Graph G, consider the set S of all possible linear orderings consistent with G. For two vertices A and B, let P(A,B) be the probability that A comes before B in an element of S chosen uniformly at random. Prove that if |S|>1 then there exist A and B such that 1/3 <= P(A,B) <= 2/3.

That's not a problem writable as a Directed Acyclic Graph, that's a problem about Directed Acyclic Graphs. There is a difference. You're going to have to express your problem as a graph, at which point the effectiveness of the algorithm should be obvious. either for or against (see parenthetical paragraph below). However, while with sufficient work such proofs can be expressed as graphs, you may not like the running time.

A graph of a proof will start with what you gave the system (the Givens in your problem). Each application of an axiom is an arc leading to a new result. It gets real big, real fast. (Colloquialism deliberate.)

(In fact it is infinite, technically, and despite the claim that Stu Feldman's algorithm finds a solution to all DAG problems, I would expect that only holds for graphs where all nodes have a finite number of exiting arcs. That isn't true in the obvious formulations of the graph I described, because of the presence of numbers, where you can technically try statements about any proportion of the graph.)

Well, I guess I'm having trouble finding any examples of difficult and/or interesting problems that can be "written as a DAG". The only examples I've come up with are simple search problems, or have been devised by taking problems and rewriting/encoding them in a non-natural way.

The Reform Society probably isn't the kind of example you were looking for, but you may find it interesting nevertheless as it's meant to be a Directed Acyclic Graph.

As a graph-theorist and compiler writer I have any number of examples of DAGs. I just don't understand what it means to "write a problem as a DAG."

"Traditional" artificial intelligence is where you want to look, specifically their "search problems". Massive state spaces with discrete transitions, all represented as DAGs. A lot of problems that don't look like a "search" actually are.

OK, I can see you're trying to help, so let me be more specific. It was claimed above that Stu Feldman's algorithm(s) "solved" every problem that can be written as a DAG. I can't see how Stu Feldman's algorithm(s) do anything particularly special. I had discounted the traditional AI problems because Stu Feldman's algorithm clearly does nothing there more interesting than the usual, and not very successful, AI searches, so I guess I was hoping for more. I can't find a "problem written as a DAG" in which the "make" algorithms are of any clear benefit over almost any other techniques well-known to almost any graph-theorist.

Actually, I only wrote the later stuff; I've never heard of Stu Feldman's algorithm. I was just trying to explain the problem-as-DAG aspect. Sorry.

No need to apologise, I'm just trying to understand what the original author was saying.

I have written a directed graph class for Java where the nodes are Enum values and the vertexes are stored in Enum Set objects. Generics makes it a whole lot clearer:

class Directed Graph> extends Enum Map>

Good for you. Rather than waste the reader's time patting yourself on the back, would you consider either (a) sharing your code with us; or (b) delete the above and stop teasing us?

See original on c2.com

Category Data Structure