Utilities

algo2label(algo::String)::String

Map the function name of the used algorithm to a label for the plot.

Examples

julia> algo2label("pdag2dag_hs()-1")
Dor Tarsi HS - Standard - 1

dict_to_csv(dict::Dict, use_median::Bool = true)::String

Convert a dictionary of time measurements into a csv-formatted string. The parameter use_median indicates whether the median or mean should be used: If set to true (or ommitted), the median will be used, otherwise the mean.

It is possible to set the file parameter in order to save the csv-formatted string in that given file.

Examples

julia> dict = get_times_dict("../logs/log.txt")
Dict{String,Dict{Any,Any}} with 1 entry:
  "pdag2dag_lg()-1" => Dict{Any,Any}("example.txt"=>Dict("median"=>2426.5,"mean"=>2594.65))
julia> dict_to_csv(dict)
  "Algorithm;Instance;Time
pdag2dag_lg()-1;example.txt;2426.5
"

get_times_dict(file::String)::Dict

Convert a logfile to a dictionary containing the times. The dictionary has the following structure: { "algorithm": { "input1": { "median": 1.124, "mean": 1.312 }, "input2": ... } }

Examples

julia> get_times_dict("../logs/log.txt")
Dict{String,Dict{Any,Any}} with 1 entry:
  "pdag2dag_lg()-1" => Dict{Any,Any}("example.txt"=>Dict("median"=>2426.5,"mean"=>2594.65))

print_dict(dict::Dict, io::Core.IO = stdout)

Print the contents of a dictionary as a formatted JSON string with readable indentation.

Examples

julia> dict = get_times_dict("../logs/log.txt")
Dict{String,Dict{Any,Any}} with 1 entry:
  "pdag2dag_lg()" => Dict{Any,Any}("example.txt"=>Dict("median"=>2426.5,"mean"=>2594.65))
julia> julia> print_dict(dict)
{
    "pdag2dag_lg()": {
        "example.txt": {
            "median": 2426.5,
            "mean": 2594.646
        }
    }
}

plotsvg(g, file::String)

Draw a graph and save it in a .svg file.

Examples

julia> g = SimpleDiGraph(2)
{2, 0} directed simple Int64 graph
julia> add_edge!(g, 1, 2)
true
julia> plotsvg(g, "plot.svg")
false

readinputgraph(file::String, only_undir::Bool = false)::SimpleDiGraph

Read a graph from a file and return a SimpleDiGraph. The file must be formatted as follows. The first line contains the number of vertices and the number of edges, separated by a space. One empty line follows. Afterwards, there is one line for each edge. Each line representing an edge has a startvertex and an endvertex, separated by a space. Undirected edges are represented by two directed edges.

The parameter only_undir can be set to true to indicate that the input graph contains only undirected edges. This allows the input file to contain only one edge for each undirected edge.

Examples

julia> g = readinputgraph("../benchmarks/example.txt")
{3, 3} directed simple Int64 graph

graph2digraph(g::SimpleGraph)::SimpleDiGraph

Convert an undirected graph (SimpleGraph) into a directed graph (SimpleDiGraph).

Examples

julia> g = SimpleGraph(3)
{3, 0} undirected simple Int64 graph
julia> add_edge!(g, 1, 2)
true
julia> collect(edges(graph2digraph(g)))
2-element Vector{LightGraphs.SimpleGraphs.SimpleEdge{Int64}}:
 Edge 1 => 2
 Edge 2 => 1

graph2str(g; is_only_undir::Bool = false)::String

Convert a graph g to the corresponding string representation. Set is_only_undir to false if the graph contains directed edges.

Examples

julia> g = SimpleDiGraph(3)
{3, 0} directed simple Int64 graph
julia> graph2str(g)
"3 0
"

is_consistent_extension(g1::SimpleDiGraph, g2::SimpleDiGraph)::Bool

Check whether g1 is a consistent extension of g2.

Examples

julia> g = SimpleDiGraph(3)
{3, 0} directed simple Int64 graph
julia> add_edge!(g, 1, 2)
true
julia> add_edge!(g, 2, 3)
true
julia> add_edge!(g, 3, 2)
true
julia> e = SimpleDiGraph(3)
{3, 0} directed simple Int64 graph
julia> add_edge!(e, 1, 2)
true
julia> add_edge!(e, 2, 3)
true
julia> is_consistent_extension(e, g)
true

isdag(g::SimpleDiGraph)::Bool

Check whether g is a directed acyclic graph.

