ChordalGraph.jl

ChordalGraph is an extension of the Julia package LightGraph to handle chordal graphs.
Author wangjie212
Popularity
1 Star
Updated Last
8 Months Ago
Started In
June 2020

ChordalGraph

ChordalGraph is an extension of the Julia package LightGraphs to handle chordal graphs.

To use ChordalGraph in Julia, run

pkg> add https://github.com/wangjie212/ChordalGraph

Dependencies

  • LightGraphs

Usage

The function CheckChordal checks whether a graph G is chordal. If G is chordal, then flag=true and a perfect elimination ordering order is returned; otherwise, flag=false.

julia> flag,order=CheckChordal(G)

The function chordal_cliques! generates a chordal extension of G and enumerates all maximal cliques of the obtained graph.

julia> cliques,num_cliques,size_cliques=chordal_cliques!(G, method="MF", minimize=true)

Options:
method: MF (a chordal extension based on greedy minimal fill-in), MD (a chordal extension based on greedy minimal degree)
minimize: true (minimizing the obtained chordal extension), false (not minimizing the obtained chordal extension)

References

ChordalGraph: A Julia Package to Handle Chordal Graphs, Jie Wang, 2020.

Citing

@article{Wang20,
author = {Jie Wang},
title = {ChordalGraph: A Julia Package to Handle Chordal Graphs},
year = 2020,
url = {https://github.com/wangjie212/ChordalGraph}
}

Contact

Jie Wang: jwang@laas.fr

Used By Packages

No packages found.