Welcome to GrinPy¶

GrinPy is a NetworkX extension for calculating graph invariants. This extension imports all of NetworkX into the same interface as GrinPy for easy of use and provides the following extensions:

extended functional interface for graph properties
calculation of NP-hard invariants such as: independence number, domination number and zero forcing number
calculation of several invariants that are known to be related to the NP-hard invariants, such as the residue, the annihilation number and the sub-domination number

Our goal is to provide the most comprehensive list of invariants. We will be continuing to add to this list as time goes on, and we invite others to join us by contributing their own implementations of algorithms for computing new or existing GrinPy invariants.

Audience¶

We envision GrinPy’s primary audience to be professional mathematicians and students of mathematics. Computer scientists, electrical engineers, physicists, biologists, chemists and social scientists may also find GrinPy’s extensions to the standard NetworkX package useful.

History¶

Grinpy was originally created to aid the developers, David Amos and Randy Davila, in creating an ordered tree of graph databases for use in an experimental automated conjecturing program. It quickly became clear that a Python package for calculating graph invariants would be useful. GrinPy was created in November 2017 and is still in its infancy. We look forward to what the future brings!

Free Software¶

GrinPy is free software; you can redistribute it and/or modify it under the terms of the 3-clause BSD license, the same license that NetworkX is released under. We greatly appreciate contributions. Please join us on Github.

Documentation¶

Tutorial¶

This guide can help you start working with GrinPy. We assume basic knowledge of NetworkX. For more information on how to use NetworkX, see the NetworkX Documentation.

Calculating the Independence Number¶

For this example we will create a cycle of order 5.

>>> import grinpy as gp
>>> G = gp.cycle_graph(5)

In order to compute the independence number of the cycle, we simply call the independence_number method on the graph:

>>> gp.independence_number(G)
2

It’s that simple!

Note

In this release (version latest), all methods are defined only for simple graphs. In future releases, we will expand to digraphs and multigraphs.

Get a Maximum Independent Set¶

If we are interested in finding a maximum independent set in the graph:

>>> gp.max_independent_set(G)
[0, 2]

Determine if a Given Set is Independent¶

We may check whether or not a given set is independent:

>>> gp.is_independent_set(G, [0, 1])
False
>>> gp.is_independent_set(G, [1, 3])
True

General Notes¶

The vast majority of NP-hard invariants will include three methods corresponding to the above examples. That is, for each invariant, there will be three methods:

Calculate the invariant
Get a set of nodes realizing the invariant
Determine whether or not a given set of nodes meets some necessary condition for the invariant.

Reference¶

Release: latest

Date: May 30, 2019

Classes¶

Release: latest

Date: May 30, 2019

HavelHakimi¶

Overview¶

class grinpy.HavelHakimi(sequence)¶

Class for performing and keeping track of the Havel Hakimi process on a sequence of positive integers.

Parameters:	sequence (input sequence) – The sequence of integers to initialize the Havel Hakimi process.

Methods¶

`HavelHakimi.__init__`(sequence)	Initialize self.
`HavelHakimi.depth`()	Return the depth of the Havel Hakimi process.
`HavelHakimi.get_elimination_sequence`()	Return the elimination sequence of the Havel Hakimi process.
`HavelHakimi.get_initial_sequence`()	Return the initial sequence passed to the Havel Hakimi class for initialization.
`HavelHakimi.is_graphic`()	Return whether or not the initial sequence is graphic.
`HavelHakimi.get_process`()	Return the list of sequence produced during the Havel Hakimi process.
`HavelHakimi.residue`()	Return the residue of the sequence.

Functions¶

Release: latest

Date: May 30, 2019

Degree¶

Assorted degree related graph utilities.

