×

Constraints for generating graphs with imposed and forbidden patterns: an application to molecular graphs. (English) Zbl 1477.68244

Summary: Although graphs are widely used to encode and solve various computational problems, little research exists on constrained graph construction. The current research was carried out to shed light on the problem of generating graphs, where the construction process is guided by various structural restrictions, like vertex degrees, proximity among vertices, and imposed and forbidden patterns. The main contribution of this paper is an encoding of the constrained graph generation problem in terms of a constraint satisfaction problem (CSP). This approach is motivated by the flurry of efficient solution algorithms available within the constraint programming (CP) framework. The obtained encoding has given rise to the CP-MolGen program, a new open source program dedicated to the generation of molecular graphs with imposed and forbidden fragments. Experimental results on several real-world molecular graph generation instances have shown the effectiveness and efficiency of the proposed program, especially the benefits of forbidding cyclic patterns as induced subgraphs.

MSC:

68R10 Graph theory (including graph drawing) in computer science
05C92 Chemical graph theory
90C27 Combinatorial optimization
90C35 Programming involving graphs or networks

Software:

CDK; CPGraph; MINION; Choco; OMG; Gecode
PDFBibTeX XMLCite
Full Text: DOI

References:

[1] Apt, K., Constraint Logic Programming Using ECLiPSe (2007), Cambridge: Cambridge University Press, Cambridge · Zbl 1119.68044
[2] Barvinok, A.; Hartigan, J., The number of graphs and a random graph with a given degree sequence, Random Structures &, Algorithms, 42, 3, 301-348 (2012) · Zbl 1264.05125 · doi:10.1002/rsa.20409
[3] Bayati, M., Montanari, A., Saberi, A. (2009). Generating random graphs with large girth. In: Proceedings of the Twentieth Annual ACM-SIAM Symposium on Discrete Algorithms (pp. 566-575). Society for Industrial and Applied Mathematics. 10.1137/1.9781611973068.63. · Zbl 1423.05161
[4] Bistarelli, S.; Montanari, U.; Rossi, F.; Schiex, T.; Verfaillie, G.; Fargier, H., Semiring-based CSPs and Valued CSPs: Frameworks, properties, and comparison, Constraints, 4, 3, 199-240 (1999) · Zbl 0946.68143 · doi:10.1023/A:1026441215081
[5] Brown, K.N., Prosser, P., Beck, J.C., Wu, C.W. (2005). Exploring the use of constraint programming for enforcing connectivity during graph generation. In: 5Th Workshop on Modelling and Solving Problems with Constraints. ACM.
[6] Corander, J., Janhunen, T., Rintanen, J., Nyman, H.J., Pensar, J. (2013). Learning chordal markov networks by constraint satisfaction, pp. 1349-1357. arXiv:1310.0927.
[7] Dooms, G., Deville, Y., Dupont, P. (2005). Constrained metabolic network analysis: discovering pathways using CP(Graph). In: Workshop on Constraint Based Methods for Bioinformatics (pp. 29-35).
[8] Dooms, G., Deville, Y., Dupont, P. (2005). CP(GRaph): Introducing a graph computation domain in constraint programming. In Proceedings of the 11th International Conference on Principles and Practice of Constraint Programming, CP05 (pp. 211-225). Berlin: Springer. · Zbl 1153.68457
[9] Elyashberg, ME; Blinov, KA; Williams, AJ; Molodtsov, SG; Martin, GE; Martirosian, ER, Structure Elucidator: A versatile expert system for molecular structure elucidation from 1D and 2D NMR data and molecular fragments, Journal of Chemical Information and Computer Sciences, 44, 3, 771-792 (2004) · doi:10.1021/ci0341060
[10] Erdös, P., Graph theory and probability, Canadian Journal of Mathematics, 11, 34-38 (1959) · Zbl 0084.39602 · doi:10.4153/CJM-1959-003-9
[11] Fages, JG, On the use of graphs within constraint-programming, Constraints, 20, 498-499 (2014) · doi:10.1007/s10601-015-9223-9
[12] Frieze, A., & Karoński, M. (2016). Introduction to random graphs. Cambridge University Press. · Zbl 1328.05002
[13] G Tack, M.L., & Schulte, C. Gecode: generic constraint development environment. http://www.gecode.org/. Accessed: 2019-05-02.
[14] Garey, MR; Johnson, DS, Computers and Intractability; A Guide to the Theory of NP-completeness (1990), New York: W. H. Freeman & Co., New York
[15] Genio, CID; Kim, H.; Toroczkai, Z.; Bassler, KE, Efficient and exact sampling of simple graphs with given arbitrary degree sequence, PLoS ONE, 5, 4, e10012 (2010) · doi:10.1371/journal.pone.0010012
[16] Genova, D.; Jonoska, N., Forbidding and enforcing on graphs, Theoretical Computer Science, 429, 108-117 (2012) · Zbl 1242.05228 · doi:10.1016/j.tcs.2011.12.029
[17] Gent, I., Jefferson, C., Miguel, I. (2006). MINION: A fast, scalable, constraint solver. In: ECAI 2006: 17Th European Conference on Artificial Intelligence, Frontiers in Artificial Intelligence and Applications (pp. 98-102). IOS press.
[18] Gent, IP; Macintyre, E.; Prosser, P.; Smith, BM; Walsh, T., Random constraint satisfaction: Flaws and structure, Constraints, 6, 4, 345-372 (2001) · Zbl 0992.68193 · doi:10.1023/A:1011454308633
[19] van der Hofstad, R. (2016). Random graphs and complex networks cambridge university press. 10.1017/9781316779422. · Zbl 1361.05002
[20] IBM: IBM ILOG Solver V6.7. https://www.ibm.com/analytics/cplex-cp-optimizer. Accessed: 2019-05-02.
[21] Jaspars, M., Computer assisted structure elucidation of natural products using two-dimensional NMR spectroscopy, Natural Product Reports, 16, 2, 241-248 (1999) · doi:10.1039/a804433c
[22] Laburthe, F. (2000). CHOCO: Implementing A CP kernel. In: CP00 Post Conference Workshop on Techniques for Implementing Constraint Programming Systems (TRICS).
[23] Lehmberg, O., Meusel, R., Bizer, C. (2014). Graph structure in the web: Aggregated by pay-level domain. In Proceedings of the 2014 ACM Conference on Web Science, WebSci’14. 10.1145/2615569.2615674 (pp. 119-128). New York: ACM.
[24] Liebenau, A., & Wormald, N. (2017). Asymptotic enumeration of graphs by degree sequence, and the degree sequence of a random graph. arXiv:1702.08373.
[25] MacKay, D.J.C. (2003). Information theory, inference and learning algorithms. Cambridge University Press. · Zbl 1055.94001
[26] Masui, H.; Hong, H., Spec2D: a structure elucidation system based on 1H NMR and h-H COSY spectra in organic chemistry, Journal of Chemical Information and Modeling, 46, 2, 775-787 (2006) · doi:10.1021/ci0502810
[27] Melançon, G., Dutour, I., Bousquet-Mélou, M. (2001). Random generation of directed acyclic graphs. In: Comb01, Euroconference on Combinatorics, Graph Theory and Applications, pp. 1-7. Spain. · Zbl 1171.05339
[28] Meringer, M.; Schymanski, E., Small molecule identification with MOLGEN and mass spectrometry, Metabolites, 3, 2, 440-462 (2013) · doi:10.3390/metabo3020440
[29] Mihail, M., & Vishnoi, N.K. (2003). On generating graphs with prescribed vertex degrees for complex network modeling. In: 3Rd Workshop on Approximation and Randomization Algorithms in Communication NEtworks.
[30] Milo, R., Kashtan, N., Itzkovitz, S., Newman, M.E., Alon, U. (2003). On the uniform generation of random graphs with prescribed degree sequences. arXiv:cond-mat/0312028.
[31] Nuzillard, JM; Naanaa, W.; Pimont, S., Applying the constraint satisfaction problem paradigm to structure generation, Journal of Chemical Information and Modeling, 35, 6, 1068-1073 (1995) · doi:10.1021/ci00028a018
[32] Nuzillard, J.M., & Plainchont, B. (2017). Tutorial for the structure elucidation of small molecules by means of the LSD software. Magnetic resonance in chemistry : MRC 56. 10.1002/mrc.4612.
[33] Omrani, M.A., & Naanaa, W. (2016). A constrained molecular graph generation with imposed and forbidden fragments. In: Proceedings of the 9th Hellenic Conference on Artificial Intelligence - SETN16. ACM Press. 10.1145/2903220.2903234.
[34] Peironcely, JE; Rojas-Chertó, M.; Fichera, D.; Reijmers, T.; Coulier, L.; Faulon, JL; Hankemeier, T., OMG: Open Molecule generator, Journal of Cheminformatics, 4, 1, 21 (2012) · doi:10.1186/1758-2946-4-21
[35] Reinelt, G., The Traveling Salesman: Computational Solutions for TSP Applications (1994), Berlin: Springer, Berlin · Zbl 0825.90720
[36] Sarkar, D.; Sarkar, UK; Peng, G., Bandwidth requirement of links in a hierarchical caching network: a graph-based formulation, an algorithm and its performance evaluation, International Journal of Computers and Applications, 29, 1, 70-78 (2007) · doi:10.1080/1206212X.2007.11441834
[37] Steinbeck, C.; Han, Y.; Kuhn, S.; Horlacher, O.; Luttmann, E.; Willighagen, E., The chemistry development kit (CDK): an open-source java library for chemo- and bioinformatics, Journal of Chemical Information and Computer Sciences, 43, 2, 493-500 (2003) · doi:10.1021/ci025584y
[38] Tsang, E. (2014). Foundations of constraint satisfaction. books on demand.
[39] Williams, R. (2013). Faster all-pairs shortest paths via circuit complexity. CoRR arXiv:abs/1312.6680. · Zbl 1315.68282
[40] Zampelli, S.; Deville, Y.; Solnon, C., Solving subgraph isomorphism problems with constraint programming, Constraints, 15, 3, 327-353 (2010) · Zbl 1213.68473 · doi:10.1007/s10601-009-9074-3
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.