[Lemon-user] recognize multiple perfect matchings?

[Zac Bullard]

Hello All,

   I am trying to identify which edges can be a part of perfect matching,
given a graph that can hold multiple perfect matching sets. I can find the
edges for one configuration, but not the other.

   For example, if a 7 ring and a 5 ring are flush (as in the Azulene
structure), then there is resonance, and two configuration of double bonds
(perfect matching edges in this case). The edge between the two rings will
never be part of a perfect set, under any configuration.

   However, I am only seeing one set of perfect edges and never the other.
Even when I try to seed the other set by initializing a boolean edge map, I
only see one configuration. How can I make this work?

   Please note: I am completely new to Lemon, and this bit of code is
experimental.

#include <iostream>
#include <lemon/list_graph.h>
#include <lemon/matching.h>
#include <lemon/concepts/graph.h>
#include <lemon/concepts/maps.h>
#include <lemon/concepts/graph_components.h>
#include <sstream>
#include <vector>
#include <queue>
#include <cstdlib>
#include <lemon/smart_graph.h>
#include <lemon/lgf_reader.h>
#include <lemon/math.h>

using namespace std;
using namespace lemon;

GRAPH_TYPEDEFS(SmartGraph);

int main() {

    ListGraph g;

    ListGraph::Node a = g.addNode();
    ListGraph::Node b = g.addNode();
    ListGraph::Node c = g.addNode();
    ListGraph::Node d = g.addNode();
    ListGraph::Node e = g.addNode();
    ListGraph::Node f = g.addNode();
    ListGraph::Node gee = g.addNode();
    ListGraph::Node h = g.addNode();
    ListGraph::Node i = g.addNode();
    ListGraph::Node j = g.addNode();

    ListGraph::Edge ab = g.addEdge(a, b);
    ListGraph::Edge bc = g.addEdge(c, b);
    ListGraph::Edge cd = g.addEdge(c, d);
    ListGraph::Edge ed = g.addEdge(e, d);
    ListGraph::Edge fb = g.addEdge(f, b);
    ListGraph::Edge fg = g.addEdge(f, gee);
    ListGraph::Edge gh = g.addEdge(gee, h);
    ListGraph::Edge hi = g.addEdge(h, i);
    ListGraph::Edge ij = g.addEdge(j, i);
    ListGraph::Edge ja = g.addEdge(j, a);
    ListGraph::Edge ea = g.addEdge(e, a);

    ListGraph::EdgeMap<bool> edgeMap(g);
    edgeMap[ea] = true; //This never returns true after running!!!

    MaxMatching<ListGraph> mat_test(g);
    mat_test.matchingInit(edgeMap);
    mat_test.startSparse();
    mat_test.run();

    cout << "STATUS EDGE AB: (should always be false) " <<
mat_test.matching(ab) << endl;
    cout << "STATUS EDGE BC: (should be opposite bool of EA) " <<
mat_test.matching(bc) << endl;
    cout << "STATUS EDGE EA: (should be opposite bool of BC) " <<
mat_test.matching(ea) << endl;

    return 0;
}


Thank you for your time
-------------- next part --------------
An HTML attachment was scrubbed...
URL: <http://lemon.cs.elte.hu/pipermail/lemon-user/attachments/20110927/c55d00fb/attachment.html>