//============================================================================== // // Copyright (C) 2005 Dick van Oudheusden // // This program is free software; you can redistribute it and/or // modify it under the terms of the GNU General Public // License as published by the Free Software Foundation; either // version 2 of the License, or (at your option) any later version. // // This program is distributed in the hope that it will be useful, // but WITHOUT ANY WARRANTY; without even the implied warranty of // MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU // General Public License for more details. // // You should have received a copy of the GNU General Public // License along with this program; if not, write to the Free // Software Foundation, Inc., 675 Mass Ave, Cambridge, MA 02139, USA. // //============================================================================== // // $Date: 2006/07/22 13:28:58 $ $Revision: 1.2 $ // //============================================================================== #include #include #include "ofc/DGraph.h" #include "ofc/DText.h" #include "ofc/DFile.h" #include "DInc.h" #include "DTest.h" //-DataType-------------------------------------------------------------------- void DGraph_test(void) { DGraphNode *node1 = nil; DGraphNode *node2 = nil; DGraphNode *node3 = nil; DGraphNode *node4 = nil; DGraphNode *node5 = nil; DGraphNode *node6 = nil; DGraphNode *node7 = nil; DGraphNode *node8 = nil; DGraphEdge *edge1 = nil; DGraphEdge *edge2 = nil; DGraphEdge *edge3 = nil; DGraphEdge *edge4 = nil; DGraphEdge *edge7 = nil; DGraphEdge *edge8 = nil; DGraph *graph = [DGraph new]; DGraph *copy = nil; DFile *output = [DFile new]; DList *path = nil; double weight; DText *obj = [DText new]; DText *obx = [DText new]; DListIterator *iter = nil; STARTTEST(); [obj set :"Edge"]; [obx set :"Node"]; // Test shortest paths node1 = [graph addNode :NULL :NULL :nil]; // default label, no attributes and object node2 = [graph addNode :NULL :NULL :obx]; node3 = [graph addNode :NULL :NULL :nil]; node4 = [graph addNode :NULL :NULL :nil]; node5 = [graph addNode :NULL :NULL :nil]; node6 = [graph addNode :NULL :NULL :nil]; node7 = [graph addNode :NULL :NULL :nil]; node8 = [graph addNode :NULL :NULL :nil]; edge1 = [graph addEdge :NULL :NULL : 6.0 :nil :node1 :node2]; edge2 = [graph addEdge :NULL :NULL : 1.0 :obj :node2 :node3]; [graph addEdge :NULL :NULL :10.0 :nil :node3 :node8]; [graph addEdge :NULL :NULL : 4.0 :nil :node1 :node4]; [graph addEdge :NULL :NULL : 3.0 :nil :node3 :node4]; [graph addEdge :NULL :NULL : 8.0 :nil :node4 :node5]; edge7 = [graph addEdge :NULL :NULL : 3.0 :nil :node3 :node5]; edge8 = [graph addEdge :NULL :NULL : 3.0 :nil :node2 :node5]; [graph addEdge :NULL :NULL : 7.0 :nil :node5 :node8]; [graph addEdge :NULL :NULL :16.0 :nil :node1 :node6]; [graph addEdge :NULL :NULL : 3.0 :nil :node5 :node6]; [graph addEdge :NULL :NULL : 1.0 :nil :node6 :node7]; [graph addEdge :NULL :NULL : 5.0 :nil :node5 :node7]; [graph addEdge :NULL :NULL : 1.0 :nil :node7 :node8]; if ([output open :"test.dot" :"w"]) { TEST([graph toDot :output]); [output close]; } path = [graph shortestPath :&weight :node1 :node8]; TEST([path length] == 6); TEST(weight == 14.0); TEST([path get :0] == node1); TEST([path get :1] == node2); TEST([path get :2] == node5); TEST([path get :3] == node6); TEST([path get :4] == node7); TEST([path get :5] == node8); [path shallowFree]; // shallow copy the graph copy = [graph shallowCopy]; iter = [copy nodes]; path = [copy shortestPath :&weight :[iter first] :[iter last]]; TEST([path length] == 6); TEST(weight == 14.0); TEST([iter first] != node1); TEST([[iter next] object] == obx); // shallow copy, stored object is a reference TEST([iter last ] != node8); [iter free]; [copy shallowFree]; // deep copy the graph copy = [graph copy]; iter = [copy nodes]; path = [copy shortestPath :&weight :[iter first] :[iter last]]; TEST([path length] == 6); TEST(weight == 14.0); TEST([iter first] != node1); TEST([[iter next] object] != obx); // deep copy, stored object is a copy .. TEST([[[iter object] object] compare :obx] == 0); // .. and identical TEST([iter last ] != node8); [iter free]; [copy free]; // reroute [graph reroute :edge8 :node4 :node6]; path = [graph shortestPath :&weight :node1 :node8]; TEST([path length] == 5); TEST(weight == 9.0); TEST([path get :0] == node1); TEST([path get :1] == node4); TEST([path get :2] == node6); TEST([path get :3] == node7); TEST([path get :4] == node8); [path shallowFree]; // weight change [edge8 weight :12.0]; path = [graph shortestPath :&weight :node1 :node8]; TEST([path length] == 7); TEST(weight == 15.0); TEST([path get :0] == node1); TEST([path get :1] == node2); TEST([path get :2] == node3); TEST([path get :3] == node5); TEST([path get :4] == node6); TEST([path get :5] == node7); TEST([path get :6] == node8); [path shallowFree]; // reverse [edge7 reverse]; path = [graph shortestPath :&weight :node1 :node8]; TEST([path length] == 4); TEST(weight == 17.0); TEST([path get :0] == node1); TEST([path get :1] == node2); TEST([path get :2] == node3); TEST([path get :3] == node8); [path shallowFree]; // remove edge TEST([graph removeEdge :edge2] == obj); path = [graph shortestPath :&weight :node1 :node8]; TEST([path length] == 6); TEST(weight == 17.0); TEST([path get :0] == node1); TEST([path get :1] == node4); TEST([path get :2] == node5); TEST([path get :3] == node6); TEST([path get :4] == node7); TEST([path get :5] == node8); [path shallowFree]; // Remove node [graph removeEdge :edge1]; // disconnect the node TEST([graph removeNode :node2] == obx); [graph free]; // Test graph output graph = [DGraph new]; [graph attributes :"rotate=90"]; node1 = [graph addNode :"start" :"shape=diamond" :nil]; TEST(node1 != nil); node2 = [graph addNode :NULL :NULL :nil]; TEST(node2 != nil); node3 = [graph addNode :NULL :NULL :nil]; TEST(node3 != nil); node4 = [graph addNode :NULL :NULL :nil]; TEST(node4 != nil); edge1 = [graph addEdge :"edge" :"color=red,style=dashed" :1.0 :nil :node1 :node2]; TEST(edge1 != nil); edge2 = [graph addEdge :NULL :"arrowhead=crow" :2.0 :nil :node1 :node3]; TEST(edge2 != nil); edge3 = [graph addEdge :"loop" :NULL :3.0 :nil :node2 :node2]; TEST(edge3 != nil); edge4 = [graph addEdge :NULL :NULL :4.0 :nil :node3 :node1]; TEST(edge4 != nil); TEST([node1 ingoingDegree] == 1); TEST([node2 ingoingDegree] == 2); TEST([node3 ingoingDegree] == 1); TEST([node4 ingoingDegree] == 0); TEST([node1 outgoingDegree] == 2); TEST([node2 outgoingDegree] == 1); TEST([node3 outgoingDegree] == 1); TEST([node4 outgoingDegree] == 0); TEST([node1 degree] == 3); TEST([node2 degree] == 3); TEST([node3 degree] == 2); TEST([node4 degree] == 0); TEST(strcmp([node1 name], "n1") == 0); TEST(strcmp([node4 name], "n4") == 0); TEST(strcmp([edge1 name], "e1") == 0); TEST(strcmp([edge4 name], "e4") == 0); TEST(strcmp([node1 label], "start") == 0); TEST([node4 label] == NULL); TEST(strcmp([edge1 label], "edge") == 0); TEST([edge4 label] == NULL); TEST(strcmp([graph attributes], "rotate=90") == 0); TEST(strcmp([node1 attributes], "shape=diamond") == 0); TEST([node4 attributes] == NULL); TEST(strcmp([edge2 attributes], "arrowhead=crow") == 0); TEST([edge4 attributes] == NULL); TEST([edge1 weight] == 1.0); TEST([edge3 weight] == 3.0); TEST([node3 object] == nil); TEST([node3 object :obj] == nil); TEST([node3 object :nil] == obj); TEST([node3 object] == nil); TEST([edge3 object] == nil); TEST([edge3 object :obj] == nil); TEST([edge3 object :nil] == obj); TEST([edge3 object] == nil); TEST([graph hasNode :node1]); TEST([graph hasEdge :edge3]); // Generate graph with: dot -Tpng -o graph.png test2.dot if ([output open :"test2.dot" :"w"]) { TEST([graph toDot :output]); [output close]; } path = [graph shortestPath :NULL :node1 :node2]; TEST([path length] == 2); [path shallowFree]; path = [graph shortestPath :NULL :node1 :node4]; // no path present TEST(path == nil); [output free]; [graph free]; [obj free]; [obx free]; STOPTEST(); }