Document Open Access Logo

Practical Bigraphs via Subgraph Isomorphism

Authors Blair Archibald , Kyle Burns , Ciaran McCreesh , Michele Sevegnani

PDF
Thumbnail PDF

File

LIPIcs.CP.2021.15.pdf
  • Filesize: 1.66 MB
  • 17 pages

Document Identifiers

Author Details

Blair Archibald
  • School of Computing Science, University of Glasgow, UK
Kyle Burns
  • School of Computing Science, University of Glasgow, UK
Ciaran McCreesh
  • School of Computing Science, University of Glasgow, UK
Michele Sevegnani
  • School of Computing Science, University of Glasgow, UK

Funding

  • Archibald, Blair: supported by the EPSRC under grant S4: Science of Sensor Systems Software (EP/N007565/1).
  • Burns, Kyle: supported by the EPSRC under a Doctoral Training Partnership (EP/R513222/1).
  • McCreesh, Ciaran: supported by the EPSRC under grant Modelling and Optimisation with Graphs (EP/P026842/1).
  • Sevegnani, Michele: supported by the EPSRC under PETRAS SRF grant MAGIC (EP/S035362/1).

Cite As Get BibTex

Blair Archibald, Kyle Burns, Ciaran McCreesh, and Michele Sevegnani. Practical Bigraphs via Subgraph Isomorphism. In 27th International Conference on Principles and Practice of Constraint Programming (CP 2021). Leibniz International Proceedings in Informatics (LIPIcs), Volume 210, pp. 15:1-15:17, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2021) https://doi.org/10.4230/LIPIcs.CP.2021.15

Abstract

Bigraphs simultaneously model the spatial and non-spatial relationships between entities, and have been used for systems modelling in areas including biology, networking, and sensors. Temporal evolution can be modelled through a rewriting system, driven by a matching algorithm that identifies instances of bigraphs to be rewritten. The previous state-of-the-art matching algorithm for bigraphs with sharing is based on Boolean satisfiability (SAT), and suffers from a large encoding that limits scalability and makes it hard to support extensions. This work instead adapts a subgraph isomorphism solver that is based upon constraint programming to solve the bigraph matching problem. This approach continues to support bigraphs with sharing, is more open to other extensions and side constraints, and improves performance by over two orders of magnitude on a range of problem instances drawn from real-world mixed-reality, protocol, and conference models.

Subject Classification

ACM Subject Classification
  • Mathematics of computing → Graph algorithms
  • Theory of computation → Models of computation
Keywords
  • bigraphs
  • subgraph isomorphism
  • constraint programming
  • rewriting systems

Metrics

  • Access Statistics
  • Total Accesses (updated on a weekly basis)
    0
    PDF Downloads
    0
    Metadata Views

Supplementary Materials

