Changeset 1142:2f479109a71d in lemon-main for doc

Timestamp:

05/14/15 16:07:38 (10 years ago)

Author:

Alpar Juttner <alpar@…>

Branch:

default

Phase:

public

Message:

Documentation for VF2 (#597)

The implementation of this feature was sponsored by QuantumBio? Inc.

Location:

doc

Files:

• groups.dox (modified) (1 diff)
• named-param.dox (modified) (1 diff)
• references.bib (modified) (1 diff)

doc/groups.dox

@@ -562 +562 @@
 
 /**
+@defgroup graph_isomorphism Graph Isomorphism
+@ingroup algs
+\brief Algorithms for testing (sub)graph isomorphism
+
+This group contains algorithms for finding isomorph copies of a
+given graph in another one, or simply check whether two graphs are isomorphic.
+
+The formal definition of subgraph isomorphism is as follows.
+
+We are given two graphs, \f$G_1=(V_1,E_1)\f$ and \f$G_2=(V_2,E_2)\f$. A
+function \f$f:V_1\longrightarrow V_2\f$ is called \e mapping or \e
+embedding if \f$f(u)\neq f(v)\f$ whenever \f$u\neq v\f$.
+
+The standard <em>Subgraph Isomorphism Problem (SIP)</em> looks for a
+mapping with the property that whenever \f$(u,v)\in E_1\f$, then
+\f$(f(u),f(v))\in E_2\f$.
+
+In case of <em>Induced Subgraph Isomorphism Problem (ISIP)</em> one
+also requires that if \f$(u,v)\not\in E_1\f$, then \f$(f(u),f(v))\not\in
+E_2\f$
+
+In addition, the graph nodes may be \e labeled, i.e. we are given two
+node labelings \f$l_1:V_1\longrightarrow L\f$ and \f$l_2:V_2\longrightarrow
+L\f$ and we require that \f$l_1(u)=l_2(f(u))\f$ holds for all nodes \f$u \in
+G\f$.
+
+*/
+
+/**
 @defgroup planar Planar Embedding and Drawing
 @ingroup algs

doc/named-param.dox

@@ -26 +26 @@
 function parameters by name also when you call the function. It is
 especially comfortable in case of a function having tons of parameters
-with natural default values. Sadly, C++ lack this amenity.
+with natural default values. Sadly, C++ lacks this amenity.
 
 However, with a crafty trick and with some little

doc/references.bib

@@ -355 +355 @@
   pages =        {587--612}
 }
+
+@article{cordella2004sub,
+  title =        {A (sub) graph isomorphism algorithm for matching
+                  large graphs},
+  author =       {Cordella, Luigi P and Foggia, Pasquale and Sansone,
+                  Carlo and Vento, Mario},
+  journal =      {Pattern Analysis and Machine Intelligence, IEEE
+                  Transactions on},
+  volume =       26,
+  number =       10,
+  pages =        {1367--1372},
+  year =         2004,
+  publisher =    {IEEE}
+}