`degree_sequence`(G)	Return the degree sequence of G.
`min_degree`(G)	Return the minimum degree of G.
`max_degree`(G)	Return the maximum degree of G.
`average_degree`(G)	Return the average degree of G.
`number_of_nodes_of_degree_k`(G, k)	Return the number of nodes of the graph with degree equal to k.
`number_of_degree_one_nodes`(G)	Return the number of nodes of the graph with degree equal to 1.
`number_of_min_degree_nodes`(G)	Return the number of nodes of the graph with degree equal to the minimum degree of the graph.
`number_of_max_degree_nodes`(G)	Return the number of nodes of the graph with degree equal to the maximum degree of the graph.
`neighborhood_degree_list`(G, nbunch)	Return a list of the unique degrees of all neighbors of nodes in nbunch.
`closed_neighborhood_degree_list`(G, nbunch)	Return a list of the unique degrees of all nodes in the closed neighborhood of the nodes in nbunch.

Neighborhoods¶

Functions for computing neighborhoods of vertices and sets of vertices.

`are_neighbors`(G, u, v)	Returns true if u is adjacent to v.
`closed_neighborhood`(G, v)	Return a list with v and of all neighbors of v.
`common_neighbors`(G, nodes)	Returns a list of all nodes in G that are adjacent to every node in nodes.
`neighborhood`(G, v)	Return a list of all neighbors of v.

Invariants¶

Release: latest

Date: May 30, 2019

Chromatic Number¶

Functions for computing the chromatic number of a graph.

chromatic_number(G) Returns the chromatic number of G.

Clique Number¶

Functions for computing independence related invariants for a graph.

clique_number(G[, cliques]) Return the clique number of the graph.

Disparity¶

Functions for computing disparity related invariants.

`vertex_disparity`(G, v)	Return number of distinct degrees of neighbors of v.
`closed_vertex_disparity`(G, v)	Return number of distinct degrees of nodes in the closed neighborhood of v.
`disparity_sequence`(G)	Return the sequence of disparities of each node in the graph.
`closed_disparity_sequence`(G)	Return the sequence of closed disparities of each node in the graph.
`CW_disparity`(G)	Return the Caro-Wei disparity of the graph.
`closed_CW_disparity`(G)	Return the closed Caro-Wei disparity of the graph.
`inverse_disparity`(G)	Return the inverse disparity of the graph.
`closed_inverse_disparity`(G)	Return the closed inverse disparity of the graph.
`average_vertex_disparity`(G)	Return the average vertex disparity of the graph.
`average_closed_vertex_disparity`(G)	Return the average closed vertex disparity of the graph.
`k_disparity`(G, k)	Return the k-disparity of the graph.
`closed_k_disparity`(G, k)	Return the closed k-disparity of the graph.
`irregularity`(G)	Return the irregularity measure of the graph.

Domination¶

Functions for computing dominating sets in a graph.

`is_k_dominating_set`(G, nodes, k)	Return whether or not nodes comprises a k-dominating set.
`is_total_dominating_set`(G, nodes)	Return whether or not nodes comprises a total dominating set.
`min_k_dominating_set`(G, k)	Return a smallest k-dominating set in the graph.
`min_dominating_set`(G)	Return a smallest dominating set in the graph.
`min_total_dominating_set`(G)	Return a smallest total dominating set in the graph.
`domination_number`(G)	Return the domination number the graph.
`k_domination_number`(G, k)	Return the k-domination number the graph.
`total_domination_number`(G)	Return the total domination number the graph.

DSI¶

Functions for computing DSI style invariants.

`sub_k_domination_number`(G, k)	Return the sub-k-domination number of the graph.
`slater`(G)	Return the Slater invariant for the graph.
`sub_total_domination_number`(G)	Return the sub-total domination number of the graph.
`annihilation_number`(G)	Return the annihilation number of the graph.

Independence¶

Functions for computing independence related invariants for a graph.

`is_independent_set`(G, nodes)	Return whether or not the nodes comprises an independent set.
`is_k_independent_set`(G, nodes, k)	Return whether or not the nodes in nodes comprise an a k-independent set.
`max_k_independent_set`(G, k)	Return a largest k-independent set of nodes in G.
`max_independent_set`(G)	Return a largest independent set of nodes in G.
`independence_number`(G)	Return a the independence number of G.
`k_independence_number`(G, k)	Return a the k-independence number of G.

