Skip to content
A Python library for computing matching and independence polynomials
Python
Branch: master
Clone or download
pernici added case periodicity in x in graphs_gen.py;
fixed case val=0 in ``dup_gen_count_hobj``;
eliminated `valued` and `pr` parameters from ``iadd_object``
Latest commit ccd3e49 Jul 3, 2014
Permalink
Type Name Latest commit message Commit time
Failed to load latest commit information.
bench
examples
src
tests
LICENCE
LICENSE
README.md
run_all.py

README.md

hobj

A Python library for computing matching and independence polynomials

Website: https://github.com/pernici/hobj

Author: Mario Pernici mario.pernici@gmail.com INFN - Sezione di Milano, Italy

hobj is free software released under the New BSD License (see the LICENSE file for details)

Dependences

There are no dependences.

One can use gmpy setting GMP = 1 in src/domains.py, but usually the pure Python version is faster (dup_permanental_minor_poly(m, QQ) is faster with gmpy).

Usage

Use python from the directory src, or add the path to it using

>>> import sys
>>> sys.path.append('path_to_hobj/src')

Examples:

>>> from hobj import dup_permanental_minor_poly
>>> from domains import ZZ
>>> m = [[i*j if abs(i-j) < 6 else 0 for i in range(20)] for j in range(20)]
>>> sum(dup_permanental_minor_poly(m, ZZ))
11936810897247956264161397956481650508142206788L
>>> dup_permanental_minor_poly(m, ZZ, 1)
11936810897247956264161397956481650508142206788L

>>> from hobj import dup_matching_generating_poly, dup_independence_poly
>>> from graphs_gen import dict_fuller
>>> d = dict_fuller(60)
>>> dup_matching_generating_poly(d, val=1)
1417036634543488
>>> dup_independence_poly(d, val=1)
217727997152

It can be used in Sage:

sage: from hobj import dup_matching_generating_poly
sage: g = graphs.PetersenGraph()
sage: d = g.to_dictionary()
sage: g.matching_polynomial()
x^10 - 15*x^8 + 75*x^6 - 145*x^4 + 90*x^2 - 6
sage: dup_matching_generating_poly(d)
[6, 90, 145, 75, 15, 1]

Notes

The code is organized in a way to be easily included in SymPy. The low-level representation of SymPy univariate polynomials is used; the code in src/densearith.py is taken from SymPy.

Eventually hobj.py will appear in a Pull Request for inclusion in SymPy.

Credits

Thanks to Paolo Butera: this module has been written in preparation of the article

P. Butera, M. Pernici ``Sums of permanental minors using Grassmann algebra'' http://arxiv.org/abs/1406.5337

You can’t perform that action at this time.