source: tol/tol_pkg/GraphTools/GraphTools.tol @ cf0e0df

/* -*- mode: C++ -*- */
//////////////////////////////////////////////////////////////////////////////
// FILE   : GraphTools.tol
// PURPOSE: Defines Package GraphTools
//////////////////////////////////////////////////////////////////////////////

//////////////////////////////////////////////////////////////////////////////
NameBlock GraphTools =
//////////////////////////////////////////////////////////////////////////////
[[
#Require MatEncode;
#Require MatQuery;

Text _.autodoc.description = "Functions and classes related with Graph "
  "theory. In order to get faster behaviour, internal implementation uses "
  "matrix and sparse matrix to storing and handling with all numerical "
  "information about vertices and edges and indexed sets to handle with non "
  "numerical data.";
Text _.autodoc.url = "";
Set _.autodoc.keys = [["Graph theory","vertex","edge","adjacent"]];
Set _.autodoc.authors = [[
   "vdebuen@tol-project.org",
   "josp@tol-project.org" ]];

//////////////////////////////////////////////////////////////////////////////
Class @Graph
//////////////////////////////////////////////////////////////////////////////
{
  Static Text _.autodoc.description = "Class for handling with generic "
  "indexed by name graphs in TOL. In abstract, a graph is a pair of sets \n"
  "  V : a finite set of vertices \n"
  "  E : a finite set of edges relating an input vertex with an output \n"
  "Each vertex has a set of features related with the system\n"
  "Each edge also has its own set of features.\n";

  //The identifier of the graph
  Text _.name;
  //Indicates if the graph is directed or symmetric
  Real _.directed;
  //Features of vertices. First feature must be the identifier of vertices
  MatEncode::@FeatureSet _.vertex = MatEncode::@FeatureSet::New(?);
  //Number of vertices
  Real _.vertex.num = 0;  
  //Features of edges. First two features must be input and output vertex
  MatEncode::@FeatureSet _.edge = MatEncode::@FeatureSet::New(?);
  //Number of edges
  Real _.edge.num = 0;  
  //Sparse matrix storing index of edge for each cell (out,in) 
  VMatrix _.edge.map = Rand(0,0,0,0);
  VMatrix _.edge.adjacency.out = Rand(0,0,0,0);
  VMatrix _.edge.adjacency.in  = Rand(0,0,0,0);
  VMatrix _.edge.repeated = Rand(0,0,0,0);
  Real _.edge.check.repeated = ?;
  Real _.edge.check.repaired = ?;
  ////////////////////////////////////////////////////////////////////////////
  Static Text _.autodoc.member.New = "Creates a new instance of "
  "Class @Graph";
  Static @Graph New(Text name, Real directed)
  ////////////////////////////////////////////////////////////////////////////
  {
    @Graph aux =
    [[
      Text _.name = name;
      Real _.directed = directed
    ]]
  };

  ////////////////////////////////////////////////////////////////////////////
  Real initialize(Set vertex.names)
  ////////////////////////////////////////////////////////////////////////////
  {
    Real _.vertex.num := Card(vertex.names);
    Set For(1,_.vertex.num, Real(Real k)
    {
      Text PutName(vertex.names[k], vertex.names[k]);
      k
    });
    Real _.vertex::add.feature.nonnumeric("Identifier", vertex.names);
    Matrix _.vertex::_.data := DifEq(1/(1-B),Rand(_.vertex.num,1,1,1));
    Real _.edge::add.feature.numeric("Output");
    Real _.edge::add.feature.numeric("Input");
    True
  };

  ////////////////////////////////////////////////////////////////////////////
  Text _.autodoc.member.edge.build = "";
  Real edge.build(Matrix data, Real removeRepeatedEdges)
  ////////////////////////////////////////////////////////////////////////////
  {
    Real _.edge.num := Rows(data);
    Matrix out_ = SubCol(data,[[1]]);
    Matrix in_  = SubCol(data,[[2]]);
    Matrix out  = If(_.directed, out_, Min(in_, out_));
    Matrix in   = If(_.directed, in_,  Max(in_, out_));
    Matrix _.edge::_.data := out | in | SubCol(data,Range(3,Columns(data),1));
    Matrix idx = DifEq(1/(1-B),Rand(_.edge.num,1,1,1));
    Matrix idx.rep = Rand(_.edge.num,1,1,1);
    Matrix outInRep = out|in|idx.rep;
    VMatrix triplet.rep = Triplet(outInRep,_.vertex.num,_.vertex.num);
    VMatrix _.edge.repeated := Convert(triplet.rep,"Cholmod.R.Sparse");
    VMatrix _.edge.adjacency.out := Or(_.edge.repeated, Zeros(_.vertex.num));
    VMatrix _.edge.adjacency.in := Tra(_.edge.adjacency.out);
    VMatrix _.edge.repeated := _.edge.repeated - _.edge.adjacency.out;
    Real _.edge.check.repeated := VMatSum(_.edge.repeated);
    Code funTriplet = Case(
    !_.edge.check.repeated,
    {
      Real _.edge.check.repaired := 0;
      Triplet
    },
    removeRepeatedEdges,
    {
      WriteLn("[GraphTools::@Graph "+_.name+"::edge.build()] "+
              "There was "<<_.edge.check.repeated+
              " repeated edges that has been removed","W");
      Real _.edge.check.repaired := _.edge.check.repeated;
      TripletUnique
    },
    1==1,
    {
      WriteLn("[GraphTools::@Graph "+_.name+"::edge.build()] "+
              "There are "<<_.edge.check.repeated+" repeated edges "
              "but they don't will be deleted","W");
      Real _.edge.check.repaired := 0;
      Triplet
    });
    VMatrix triplet.map = funTriplet(out|in|idx,_.vertex.num,_.vertex.num);
    VMatrix _.edge.map := Convert(triplet.map,"Cholmod.R.Sparse");
    VMatrix _.edge.map.t := Tra(_.edge.map);
    True
  };

  ////////////////////////////////////////////////////////////////////////////
  Text _.autodoc.member.get.vertex.names = "Returns the names of all "
  "vertices";
  Set get.vertex.names(Real void)
  ////////////////////////////////////////////////////////////////////////////
  {
    ((_.vertex::_.feature)[1])::_.domain
  };

  ////////////////////////////////////////////////////////////////////////////
  Text _.autodoc.member.get.vertex.name = "Returns the name of one "
  "vertex";
  Text get.vertex.name(Real idx)
  ////////////////////////////////////////////////////////////////////////////
  {
    (((_.vertex::_.feature)[1])::_.domain)[idx]
  };

  ////////////////////////////////////////////////////////////////////////////
  Text _.autodoc.member.get.vertex.index = "Returns the index of a vertex or 0 "
  "if it not exists";
  Real get.vertex.index(Text name)
  ////////////////////////////////////////////////////////////////////////////
  {
    FindIndexByName(((_.vertex::_.feature)[1])::_.domain, name )
  };

  ////////////////////////////////////////////////////////////////////////////
  Text _.autodoc.member.get.vertex.feature.index = "Returns the index of an "
  "vertex feature or 0 if it not exists";
  Real get.vertex.feature.index(Text name)
  ////////////////////////////////////////////////////////////////////////////
  {
    FindIndexByName(_.vertex::_.feature, name )
  };

  ////////////////////////////////////////////////////////////////////////////
  Text _.autodoc.member.get.vertex.features = "Returns all the features for "
  "an vertex";
  Set get.vertex.features(Real vertex.idx)
  ////////////////////////////////////////////////////////////////////////////
  {
    _.vertex::get.all(vertex.idx)
  };

  ////////////////////////////////////////////////////////////////////////////
  Text _.autodoc.member.get.vertex.feature = "Returns specified feature for "
  "an vertex. Feature identifier can be the name (Text) or the position "
  "(Real)";
  Anything get.vertex.feature(
    Real vertex.idx,
    Anything feature.id) //Text name or Real num
  ////////////////////////////////////////////////////////////////////////////
  {
    _.edge::get(vertex.idx, feature.id)
  };

  ////////////////////////////////////////////////////////////////////////////
  Text _.autodoc.member.get.edge.index = "Returns the index of an edge or 0 "
  "if it not exists";
  Real get.edge.index(Real out_, Real in_)
  ////////////////////////////////////////////////////////////////////////////
  {
    Real out  = If(_.directed, out_, Min(in_, out_));
    Real in   = If(_.directed, in_,  Max(in_, out_));
    Real edge.idx = VMatDat(_.edge.map, out, in);
    edge.idx
  };

  ////////////////////////////////////////////////////////////////////////////
  Text _.autodoc.member.edge.exists = "Returns true if exists the edge from "
  "out_ to in_";
  Real edge.exists(Real out_, Real in_)
  ////////////////////////////////////////////////////////////////////////////
  {
    get.edge.index(out_, in_)!=0
  };

  ////////////////////////////////////////////////////////////////////////////
  Text _.autodoc.member.get.edge.feature.index = "Returns the index of an "
  "edge feature or 0 if it not exists";
  Real get.edge.feature.index(Text name)
  ////////////////////////////////////////////////////////////////////////////
  {
    FindIndexByName(_.edge::_.feature, name )
  };

  ////////////////////////////////////////////////////////////////////////////
  Text _.autodoc.member.get.edge.features = "Returns all the features for "
  "an edge";
  Set get.edge.features(Real edge.idx)
  ////////////////////////////////////////////////////////////////////////////
  {
    _.edge::get.all(edge.idx)
  };

  ////////////////////////////////////////////////////////////////////////////
  Text _.autodoc.member.get.edge.feature = "Returns specified feature for "
  "an edge. Feature identifier can be the name (Text) or the position (Real)";
  Anything get.edge.feature(
    Real edge.idx,
    Anything feature.id) //Text name or Real num
  ////////////////////////////////////////////////////////////////////////////
  {
    _.edge::get(edge.idx, feature.id)
  };

  ////////////////////////////////////////////////////////////////////////////
  Text _.autodoc.member.vertex.in.degree = "Returns the number of input "
  "vertices in edges whose output is the specified vertex";
  ////////////////////////////////////////////////////////////////////////////
  Real vertex.in.degree(Real vertex.index)
  {
    VMatSum(SubCol(_.edge.adjacency.in,[[vertex.index]]))
  };

  ////////////////////////////////////////////////////////////////////////////
  Text _.autodoc.member.vertex.out.degree = "Returns the number of output "
  "vertices in edges whose input is the specified vertex";
  ////////////////////////////////////////////////////////////////////////////
  Real vertex.out.degree(Real vertex.index)
  {
    VMatSum(SubCol(_.edge.adjacency.out,[[vertex.index]]))
  }

/*
PENDIENTE! : Funciones de adyacencia o vecindad de vértices

http://www.absoluteastronomy.com/topics/Adjacency_matrix

////////////////////////////////////////////////////////////////////////////
Crea las matrices de adyancencia hasta un orden pedido por el usuario y las 
guarda en un set. Sólo crea las que no existan aún. Sólo devuelve la del
orden solicitado.
Matrix get.adyacency(Real order)
////////////////////////////////////////////////////////////////////////////

  ////////////////////////////////////////////////////////////////////////////
  Text _.autodoc.member.get.adyacent.input = "Returns the set of vertices "
  "U which are input adyacent with specified order n of a given output "
  "vertex V \n"
  "  V -> ... (n-1) ... -> U \n";
  Set get.input.order(Real V, Real n)
  ////////////////////////////////////////////////////////////////////////////
  {
    VMatrix match = SubCol(_.edge.adjacency.out, [[V]]);
    Matrix select = VMat2Triplet(Convert(match,"Cholmod.R.Triplet"));
    If(!Rows(select),Copy(Empty), MatSet(Tra(SubCol(select,[[1]])))[1])    
  };

  ////////////////////////////////////////////////////////////////////////////
  Text _.autodoc.member.get.adyacent.output = "Returns the set of vertices "
  "U which are output adyacent with specified order n of a given input "
  "vertex V \n"
  "  U -> ... (n-1) ... -> V \n";
  Set get.output.order(Real V, Real n)
  ////////////////////////////////////////////////////////////////////////////
  {
    VMatrix match = SubCol(_.edge.adjacency.in, [[V]]);
    Matrix select = VMat2Triplet(Convert(match,"Cholmod.R.Triplet"));
    If(!Rows(select),Copy(Empty), MatSet(Tra(SubCol(select,[[1]])))[1])    
  }

*/

}

]];