Algorithmes de graphes : Corrections
de Philippe Lacomme (Auteur), Christian Prins (Auteur), Marc Sevaux (Auteur
Dates des corrections : Janvier 2010
Corrections proposées par : Gilles Marcou MCF à l'Université de Strasbourg
email : g.marcou_at_chimie.u-strasbg.fr
* Use of {$MODE Delphi} for compatibility with Free Pascal Compiler (FPC).
* Include the compiler define GUImode. This is used to exclude GUI dependant hooks from the library. In such a way, the library is independant of the disponibility of a graphical environment. If the compiler is used with a swith to define GUImode (-d GUImode(?)), then functions and messages taking advantage of the local graphical interface will be available.
* In T_GRAPHE_MATRICIEL, the method MakeMatrixSimple is made public.
* Corrected bug in MatrixIsSimple. In evaluating the diagonal of the matrix, there was an error in matrix indices.
* Corrected bug in Method T_GRAPH_LISTE.GraphIsSimple. When the Exit instance was used, the memory for the hash table HT was not properly released.
* In T_GRAPHE_LISTE, the methods MatrixIsSimple and MakeMatrixSimple are made public.
* properties have been added to encapsulate private methods in T_GRAPH_MATRICIEL: p_LastCol, p_MatrixArcs, p_GraphLoops, p_MatrixIsSimple.
* properties have been added to encapsulate private methods in T_GRAPH_LISTE: p_M, p_HEAD[i : Node], p_SUCC[i : ArcNum], p_GraphLoops, p_MaxOutDeg, p_OutDeg[x : Node]
* Added methods
- Procedure T_GRAPH_MATRICIEL.AFFGraph (SLOut : TStringList; W1,W2,W3:PTArcCost; Inv:PTInverse; Msg:String; Width:Byte);
- Procedure T_GRAPH_MATRICIEL.AFFGraph (SLOut : TStringList; W1,W2,W3:PTArcCost; Inv:PTInverse; Msg:String; Width:Byte);
which store ASCII representation of the graph in a TStringList to display later on. Is Equivalent to the method using the TMemo, except that the Break parameter does not has any utility in this context and was removed.
* Range error corrected in T_GRAPHE_LISTE.GraphIsSimple and MakeGraphSimple. SaveSeed changed to a Cardinal instead of a LongInt.
* Corrected bug in T_GRAPHE_LISTE.GetPath. Added FreeAndNil to release memory in case of early exit. Also, for a normal exit, FreeAndNil the pile instead of simply destroying it.
* Corrected bug in T_GRAPH_LISTE.Bellman. The direct graph was used to find next nodes and costs. Corrected to use the inverse graph.
* Corrected bugs in T_GRAPHE_LISTE.Fulkerson. The memory for the inverse graph was allocated several times. Beside, the memory was improperly released.
* Corrected bug in T_GRAPHE_MATRICIEL.Assignment. The memory for the temporary network was not properly released.
* In T_GRAPHE_LISTE.TabuCol, the method seems to fail with an access violation when the graph is 2-color. The problem is not solved.
General remark:
* With Free Pascal on Linux, the use of several statically declared array of weights provoke a segmentation fault. This might be due to the large amount of memory required by this operation. Use of pointers with new and dispose commands overcome this limitation.
* Replaced the command Destroy by FreeAndNil wherever the Destroy statement corresponded to a release of memory. This is because Destroy does not free memory and the adress of the destroyed object is not nil, yet invalid. FreeAndNil releases the memory and set the pointer to nil value.
