Directed Graph

A directed graph is a DataStructure 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 UndirectedGraph.
Weights may be put on the arcs, resulting in a WeightedDirectedGraph.
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 DirectedAcyclicGraph.
Of course, there's also WeightedDirectedAcyclicGraphs.

A DirectedGraph is primarily a MathematicalNotation which can be represented as a DataStructure for programming. You might say ProgrammingIsMath, but IsProgrammingMath?

StuFeldman's algorithm (1979) finds a solution to every problem that can be written as a DirectedAcyclicGraph. The algorithm finds and traverses a path through the graph. The graph is called a makefile, and his tool is called make (see MakeProgram). -- ChrisGarrod

How does StuFeldman's algorithm answer this?

: Given a DirectedAcyclicGraph 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 DirectedAcyclicGraph, that's a problem about DirectedAcyclicGraphs. 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 StuFeldman'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.

TheReformSociety 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 DirectedAcyclicGraph.

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 StuFeldman's algorithm(s) "solved" every problem that can be written as a DAG. I can't see how StuFeldman's algorithm(s) do anything particularly special. I had discounted the traditional AI problems because StuFeldman'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 StuFeldman'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 EnumSet? objects. Generics makes it a whole lot clearer:

class DirectedGraph<T extends Enum<T>> extends EnumMap?<T, EnumSet?<T>>

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?

CategoryDataStructure