Matching¶

Functions for computing matching related invariants for a graph.

`max_matching`(G)	Return a maximum matching in G.
`matching_number`(G)	Return the matching number of G.
`min_maximal_matching`(G)	Return a smallest maximal matching in G.
`min_maximal_matching_number`(G)	Return the minimum maximal matching number of G.

Power Domination¶

Functions for computing power domination related invariants of a graph.

`is_power_dominating_set`(G, nodes)	Return whether or not the nodes in nodes comprise a power dominating set.
`min_power_dominating_set`(G)	Return a smallest power dominating set of nodes in G.
`power_domination_number`(G)	Return the power domination number of G.

Residue¶

Functions for computing the residue and related invariants.

`residue`(G)	Return the residue of G.
`k_residue`(G, k)	Return the k-residue of G.

Zero Forcing¶

Functions for computing zero forcing related invariants of a graph.

`is_k_forcing_vertex`(G, v, nodes, k)	Return whether or not v can k-force relative to the set of nodes in nodes.
`is_k_forcing_active_set`(G, nodes, k)	Return whether or not at least one node in nodes can k-force.
`is_k_forcing_set`(G, nodes, k)	Return whether or not the nodes in nodes comprise a k-forcing set in G.
`min_k_forcing_set`(G, k)	Return a smallest k-forcing set in G.
`k_forcing_number`(G, k)	Return the k-forcing number of G.
`is_zero_forcing_vertex`(G, v, nbunch)	Return whether or not v can force relative to the set of nodes in nbunch.
`is_zero_forcing_active_set`(G, nbunch)	Return whether or not at least one node in nbunch can force.
`is_zero_forcing_set`(G, nbunch)	Return whether or not the nodes in nbunch comprise a zero forcing set in G.
`min_zero_forcing_set`(G)	Return a smallest zero forcing set in G.
`zero_forcing_number`(G)	Return the zero forcing number of G.

License¶

GrinPy is distributed with the 3-clause BSD license. As an extension of the NetworkX package, we list the pertinent copyright information as requested by the NetworkX authors.

GrinPy
------
Copyright (C) 2017, GrinPy Developers
David Amos <somacdivad@gmail.com>
Randy Davila <davilar@uhd.edu>

NetworkX
--------
Copyright (C) 2004-2017, NetworkX Developers
Aric Hagberg <hagberg@lanl.gov>
Dan Schult <dschult@colgate.edu>
Pieter Swart <swart@lanl.gov>
All rights reserved.

Redistribution and use in source and binary forms, with or without
modification, are permitted provided that the following conditions are
met:

  * Redistributions of source code must retain the above copyright
    notice, this list of conditions and the following disclaimer.

  * Redistributions in binary form must reproduce the above
    copyright notice, this list of conditions and the following
    disclaimer in the documentation and/or other materials provided
    with the distribution.

  * Neither the name of the NetworkX Developers nor the names of its
    contributors may be used to endorse or promote products derived
    from this software without specific prior written permission.

THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS
"AS IS" AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT
LIMITED TO, THE IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR
A PARTICULAR PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT
OWNER OR CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL,
SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT
LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE,
DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY
THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT
(INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE
OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.

Welcome to GrinPy¶

Audience¶

History¶

Free Software¶

Documentation¶

Tutorial¶

Calculating the Independence Number¶

Get a Maximum Independent Set¶

Determine if a Given Set is Independent¶

General Notes¶

Reference¶

Classes¶

HavelHakimi¶

Overview¶

Methods¶

Functions¶

Degree¶

Neighborhoods¶

Invariants¶

Chromatic Number¶

Clique Number¶

Disparity¶

Domination¶

DSI¶

Independence¶

Matching¶

Power Domination¶

Residue¶

Zero Forcing¶

License¶

Indices and tables¶