For each input, verify that the resulting graph has the same skeleton and v-structures as the input.

Generate graphs systematically.

Begin with chordal graphs and think about how to add directed edges in order to obtain PDAGs. We want most of them to be extendable.

Try to find worst-case instances for Dor Tarsi.

Divide the documentation into multiple pages for better readability.

Consider MPDAGs as well.

• Implement the algorithm to extend MPDAGs.
• Generate MPDAGs by applying Meek's Rules to PDAGs.
• Extend arbitrary PDAGs by 1) PDAG -> MPDAG 2) check if acyclic or new v-structures 3) MPDAG -> DAG

Initialize HashSets and remove isassigned calls, if this is faster (compare it to uninitialized HashSets with isassigned).

Fix bugs in graph generators (e.g., binary tree is not correctly generated). Whenever possible, use LightGraphs implementations (if they exist).

The problem is that rem_vertex! changes the node labels.

Add a reference to the new paper in the documentation of the function fastpdag2dag.

(see https://www.auai.org/uai2021/accepted_papers)

Check whether it is possible to provide an auto-generated Julia documentation via Travis CI on GitHub pages and if so, deploy it.

Add Docker setup to run the code completely in Docker containers.

• Set up Travis CI
• Verify that Docker is working locally (execution of the Julia code works).
• Maybe a JuliaProject.toml or Project.toml is needed to download dependencies in the Docker container? -> Not for now.

See: https://github.com/JuliaGraphs/LightGraphs.jl/blob/master/src/SimpleGraphs/simpledigraph.jl#L397

Avoid the check if s and d are vertices because inputs are always existing vertices.

Use @inbounds wherever possible.

Having implemented the graph generators (see #20), extend the test cases by these new graph types.

Implement the linear-time algorithm for chordal graphs.

Implement a greedy algorithm which prefers nodes with a lower degree over nodes with a higher degree.

Use an array with indices for each degree (0 to n-1) holding a list of vertices with degree i at index i.

Improve construction by computing the degree as follows. Iterate over outgoing edges for each node and check if an incoming edge exists as well to compute the degree. Should be roughly (ignoring the check for the reverse edge which should be fast) in time complexity O(|E|). LightGraphs offers vectors fadj and badj for this.

If the benchmark directory contains subfolders, iterate over them recursively.

Maybe later on: Compare my Dor Tarsi implementation to the implementation in the R package.

Generate big graphs which are not extendable. (undirected, partially directed, directed)

Maybe get rid of the readinputgraph part in the new algorithm. Since the setup is expensive, it might be better for each algorithm to use its own setup, i.e., the old one uses readinputgraph but the new one parses the graph directly from a string/array.

Generate instances using the Erdős–Rényi model and the Barabási–Albert model.

Output a topological ordering instead of the extended graph. Use an extra function for computing the extended graph from the ordering. This allows separate time measurements.

Another advantage of this is that filter can be used to direct all edges in one step which should be faster than directing each edge on its own.

Create a README.md file.

• Add badges for build status and documentation on branch gh-pages (if possible).
• Add a description of the project itself.
• Provide steps on how to use the code (Docker setup) and explain where logs can be found.

Implement the degeneracy ordering without LightGraphs.

Generate PDAGs which are extendable. Until now, there are only fully undirected graphs which are extendable.

Add graph generators for more types of graphs.

Add some tests.

Maybe add some coverage tool like Coverage.jl.

Add missing text in the documentation.

Currently, rem_vertex! is called which leads to the problem that node labels are changed. To circumvent this issue, a hashtable is used to map old node labels on their new label.

Maybe it is not even easier but also more efficient to only delete the edges of the node to delete and leave the node unconnected in the graph - this should be possible.

Implement DFS as a baseline for fully directed graphs (simple cycle checking).

The value for n=... is not always correct since the functions may add nodes to the given n. Use the actual n in the name.

Generation of MPDAGs does not work as intended. The rules are not applied exhaustively since changes of edges are not considered at the moment.

Implement a version of the new algorithm using LightGraphs instead of HashSets.

Add the optimized setup for the LightGraphs implementation.

Generate fully directed graphs.

Implement a version of the old algorithm where HashSets are used instead of LightGraphs.

The separation of each set into two parts does not work as intended yet.

Problem: Set with vertices that have no ingoing edges might be empty and thus index j is decreased but later on there are still vertices in some later set that are moved into the set for vertices without ingoing edges.

If possible, add an icon to the documentation.

Add documentation for the implementation with LightGraphs.