source: tol/tol_pkg/GraphTools/_GraphTools.tol @ e7af41b

1941-docker-image-to-testdevel
Last change on this file since e7af41b was e7af41b, checked in by Víctor de Buen <vdebuen@…>, 17 years ago

Making standard package

git-svn-id: ​https://www.tol-project.org/svn/tolp/trunk@1656 be4846ae-f051-483a-831f-b64e7d08527f
  • Property mode set to 100644
File size: 16.4 KB
Line 
1/* -*- mode: C++ -*- */
2//////////////////////////////////////////////////////////////////////////////
3// FILE   : graphtools.tol
4// PURPOSE: Defines NameBlock GraphTools
5//////////////////////////////////////////////////////////////////////////////
6
7//////////////////////////////////////////////////////////////////////////////
8NameBlock GraphTools =
9//////////////////////////////////////////////////////////////////////////////
10[[
11
12Text _.autodoc.description = "Functions and classes related with "
13"Graph Theory.";
14
15Text _.autodoc.keywords = "Graph Theory,vertex,edge,adjacent";
16
17//////////////////////////////////////////////////////////////////////////////
18Text _.autodoc.member.Append.Indexed = "Adds and index a new element to a "
19"set and returns 0 if itŽs all right. If an element with given name exists "
20"already then returns its index, else returns 0";
21Real Append.Indexed(Set set, Anything newElement, Text name)
22//////////////////////////////////////////////////////////////////////////////
23{
24  Real idx = FindIndexByName(set, name );
25  If(idx != 0,
26  {
27    WriteLn("[GraphTools::Append.Indexed] Cannot add an existant element "+
28            Name(set)+"["<<idx+"] with name "+ name,"E");
29    0
30  },
31  {
32    Set aux =  [[ Copy(newElement) ]];
33    Anything PutName(name, aux[1]);
34    Set Append(set, aux, True);
35    idx
36  })
37};
38
39//////////////////////////////////////////////////////////////////////////////
40Class @Feature.Abstract
41//////////////////////////////////////////////////////////////////////////////
42{
43  Static Text _.autodoc.description = "Class for handling with abstract "
44  "features of arbitrary entities, numerical or not, that will be stored in "
45  "an external matrix with a row for each entity.";
46  //The name of the feature
47  Text _.name;
48  //The number of the feature in the full set of features
49  Real _.position;
50
51  ////////////////////////////////////////////////////////////////////////////
52  Static Text _.autodoc.member.get = "Returns the stored value corresponding "
53  "to this feature related to an individual entity.";
54  Anything get(Matrix store, Real entity)
55  ////////////////////////////////////////////////////////////////////////////
56};
57
58//////////////////////////////////////////////////////////////////////////////
59Class @Feature.Numeric : @Feature.Abstract
60//////////////////////////////////////////////////////////////////////////////
61{
62  Static Text _.autodoc.description = "Class for handling with numerical "
63  "numerical features of arbitrary entities that will be stored in an "
64  "external matrix with a row for each entity.";
65
66  ////////////////////////////////////////////////////////////////////////////
67  Static Text _.autodoc.member.New = "Creates a new instance of "
68  "Class @Feature.Numeric";
69  Static @Feature.Numeric New(Text name, Real position)
70  ////////////////////////////////////////////////////////////////////////////
71  {
72    @Feature.Numeric aux =
73    [[
74      Text _.name = name;
75      Real _.position  = position
76    ]]
77  };
78 
79  ////////////////////////////////////////////////////////////////////////////
80  Anything get(Matrix store, Real entity)
81  ////////////////////////////////////////////////////////////////////////////
82  {
83    MatDat(store, entity, _.position)
84  }
85};
86
87//////////////////////////////////////////////////////////////////////////////
88Class @Feature.NonNumeric : @Feature.Abstract
89//////////////////////////////////////////////////////////////////////////////
90{
91  Static Text _.autodoc.description = "Class for handling with numerical "
92  "numerical features of arbitrary entities that will be stored in an "
93  "external matrix with a row for each entity. Here the stored value is the "
94  "index of the feature stored in an arbitrary domain.";
95
96  //The set of valid values for this feature indexed by name
97  Set _.domain;
98
99  ////////////////////////////////////////////////////////////////////////////
100  Static Text _.autodoc.member.New = "Creates a new instance of "
101  "Class @Feature.NonNumeric";
102  Static @Feature.NonNumeric New(Text name, Real position, Set domain)
103  ////////////////////////////////////////////////////////////////////////////
104  {
105    @Feature.NonNumeric aux =
106    [[
107      Text _.name = name;
108      Real _.position  = position;
109      Set _.domain = domain   
110    ]];
111    Real SetIndexByName(aux::_.domain);
112    aux
113  };
114
115  ////////////////////////////////////////////////////////////////////////////
116  Anything get(Matrix store, Real entity)
117  ////////////////////////////////////////////////////////////////////////////
118  {
119    Real idx = MatDat(store, entity, _.position);
120    _.domain[idx]
121  }
122
123};
124
125//////////////////////////////////////////////////////////////////////////////
126Class @FeatureSet
127//////////////////////////////////////////////////////////////////////////////
128{
129  //Stores and index by name a set of instances od @Feature.Abstract
130  Set _.feature = Copy(Empty);
131  //In each row of this matrix are stored the values or indexes of features
132  //related to an individual entity
133  Matrix _.data = Rand(0,0,0,0);
134
135  ////////////////////////////////////////////////////////////////////////////
136  Static Text _.autodoc.member.New = "Creates a new instance of "
137  "Class @FeatureSet";
138  Static @FeatureSet New(Real void)
139  ////////////////////////////////////////////////////////////////////////////
140  {
141    @FeatureSet aux
142  };
143
144  ////////////////////////////////////////////////////////////////////////////
145  Static Text _.autodoc.member.add.feature.numeric =
146  "Adds a new numerical feature";
147  Real add.feature.numeric(Text name)
148  ////////////////////////////////////////////////////////////////////////////
149  {
150    GraphTools::Append.Indexed(
151      _.feature,
152      @Feature.Numeric::New(name, Card(_.feature)+1),
153      name)
154  };
155
156  ////////////////////////////////////////////////////////////////////////////
157  Static Text _.autodoc.member.add.feature.nonnumeric=
158  "Adds a new non numerical feature";
159  Real add.feature.nonnumeric(Text name, Set domain)
160  ////////////////////////////////////////////////////////////////////////////
161  {
162    GraphTools::Append.Indexed(
163      _.feature,
164      @Feature.NonNumeric::New(name, Card(_.feature)+1, domain),
165      name)
166  };
167
168  ////////////////////////////////////////////////////////////////////////////
169  Text _.autodoc.member.feature.index = "Returns the index of a feature or 0 "
170  "if it not exists";
171  Real feature.index(Text name)
172  ////////////////////////////////////////////////////////////////////////////
173  {
174    FindIndexByName(_.feature, name )
175  };
176
177  ////////////////////////////////////////////////////////////////////////////
178  Text _.autodoc.member.get = "Returns the value of a feature for an entity";
179  Anything get(Real entity,
180               Anything feature) //Real position or Text name
181  ////////////////////////////////////////////////////////////////////////////
182  {
183    @Feature.Abstract f = _.feature[feature];
184    f::get(_.data, entity)
185  };
186
187  ////////////////////////////////////////////////////////////////////////////
188  Text _.autodoc.member.get.all = "Returns a set with the values of all "
189  "features for an entity";
190  Set get.all(Real entity)
191  ////////////////////////////////////////////////////////////////////////////
192  {
193    EvalSet(_.feature, Anything get.all.cycle(@FeatureSet f)
194    {
195      f::get(_.data, entity)
196    })
197  }
198
199};
200
201
202//////////////////////////////////////////////////////////////////////////////
203Class @Graph
204//////////////////////////////////////////////////////////////////////////////
205{
206  Text _.autodoc.description = "Class for handling with generic indexed by "
207  "name graphs in TOL. In abstract, a graph is a pair of sets \n"
208  "  V : a finite set of vertices \n"
209  "  E : a finite set of edges relating an input vertex with an output \n"
210  "Each vertex has a set of features related with the system\n"
211  "Each edge also has its own set of features.\n";
212
213  //The identifier of the graph
214  Text _.name;
215  //Indicates if the graph is directed or symmetric
216  Real _.directed;
217  //Features of vertices. First feature must be the identifier of vertices
218  @FeatureSet _.vertex = @FeatureSet::New(?);
219  //Number of vertices
220  Real _.vertex.num = 0; 
221  //Features of edges. First two features must be input and output vertex
222  @FeatureSet _.edge = @FeatureSet::New(?);
223  //Number of edges
224  Real _.edge.num = 0; 
225  //Sparse matrix storing index of edge for each cell (out,in)
226  VMatrix _.edge.map = Rand(0,0,0,0);
227  VMatrix _.edge.adjacency = Rand(0,0,0,0);
228  VMatrix _.edge.repeated = Rand(0,0,0,0);
229  Real _.edge.check.repeated = ?;
230  Real _.edge.check.repaired = ?;
231  ////////////////////////////////////////////////////////////////////////////
232  Static Text _.autodoc.member.New = "Creates a new instance of "
233  "Class @Graph";
234  Static @Graph New(Text name, Real directed)
235  ////////////////////////////////////////////////////////////////////////////
236  {
237    @Graph aux =
238    [[
239      Text _.name = name;
240      Real _.directed = directed
241    ]]
242  };
243
244  ////////////////////////////////////////////////////////////////////////////
245  Real initialize(Set vertex.names)
246  ////////////////////////////////////////////////////////////////////////////
247  {
248    Real _.vertex.num := Card(vertex.names);
249    Set For(1,_.vertex.num, Real(Real k)
250    {
251      Text PutName(vertex.names[k], vertex.names[k]);
252      k
253    });
254    Real _.vertex::add.feature.nonnumeric("Identifier", vertex.names);
255    Matrix _.vertex::_.data := DifEq(1/(1-B),Rand(_.vertex.num,1,1,1));
256    Real _.edge::add.feature.numeric("Output");
257    Real _.edge::add.feature.numeric("Input");
258    True
259  };
260
261  ////////////////////////////////////////////////////////////////////////////
262  Text _.autodoc.member.edge.build = "";
263  Real edge.build(Matrix data, Real removeRepeatedEdges)
264  ////////////////////////////////////////////////////////////////////////////
265  {
266    Real _.edge.num := Rows(data);
267    Matrix out_ = SubCol(data,[[1]]);
268    Matrix in_  = SubCol(data,[[2]]);
269    Matrix out  = If(_.directed, out_, Min(in_, out_));
270    Matrix in   = If(_.directed, in_,  Max(in_, out_));
271    Matrix _.edge::_.data := out | in | SubCol(data,Range(3,Columns(data),1));
272    Matrix idx = DifEq(1/(1-B),Rand(_.edge.num,1,1,1));
273    Matrix idx.rep = Rand(_.edge.num,1,1,1);
274    Matrix outInRep = out|in|idx.rep;
275    VMatrix triplet.rep = Triplet(outInRep,_.vertex.num,_.vertex.num);
276    VMatrix _.edge.repeated := Convert(triplet.rep,"Cholmod.R.Sparse");
277    VMatrix _.edge.adjacency := Or(_.edge.repeated, Zeros(_.vertex.num));
278    VMatrix _.edge.repeated := _.edge.repeated - _.edge.adjacency;
279    Real _.edge.check.repeated := VMatSum(_.edge.repeated);
280    Code funTriplet = Case(
281    !_.edge.check.repeated,
282    {
283      Real _.edge.check.repaired := 0;
284      Triplet
285    },
286    removeRepeatedEdges,
287    {
288      WriteLn("[GraphTools::@Graph "+_.name+"::edge.build()] "+
289              "There was "<<_.edge.check.repeated+
290              " repeated edges that has been removed","W");
291      Real _.edge.check.repaired := _.edge.check.repeated;
292      TripletUnique
293    },
294    1==1,
295    {
296      WriteLn("[GraphTools::@Graph "+_.name+"::edge.build()] "+
297              "There are "<<_.edge.check.repeated+" repeated edges "
298              "but they don't will be deleted","W");
299      Real _.edge.check.repaired := 0;
300      Triplet
301    });
302    VMatrix triplet.map = funTriplet(out|in|idx,_.vertex.num,_.vertex.num);
303    VMatrix _.edge.map := Convert(triplet.map,"Cholmod.R.Sparse");
304    True
305  };
306
307  ////////////////////////////////////////////////////////////////////////////
308  Text _.autodoc.member.get.vertex.names = "Returns the names of all "
309  "vertices";
310  Set get.vertex.names(Real void)
311  ////////////////////////////////////////////////////////////////////////////
312  {
313    ((_.vertex::_.feature)[1])::_.domain
314  };
315
316  ////////////////////////////////////////////////////////////////////////////
317  Text _.autodoc.member.get.vertex.name = "Returns the name of one "
318  "vertex";
319  Text get.vertex.name(Real idx)
320  ////////////////////////////////////////////////////////////////////////////
321  {
322    (((_.vertex::_.feature)[1])::_.domain)[idx]
323  };
324
325  ////////////////////////////////////////////////////////////////////////////
326  Text _.autodoc.member.get.vertex.index = "Returns the index of a vertex or 0 "
327  "if it not exists";
328  Real get.vertex.index(Text name)
329  ////////////////////////////////////////////////////////////////////////////
330  {
331    FindIndexByName(((_.vertex::_.feature)[1])::_.domain, name )
332  };
333
334  ////////////////////////////////////////////////////////////////////////////
335  Text _.autodoc.member.get.vertex.feature.index = "Returns the index of an "
336  "vertex feature or 0 if it not exists";
337  Real get.vertex.feature.index(Text name)
338  ////////////////////////////////////////////////////////////////////////////
339  {
340    FindIndexByName(_.vertex::_.feature, name )
341  };
342
343  ////////////////////////////////////////////////////////////////////////////
344  Text _.autodoc.member.get.vertex.features = "Returns all the features for "
345  "an vertex";
346  Set get.vertex.features(Real vertex.idx)
347  ////////////////////////////////////////////////////////////////////////////
348  {
349    _.vertex::get.all(vertex.idx)
350  };
351
352  ////////////////////////////////////////////////////////////////////////////
353  Text _.autodoc.member.get.vertex.feature = "Returns specified feature for "
354  "an vertex. Feature identifier can be the name (Text) or the position "
355  "(Real)";
356  Anything get.vertex.feature(
357    Real vertex.idx,
358    Anything feature.id) //Text name or Real num
359  ////////////////////////////////////////////////////////////////////////////
360  {
361    _.edge::get(vertex.idx, feature.id)
362  };
363
364  ////////////////////////////////////////////////////////////////////////////
365  Text _.autodoc.member.get.edge.index = "Returns the index of an edge or 0 "
366  "if it not exists";
367  Real get.edge.index(Real out_, Real in_)
368  ////////////////////////////////////////////////////////////////////////////
369  {
370    Real out  = If(_.directed, out_, Min(in_, out_));
371    Real in   = If(_.directed, in_,  Max(in_, out_));
372    Real edge.idx = VMatDat(_.edge.map, out, in);
373    edge.idx
374  };
375
376  ////////////////////////////////////////////////////////////////////////////
377  Text _.autodoc.member.edge.exists = "Returns true if exists the edge from "
378  "out_ to in_";
379  Real edge.exists(Real out_, Real in_)
380  ////////////////////////////////////////////////////////////////////////////
381  {
382    get.edge.index(out_, in_)!=0
383  };
384
385  ////////////////////////////////////////////////////////////////////////////
386  Text _.autodoc.member.get.edge.feature.index = "Returns the index of an "
387  "edge feature or 0 if it not exists";
388  Real get.edge.feature.index(Text name)
389  ////////////////////////////////////////////////////////////////////////////
390  {
391    FindIndexByName(_.edge::_.feature, name )
392  };
393
394  ////////////////////////////////////////////////////////////////////////////
395  Text _.autodoc.member.get.edge.features = "Returns all the features for "
396  "an edge";
397  Set get.edge.features(Real edge.idx)
398  ////////////////////////////////////////////////////////////////////////////
399  {
400    _.edge::get.all(edge.idx)
401  };
402
403  ////////////////////////////////////////////////////////////////////////////
404  Text _.autodoc.member.get.edge.feature = "Returns specified feature for "
405  "an edge. Feature identifier can be the name (Text) or the position (Real";
406  Anything get.edge.feature(
407    Real edge.idx,
408    Anything feature.id) //Text name or Real num
409  ////////////////////////////////////////////////////////////////////////////
410  {
411    _.edge::get(edge.idx, feature.id)
412  }
413
414/*
415PENDIENTE! : Funciones de adyacencia o vecindad de vértices
416
417http://www.absoluteastronomy.com/topics/Adjacency_matrix
418
419////////////////////////////////////////////////////////////////////////////
420Crea las matrices de adyancencia hasta un orden pedido por el usuario y las
421guarda en un set. Sólo crea las que no existan aún. Sólo devuelve la del
422orden solicitado.
423Matrix get.adyacency(Real order)
424////////////////////////////////////////////////////////////////////////////
425
426////////////////////////////////////////////////////////////////////////////
427Devuelve los vértices adyacentes de salida de orden dado para el vértice
428especificado.  V -> ... (n-1) ... -> U
429Set get.adyacency.output(Real V, Real order)
430////////////////////////////////////////////////////////////////////////////
431
432////////////////////////////////////////////////////////////////////////////
433Devuelve los vértices adyacentes U de entrada de orden dado para el vértice
434especificado.  U -> ... (n-1) ... -> V
435Set get.adyacency.input(Real V, Real order)
436////////////////////////////////////////////////////////////////////////////
437
438*/
439
440}
441
442]];
Note: See TracBrowser for help on using the repository browser.