References

  1. Faeq Alrimawi, Liliana Pasquale, and Bashar Nuseibeh. On the automated management of security incidents in smart spaces. IEEE Access, 7:111513-111527, 2019. URL: https://doi.org/10.1109/ACCESS.2019.2934221.
  2. Blair Archibald, Kyle Burns, Ciaran McCreesh, and Michele Sevegnani. Practical Bigraphs via Subgraph Isomorphism - Benchmark Instances and Results. URL: https://doi.org/10.5281/zenodo.4597074.
  3. Blair Archibald, Kyle Burns, Ciaran McCreesh, and Michele Sevegnani. Practical Bigraphs via Subgraph Isomorphism - Glasgow Subgraph Solver Bigraph Source Code. URL: https://doi.org/10.5281/zenodo.5161185.
  4. Blair Archibald, Muffy Calder, and Michele Sevegnani. Conditional bigraphs. In Fabio Gadducci and Timo Kehrer, editors, Graph Transformation - 13th International Conference, ICGT 2020, volume 12150 of Lecture Notes in Computer Science, pages 3-19. Springer, 2020. URL: https://doi.org/10.1007/978-3-030-51372-6_1.
  5. Blair Archibald, Fraser Dunlop, Ruth Hoffmann, Ciaran McCreesh, Patrick Prosser, and James Trimble. Sequential and parallel solution-biased search for subgraph algorithms. In Integration of Constraint Programming, Artificial Intelligence, and Operations Research - 16th International Conference, CPAIOR 2019, Proceedings, 2019. URL: https://doi.org/10.1007/978-3-030-19212-9_2.
  6. Blair Archibald, Min-Zheng Shieh, Yu-Hsuan Hu, Michele Sevegnani, and Yi-Bing Lin. BigraphTalk: Verified design of IoT applications. IEEE Internet Things J., 7(4):2955-2967, 2020. URL: https://doi.org/10.1109/JIOT.2020.2964026.
  7. Gilles Audemard, Christophe Lecoutre, Mouny Samy Modeliar, Gilles Goncalves, and Daniel Cosmin Porumbel. Scoring-based neighborhood dominance for the subgraph isomorphism problem. In Principles and Practice of Constraint Programming - 20th International Conference, CP 2014, 2014. URL: https://doi.org/10.1007/978-3-319-10428-7_12.
  8. Giorgio Bacci, Davide Grohmann, and Marino Miculan. DBtk: A toolkit for directed bigraphs. In Algebra and Coalgebra in Computer Science, Third International Conference, CALCO 2009. Proceedings, pages 413-422, 2009. URL: https://doi.org/10.1007/978-3-642-03741-2_28.
  9. Steve Benford, Muffy Calder, Tom Rodden, and Michele Sevegnani. On lions, impala, and bigraphs: Modelling interactions in physical/virtual spaces. ACM Trans. Comput.-Hum. Interact., 23(2):9:1-9:56, 2016. URL: https://doi.org/10.1145/2882784.
  10. Muffy Calder, Alexandros Koliousis, Michele Sevegnani, and Joseph S. Sventek. Real-time verification of wireless home networks using bigraphs with sharing. Science of Computer Programming, 80:288-310, 2014. URL: https://doi.org/10.1016/j.scico.2013.08.004.
  11. Muffy Calder and Michele Sevegnani. Modelling IEEE 802.11 CSMA/CA RTS/CTS with stochastic bigraphs with sharing. Formal Asp. Comput., 26(3):537-561, 2014. URL: https://doi.org/10.1007/s00165-012-0270-3.
  12. Alessio Chiapperini, Marino Miculan, and Marco Peressotti. Computing embeddings of directed bigraphs. In Fabio Gadducci and Timo Kehrer, editors, Graph Transformation - 13th International Conference, ICGT 2020, volume 12150 of Lecture Notes in Computer Science, pages 38-56. Springer, 2020. URL: https://doi.org/10.1007/978-3-030-51372-6_3.
  13. Niklas Eén and Niklas Sörensson. An extensible SAT-solver. In Enrico Giunchiglia and Armando Tacchella, editors, Theory and Applications of Satisfiability Testing, 6th International Conference, SAT 2003., volume 2919 of Lecture Notes in Computer Science, pages 502-518. Springer, 2003. URL: https://doi.org/10.1007/978-3-540-24605-3_37.
  14. Amal Gassara, Ismael Bouassida Rodriguez, Mohamed Jmaiel, and Khalil Drira. Executing bigraphical reactive systems. Discret. Appl. Math., 253:73-92, 2019. URL: https://doi.org/10.1016/j.dam.2018.07.006.
  15. Arne John Glenstrup, Troels Christoffer Damgaard, Lars Birkedal, and Espen Højsgaard. An implementation of bigraph matching. Technical Report TR-2010-135, IT University of Copenhagen, 2010. Google Scholar
  16. Davide Grohmann and Marino Miculan. Directed bigraphs. In Marcelo Fiore, editor, Proceedings of the 23rd Conference on the Mathematical Foundations of Programming Semantics, MFPS 2007, volume 173 of Electronic Notes in Theoretical Computer Science, pages 121-137. Elsevier, 2007. URL: https://doi.org/10.1016/j.entcs.2007.02.031.
  17. Ruth Hoffmann, Ciaran McCreesh, Samba Ndojh Ndiaye, Patrick Prosser, Craig Reilly, Christine Solnon, and James Trimble. Observations from parallelising three maximum common (connected) subgraph algorithms. In Integration of Constraint Programming, Artificial Intelligence, and Operations Research - 15th International Conference, CPAIOR 2018, pages 298-315, 2018. URL: https://doi.org/10.1007/978-3-319-93031-2_22.
  18. Jean Krivine, Robin Milner, and Angelo Troina. Stochastic bigraphs. Electr. Notes Theor. Comput. Sci., 218:73-96, 2008. URL: https://doi.org/10.1016/j.entcs.2008.10.006.
  19. Mark H. Liffiton and Jordyn C. Maglalang. A cardinality solver: More expressive constraints for free - (poster presentation). In Alessandro Cimatti and Roberto Sebastiani, editors, Theory and Applications of Satisfiability Testing - SAT 2012 - 15th International Conference, Trento, Italy, June 17-20, 2012. Proceedings, volume 7317 of Lecture Notes in Computer Science, pages 485-486. Springer, 2012. URL: https://doi.org/10.1007/978-3-642-31612-8_47.
  20. Ciaran McCreesh and Patrick Prosser. A parallel, backjumping subgraph isomorphism algorithm using supplemental graphs. In Principles and Practice of Constraint Programming - 21st International Conference, CP 2015, Proceedings, 2015. URL: https://doi.org/10.1007/978-3-319-23219-5_21.
  21. Ciaran McCreesh, Patrick Prosser, Christine Solnon, and James Trimble. When subgraph isomorphism is really hard, and why this matters for graph databases. J. Artif. Intell. Res., 61:723-759, 2018. URL: https://doi.org/10.1613/jair.5768.
  22. Ciaran McCreesh, Patrick Prosser, and James Trimble. The Glasgow Subgraph Solver: Using constraint programming to tackle hard subgraph isomorphism problem variants. In Graph Transformation - 13th International Conference, ICGT 2020, pages 316-324, 2020. URL: https://doi.org/10.1007/978-3-030-51372-6_19.
  23. Robin Milner. Local bigraphs and confluence: Two conjectures: (extended abstract). Electr. Notes Theor. Comput. Sci., 175(3):65-73, 2007. URL: https://doi.org/10.1016/j.entcs.2006.07.035.
  24. Robin Milner. The Space and Motion of Communicating Agents. Cambridge University Press, 2009. Google Scholar
  25. Michele Sevegnani and Muffy Calder. Bigraphs with sharing. Theor. Comput. Sci., 577:43-73, 2015. URL: https://doi.org/10.1016/j.tcs.2015.02.011.
  26. Michele Sevegnani and Muffy Calder. BigraphER: Rewriting and analysis engine for bigraphs. In Computer Aided Verification - 28th International Conference, CAV 2016. Proceedings, Part II, pages 494-501, 2016. URL: https://doi.org/10.1007/978-3-319-41540-6_27.
  27. Michele Sevegnani, Milan Kabác, Muffy Calder, and Julie A. McCann. Modelling and verification of large-scale sensor network infrastructures. In 23rd International Conference on Engineering of Complex Computer Systems, ICECCS 2018, pages 71-81. IEEE Computer Society, 2018. URL: https://doi.org/10.1109/ICECCS2018.2018.00016.
  28. Christine Solnon. Alldifferent-based filtering for subgraph isomorphism. Artif. Intell., 174(12-13):850-864, 2010. URL: https://doi.org/10.1016/j.artint.2010.05.002.
  29. Stéphane Zampelli, Yves Deville, and Christine Solnon. Solving subgraph isomorphism problems with constraint programming. Constraints, 15(3):327-353, 2010. URL: https://doi.org/10.1007/s10601-009-9074-3.
Questions / Remarks / Feedback
X

Feedback for Dagstuhl Publishing


Thanks for your feedback!

Feedback submitted

Could not send message

Please try again later or send an E-mail
© 2023-2024 Schloss Dagstuhl – LZI GmbH About DROPS Imprint Privacy Contact