# HG changeset patch
# User Peter Kovacs <kpeter@inf.elte.hu>
# Date 1507339129 -7200
# Node ID 76349d8212d3953003885aabcef528a29de3d42d
# Parent 120b9031eadac340f6078b85d9bcb43c9342bc93
Improve and unify comments and API docs of VF2 algorithms (#597)
diff -r 120b9031eada -r 76349d8212d3 lemon/bits/vf2_internals.h
--- a/lemon/bits/vf2_internals.h Sat Oct 07 00:14:05 2017 +0200
+++ b/lemon/bits/vf2_internals.h Sat Oct 07 03:18:49 2017 +0200
@@ -26,7 +26,7 @@
namespace lemon {
///\ingroup graph_isomorphism
///The \ref Vf2 "VF2" algorithm is capable of finding different kind of
- ///embeddings, this enum specifies its type.
+ ///graph embeddings, this enum specifies their types.
///
///See \ref graph_isomorphism for a more detailed description.
enum MappingType {
@@ -35,13 +35,12 @@
/// Induced subgraph isomorphism
INDUCED = 1,
/// Graph isomorphism
-
- /// If the two graph has the same number of nodes, than it is
+ ///
+ /// If the two graphs have the same number of nodes, than it is
/// equivalent to \ref INDUCED, and if they also have the same
/// number of edges, then it is also equivalent to \ref SUBGRAPH.
///
- /// However, using this setting is faster than the other two
- /// options.
+ /// However, using this setting is faster than the other two options.
ISOMORPH = 2
};
}
diff -r 120b9031eada -r 76349d8212d3 lemon/vf2.h
--- a/lemon/vf2.h Sat Oct 07 00:14:05 2017 +0200
+++ b/lemon/vf2.h Sat Oct 07 03:18:49 2017 +0200
@@ -53,8 +53,6 @@
}
};
-
-
template <class G>
class DfsLeaveOrder : public DfsVisitor<G> {
const G &_g;
@@ -93,7 +91,7 @@
///
///There is also a \ref vf2() "function-type interface" called \ref vf2()
///for the %VF2 algorithm, which is probably more convenient in most
- ///use-cases.
+ ///use cases.
///
///\tparam G1 The type of the graph to be embedded.
///The default type is \ref ListDigraph.
@@ -102,7 +100,7 @@
///\tparam M The type of the NodeMap storing the mapping.
///By default, it is G1::NodeMap<G2::Node>
///\tparam NEQ A bool-valued binary functor determinining whether a node is
- ///mappable to another. By default it is an always true operator.
+ ///mappable to another. By default, it is an always-true operator.
///
///\sa vf2()
#ifdef DOXYGEN
@@ -116,23 +114,31 @@
class Vf2 {
//Current depth in the DFS tree.
int _depth;
+
//Functor with bool operator()(G1::Node,G2::Node), which returns 1
- //ifff the two nodes are equivalent.
+ //if and only if the two nodes are equivalent
NEQ _nEq;
+ //_conn[v2] = number of covered neighbours of v2
typename G2::template NodeMap<int> _conn;
- //Current mapping. We index it by the nodes of g1, and match[v] is
- //a node of g2.
+
+ //The current mapping. _mapping[v1]=v2 iff v1 has been mapped to v2,
+ //where v1 is a node of G1 and v2 is a node of G2
M &_mapping;
- //order[i] is the node of g1, for which we search a pair if depth=i
+
+ //order[i] is the node of g1 for which a pair is searched if depth=i
std::vector<typename G1::Node> order;
- //currEdgeIts[i] is an edge iterator, witch is last used in the ith
- //depth to find a pair for order[i].
+
+ //currEdgeIts[i] is the last used edge iterator in the i-th
+ //depth to find a pair for node order[i]
std::vector<typename G2::IncEdgeIt> currEdgeIts;
- //The small graph.
+
+ //The graph to be embedded
const G1 &_g1;
- //The large graph.
+
+ //The graph into which g1 is to be embedded
const G2 &_g2;
+
//lookup tables for cutting the searchtree
typename G1::template NodeMap<int> rNew1t,rInOut1t;
@@ -242,34 +248,34 @@
template<MappingType MT>
bool extMatch() {
while(_depth>=0) {
- //there are not nodes in g1, which has not pair in g2.
if(_depth==static_cast<int>(order.size())) {
+ //all nodes of g1 are mapped to nodes of g2
--_depth;
return true;
}
typename G1::Node& nodeOfDepth = order[_depth];
const typename G2::Node& pairOfNodeOfDepth = _mapping[nodeOfDepth];
typename G2::IncEdgeIt &edgeItOfDepth = currEdgeIts[_depth];
- //the node of g2, which neighbours are the candidates for
+ //the node of g2 whose neighbours are the candidates for
//the pair of nodeOfDepth
typename G2::Node currPNode;
if(edgeItOfDepth==INVALID) {
typename G1::IncEdgeIt fstMatchedE(_g1,nodeOfDepth);
- //if pairOfNodeOfDepth!=INVALID, we dont use
- //fstMatchedE
- if(pairOfNodeOfDepth==INVALID)
+ //if pairOfNodeOfDepth!=INVALID, we don't use fstMatchedE
+ if(pairOfNodeOfDepth==INVALID) {
for(; fstMatchedE!=INVALID &&
_mapping[_g1.oppositeNode(nodeOfDepth,
fstMatchedE)]==INVALID;
++fstMatchedE) ; //find fstMatchedE
+ }
if(fstMatchedE==INVALID||pairOfNodeOfDepth!=INVALID) {
- //We found no covered neighbours, this means
- //the graph is not connected(or _depth==0). Each
- //uncovered(and there are some other properties due
+ //We found no covered neighbours, this means that
+ //the graph is not connected (or _depth==0). Each
+ //uncovered (and there are some other properties due
//to the spec. problem types) node of g2 is
- //candidate. We can read the iterator of the last
+ //candidate. We can read the iterator of the last
//tried node from the match if it is not the first
- //try(match[nodeOfDepth]!=INVALID)
+ //try (match[nodeOfDepth]!=INVALID)
typename G2::NodeIt n2(_g2);
//if it's not the first try
if(pairOfNodeOfDepth!=INVALID) {
@@ -317,7 +323,7 @@
return false;
}
- //calc. the lookup table for cut the searchtree
+ //calculate the lookup table for cutting the search tree
void setRNew1tRInOut1t() {
typename G1::template NodeMap<int> tmp(_g1,0);
for(unsigned int i=0; i<order.size(); ++i) {
@@ -351,7 +357,8 @@
Vf2(const G1 &g1, const G2 &g2, M &m, const NEQ &neq = NEQ() ) :
_nEq(neq), _conn(g2,0), _mapping(m), order(countNodes(g1)),
currEdgeIts(countNodes(g1),INVALID), _g1(g1), _g2(g2), rNew1t(g1,0),
- rInOut1t(g1,0), _mapping_type(SUBGRAPH), _deallocMappingAfterUse(0) {
+ rInOut1t(g1,0), _mapping_type(SUBGRAPH), _deallocMappingAfterUse(0)
+ {
_depth=0;
setOrder();
setRNew1tRInOut1t();
@@ -440,11 +447,11 @@
/// Auxiliary class for the function-type interface of %VF2 algorithm.
-
+ ///
/// This auxiliary class implements the named parameters of
/// \ref vf2() "function-type interface" of \ref Vf2 algorithm.
///
- /// \warning This class should only be used through the function \ref vf2().
+ /// \warning This class is not to be used directly.
///
/// \tparam TR The traits class that defines various types used by the
/// algorithm.
@@ -465,11 +472,10 @@
public:
///Constructor
- Vf2Wizard(const Graph1 &g1,const Graph2 &g2) : Base(g1,g2) {
- }
+ Vf2Wizard(const Graph1 &g1,const Graph2 &g2) : Base(g1,g2) {}
///Copy constructor
- Vf2Wizard(const Base &b) : Base(b) { }
+ Vf2Wizard(const Base &b) : Base(b) {}
///Copy constructor
Vf2Wizard(const Vf2Wizard &b) : Base(b) {}
diff -r 120b9031eada -r 76349d8212d3 lemon/vf2pp.h
--- a/lemon/vf2pp.h Sat Oct 07 00:14:05 2017 +0200
+++ b/lemon/vf2pp.h Sat Oct 07 03:18:49 2017 +0200
@@ -75,7 +75,7 @@
///
///There is also a \ref vf2pp() "function-type interface" called
///\ref vf2pp() for the %VF2 Plus Plus algorithm, which is probably
- ///more convenient in most use-cases.
+ ///more convenient in most use cases.
///
///\tparam G1 The type of the graph to be embedded.
///The default type is \ref ListDigraph.
@@ -96,11 +96,8 @@
#else
template<class G1=ListDigraph,
class G2=ListDigraph,
- class M = typename G1::template NodeMap<G2::Node>,//the mapping
- //labels of G1,the labels are the numbers {0,1,2,..,K-1},
- //where K is the number of different labels
+ class M = typename G1::template NodeMap<G2::Node>,
class M1 = typename G1::template NodeMap<int>,
- //labels of G2, ...
class M2 = typename G2::template NodeMap<int> >
#endif
class Vf2pp {
@@ -114,17 +111,17 @@
//where v1 is a node of G1 and v2 is a node of G2
M &_mapping;
- //order[i] is a node of g1, for which a pair is searched if depth=i
+ //order[i] is a node of g1 for which a pair is searched if depth=i
std::vector<typename G1::Node> order;
- //currEdgeIts[i] is the last used edge iterator in the ith
+ //currEdgeIts[i] is the last used edge iterator in the i-th
//depth to find a pair for node order[i]
std::vector<typename G2::IncEdgeIt> currEdgeIts;
-
- //The small graph.
+
+ //The graph to be embedded
const G1 &_g1;
- //The large graph.
+ //The graph into which g1 is to be embedded
const G2 &_g2;
//rNewLabels1[v] is a pair of form
@@ -137,24 +134,24 @@
typename G1::template NodeMap<std::vector<std::pair<int,int> > >
rInOutLabels1;
- //_intLabels1[v]==i means that vertex v has the i label in
- //_g1 (i is in {0,1,2,..,K-1}, where K is the number of diff. labels)
+ //_intLabels1[v]==i means that node v has label i in _g1
+ //(i is in {0,1,2,..,K-1}, where K is the number of diff. labels)
M1 &_intLabels1;
- //_intLabels2[v]==i means that vertex v has the i label in
- //_g2 (i is in {0,1,2,..,K-1}, where K is the number of diff. labels)
+ //_intLabels2[v]==i means that node v has label i in _g2
+ //(i is in {0,1,2,..,K-1}, where K is the number of diff. labels)
M2 &_intLabels2;
//largest label
const int maxLabel;
//lookup tables for manipulating with label class cardinalities
- //after use they have to be reset to 0..0
+ //(after use they have to be reset to 0..0)
std::vector<int> labelTmp1,labelTmp2;
MappingType _mapping_type;
- //indicates whether the mapping or the labels must be deleted in the ctor
+ //indicates whether the mapping or the labels must be deleted in the destructor
bool _deallocMappingAfterUse,_deallocLabelsAfterUse;
@@ -286,8 +283,7 @@
return isIso&&cutByLabels<MT>(n1,n2);
}
-
- //matches n1 and n2
+ //maps n1 to n2
void addPair(const typename G1::Node n1,const typename G2::Node n2) {
_conn[n2]=-1;
_mapping.set(n1,n2);
@@ -298,8 +294,7 @@
}
}
-
- //dematches n1 and n2
+ //removes mapping of n1 to n2
void subPair(const typename G1::Node n1,const typename G2::Node n2) {
_conn[n2]=0;
_mapping.set(n1,INVALID);
@@ -312,7 +307,6 @@
}
}
-
void processBFSLevel(typename G1::Node source,unsigned int& orderIndex,
typename G1::template NodeMap<int>& dm1,
typename G1::template NodeMap<bool>& added) {
@@ -364,7 +358,6 @@
for(typename G2::NodeIt n2(_g2); n2!=INVALID; ++n2)
++labelTmp1[_intLabels2[n2]];
- // OutDegMap<G1> dm1(_g1);
typename G1::template NodeMap<int> dm1(_g1,0);
for(typename G1::EdgeIt e(_g1); e!=INVALID; ++e) {
++dm1[_g1.u(e)];
@@ -397,34 +390,34 @@
template<MappingType MT>
bool extMatch(){
while(_depth>=0) {
- //there is no node in g1, which has not pair in g2.
if(_depth==static_cast<int>(order.size())) {
+ //all nodes of g1 are mapped to nodes of g2
--_depth;
return true;
}
typename G1::Node& nodeOfDepth = order[_depth];
const typename G2::Node& pairOfNodeOfDepth = _mapping[nodeOfDepth];
typename G2::IncEdgeIt &edgeItOfDepth = currEdgeIts[_depth];
- //the node of g2, which neighbours are the candidates for
+ //the node of g2 whose neighbours are the candidates for
//the pair of order[_depth]
typename G2::Node currPNode;
if(edgeItOfDepth==INVALID){
typename G1::IncEdgeIt fstMatchedE(_g1,nodeOfDepth);
- //if _mapping[order[_depth]]!=INVALID, we dont need
- //fstMatchedE
- if(pairOfNodeOfDepth==INVALID)
+ //if _mapping[order[_depth]]!=INVALID, we don't need fstMatchedE
+ if(pairOfNodeOfDepth==INVALID) {
for(; fstMatchedE!=INVALID &&
_mapping[_g1.oppositeNode(nodeOfDepth,
fstMatchedE)]==INVALID;
++fstMatchedE); //find fstMatchedE, it could be preprocessed
+ }
if(fstMatchedE==INVALID||pairOfNodeOfDepth!=INVALID) {
- //We found no covered neighbours, this means
- //the graph is not connected(or _depth==0). Each
- //uncovered(and there are some other properties due
+ //We found no covered neighbours, this means that
+ //the graph is not connected (or _depth==0). Each
+ //uncovered (and there are some other properties due
//to the spec. problem types) node of g2 is
- //candidate. We can read the iterator of the last
+ //candidate. We can read the iterator of the last
//tried node from the match if it is not the first
- //try(match[nodeOfDepth]!=INVALID)
+ //try (match[nodeOfDepth]!=INVALID)
typename G2::NodeIt n2(_g2);
//if it's not the first try
if(pairOfNodeOfDepth!=INVALID) {
@@ -447,13 +440,13 @@
--_depth;
continue;
}
- else{
+ else {
currPNode=_mapping[_g1.oppositeNode(nodeOfDepth,
fstMatchedE)];
edgeItOfDepth=typename G2::IncEdgeIt(_g2,currPNode);
}
}
- else{
+ else {
currPNode=_g2.oppositeNode(pairOfNodeOfDepth,
edgeItOfDepth);
subPair(nodeOfDepth,pairOfNodeOfDepth);
@@ -472,7 +465,7 @@
return false;
}
- //calc. the lookup table for cutting the searchtree
+ //calculate the lookup table for cutting the search tree
void setRNew1tRInOut1t(){
typename G1::template NodeMap<int> tmp(_g1,0);
for(unsigned int i=0; i<order.size(); ++i) {
@@ -675,7 +668,7 @@
public:
///Constructor
- Vf2ppWizard(const Graph1 &g1,const Graph2 &g2) : Base(g1,g2) { }
+ Vf2ppWizard(const Graph1 &g1,const Graph2 &g2) : Base(g1,g2) {}
///Copy constructor
Vf2ppWizard(const Base &b) : Base(b) {}
@@ -684,7 +677,7 @@
template<typename T>
struct SetMappingBase : public Base {
typedef T Mapping;
- SetMappingBase(const Base &b) : Base(b) { }
+ SetMappingBase(const Base &b) : Base(b) {}
};
///\brief \ref named-templ-param "Named parameter" for setting
@@ -713,11 +706,11 @@
///the node labels.
///
///\param nodeLabels1 A \ref concepts::ReadMap "readable node map"
- ///of g1 with integer value. In case of K different labels, the labels
- ///must be the {0,1,..,K-1} numbers.
+ ///of g1 with integer values. In case of K different labels, the labels
+ ///must be the numbers {0,1,..,K-1}.
///\param nodeLabels2 A \ref concepts::ReadMap "readable node map"
- ///of g2 with integer value. In case of K different labels, the labels
- ///must be the {0,1,..,K-1} numbers.
+ ///of g2 with integer values. In case of K different labels, the labels
+ ///must be the numbers {0,1,..,K-1}.
template<typename NL1, typename NL2>
Vf2ppWizard< SetNodeLabelsBase<NL1,NL2> >
nodeLabels(const NL1 &nodeLabels1, const NL2 &nodeLabels2) {
@@ -877,7 +870,7 @@
/// int num_isos = vf2pp(g1,g2).iso().count();
///
/// // Iterate through all the induced subgraph mappings
- /// //of graph g1 into g2 using the labels c1 and c2
+ /// // of graph g1 into g2 using the labels c1 and c2
/// auto* myVf2pp = vf2pp(g1,g2).mapping(m).nodeLabels(c1,c2)
/// .induced().getPtrToVf2Object();
/// while(myVf2pp->find()){