Examples

julia> g = SimpleDiGraph(3)
{3, 0} directed simple Int64 graph
julia> add_edge!(g, 1, 2)
true
julia> add_edge!(g, 2, 3)
true
julia> isdag(g)
true
julia> add_edge!(g, 3, 1)
true
julia> isdag(g)
false

nanosec2sec(time::Float64)::Float64

Convert a number in nanoseconds to milliseconds.

Examples

julia> nanosec2millisec(1000000.0)
1.0

save2file(g, file::String; is_only_undir::Bool = true)

Save a graph g to a given file. Set is_only_undir to false if the graph contains directed edges.

Examples

julia> g = SimpleDiGraph(3)
{3, 0} directed simple Int64 graph
julia> save2file(g, "../benchmarks/dummy/graph.txt")

skeleton(g::SimpleDiGraph)::Vector{Tuple{Int64, Int64}}

Compute the skeleton of g. Edges are represented as tuples (u, v) where the smaller number is always first.

Examples

julia> g = SimpleDiGraph(3)
{3, 0} directed simple Int64 graph
julia> add_edge!(g, 1, 2)
true
julia> add_edge!(g, 3, 2)
true
julia> skeleton(g)
2-element Vector{Tuple{Int64, Int64}}:
 (1, 2)
 (2, 3)

vstructures(g::SimpleDiGraph)::Vector{Tuple{Int64, Int64, Int64}}

Compute all v-structures of graph g. The v-structures of form u -> v <- w are represented as tuples (x, v, y) where x is always the minimum of u and w and y is the maximum of u and w. The list of v-structures which is returned is sorted first by x, then by v and last by y.

Examples

julia> g = SimpleDiGraph(3)
{3, 0} directed simple Int64 graph
julia> add_edge!(g, 1, 2)
true
julia> add_edge!(g, 3, 2)
true
julia> vstructures(g)
1-element Vector{Tuple{Int64, Int64, Int64}}:
 (1, 2, 3)

random_dag(min_r, max_r, min_v_per_r, max_v_per_r, prob)::SimpleDiGraph

Create a random DAG with the following properties: min_r is the minimum number of ranks for the DAG and max_r the maximum number of ranks. min_v_per_r indicates the minimum number of vertices per rank and max_v_per_r the maximum number of vertices per rank. prob is the probability of having an edge between two vertices.

References

https://stackoverflow.com/questions/12790337/generating-a-random-dag

Examples

julia> random_dag(3, 5, 3, 5, 0.2)
{15, 19} directed simple Int64 graph
julia> random_dag(3, 5, 3, 5, 0.2)
{12, 12} directed simple Int64 graph

random_dag_v2(n::Int64, m::Int64)::SimpleDiGraph

Create a random DAG with n vertices and m edges.

Examples

julia> random_dag_v2(10, 40)
{10, 40} directed simple Int64 graph

barbellgraph(n::Int64; filepath::String = "")::SimpleGraph

Create a barbell graph with n vertices.

If a filepath is provided, the graph will also be written to that file.

Examples

julia> barbellgraph(6)
{6, 7} undirected simple Int64 graph

bintreegraph(n::Int64; filepath::String = "")::SimpleGraph

Create a binary tree with n vertices.

If a filepath is provided, the graph will also be written to that file.

Examples

julia> bintreegraph(7)
{7, 6} undirected simple Int64 graph

centipedegraph(n::Int64; filepath::String = "")::SimpleGraph

Create a centipede graph with n vertices. Note that n has to be equal.

If a filepath is provided, the graph will also be written to that file.

Examples

julia> centipedegraph(8)
{8, 7} undirected simple Int64 graph

cliquegraph(n::Int64; filepath::String = "")::SimpleGraph

Create a clique graph with n vertices. The graph contains a clique of size n/2, where each vertex of that clique has one additional neighbor which is not connected to any other vertex. Note that n has to be equal.

If a filepath is provided, the graph will also be written to that file.

Examples

julia> cliquegraph(8)
{8, 10} undirected simple Int64 graph

completegraph(n::Int64; filepath::String = "")::SimpleGraph

Create a complete graph with n vertices.

If a filepath is provided, the graph will also be written to that file.

Examples

julia> completegraph(4)
{4, 6} undirected simple Int64 graph

cyclegraph(n::Int64; filepath::String = "")::SimpleGraph

Create a cycle with n vertices. Note that n has to be greater or equal to 3.

If a filepath is provided, the graph will also be written to that file.

Examples

