1 /*
  2     Copyright 2008,2009, 2010
  3         Matthias Ehmann,
  4         Michael Gerhaeuser,
  5         Carsten Miller,
  6         Bianca Valentin,
  7         Alfred Wassermann,
  8         Peter Wilfahrt
  9 
 10     This file is part of JSXGraph.
 11 
 12     JSXGraph is free software: you can redistribute it and/or modify
 13     it under the terms of the GNU Lesser General Public License as published by
 14     the Free Software Foundation, either version 3 of the License, or
 15     (at your option) any later version.
 16 
 17     JSXGraph is distributed in the hope that it will be useful,
 18     but WITHOUT ANY WARRANTY; without even the implied warranty of
 19     MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
 20     GNU Lesser General Public License for more details.
 21 
 22     You should have received a copy of the GNU Lesser General Public License
 23     along with JSXGraph.  If not, see <http://www.gnu.org/licenses/>.
 24 */
 25 JXG.GraphReader = new function() {
 26     this.parseData = function(board, directed) {
 27         var splitted, n, nodes = [], adjMatrix = [], i, j, tmp, nodenumbers = {}, tmp2, weighted = false,
 28             boundingBox;
 29         splitted = this.data.split('\n');
 30         // remove whitespaces
 31         for(i=0; i<splitted.length;i++) {
 32             splitted[i] = splitted[i].replace (/^\s+/, '').replace (/\s+$/, '');
 33         }
 34         
 35         // first line: bounding box
 36         boundingBox = splitted[0].split(' ');
 37         for(i=0; i<boundingBox.length; i++) {
 38             boundingBox[i] = parseInt(boundingBox[i]);
 39         }
 40 
 41         board.setBoundingBox(boundingBox,true);
 42         splitted.shift();
 43         
 44         // second line: number of nodes
 45         n = parseInt(splitted[0]);
 46         
 47         // nodes
 48         for(i=1; i <= n; i++) {
 49             if(splitted[i].search(/ /) != -1) {
 50                 tmp = splitted[i].split(' ');
 51                 nodes.push({name:tmp[0],coords:[parseInt(tmp[1]),parseInt(tmp[2])]});
 52                 nodenumbers[tmp[0]] = i-1;
 53             }
 54             else { // keine Koordinaten vorgegeben 
 55                 tmp = splitted[i];
 56                 nodes.push({name:tmp,coords:[null,null]});
 57                 nodenumbers[tmp] = i-1;
 58             }
 59         }
 60         
 61         // edges
 62         // check whether the graph is weighted or not
 63         for(i=n+1; i < splitted.length; i++) {
 64             tmp = splitted[i].split(' ');
 65             if(tmp.length > 2) { // weights
 66                 weighted = true;
 67                 break;
 68             }
 69         }
 70         // initialize entries of the adjacency matrix
 71         for(i=0; i<n; i++) {
 72             adjMatrix[i] = [];
 73             for(j=0; j<n; j++) {
 74                 if(!weighted) {
 75                     adjMatrix[i][j] = 0;
 76                 }
 77                 else {
 78                     adjMatrix[i][j] = Infinity;
 79                 }
 80             }
 81         }
 82         if(weighted) { // zeros for diagonal - way from node to itself
 83             for(i=0; i<n; i++) {
 84                 adjMatrix[i][i] = 0;
 85             }        
 86         }
 87         for(i=n+1; i < splitted.length; i++) {
 88             tmp = splitted[i].split(' ');
 89             if(tmp.length > 2) { // weights
 90                 tmp2 = parseInt(tmp[2]);
 91             }
 92             else {
 93                 tmp2 = 1; // no weight given
 94             }
 95             adjMatrix[nodenumbers[tmp[0]]][nodenumbers[tmp[1]]] = tmp2;
 96             if(!directed) {
 97                 adjMatrix[nodenumbers[tmp[1]]][nodenumbers[tmp[0]]] = tmp2;
 98             }
 99         }
100         board.addedGraph = {n:n, nodes:nodes, adjMatrix:adjMatrix, nodenumbers: nodenumbers, weighted: weighted, directed: directed};
101         //console.log(adjMatrix);
102         return board.addedGraph;
103         
104     };
105     
106 
107 	this.readGraph = function(fileStr, board, directed) { 
108         var graph;
109         this.data = fileStr;
110         board.suspendUpdate();
111 		graph = this.parseData(board, directed);
112         this.drawGraph(graph, board);
113         board.unsuspendUpdate();
114 	};
115     
116     this.drawGraph = function(graph,board) {
117         var n = graph.n, nodes = graph.nodes, adjMatrix = graph.adjMatrix, i,j,s,t, p, x,y;
118         for(i=0; i<n; i++) {
119             //console.log(nodes[i].name,[nodes[i].coords[0],nodes[i].coords[1]]);
120             if(nodes[i].coords[0] == null) {
121                 x = Math.random()*board.canvasWidth/(board.unitX*1.1)-board.origin.scrCoords[1]/(board.unitX*1.1);
122                 //console.log(x);
123             }
124             else {
125                 x = nodes[i].coords[0];
126             }
127             if(nodes[i].coords[1] == null) {
128                 y = Math.random()*board.canvasHeight/(board.unitY*1.1)-(board.canvasHeight-board.origin.scrCoords[2])/(board.unitY*1.1);
129             }
130             else {
131                 y = nodes[i].coords[1];
132             }
133            // console.log(x,y);
134             p = board.create('point',[x,y], {name:nodes[i].name});
135             nodes[i].reference = p;
136         }
137         board.addedGraph.segments = [];
138         for(i=0; i<n; i++) {
139             board.addedGraph.segments[i] = [];
140             for(j=0; j<i+1; j++) {
141                 if(i==j) {
142                     board.addedGraph.segments[i].push(null);
143                 }
144                 else if(adjMatrix[i][j] < Number.MAX_VALUE && adjMatrix[i][j] != 0) {
145                     //console.log(1,[nodes[i].name, nodes[j].name]); 
146                     if(graph.directed) {
147                         s = board.create('segment',[nodes[i].name, nodes[j].name]);
148                         s.setProperty({lastArrow:true});
149                         if(graph.weighted) {
150                             t = board.create('text',[0,0,adjMatrix[i][j]],{anchor:s});
151                             board.addedGraph.segments[i].push({edge:s,weight:t});
152                         }
153                         else {
154                             board.addedGraph.segments[i].push({edge:s,weight:1});
155                         }                        
156                     }
157                     else {
158                         board.addedGraph.segments[i][j] = board.addedGraph.segments[j][i];
159                     }
160                 }
161                 else {
162                     board.addedGraph.segments[i].push(null);
163                 }
164             }
165             for(j=i+1; j<n; j++) {
166                 if(adjMatrix[i][j] < Number.MAX_VALUE && adjMatrix[i][j] != 0) {
167                     //console.log(2,[nodes[i].name, nodes[j].name]);
168                     s = board.create('segment',[nodes[i].name, nodes[j].name]);
169                     if(graph.directed) {
170                         s.setProperty({lastArrow:true});
171                     }
172                     if(graph.weighted) {
173                         t = board.create('text',[0,0,adjMatrix[i][j]],{anchor:s});
174                         board.addedGraph.segments[i].push({edge:s,weight:t});
175                     }
176                     else {
177                         board.addedGraph.segments[i].push({edge:s,weight:1});
178                     }
179                 }
180                 else {
181                     board.addedGraph.segments[i].push(null);
182                 }
183             }
184         }
185         //console.log(board.addedGraph.segments);
186     };
187 
188 };
189