[gecode-users] Reachability in a graph structure.

[Tobias Pankrath]

Hello,






To model this using gecode, I am using 4 SetVarArrays:


SetVarArray g2_edges; // like above for G2


SetVarArray g2_reach; // like above for G2.



 // define edges between nodes
 dom(*this, g1_edges[0], SRT_EQ, IntSet(1, 2));
 dom(*this, g1_edges[1],  SRT_EQ, 5 );
 dom(*this, g1_edges[2], SRT_EQ,  IntSet(3,4));
 dom(*this, g1_edges[3],  SRT_EQ, 5);
 dom(*this, g1_edges[4],  SRT_EQ, 5 );
 dom(*this, g1_edges[5],  SRT_EQ, IntSet::empty);

Then I want to encode the following relations:
        * y ∈ g1_reach[x], if y ∈ g1_edges[x] (direct neighbours)


Thus I do:
for(int x = 0; x < 6; ++x)
{
        rel(*this, g1_reach[x] >= g1_edges[x]); // superset
        element(*this, g1_reach, SOT_UNION, g1_reach[x], g1_reach[x]);
        // call to element taken from the manual, section 5.2.4
        // is it correct?
}

Then I'll branch on g1_reach, like this:
branch(*this, g1_reach, SET_VAR_NONE(), SET_VAL_MIN_INC());

However this gives me a >1000 solutions and all look like
g1_edges {{1,2}, {5}, {3,4}, {5}, {5}, {}}
g1_reach {}

What is the correct way to model this?

With my best regards,
Tobias

#include <iostream>
#include <fstream>
#include <string>
#include <sstream>
#include <stdexcept>

#include <boost/program_options.hpp>
#include <gecode/driver.hh>
#include <gecode/int.hh>
#include <gecode/set.hh>
#include <gecode/minimodel.hh>
#include "cfg.hpp"
#include "cfgparser.hpp"

using namespace std;
namespace po = boost::program_options;

using namespace Gecode;

class Homomorph: public Script {
protected:
  SetVarArray g1_edges;
  //SetVarArray g2_edges;
  SetVarArray g1_reach;
  //SetVarArray g2_reach;

  //IntVarArray mapping;
public:
  Homomorph(const Options& opt) :
      g1_edges(*this, 6, IntSet::empty, IntSet(0, 5)),
  //    g2_edges(*this, 6, IntSet::empty, IntSet(0, 5)),
      g1_reach(*this, 6, IntSet::empty, IntSet(0, 5))
    //  g2_reach(*this, 6, IntSet::empty, IntSet(0, 5)),
     // mapping(*this, 5, 0, 5)
  {
      // define edges between nodes
      dom(*this, g1_edges[0], SRT_EQ, IntSet(1, 2));
      dom(*this, g1_edges[1],  SRT_EQ, 5 );
      dom(*this, g1_edges[2], SRT_EQ,  IntSet(3,4));
      dom(*this, g1_edges[3],  SRT_EQ, 5);
      dom(*this, g1_edges[4],  SRT_EQ, 5 );
      dom(*this, g1_edges[5],  SRT_EQ, IntSet::empty);
/*
      dom(*this, g2_edges[5], SRT_EQ, IntSet(3, 4));
      dom(*this, g2_edges[1],  SRT_EQ, 0 );
      dom(*this, g2_edges[2], SRT_EQ,  0);
      dom(*this, g2_edges[3],  SRT_EQ, IntSet(1,2));
      dom(*this, g2_edges[4],  SRT_EQ, 0 );
      dom(*this, g2_edges[0],  SRT_EQ, IntSet::empty);
*/
      // define reachability sets
      for(int x = 0; x < 6; ++x )
      {
          rel(*this, g1_reach[x] >= g1_edges[x]);
          element(*this, SOT_UNION, g1_reach, g1_reach[x], g1_reach[x]);
      }
      branch(*this, g1_reach, SET_VAR_NONE(), SET_VAL_MIN_INC());
  }

  virtual void
  print(std::ostream& os) const
  {
    os << "\t" << g1_edges << std::endl;
    os << "\t" << g1_reach << std::endl;
  }

  Homomorph(bool share, Homomorph& s) : Script(share,s) {
    g1_edges.update(*this, share, s.g1_edges);
  }

  virtual Space*
  copy(bool share) {
    return new Homomorph(share,*this);
  }
};

int
main(int argc, char* argv[]) {
  Options opt("SEND+MORE=MONEY");
  opt.solutions(0);
  opt.iterations(20000);
  opt.parse(argc,argv);
  Script::run<Homomorph,DFS,Options>(opt);
  return 0;
}

I'm quite new to constraint programming and gecode in particular and ran into some issue I have to directed graphs G1=(V1,V1×V1), G2=(V2, V2×V2) and I am searching for a mapping h: V1 → V2, that mantains reachability. I.e. if there is a path v1 -*> v2 (v1,v2 ∈ V1) than there must also be a path h(v1) -*> h(v2). SetVarArray g1_edges; // y ∈ g1_edges[x]: there is an edge from v_x to v_y in G1 SetVarArray g1_reach; // y ∈ g1_reach[x]: there is a path from v_x to v_y in G1 Now I want gecode to calculate the reachability of those graphs. Thus I tried to fix the graph by the following domain constraints. A picture of the desired graph is attached to this mail. * if y ∈ g1_reach[x] and z ∈ g1_reach[y] then z ∈ g1_reach[x] (transitivity)

t.dot.pdf
Description: Adobe PDF document

_______________________________________________
Gecode users mailing list
users@gecode.org
https://www.gecode.org/mailman/listinfo/gecode-users