Git Product home page Git Product logo

mindominatingset's Introduction

Minimum dominating set

Summary

I. Abstract.

II. Thesis.

III. Presentation.

Introduction

In graph theory, the dominating set is a well know Np-complete problem. To date, we don't have a polynomial time algorithm to solve this problem. In my Master thesis, I did a review of literature about the well know exact, greedy and metha-heuristique solutions.

This repository contains my Java implementation to solve the Minimum Dominanting Set.

Project guidline

There are 4 packages:

1-exactalgorithm: contains the exacts solutions algorithms.

2-graph: for the data structure representation of the graph.

3-heuristics: contains the classes responsible for the heuristics solutions.

4-util: some utilities classes used in this project.

/*
 * @param args
 *
 *
 *
 * To run this program, you should pass as parameters:
 *  + the algorithm type.
 *  + the path of the file that contains the graph(graphs if trinagleup file format).
 *  + the type of the passed file.
 * As a result, the program will print the adjacency list of the graph, the mds size found  and the time taken in seconds.
 *
 *
 * Four parameters can be given to the program: -algo, -path, -type, -mds.
 * three parameters are mandatory: -algo, -path, -type.
 * one parameter is optional -mds (used only when running the Genetic algorithm)
 *
 *      - algo
 * - algo 1 ------> to run the Arbitrary algorithm
 * - algo 2 ------> to run the atmostDegree3 algorithm
 * - algo 3 ------> to run the trivialSetCover algorithm
 * - algo 4 ------> to run the improvedSetCover algorithm
 * - algo 5 ------> to run the greedy algorithm
 * - algo 6 ------> to run the GreedyReverse algorithm
 * - algo 7 ------> to run the GreedyRandom algorithm
 * - algo 8 ------> to run the GeneticAlgo1 algorithm
 * - algo 9 ------> to run the GeneticAlgo2 algorithm
 *
 *
 *      - path
 * - path  "filepath/file.txt" ------> to pass the location of the file.txt as a path value to the program.
 *
 *
 *
 *      - type
 * - type 1 ------> means that the file passed to the program is of type triangleup.
 * - type 2 ------> means that the file passed to the program is of type dimacs.
 * - type 3 ------> means that the file passed to the program is of type HouseofGraphs.
 *
 * Only the triangleup file format could contains many graphs.
 * The two others files format should contains only one graph per file.
 *
 * Please refer to src\main\resources to see the 3 supported files type format(triangleup, dimacs, HousOfGraphs)
 * This program can run any implemented algorithms on any supported graphs file.
 *
 *
 *      - mds
 *  When you choose to run the genetic Algorithm on a (dimacs file format or a houseofgraphs file format)
 *  it is possible to pass the known minimum dominating set size as a parameter by :
 *
 * - mds s ------> where s is an int value representing the known minimum dominating set.
 *                 the Genetic algorithm can stop running after reaching this optimal value.
 *
 *
 *
 * given mds.jar as an executable file, you can run it with as the following examples:
 *
 * Example_1 :
 * java -jar mds.jar -algo 5 -path "c:Windows\Desktop\file.col" -type 2
 * this command line run the greedy algorithm on the dimacs file located in "c:Windows\Desktop\file.col"
 *
 * Example_2 :
 * java -jar mds.jar -algo 8 -path "c:Windows\Desktop\filename.lst" -type 3 -mds 4
 * this command line run the genetic algorithm on the houseofgraphs file format located in c:Windows\Desktop\filename.lst
 * the program will stop running whenever finding a dominating set of size 4.
 *
 * The mds.jar could be found in the same directory as this README file.
 */

mindominatingset's People

Contributors

javazakariae avatar momedalhouma avatar

Stargazers

 avatar

Watchers

 avatar

mindominatingset's Issues

1

Where is the data set of precise algorithm? Could you please send me one? # @momedalhouma

Recommend Projects

  • React photo React

    A declarative, efficient, and flexible JavaScript library for building user interfaces.

  • Vue.js photo Vue.js

    🖖 Vue.js is a progressive, incrementally-adoptable JavaScript framework for building UI on the web.

  • Typescript photo Typescript

    TypeScript is a superset of JavaScript that compiles to clean JavaScript output.

  • TensorFlow photo TensorFlow

    An Open Source Machine Learning Framework for Everyone

  • Django photo Django

    The Web framework for perfectionists with deadlines.

  • D3 photo D3

    Bring data to life with SVG, Canvas and HTML. 📊📈🎉

Recommend Topics

  • javascript

    JavaScript (JS) is a lightweight interpreted programming language with first-class functions.

  • web

    Some thing interesting about web. New door for the world.

  • server

    A server is a program made to process requests and deliver data to clients.

  • Machine learning

    Machine learning is a way of modeling and interpreting data that allows a piece of software to respond intelligently.

  • Game

    Some thing interesting about game, make everyone happy.

Recommend Org

  • Facebook photo Facebook

    We are working to build community through open source technology. NB: members must have two-factor auth.

  • Microsoft photo Microsoft

    Open source projects and samples from Microsoft.

  • Google photo Google

    Google ❤️ Open Source for everyone.

  • D3 photo D3

    Data-Driven Documents codes.