1.
Directed graph
–
In mathematics, and more specifically in graph theory, a directed graph is a graph that is a set of vertices connected by edges, where the edges have a direction associated with them. It differs from an ordinary or undirected graph, in that the latter is defined in terms of unordered pairs of vertices, more specifically, these entities are addressed as directed multigraphs. On the other hand, the definition allows a directed graph to have loops. More specifically, directed graphs without loops are addressed as directed graphs. Symmetric directed graphs are directed graphs where all edges are bidirected, simple directed graphs are directed graphs that have no loops and no multiple arrows with same source and target nodes. As already introduced, in case of arrows the entity is usually addressed as directed multigraph. Some authors describe digraphs with loops as loop-digraphs. Complete directed graphs are directed graphs where each pair of vertices is joined by a symmetric pair of directed arrows. It follows that a complete digraph is symmetric, oriented graphs are directed graphs having no bidirected edges. It follows that a graph is an oriented graph iff it hasnt any 2-cycle. Tournaments are oriented graphs obtained by choosing a direction for each edge in undirected complete graphs. Directed acyclic graphs are directed graphs with no directed cycles, multitrees are DAGs in which no two directed paths from a single starting vertex meet back at the same ending vertex. Oriented trees or polytrees are DAGs formed by orienting the edges of undirected acyclic graphs, rooted trees are oriented trees in which all edges of the underlying undirected tree are directed away from the roots. Rooted directed graphs are digraphs in which a vertex has been distinguished as the root, control flow graphs are rooted digraphs used in computer science as a representation of the paths that might be traversed through a program during its execution. Signal-flow graphs are directed graphs in which nodes represent system variables and branches represent functional connections between pairs of nodes, flow graphs are digraphs associated with a set of linear algebraic or differential equations. State diagrams are directed multigraphs that represent finite state machines, representations of a quiver label its vertices with vector spaces and its edges compatibly with linear transformations between them, and transform via natural transformations. If a path leads from x to y, then y is said to be a successor of x and reachable from x, the arrow is called the inverted arrow of. The adjacency matrix of a graph is unique up to identical permutation of rows. Another matrix representation for a graph is its incidence matrix. For a vertex, the number of head ends adjacent to a vertex is called the indegree of the vertex, the indegree of v is denoted deg− and its outdegree is denoted deg+

2.
Feedback arc set
–
In graph theory, a directed graph may contain directed cycles, a one-way loop of edges. In some applications, such cycles are undesirable, and we wish to eliminate them, one way to do this is simply to drop edges from the graph to break the cycles. A feedback arc set or feedback edge set is a set of edges which, put another way, its a set containing at least one edge of every cycle in the graph. A minimal feedback arc set has the property that, if the edges in it are reversed rather than removed. Finding a small edge set with this property is a key step in layered graph drawing, sometimes it is desirable to drop as few edges as possible, obtaining a minimum feedback arc set, or dually a maximum acyclic subgraph. This is a computational problem, for which several approximate solutions have been devised. As a simple example, consider the hypothetical situation, where in order to achieve something, certain things must be achieved before other things. George says he will give you a piano, but only in exchange for a lawnmower, harry says he will give you a lawnmower, but only in exchange for a microwave. Jane says she will give you a microwave, but only in exchange for a piano and we can express this as a graph problem. Let each vertex represent an item, and add an edge from A to B if you must have A to obtain B, unfortunately, you dont have any of the three items, and because this graph is cyclic, you cant get any of them either. However, suppose you offer George $100 for his piano, if he accepts, this effectively removes the edge from the lawnmower to the piano, because you no longer need the lawnmower to get the piano. Consequently, the cycle is broken, and you can trade twice to get the lawnmower and this one edge constitutes a feedback arc set. As in the example, there is usually some cost associated with removing an edge. For this reason, wed like to remove as few edges as possible and this problem is particularly difficult in k-edge-connected graphs for large k, where each edge falls in many different cycles. The proof involves approximation-preserving reductions from vertex cover to feedback vertex set, more specifically, because vertex cover has no approximation better than 1.3606 unless P ≠ NP, the same is true for feedback arc set. That is, it is possible to take c =1.3606, if the unique games conjecture is true, this inapproximability threshold could be increased to arbitrarily close to 2. On the other hand, the best known approximation algorithm has the non-constant approximation ratio O, for the dual problem, of approximating the maximum number of edges in an acyclic subgraph, an approximation somewhat better than 1/2 is possible. Determining whether feedback arc set has an approximation algorithm, or whether a non-constant ratio is necessary

3.
Topological sorting
–
A topological ordering is possible if and only if the graph has no directed cycles, that is, if it is a directed acyclic graph. Any DAG has at least one topological ordering, and algorithms are known for constructing a topological ordering of any DAG in linear time, the canonical application of topological sorting is in scheduling a sequence of jobs or tasks based on their dependencies. The jobs are represented by vertices, and there is an edge from x to y if job x must be completed before job y can be started, then, a topological sort gives an order in which to perform the jobs. It is also used to decide in order to load tables with foreign keys in databases. The usual algorithms for topological sorting have running time linear in the number of plus the number of edges, asymptotically. One of these algorithms, first described by Kahn, works by choosing vertices in the order as the eventual topological sort. First, find a list of nodes which have no incoming edges and insert them into a set S. Otherwise, the graph must have at least one cycle and therefore a topological sorting is impossible, reflecting the non-uniqueness of the resulting sort, the structure S can be simply a set or a queue or a stack. Depending on the order that nodes n are removed from set S, a variation of Kahns algorithm that breaks ties lexicographically forms a key component of the Coffman–Graham algorithm for parallel scheduling and layered graph drawing. An alternative algorithm for sorting is based on depth-first search. Since each edge and node is visited once, the runs in linear time. This depth-first-search-based algorithm is the one described by Cormen et al. it seems to have been first described in print by Tarjan. On a parallel random-access machine, an ordering can be constructed in O time using a polynomial number of processors. One method for doing this is to square the adjacency matrix of the given graph, logarithmically many times. The resulting matrix describes the longest path distances in the graph, sorting the vertices by the lengths of their longest incoming paths produces a topological ordering. The topological ordering can also be used to compute shortest paths through a weighted directed acyclic graph. Let V be the list of vertices in such a graph, in topological order. Then the following algorithm computes the shortest path from some source vertex s to all vertices, On a graph of n vertices and m edges

4.
Tsort
–
The tsort program is a command line utility on Unix-like platforms, that performs a topological sort on its input. According to its page, this command was initially written for providing an ordering of object files that allowed the linker to process them sequentially. Note that the description is describing the behaviour of the FreeBSD implementation of tsort. Other implementations or versions may differ, tsort Options can be, -d turn on debugging -l search for and display the longest cycle. -q Do not display informational messages about cycles, the output is a total ordering that corresponds to the given partial ordering. In other words, for a directed graph, tsort produces a listing of the vertices so that for all edges a->b. Manual page of tsort on FreeBSD, OpenBSD, NetBSD, AIX, Solaris, HP-UX