julia> cyclegraph(8)
{8, 8} undirected simple Int64 graph

doublestargraph(n::Int64; filepath = "")::SimpleGraph

Create a graph with n vertices, consisting of two connected stars.

If a filepath is provided, the graph will also be written to that file.

Examples

julia> doublestargraph(8)
{8, 7} undirected simple Int64 graph

extbarbellgraph(n::Int64; filepath::String = "")::SimpleGraph

Create an extended barbell graph with n vertices. That is, two cliques connected by a path. The cliques and the path are of size n/3 each.

If a filepath is provided, the graph will also be written to that file.

Examples

julia> extbarbellgraph(8)
{8, 7} undirected simple Int64 graph

friendshipgraph(n::Int64; filepath::String = "")::SimpleGraph

Create a friendship graph with n vertices. Note that n has to be odd.

If a filepath is provided, the graph will also be written to that file.

Examples

julia> friendshipgraph(7)
{7, 9} undirected simple Int64 graph

graph2pdag(g::SimpleDiGraph, prob::Float64)::SimpleDiGraph

Convert an undirected graph (encoded as a SimpleDiGraph) into a partially directed graph.

Examples

julia> g = SimpleDiGraph(3)
{3, 0} directed simple Int64 graph
julia> add_edge!(g, 1, 2)
true
julia> add_edge!(g, 2, 1)
true
julia> add_edge!(g, 1, 3)
true
julia> add_edge!(g, 3, 1)
true
julia> collect(edges(graph2pdag(g, 0.5)))
3-element Vector{LightGraphs.SimpleGraphs.SimpleEdge{Int64}}:
 Edge 1 => 2
 Edge 1 => 3
 Edge 2 => 1

pathgraph(n::Int64; filepath::String = "")::SimpleGraph

Create a path with n vertices.

If a filepath is provided, the graph will also be written to that file.

Examples

julia> pathgraph(10)
{10, 9} undirected simple Int64 graph

stargraph(n::Int64; filepath::String = "")::SimpleGraph

Create a star graph with n vertices.

If a filepath is provided, the graph will also be written to that file.

Examples

julia> stargraph(11)
{11, 10} undirected simple Int64 graph

erdos_renyi_pdag(n::Int64, p1::Float64, p2::Float64; seed = 123)::SimpleDiGraph

Create a partially directed graph using the Erdős–Rényi model. The graph has n vertices with a probability p1 for having an edge between two vertices. p2 is the probablity for an edge to be directed.

Examples

julia> erdos_renyi_pdag(10, 0.2, 0.5)
{10, 12} directed simple Int64 graph

random_pdag(g::SimpleDiGraph, p::Float64)::g::SimpleDiGraph

Generates a partially directed graph by directing a given percentage of edges in a given undirected graph. Takes as input a fully undirected graph, encoded as a SimpleDiGraph. The generated PDAG will be extendable if the input is extendable.

Examples

julia> g = SimpleDiGraph(3)
{3, 0} directed simple Int64 graph
julia> add_edge!(g, 1, 2)
true
julia> add_edge!(g, 2, 1)
true
julia> add_edge!(g, 1, 3)
true
julia> add_edge!(g, 3, 1)
julia> collect(edges(random_pdag(g, 0.5)))
3-element Vector{LightGraphs.SimpleGraphs.SimpleEdge{Int64}}:
 Edge 1 => 2
 Edge 1 => 3
 Edge 3 => 1

random_pdag(g::SimpleDiGraph, m::Int64)::SimpleDiGraph

Generates a partially directed graph by keeping m undirected edges in a given undirected graph g; all other edges are being directed. Takes as input a fully undirected graph, encoded as a SimpleDiGraph. The generated PDAG will be extendable if the input is extendable.

Examples

julia> g = SimpleDiGraph(3)
{3, 0} directed simple Int64 graph
julia> add_edge!(g, 1, 2)
true
julia> add_edge!(g, 2, 1)
true
julia> add_edge!(g, 2, 3)
true
julia> add_edge!(g, 3, 2)
true
julia> collect(edges(random_pdag(g, 1)))
3-element Vector{LightGraphs.SimpleGraphs.SimpleEdge{Int64}}:
 Edge 1 => 2
 Edge 2 => 1
 Edge 2 => 3
julia> collect(edges(random_pdag(g, 1)))
3-element Vector{LightGraphs.SimpleGraphs.SimpleEdge{Int64}}:
 Edge 1 => 2
 Edge 2 => 3
 Edge 3 => 2