somacdivad / graphinvariants.jl Goto Github PK

We need a good README file.

Some resources to looks at:

• https://www.freecodecamp.org/news/how-to-write-a-good-readme-file/
• https://awesomeopensource.com/projects/readme

Relevant definitions from GrinPy:

• connected_domination_number()

Let's not worry about $k$-connected-dominating sets for now. We'll add those in a later version.

We need to support the residue invariant.

Relevant GrinPy functions:

• Residue function
• Havel-Hakimi stuff

We need to support the total domination number.

Relevant definitions from GrinPy:

• ILP
• Brute force

For now, the brute force algorithm can be as "dumb" as possible (i.e., searches all combinations of vertices). In the future, we can add various upper and lower bounds for the total domination to limit the search space.

Hi there, and congrats on the new package!
I'm one of the JuliaGraphs maintainers, and we've recently started to regroup all graph algorithms that require heavy dependencies (such as ILP solvers) inside a package called GraphsOptim.jl. It is dormant until I have some more time, but you might want to check out our discussion about it in this issue. It may be useful to you if you want to avoid duplicating code. Of course, we would also be interested in contributions :)

We need to support the clique number.

Relevant GrinPy definitions:

• clique_number() (this is just an alias for NetworkX’s graph_clique_number())

There are some other algorithms to consider, too, such as an ILP and this matrix approach.

Relevant definitions from GrinPy:

• ILP
• Brute force

The brute force algorithm can search through all combinations of vertices for now. We'll implement various upper and lower bounds in a later version to limit the search space.

We need to support the chromatic number.

Relevant definitions from GrinPy:

• Min. proper coloring ILP
• Ram-Rama algorithm (this might have a bug)

There are a few coloring algorithms in Graphs.jl to investigate. They might be useful (although it doesn’t look like any of them guarantee a minimum coloring).

We need to add support for computing the domination number of a graph.

Should probably be split between two functions, as we did for the independence number (see #1):

• min_dominating_set()
• domination_number()

Relevant GrinPy definitions:

• Min. Dominating Set
• Domination Number

We have an ILP and a brute force algo in GrinPy. Let's keep the brute force algo as simple as possible and have it search through all combinations of vertices. We'll add various upper and lower bounds in the future that we can use to limit the search space.