Index: doc/groups.dox =================================================================== --- doc/groups.dox (revision 1280) +++ doc/groups.dox (revision 1351) @@ -295,4 +295,12 @@ /** +@defgroup matrices Matrices +@ingroup auxdat +\brief Two dimensional data storages implemented in LEMON. + +This group contains two dimensional data storages implemented in LEMON. +*/ + +/** @defgroup algs Algorithms \brief This group contains the several algorithms @@ -327,4 +335,8 @@ but the digraph should not contain directed cycles with negative total length. + - \ref FloydWarshall "Floyd-Warshall" and \ref Johnson "Johnson" algorithms + for solving the \e all-pairs \e shortest \e paths \e problem when arc + lenghts can be either positive or negative, but the digraph should + not contain directed cycles with negative total length. - \ref Suurballe A successive shortest path algorithm for finding arc-disjoint paths between two nodes having minimum total length. @@ -360,8 +372,18 @@ \f[ 0 \leq f(uv) \leq cap(uv) \quad \forall uv\in A \f] -\ref Preflow is an efficient implementation of Goldberg-Tarjan's -preflow push-relabel algorithm \cite goldberg88newapproach for finding -maximum flows. It also provides functions to query the minimum cut, -which is the dual problem of maximum flow. +LEMON contains several algorithms for solving maximum flow problems: +- \ref EdmondsKarp Edmonds-Karp algorithm + \cite edmondskarp72theoretical. +- \ref Preflow Goldberg-Tarjan's preflow push-relabel algorithm + \cite goldberg88newapproach. +- \ref DinitzSleatorTarjan Dinitz's blocking flow algorithm with dynamic trees + \cite dinic70algorithm, \cite sleator83dynamic. +- \ref GoldbergTarjan !Preflow push-relabel algorithm with dynamic trees + \cite goldberg88newapproach, \cite sleator83dynamic. + +In most cases the \ref Preflow algorithm provides the +fastest method for computing a maximum flow. All implementations +also provide functions to query the minimum cut, which is the dual +problem of maximum flow. \ref Circulation is a preflow push-relabel algorithm implemented directly @@ -498,4 +520,14 @@ The matching algorithms implemented in LEMON: +- \ref MaxBipartiteMatching Hopcroft-Karp augmenting path algorithm + for calculating maximum cardinality matching in bipartite graphs. +- \ref PrBipartiteMatching Push-relabel algorithm + for calculating maximum cardinality matching in bipartite graphs. +- \ref MaxWeightedBipartiteMatching + Successive shortest path algorithm for calculating maximum weighted + matching and maximum weighted bipartite matching in bipartite graphs. +- \ref MinCostMaxBipartiteMatching + Successive shortest path algorithm for calculating minimum cost maximum + matching in bipartite graphs. - \ref MaxMatching Edmond's blossom shrinking algorithm for calculating maximum cardinality matching in general graphs. @@ -530,4 +562,33 @@ /** +@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 Subgraph Isomorphism Problem (SIP) 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 Induced Subgraph Isomorphism Problem (ISIP) 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 @@ -619,4 +680,21 @@ The currently supported solvers are \cite glpk, \cite clp, \cite cbc, \cite cplex, \cite soplex. +*/ + +/** +@defgroup lp_utils Tools for Lp and Mip Solvers +@ingroup lp_group +\brief Helper tools to the Lp and Mip solvers. + +This group adds some helper tools to general optimization framework +implemented in LEMON. +*/ + +/** +@defgroup metah Metaheuristics +@ingroup gen_opt_group +\brief Metaheuristics for LEMON library. + +This group contains some metaheuristic optimization tools. */ Index: doc/named-param.dox =================================================================== --- doc/named-param.dox (revision 463) +++ doc/named-param.dox (revision 1351) @@ -26,5 +26,5 @@ 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 Index: doc/references.bib =================================================================== --- doc/references.bib (revision 1219) +++ doc/references.bib (revision 1351) @@ -355,2 +355,16 @@ 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} +}