Artifact page: ‘A dynamic programming algorithm for a maximum \(s\)-clique set on trees’

Description

Experiments in the article “A dynamic programming algorithm for a maximum \(s\)-clique set on trees” were done using the code in this page. This artifact contrains source code (in Python) for the implementations of the Schäfer’s¹ and Max-DsT² algorithms.

Authors: José Alberto Fernández-Zepeda, Alejandro Flores-Lamas, Matthew Hague, Joel Antonio Trejo-Sánchez.

Assets

Artifact (The version we use for the experiments for the paper submitted to the The 16th International Conference on Reachability Problems (RP’22))

• Download

Reproducibility of results

• Please see this web page for information related to the database.

• Instructions to reproduce the experiments: experimental web page.

Instructions

General Installation

• There’s no installation procedure; please download the project.

Software Dependencies

• RP_2022_Tool is written in Python 3.10, yet it can be run on version 3.9x or later.

• RP_2022_Tool also requires the following packages:

  • NetworkX
  • YAML
  • pandas

Selected contents

See Script file and folder structure for the entire contents of the artifact.

Main file

• /RP_2022_Tool/main.py

Schäfer’s implementation

• /RP_2022_Tool/src/Algorithms/RPv2022/Schafer

Max-DkT implementation

• /RP_2022_Tool/src/Algorithms/RPv2022/Max_DkT

I / O folders:

• Input: /RP_2022_Tool/Input/
• Output: /RP_2022_Tool/Output/

Configuration file:

• /RP_2022_Tool/Settings

  • RP_small_example.yaml <– Configuration file to execute both Schäfer’a and Max-DkT on three ‘small’ trees stored the path: /RP_2022_Tool/Input/Small; result files will be stored in /RP_2022_Tool/Output/Small

  • RP_medium_example.yaml <– Configuration file to execute both Schäfer’a and Max-DkT on one ‘medium’ tree stored the path: /RP_2022_Tool/Input/Medium; result files will be stored in /RP_2022_Tool/Output/Medium

Other instructions and example of execution

After unpacking the artifact, RP_2022_Tool can be run as follows:

• Open a command-line interpreter and navigate to the ‘RP_2022_Tool’ folder
• Type the following command:

$ python main.py Settings/RP_small_example.yaml

In the above example, we call the main.py file with the parameters of RP_small_example.yaml. In particular this example proceeds as follows:

1. RP_2022_Tool reads the GML files in ‘/RP_2022_Tool/Input/Small’
2. RP_2022_Tool transforms each file into a tree with the attributes required by the algorithms.
3. RP_2022_Tool executes Max-DkT and Schäfer’s algorithm sequentially with the parameters specified in the YAML file.
4. RP_2022_Tool saves in TSV files (RP_2022_Tool/Output/Small) the outcome of the execution of the algorithms.

Experimental Installation

• Instructions for repeating the experiments are provided on the experimental web page.

License

• Free

Script file and folder structure

|-- RP_2022_Tool
    |-- main.py
    |-- Input
    |   |-- Medium
    |   |   |-- random_30_000.gml
    |   |-- Small
    |       |-- input_graph_0.gml
    |       |-- input_graph_1.gml
    |       |-- input_graph_2.gml
    |-- Output
    |   |-- Medium
    |   |-- Small
    |   |-- T_22_16
    |   |-- T_B
    |   |-- T_D
    |   |-- T_L
    |   |-- T_Ph
    |   |-- T_eta
    |-- Settings
    |   |-- RP_medium_example.yaml
    |   |-- RP_small_example.yaml
    |   |-- T_22_16.yaml
    |   |-- T_B.yaml
    |   |-- T_D.yaml
    |   |-- T_L.yaml
    |   |-- T_Ph.yaml
    |   |-- T_eta.yaml
    |-- Tests
    |   |-- Testers
    |   |   |-- abstract_benchmark_tester.py
    |   |   |-- tree_k_clique_s_club_tester.py
    |   |-- Testing
    |       |-- run_Schafers_and_Max_DkT.py
    |-- src
        |-- Algorithms
        |   |-- Enums
        |   |   |-- enum_algorithms.py
        |   |-- RPv2022
        |       |-- Max_DkT
        |       |   |-- downward_sweep.py
        |       |   |-- dp_mdkc_t_updated.py
        |       |   |-- upward_sweep_updated.py
        |       |-- Schafer
        |           |-- my_tree_s_club.py
        |           |-- tree_s_club_updated.py
        |-- Graphs
        |   |-- Enums
        |   |   |-- enum_node_type.py
        |   |-- Graph
        |   |   |-- directed_tree.py
        |   |   |-- simple_directed_tree.py
        |   |   |-- simple_graph.py
        |   |   |-- simple_undirected_tree.py
        |   |-- Nodes
        |       |-- simple_node.py
        |       |-- TreeNodes
        |       |   |-- directed_tree_node.py
        |       |   |-- dkclique_node.py
        |       |   |-- schafers_node.py
        |       |   |-- simple_directed_tree_node.py
        |       |   |-- simple_undirected_tree_node.py
        |-- Utils
            |-- input_handler.py
            |-- output_handler.py
            |-- utils.py