Revision 306:f6b16327b583

View differences:

src/main/java/tt/jointeuclid2ni/ProblemInstanceDesigner.java
16 16
import javax.vecmath.Point2d;
17 17

  
18 18
import tt.jointeuclid2ni.probleminstance.EarliestArrivalProblem;
19
import tt.jointeuclid2ni.probleminstance.EarliestArrivalProblemXMLDeserializer;
20
import tt.jointeuclid2ni.probleminstance.EarliestArrivalProblemXMLSerializer;
19
import tt.jointeuclid2ni.probleminstance.TrajectoryCoordinationProblemXMLDeserializer;
20
import tt.jointeuclid2ni.probleminstance.TrajectoryCoordinationProblemXMLSerializer;
21 21
import tt.jointeuclid2ni.probleminstance.VisUtil;
22 22
import tt.vis.PictureLayer;
23 23
import tt.vis.problemcreator.ProblemCreatedListener;
......
51 51
		// ---- extend an existing problem
52 52
		if (args.length > 1 && args[0].endsWith(".xml")) {
53 53
			String fileName = args[0];
54
			inputProblem = EarliestArrivalProblemXMLDeserializer
54
			inputProblem = TrajectoryCoordinationProblemXMLDeserializer
55 55
					.deserialize(new FileInputStream(new File(fileName)));
56 56
		}
57 57

  
......
75 75
			@Override
76 76
			public void handleProblem(EarliestArrivalProblem problem) {
77 77
				System.out.println("Output was written to " + outStringNameFinal);
78
				EarliestArrivalProblemXMLSerializer.serialize(problem, outputFinal);
78
				TrajectoryCoordinationProblemXMLSerializer.serialize(problem, outputFinal);
79 79
			}
80 80
		});
81 81

  
src/main/java/tt/jointeuclid2ni/Solver.java
12 12
import tt.euclid2i.discretization.LazyGrid;
13 13
import tt.jointeuclid2ni.probleminstance.EarliestArrivalProblem;
14 14
import tt.jointeuclid2ni.probleminstance.EarliestArrivalProblemSimpleMissionDeserializer;
15
import tt.jointeuclid2ni.probleminstance.EarliestArrivalProblemXMLDeserializer;
15
import tt.jointeuclid2ni.probleminstance.TrajectoryCoordinationProblemXMLDeserializer;
16 16
import tt.jointeuclid2ni.solver.Algorithm;
17 17
import tt.jointeuclid2ni.solver.Algorithms;
18 18
import tt.jointeuclid2ni.solver.GraphType;
......
75 75
        
76 76
        File file = new File(xml);
77 77
        params.fileName = file.getName();
78
        params.problem = EarliestArrivalProblemXMLDeserializer.deserialize(new FileInputStream(file));
78
        params.problem = TrajectoryCoordinationProblemXMLDeserializer.deserialize(new FileInputStream(file));
79 79
        
80 80
       	params.samplingInterval = 10;
81 81

  
src/main/java/tt/jointeuclid2ni/probleminstance/AsymetricObstacles.java
8 8
import tt.euclid2i.probleminstance.Environment;
9 9
import tt.euclid2i.region.Rectangle;
10 10

  
11
public class AsymetricObstacles extends EarliestArrivalProblemImpl {
11
public class AsymetricObstacles extends TrajectoryCoordinationProblemImpl {
12 12

  
13 13
    public AsymetricObstacles() {
14 14

  
src/main/java/tt/jointeuclid2ni/probleminstance/DejviceProblemRandom.java
12 12
import tt.euclid2i.util.Util;
13 13
import tt.vis.environentcreator.PolygonParser;
14 14

  
15
public class DejviceProblemRandom extends EarliestArrivalProblemImpl {
15
public class DejviceProblemRandom extends TrajectoryCoordinationProblemImpl {
16 16

  
17 17
    private static final String OBSTACLE_FILE = "src/main/resources/problems/dejvice_precise.txt";
18 18

  
src/main/java/tt/jointeuclid2ni/probleminstance/EarliestArrivalProblem.java
37 37
    public DirectedGraph<Point, Line> getPlanningGraph();
38 38
    
39 39
    public Point[] getDocks();
40
    
41
    public List<RelocationTask> getRelocationTasks();
42 40

  
43 41
}
44 42

  
src/main/java/tt/jointeuclid2ni/probleminstance/EarliestArrivalProblemImpl.java
1
package tt.jointeuclid2ni.probleminstance;
2

  
3
import java.util.Arrays;
4
import java.util.Collection;
5
import java.util.LinkedList;
6
import java.util.List;
7

  
8
import org.jgrapht.DirectedGraph;
9

  
10
import tt.euclid2i.Line;
11
import tt.euclid2i.Point;
12
import tt.euclid2i.Region;
13
import tt.euclid2i.probleminstance.Environment;
14
import tt.euclid2i.region.Rectangle;
15

  
16
public class EarliestArrivalProblemImpl implements EarliestArrivalProblem {
17

  
18
    @SuppressWarnings("serial")
19
    public static class CannotPlaceAgentsException extends RuntimeException {
20
    }
21

  
22
    final protected int targetRegionSide = 30;
23

  
24
    protected int nAgents;
25
    protected Environment environment;
26
    protected Point[] starts;
27
    protected Point[] targets;
28
    protected int[] bodyRadiuses;
29
    protected int[] maxSpeeds;
30

  
31
    private DirectedGraph<Point, Line> planningGraph;
32
    protected Point[] docks;
33
    private List<RelocationTask> relocationTasks;
34

  
35
    public EarliestArrivalProblemImpl(Environment environment, Point[] starts, Point[] targets, int[] bodyRadiuses, int[] maxSpeeds, DirectedGraph<Point, Line> planningGraph) {
36
    	this(environment, starts, targets, bodyRadiuses, maxSpeeds, planningGraph, null, new LinkedList<RelocationTask>());
37
    }
38
    
39
    public EarliestArrivalProblemImpl(Environment environment, Point[] starts, Point[] targets, int[] bodyRadiuses, DirectedGraph<Point, Line> planningGraph) {
40
        this(environment, starts, targets, bodyRadiuses, getSpeedArray(starts.length, 1), planningGraph);
41
    }
42

  
43
    private static int[] getSpeedArray(int nAgents, int speed) {
44
        int[] speeds = new int[nAgents];
45
        Arrays.fill(speeds, speed);
46
        return speeds;
47
    }
48

  
49
    public EarliestArrivalProblemImpl(Environment environment, Point[] starts, Point[] targets, int[] bodyRadiuses, int[] maxSpeeds, 
50
    		DirectedGraph<Point, Line> planningGraph, Point[] docks, List<RelocationTask> relocationTasks) {
51
        super();
52
        this.environment = environment;
53
        this.starts = starts;
54
        this.targets = targets;
55
        this.bodyRadiuses = bodyRadiuses;
56
        this.maxSpeeds = maxSpeeds;
57
        this.planningGraph = planningGraph;
58
        this.docks = docks;
59
        this.relocationTasks = relocationTasks;
60

  
61
        if (starts.length == targets.length && targets.length == bodyRadiuses.length)
62
            nAgents = starts.length;
63
        else
64
            throw new RuntimeException("Lengths of arrays differ");
65
    }
66

  
67
    public EarliestArrivalProblemImpl(Environment environment, int nAgents) {
68
        this.nAgents = nAgents;
69
        this.environment = environment;
70
        this.maxSpeeds = new int[nAgents];
71
        Arrays.fill(maxSpeeds, 1);
72

  
73
        starts = new Point[nAgents];
74
        targets = new Point[nAgents];
75
        bodyRadiuses = new int[nAgents];
76
    }
77

  
78
    public boolean isUniqueStart(Point point, int bodyRadius) {
79
        for (int i = 0; i < nAgents; i++) {
80
            if (starts[i] != null) {
81
                if (starts[i].distance(point) < bodyRadiuses[i] + bodyRadius) {
82
                    return false;
83
                }
84
            }
85
        }
86
        return true;
87
    }
88

  
89
    public boolean isUniqueTarget(Point point, int bodyRadius) {
90
        for (int i = 0; i < nAgents; i++) {
91
            if (targets[i] != null) {
92
                if (targets[i].distance(point) < bodyRadiuses[i] + bodyRadius) {
93
                    return false;
94
                }
95
            }
96
        }
97

  
98
        return true;
99
    }
100

  
101
    @Override
102
    public int nAgents() {
103
        return starts.length;
104
    }
105

  
106
    @Override
107
    public Point getStart(int i) {
108
        return starts[i];
109
    }
110

  
111
    @Override
112
    public Point[] getStarts() {
113
        return starts;
114
    }
115

  
116
    @Override
117
    public Point getTarget(int i) {
118
        return targets[i];
119
    }
120

  
121
    @Override
122
    public tt.euclid2i.Point[] getTargets() {
123
        return targets;
124
    }
125

  
126
    @Override
127
    public int getBodyRadius(int i) {
128
        return bodyRadiuses[i];
129
    }
130

  
131
    @Override
132
    public int[] getBodyRadiuses() {
133
        return bodyRadiuses;
134
    }
135

  
136
    @Override
137
    public int getMaxSpeed(int i) {
138
        return maxSpeeds[i];
139
    }
140

  
141
    @Override
142
    public int[] getMaxSpeeds() {
143
        return maxSpeeds;
144
    }
145

  
146
    @Override
147
    public Collection<Region> getObstacles() {
148
        return environment.getObstacles();
149
    }
150

  
151
    @Override
152
    public Environment getEnvironment() {
153
        return environment;
154
    }
155

  
156
    @Override
157
    public DirectedGraph<Point, Line> getPlanningGraph() {
158
        return planningGraph;
159
    }
160

  
161
	@Override
162
	public Point[] getDocks() {
163
		return docks;
164
	}
165

  
166
	@Override
167
	public List<RelocationTask> getRelocationTasks() {
168
		return relocationTasks;
169
	}
170
    
171
    
172

  
173

  
174
}
src/main/java/tt/jointeuclid2ni/probleminstance/EarliestArrivalProblemSimpleMissionDeserializer.java
68 68
            maxSpeeds[i] = agents.get(i).maxSpeed;
69 69
        }
70 70

  
71
        return new EarliestArrivalProblemImpl(env, starts, targets, bodyRadiuses, maxSpeeds, null);
71
        return new TrajectoryCoordinationProblemImpl(env, starts, targets, bodyRadiuses, maxSpeeds, null);
72 72

  
73 73
    }
74 74
}
src/main/java/tt/jointeuclid2ni/probleminstance/EarliestArrivalProblemXMLDeserializer.java
1
package tt.jointeuclid2ni.probleminstance;
2

  
3
import java.io.File;
4
import java.io.FileInputStream;
5
import java.io.FileNotFoundException;
6
import java.io.FileOutputStream;
7
import java.io.IOException;
8
import java.io.InputStream;
9
import java.io.StringWriter;
10
import java.util.ArrayList;
11
import java.util.Collection;
12
import java.util.LinkedList;
13
import java.util.List;
14

  
15
import javax.xml.parsers.DocumentBuilder;
16
import javax.xml.parsers.DocumentBuilderFactory;
17
import javax.xml.parsers.ParserConfigurationException;
18
import javax.xml.transform.OutputKeys;
19
import javax.xml.transform.Transformer;
20
import javax.xml.transform.TransformerException;
21
import javax.xml.transform.TransformerFactory;
22
import javax.xml.transform.dom.DOMSource;
23
import javax.xml.transform.stream.StreamResult;
24

  
25
import org.apache.commons.lang3.ArrayUtils;
26
import org.apache.log4j.Logger;
27
import org.jgrapht.DirectedGraph;
28
import org.jgrapht.EdgeFactory;
29
import org.jgrapht.graph.DirectedWeightedMultigraph;
30
import org.jgrapht.graph.SimpleDirectedWeightedGraph;
31
import org.w3c.dom.Document;
32
import org.w3c.dom.Element;
33
import org.w3c.dom.Node;
34
import org.w3c.dom.Text;
35
import org.w3c.dom.NodeList;
36
import org.xml.sax.SAXException;
37

  
38
import tt.euclid2i.Line;
39
import tt.euclid2i.Point;
40
import tt.euclid2i.Region;
41
import tt.euclid2i.probleminstance.Environment;
42
import tt.euclid2i.region.Circle;
43
import tt.euclid2i.region.Polygon;
44
import tt.euclid2i.region.Rectangle;
45

  
46
public class EarliestArrivalProblemXMLDeserializer {
47

  
48
	private static Logger LOGGER = Logger.getLogger(EarliestArrivalProblem.class);
49

  
50
    private class Agents {
51

  
52
        private int size;
53
        private List<Point> starts;
54
        private List<Point> targets;
55
        private List<Integer> radiuses;
56
        private List<Integer> maxSpeeds;
57

  
58
        private Agents() {
59
            this.size = 0;
60
            this.starts = new ArrayList<Point>();
61
            this.targets = new ArrayList<Point>();
62
            this.radiuses = new ArrayList<Integer>();
63
            this.maxSpeeds = new ArrayList<Integer>();
64
        }
65

  
66
        public void add(Point start, Point target, int radius, int maxSpeed) {
67
            starts.add(start);
68
            targets.add(target);
69
            radiuses.add(radius);
70
            maxSpeeds.add(maxSpeed);
71
            size++;
72
        }
73
    }
74

  
75
    private Document doc;
76

  
77
    public static EarliestArrivalProblem deserialize(InputStream stream) {
78
        return new EarliestArrivalProblemXMLDeserializer(stream).deserialize();
79
    }
80

  
81
    private EarliestArrivalProblemXMLDeserializer(InputStream stream) {
82

  
83
        try {
84
            DocumentBuilderFactory docFactory = DocumentBuilderFactory.newInstance();
85
            DocumentBuilder docBuilder = docFactory.newDocumentBuilder();
86
            this.doc = docBuilder.parse(stream);
87
        } catch (ParserConfigurationException e) {
88
            e.printStackTrace();
89
        } catch (SAXException e) {
90
            e.printStackTrace();
91
        } catch (IOException e) {
92
            e.printStackTrace();
93
        }
94
    }
95

  
96
    public EarliestArrivalProblem deserialize() {
97
        Environment environment = parseEnvironment();
98
        Agents agents = parseAgents();
99
        DirectedGraph<Point, Line> graph = parseGraph();
100
        Point[] docks = parseDocks();
101
        List<RelocationTask> tasks = parseTasks();
102

  
103
        Point[] starts = agents.starts.toArray(new Point[agents.size]);
104
        Point[] targets = agents.targets.toArray(new Point[agents.size]);
105
        int[] radiuses = ArrayUtils.toPrimitive(agents.radiuses.toArray(new Integer[agents.size]));
106
        int[] maxSpeeds = ArrayUtils.toPrimitive(agents.maxSpeeds.toArray(new Integer[agents.size]));
107

  
108
        return new EarliestArrivalProblemImpl(environment, starts, targets, radiuses, maxSpeeds, graph, docks, tasks);
109
    }
110

  
111
    private Point[] parseDocks() {
112
    	NodeList docksNL = doc.getElementsByTagName(EarliestArrivalProblemXMLConstants.DOCKS);
113
    	if(docksNL.getLength() == 0) {
114
    		return null;
115
    	}
116
    	
117
        assert docksNL.getLength() == 1;
118
        if (docksNL.item(0).getChildNodes().getLength() == 0) {
119
        	return null;
120
        }
121
        
122
        assert docksNL.item(0).getChildNodes().item(0).getNodeType() == Node.TEXT_NODE;
123
        String docksStr = docksNL.item(0).getTextContent();
124
        
125
        return stringToPointArray(docksStr);
126
	}
127
    
128
    private List<RelocationTask> parseTasks() {
129
    	
130
    	LinkedList<RelocationTask> tasks = new LinkedList<RelocationTask>();
131
    	
132
    	NodeList tasksNL = doc.getElementsByTagName(EarliestArrivalProblemXMLConstants.TASKS);
133
    	if(tasksNL.getLength() == 0) {
134
    		return null;
135
    	}
136
    	
137
    	Element tasksElem = (Element) tasksNL.item(0);
138

  
139
    	NodeList taskNL = tasksElem.getElementsByTagName(EarliestArrivalProblemXMLConstants.TASK);
140
    	
141
    	for (int i=0; i < taskNL.getLength(); i++) {
142
    		Element elem = (Element) taskNL.item(0);
143
    		assert elem.getNodeName().equals(EarliestArrivalProblemXMLConstants.TASK);
144
    		
145
    		int time = Integer.parseInt(elem.getAttribute("time"));
146
    		int agentId = Integer.parseInt(elem.getAttribute("agent"));
147
    		Point goal = stringToPoint(elem.getAttribute("goal"));
148
    		
149
    		tasks.add(new RelocationTaskImpl(time, agentId, goal));
150
    	} 	
151
    	
152
    	return tasks;
153
    	
154
	}
155

  
156
	private DirectedGraph<Point, Line> parseGraph() {
157
        long startTime = System.currentTimeMillis();
158
        DirectedWeightedMultigraph<Point, Line> graph = null;
159

  
160
        NodeList graphNL = doc.getElementsByTagName(EarliestArrivalProblemXMLConstants.GRAPH);
161

  
162
        if (graphNL.getLength() == 1) {
163

  
164
            graph = new DirectedWeightedMultigraph<Point, Line>(
165
                    new EdgeFactory<Point, Line>() {
166

  
167
                        @Override
168
                        public Line createEdge(Point sourceVertex,
169
                                               Point targetVertex) {
170
                            return new Line(sourceVertex, targetVertex);
171
                        }
172
                    }) {
173
						private static final long serialVersionUID = 1L;
174

  
175
						@Override
176
						public double getEdgeWeight(Line line) {
177
							return line.getDistance();
178
						}
179

  
180
            };
181

  
182
            NodeList verticesNL = doc.getElementsByTagName(EarliestArrivalProblemXMLConstants.VERTICES);
183
            assert verticesNL.getLength() == 1;
184
            NodeList nl = verticesNL.item(0).getChildNodes();
185
            assert nl.getLength() == 1 && nl.item(0).getNodeType() == Node.TEXT_NODE;
186
            String verticesListStr = ((Text) nl.item(0)).getData();
187

  
188
            Point[] vertices = stringToPointArray(verticesListStr);
189
            for (Point vertex : vertices) {
190
                graph.addVertex(vertex);
191
            }
192

  
193
            NodeList edgesNL = doc.getElementsByTagName(EarliestArrivalProblemXMLConstants.EDGES);
194
            assert edgesNL.getLength() == 1;
195
            assert edgesNL.item(0).getChildNodes().item(0).getNodeType() == Node.TEXT_NODE;
196
            String edgesListStr = edgesNL.item(0).getTextContent();
197

  
198
            String[] edgesStr = edgesListStr.split(";");
199
            for (String edgeStr : edgesStr) {
200
                if (!edgeStr.isEmpty()) {
201
                    String[] pointsStr = edgeStr.split(" ");
202

  
203
                    Point start = stringToPoint(pointsStr[0]);
204
                    Point end = stringToPoint(pointsStr[1]);
205

  
206
                    Line edge = graph.addEdge(start, end);
207
                }
208
            }
209

  
210
            LOGGER.debug("Graph (|V|=" + graph.vertexSet().size() + ", |E|=" + graph.edgeSet().size() + ") parsing took " + (System.currentTimeMillis() - startTime) + " ms");
211

  
212
            return graph;
213
        } else {
214
            return null;
215
        }
216
    }
217

  
218
    private Point[] stringToPointArray(String pointListStr) {
219

  
220
        String[] pointsStrArray = pointListStr.split(" ");
221
        LinkedList<Point> points = new LinkedList<Point>();
222
        for (String pointStr : pointsStrArray) {
223
            if (!pointStr.isEmpty()) {
224
                Point point = stringToPoint(pointStr);
225
                points.add(point);
226
            }
227
        }
228
        return points.toArray(new Point[points.size()]);
229
    }
230

  
231
    private Point stringToPoint(String verticeStr) {
232
        String[] xyStr = verticeStr.split(",");
233
        Point point = new Point(Integer.parseInt(xyStr[0]), Integer.parseInt(xyStr[1]));
234
        return point;
235
    }
236

  
237
    private Agents parseAgents() {
238
        Agents agents = new Agents();
239
        NodeList agentElements = doc.getElementsByTagName(EarliestArrivalProblemXMLConstants.AGENT);
240

  
241
        for (int i = 0; i < agentElements.getLength(); i++) {
242
            Element agent = (Element) agentElements.item(i);
243

  
244
            Point start, target;
245
            int radius, maxSpeed;
246
            
247
            if (agent.hasAttribute(EarliestArrivalProblemXMLConstants.START)) {
248
            	// use simple syntax
249
            	start = stringToPoint(agent.getAttribute(EarliestArrivalProblemXMLConstants.START));
250
            	target = stringToPoint(agent.getAttribute(EarliestArrivalProblemXMLConstants.TARGET));
251
            	radius = Integer.parseInt(agent.getAttribute(EarliestArrivalProblemXMLConstants.BODY_RADIUS));
252
            	maxSpeed = Integer.parseInt(agent.getAttribute(EarliestArrivalProblemXMLConstants.MAX_SPEED));
253
            } else {
254
            	// use verbose syntax
255
                NodeList startNL = agent.getElementsByTagName(EarliestArrivalProblemXMLConstants.START);
256
                try {
257
                    start = parsePoint((Element) startNL.item(0));
258
                } catch (Exception ex) {
259
                    throw new RuntimeException("Error while parsing start" + formatOutput(agent));
260
                }
261

  
262
                NodeList targetNL = agent.getElementsByTagName(EarliestArrivalProblemXMLConstants.TARGET);
263
                try {
264
                    target = parsePoint((Element) targetNL.item(0));
265
                } catch (Exception ex) {
266
                    throw new RuntimeException("Error while parsing target" + formatOutput(agent));
267
                }
268

  
269
                NodeList radiusNL = agent.getElementsByTagName(EarliestArrivalProblemXMLConstants.BODY_RADIUS);
270
                try {
271
                    radius = Integer.parseInt(radiusNL.item(0).getTextContent());
272
                } catch (Exception ex) {
273
                    throw new RuntimeException("Error while parsing radius" + formatOutput(agent));
274
                }
275

  
276
                NodeList maxSpeedNL = agent.getElementsByTagName(EarliestArrivalProblemXMLConstants.MAX_SPEED);
277
                try {
278
                    maxSpeed = Integer.parseInt(maxSpeedNL.item(0).getTextContent());
279
                } catch (Exception ex) {
280
                    System.err.printf("Error while parsing maxSpeed for %d. agent - value set do default (1)%n", i);
281
                    maxSpeed = 1;
282
                }
283
            }
284

  
285
            agents.add(start, target, radius, maxSpeed);
286
        }
287

  
288
        return agents;
289
    }
290

  
291
    private Environment parseEnvironment() {
292

  
293
    	List<Region> obstacles = null; 
294
    	NodeList obstacleNL = doc.getElementsByTagName(EarliestArrivalProblemXMLConstants.OBSTACLES);
295
    	if (obstacleNL.getLength() == 1) {
296
    		NodeList obstacleChildren = obstacleNL.item(0).getChildNodes();
297
    		obstacles = parseObstacles(obstacleChildren);
298
    	}
299
    	
300
        Rectangle bounds = parseBounds();
301
        Region boundary = parseBoundary();
302

  
303
        if (boundary == null) {
304
            if (bounds != null) {
305
                boundary = bounds.toOutFilledPolygon();
306
            } else {
307
                boundary = computeBoundsAroundObstacles(obstacles);
308
            }
309
        }
310
        
311
        // Compute statistics
312
        
313
        int obstacleCount = 0;
314
        int cornerCount = 0;
315
        for (Region obstacle : obstacles) {
316
        	obstacleCount++;
317
        	if (obstacle instanceof Polygon) {
318
        		cornerCount += ((Polygon) obstacle).getPoints().length;
319
        	}
320
        }
321
        
322
        if (boundary instanceof Polygon) {
323
        	cornerCount += ((Polygon) boundary).getPoints().length; 
324
        }
325
        
326
        LOGGER.debug("The environment consist of boundary and " + obstacleCount + " obstacles, with total " + cornerCount + " corners.");
327

  
328
        final Region boundaryRegionFinal = boundary;
329

  
330
        final List<Region> obstaclesFinal = obstacles;
331
        return new Environment() {
332
            @Override
333
            public Collection<Region> getObstacles() {
334
                return obstaclesFinal;
335
            }
336

  
337
            @Override
338
            public Region getBoundary() {
339
                return boundaryRegionFinal;
340
            }
341
        };
342
    }
343

  
344
    private Rectangle computeBoundsAroundObstacles(List<Region> obstacles) {
345
        int minx = Integer.MAX_VALUE;
346
        int miny = Integer.MAX_VALUE;
347
        int maxx = Integer.MIN_VALUE;
348
        int maxy = Integer.MIN_VALUE;
349
        for (Region obstacle : obstacles) {
350
            Rectangle bbox = obstacle.getBoundingBox();
351
            minx = Math.min(minx, bbox.getCorner1().x);
352
            miny = Math.min(miny, bbox.getCorner1().y);
353
            maxx = Math.max(maxx, bbox.getCorner2().x);
354
            maxy = Math.max(maxy, bbox.getCorner2().y);
355
        }
356

  
357
        return new Rectangle(new Point(minx, miny), new Point(maxx, maxy));
358
    }
359

  
360
    private Polygon parseBoundary() {
361
        Element boundaryElement = (Element) doc.getElementsByTagName(EarliestArrivalProblemXMLConstants.BOUNDARY).item(0);
362
        if (boundaryElement != null) {
363
            try {
364
                Polygon boundaryPolygon = new Polygon(stringToPointArray(boundaryElement.getTextContent()));
365
                return boundaryPolygon;
366
            } catch (Exception ex) {
367
                throw new RuntimeException("Error while parsing" + formatOutput(boundaryElement));
368
            }
369
        } else {
370
            return null;
371
        }
372
    }
373

  
374
    private Rectangle parseBounds() {
375
        Element boundsElement = (Element) doc.getElementsByTagName(EarliestArrivalProblemXMLConstants.BOUNDS).item(0);
376
        if (boundsElement != null) {
377
            NodeList cornerElements = boundsElement.getElementsByTagName(EarliestArrivalProblemXMLConstants.POINT);
378

  
379
            try {
380
                Point corner1 = parsePoint((Element) cornerElements.item(0));
381
                Point corner2 = parsePoint((Element) cornerElements.item(1));
382

  
383
                return new Rectangle(corner1, corner2);
384
            } catch (Exception ex) {
385
                throw new RuntimeException("Error while parsing" + formatOutput(boundsElement));
386
            }
387
        } else {
388
            return null;
389
        }
390
    }
391

  
392
    private List<Region> parseObstacles(NodeList obstacleElements) {
393
        final List<Region> obstacles = new ArrayList<Region>();
394

  
395
        for (int i = 0; i < obstacleElements.getLength(); i++) {
396
        	Region region = null;
397
            if (obstacleElements.item(i).getNodeName().equals("obstacle")) {
398
            	region = parseObstacle((Element) obstacleElements.item(i));
399
            } else if (obstacleElements.item(i).getNodeName().equals("circle")) {
400
            	region = parseCircle((Element) obstacleElements.item(i));
401
            } 
402
            if (region != null) {
403
            	obstacles.add(region);
404
            }
405
        }
406

  
407
        return obstacles;
408
    }
409

  
410
    private Polygon parseObstacle(Element obstacle) {
411
        try {
412

  
413
            boolean forceFilledInside = false;
414
            if (obstacle.hasAttribute("filledinside")) {
415
                forceFilledInside = true;
416
            }
417

  
418
            NodeList pointElements = obstacle.getElementsByTagName(EarliestArrivalProblemXMLConstants.POINT);
419

  
420
            Point[] pointsArray;
421
            if (pointElements.getLength() == 0) {
422
                // Polygon is defined using the simple syntax
423
                String text = obstacle.getTextContent();
424
                pointsArray = stringToPointArray(text);
425
            } else {
426
                // Polygon is defined using the verbose syntax
427
                List<Point> points = new ArrayList<Point>();
428

  
429
                for (int i = 0; i < pointElements.getLength(); i++) {
430
                    Node pointElement = pointElements.item(i);
431
                    points.add(parsePoint((Element) pointElement));
432
                }
433

  
434
                pointsArray = points.toArray(new Point[points.size()]);
435
            }
436

  
437
            if (forceFilledInside) {
438
                if (!Polygon.isClockwise(pointsArray)) {
439
                    ArrayUtils.reverse(pointsArray);
440
                }
441
            }
442

  
443
            return new Polygon(pointsArray);
444

  
445
        } catch (Exception ex) {
446
            throw new RuntimeException("Error while parsing" + formatOutput(obstacle));
447
        }
448
    }
449
    
450
    private Region parseCircle(Element obstacle) {
451
        	
452
        	Point center = stringToPoint(obstacle.getAttribute("center"));
453
        	int radius = Integer.parseInt(obstacle.getAttribute("radius"));
454
        	return new Circle(center, radius);
455
    }
456

  
457
    private Point parsePoint(Element pointElement) {
458
        NodeList xElement = pointElement.getElementsByTagName(EarliestArrivalProblemXMLConstants.X);
459
        NodeList yElement = pointElement.getElementsByTagName(EarliestArrivalProblemXMLConstants.Y);
460

  
461
        int x = Integer.valueOf(xElement.item(0).getTextContent());
462
        int y = Integer.valueOf(yElement.item(0).getTextContent());
463

  
464
        return new Point(x, y);
465
    }
466

  
467
    public String formatOutput(Node node) {
468
        try {
469
            Transformer transformer = TransformerFactory.newInstance().newTransformer();
470
            transformer.setOutputProperty(OutputKeys.INDENT, "yes");
471

  
472
            StreamResult result = new StreamResult(new StringWriter());
473
            DOMSource source = new DOMSource(node);
474

  
475
            transformer.transform(source, result);
476
            return result.getWriter().toString();
477
        } catch (TransformerException e) {
478

  
479
            e.printStackTrace();
480
            return "";
481
        }
482
    }
483

  
484
    public static void main(String[] args) throws FileNotFoundException {
485
        EarliestArrivalProblem deserialize = deserialize(new FileInputStream(new File("src/main/resources/problems/dejvice.xml")));
486
        EarliestArrivalProblemXMLSerializer.serialize(deserialize, new FileOutputStream(new File("src/main/resources/problems/dejvice_tst.xml")));
487
    }
488
}
src/main/java/tt/jointeuclid2ni/probleminstance/EarliestArrivalProblemXMLSerializer.java
1
package tt.jointeuclid2ni.probleminstance;
2

  
3
import java.io.File;
4
import java.io.FileNotFoundException;
5
import java.io.FileOutputStream;
6
import java.io.OutputStream;
7

  
8
import javax.xml.parsers.DocumentBuilder;
9
import javax.xml.parsers.DocumentBuilderFactory;
10
import javax.xml.parsers.ParserConfigurationException;
11
import javax.xml.transform.OutputKeys;
12
import javax.xml.transform.Transformer;
13
import javax.xml.transform.TransformerException;
14
import javax.xml.transform.TransformerFactory;
15
import javax.xml.transform.dom.DOMSource;
16
import javax.xml.transform.stream.StreamResult;
17

  
18
import org.jgrapht.DirectedGraph;
19
import org.w3c.dom.Document;
20
import org.w3c.dom.Element;
21
import org.w3c.dom.Node;
22

  
23
import tt.euclid2i.Line;
24
import tt.euclid2i.Point;
25
import tt.euclid2i.Region;
26
import tt.euclid2i.region.Circle;
27
import tt.euclid2i.region.Polygon;
28
import tt.euclid2i.region.Rectangle;
29

  
30

  
31
public class EarliestArrivalProblemXMLSerializer {
32

  
33
    private EarliestArrivalProblem problem;
34
    private OutputStream stream;
35
    private Document doc;
36

  
37
    public static void serialize(EarliestArrivalProblem problem, OutputStream stream) {
38
        new EarliestArrivalProblemXMLSerializer(problem, stream).serialize();
39
    }
40

  
41
    private EarliestArrivalProblemXMLSerializer(EarliestArrivalProblem problem, OutputStream stream) {
42
        this.problem = problem;
43
        this.stream = stream;
44

  
45
        try {
46
            DocumentBuilderFactory docFactory = DocumentBuilderFactory.newInstance();
47
            DocumentBuilder docBuilder = docFactory.newDocumentBuilder();
48
            this.doc = docBuilder.newDocument();
49
        } catch (ParserConfigurationException e) {
50
            e.printStackTrace();
51
        }
52
    }
53

  
54
    public void serialize() {
55
        // root
56
        Element problemElem = addElement(EarliestArrivalProblemXMLConstants.PROBLEM, doc);
57
        // env
58
        Element environmentElem = addElement(EarliestArrivalProblemXMLConstants.ENVIRONMENT, problemElem);
59
        // obstacles
60
        Element obstaclesElem = addElement(EarliestArrivalProblemXMLConstants.OBSTACLES, environmentElem);
61

  
62
        //int i = 0;
63
        for (Region region : problem.getObstacles()) {
64
            // obstacle
65
            if (region instanceof Polygon) {
66
            	Element obstacleElem = addElement(EarliestArrivalProblemXMLConstants.OBSTACLE, obstaclesElem);
67
	            String pointsStr = pointArrayToString(((Polygon) region).getPoints());
68
	            obstacleElem.appendChild(doc.createTextNode(pointsStr));
69
            } else if (region instanceof Circle) {
70
            	Circle circle = (Circle) region;
71
            	Element circleElem = addElement(EarliestArrivalProblemXMLConstants.CIRCLE, obstaclesElem);
72
            	circleElem.setAttribute("center", pointToString(circle.getCenter()));
73
            	circleElem.setAttribute("radius", Integer.toString(circle.getRadius()));
74
            } else {
75
            	throw new RuntimeException("Unsupported type of region: " + region);
76
            }
77
        }
78

  
79
        // boundary
80
        Element boundaryElem = addElement(EarliestArrivalProblemXMLConstants.BOUNDARY, environmentElem);
81
        Point[] points = null;
82
        if (problem.getEnvironment().getBoundary() instanceof Rectangle) {
83
        	points = ((Rectangle) problem.getEnvironment().getBoundary()).toPolygon().getPoints();
84
        } else if (problem.getEnvironment().getBoundary() instanceof Polygon) {
85
        	points = ((Polygon) problem.getEnvironment().getBoundary()).getPoints();
86
        } else {
87
        	throw new RuntimeException("This type of boundary is not supported for serialization");
88
        }
89
        
90
        addText(pointArrayToString(points), boundaryElem);
91

  
92
        //graph
93
        DirectedGraph<Point, Line> graph = problem.getPlanningGraph();
94
        if (graph != null) {
95
            Element graphElem = addElement(EarliestArrivalProblemXMLConstants.GRAPH, problemElem);
96

  
97
            Element verticesElem = addElement(EarliestArrivalProblemXMLConstants.VERTICES, graphElem);
98
            String verticesStr = pointArrayToString(graph.vertexSet().toArray(new Point[graph.vertexSet().size()]));
99
            verticesElem.appendChild(doc.createTextNode(verticesStr));
100

  
101
            Element edgesElem = addElement(EarliestArrivalProblemXMLConstants.EDGES, graphElem);
102

  
103
            StringBuilder sb = new StringBuilder();
104
            for (Line line : graph.edgeSet()) {
105
                sb.append(pointArrayToString(new Point[]{line.getStart(), line.getEnd()}) + ";");
106
            }
107
            edgesElem.appendChild(doc.createTextNode(sb.toString()));
108
        }
109

  
110
        // agents
111
        Element agentsElem = addElement(EarliestArrivalProblemXMLConstants.AGENTS, problemElem);
112

  
113
        for (int j = 0; j < problem.nAgents(); j++) {
114
            //agent
115
            Element agentElem = addElement(EarliestArrivalProblemXMLConstants.AGENT, agentsElem);
116

  
117
            agentElem.setAttribute(EarliestArrivalProblemXMLConstants.START, pointToString(problem.getStart(j)));
118
            agentElem.setAttribute(EarliestArrivalProblemXMLConstants.TARGET, pointToString(problem.getTarget(j)));
119
            agentElem.setAttribute(EarliestArrivalProblemXMLConstants.BODY_RADIUS, Integer.toString(problem.getBodyRadius(j)));
120
            agentElem.setAttribute(EarliestArrivalProblemXMLConstants.MAX_SPEED, Integer.toString(problem.getMaxSpeed(j)));
121
        }
122
        
123
        // docks
124
        if (problem.getDocks() != null) {
125
        	Element docksElem = addElement(EarliestArrivalProblemXMLConstants.DOCKS, problemElem);
126
            String docksStr = pointArrayToString(problem.getDocks());
127
            docksElem.appendChild(doc.createTextNode(docksStr));
128
        }
129

  
130
        try {
131
            TransformerFactory transformerFactory = TransformerFactory.newInstance();
132
            Transformer transformer = transformerFactory.newTransformer();
133
            transformer.setOutputProperty(OutputKeys.INDENT, "yes");
134
            transformer.setOutputProperty(OutputKeys.METHOD, "xml");
135

  
136
            DOMSource source = new DOMSource(doc);
137
            StreamResult result = new StreamResult(stream);
138

  
139
            transformer.transform(source, result);
140

  
141
        } catch (TransformerException e) {
142
            e.printStackTrace();
143
        }
144
    }
145

  
146
    private String pointArrayToString(Point[] pointArray) {
147
        StringBuilder sb = new StringBuilder();
148
        for (Point point : pointArray) {
149
            sb.append(point.x);
150
            sb.append(",");
151
            sb.append(point.y);
152
            sb.append(" ");
153
        }
154
        return sb.toString();
155
    }
156
    
157
    private String pointToString(Point point) {
158
        StringBuilder sb = new StringBuilder();
159
        sb.append(point.x);
160
        sb.append(",");
161
        sb.append(point.y);
162
        return sb.toString();
163
    }
164

  
165
    private Element addPointElement(Point point, Element parent) {
166
        Element pointElem = addElement(EarliestArrivalProblemXMLConstants.POINT, parent);
167

  
168
        Element xElem = addElement(EarliestArrivalProblemXMLConstants.X, pointElem);
169
        addText(Integer.toString(point.getX()), xElem);
170

  
171
        Element yElem = addElement(EarliestArrivalProblemXMLConstants.Y, pointElem);
172
        addText(Integer.toString(point.getY()), yElem);
173

  
174
        return pointElem;
175
    }
176

  
177
    private void addText(String text, Node parent) {
178
        parent.appendChild(doc.createTextNode(text));
179
    }
180

  
181
    private Element addElement(String name, Node parent) {
182
        Element element = doc.createElement(name);
183
        addText("", element);
184
        parent.appendChild(element);
185
        return element;
186
    }
187
}
src/main/java/tt/jointeuclid2ni/probleminstance/NarrowPassageProblem.java
8 8
import tt.euclid2i.probleminstance.Environment;
9 9
import tt.euclid2i.region.Rectangle;
10 10

  
11
public class NarrowPassageProblem extends EarliestArrivalProblemImpl {
11
public class NarrowPassageProblem extends TrajectoryCoordinationProblemImpl {
12 12

  
13 13
    public NarrowPassageProblem() {
14 14

  
src/main/java/tt/jointeuclid2ni/probleminstance/RandomProblem.java
9 9
import tt.euclid2i.probleminstance.RandomEnvironment;
10 10
import tt.euclid2i.util.Util;
11 11

  
12
public class RandomProblem extends EarliestArrivalProblemImpl {
12
public class RandomProblem extends TrajectoryCoordinationProblemImpl {
13 13

  
14 14
    int agentBodyRadius;
15 15
    Random random;
src/main/java/tt/jointeuclid2ni/probleminstance/RelocationTaskCoordinationProblem.java
1
package tt.jointeuclid2ni.probleminstance;
2

  
3
import java.util.Collection;
4
import java.util.List;
5

  
6
import org.jgrapht.DirectedGraph;
7

  
8
import tt.euclid2i.Line;
9
import tt.euclid2i.Point;
10
import tt.euclid2i.Region;
11
import tt.euclid2i.probleminstance.Environment;
12

  
13
public interface RelocationTaskCoordinationProblem {
14

  
15
    public int nAgents();
16

  
17
    public Point getStart(int i);
18

  
19
    public int getBodyRadius(int i);
20

  
21
    public int getMaxSpeed(int i);
22

  
23
    public Point[] getStarts();
24

  
25
    public int[] getBodyRadiuses();
26

  
27
    public int[] getMaxSpeeds();
28

  
29
    public Collection<Region> getObstacles();
30

  
31
    public Environment getEnvironment();
32

  
33
    public DirectedGraph<Point, Line> getPlanningGraph();
34
    
35
    public Point[] getDocks();
36
    
37
    public List<RelocationTask> getRelocationTasks();
38

  
39
}
40

  
src/main/java/tt/jointeuclid2ni/probleminstance/SuperconflictProblem.java
4 4
import tt.euclid2i.probleminstance.Environment;
5 5
import tt.euclid2i.probleminstance.RandomEnvironment;
6 6

  
7
public class SuperconflictProblem extends EarliestArrivalProblemImpl {
7
public class SuperconflictProblem extends TrajectoryCoordinationProblemImpl {
8 8

  
9 9
    int agentBodyRadius;
10 10

  
src/main/java/tt/jointeuclid2ni/probleminstance/SymetricObstacles.java
8 8
import tt.euclid2i.probleminstance.Environment;
9 9
import tt.euclid2i.region.Rectangle;
10 10

  
11
public class SymetricObstacles extends EarliestArrivalProblemImpl {
11
public class SymetricObstacles extends TrajectoryCoordinationProblemImpl {
12 12

  
13 13
    Environment env;
14 14

  
src/main/java/tt/jointeuclid2ni/probleminstance/SymmetricObstacles.java
8 8
import tt.euclid2i.probleminstance.Environment;
9 9
import tt.euclid2i.region.Rectangle;
10 10

  
11
public class SymmetricObstacles extends EarliestArrivalProblemImpl {
11
public class SymmetricObstacles extends TrajectoryCoordinationProblemImpl {
12 12

  
13 13
    Environment env;
14 14

  
src/main/java/tt/jointeuclid2ni/probleminstance/TrajectoryCoordinationProblemImpl.java
1
package tt.jointeuclid2ni.probleminstance;
2

  
3
import java.util.Arrays;
4
import java.util.Collection;
5
import java.util.LinkedList;
6
import java.util.List;
7

  
8
import org.jgrapht.DirectedGraph;
9

  
10
import tt.euclid2i.Line;
11
import tt.euclid2i.Point;
12
import tt.euclid2i.Region;
13
import tt.euclid2i.probleminstance.Environment;
14
import tt.euclid2i.region.Rectangle;
15

  
16
public class TrajectoryCoordinationProblemImpl implements EarliestArrivalProblem, RelocationTaskCoordinationProblem {
17

  
18
    @SuppressWarnings("serial")
19
    public static class CannotPlaceAgentsException extends RuntimeException {
20
    }
21

  
22
    final protected int targetRegionSide = 30;
23

  
24
    protected int nAgents;
25
    protected Environment environment;
26
    protected Point[] starts;
27
    protected Point[] targets;
28
    protected int[] bodyRadiuses;
29
    protected int[] maxSpeeds;
30

  
31
    private DirectedGraph<Point, Line> planningGraph;
32
    protected Point[] docks;
33
    private List<RelocationTask> relocationTasks;
34

  
35
    public TrajectoryCoordinationProblemImpl(Environment environment, Point[] starts, Point[] targets, int[] bodyRadiuses, int[] maxSpeeds, DirectedGraph<Point, Line> planningGraph) {
36
    	this(environment, starts, targets, bodyRadiuses, maxSpeeds, planningGraph, null, new LinkedList<RelocationTask>());
37
    }
38
    
39
    public TrajectoryCoordinationProblemImpl(Environment environment, Point[] starts, Point[] targets, int[] bodyRadiuses, DirectedGraph<Point, Line> planningGraph) {
40
        this(environment, starts, targets, bodyRadiuses, getSpeedArray(starts.length, 1), planningGraph);
41
    }
42

  
43
    private static int[] getSpeedArray(int nAgents, int speed) {
44
        int[] speeds = new int[nAgents];
45
        Arrays.fill(speeds, speed);
46
        return speeds;
47
    }
48

  
49
    public TrajectoryCoordinationProblemImpl(Environment environment, Point[] starts, Point[] targets, int[] bodyRadiuses, int[] maxSpeeds, 
50
    		DirectedGraph<Point, Line> planningGraph, Point[] docks, List<RelocationTask> relocationTasks) {
51
        super();
52
        this.environment = environment;
53
        this.starts = starts;
54
        this.targets = targets;
55
        this.bodyRadiuses = bodyRadiuses;
56
        this.maxSpeeds = maxSpeeds;
57
        this.planningGraph = planningGraph;
58
        this.docks = docks;
59
        this.relocationTasks = relocationTasks;
60

  
61
        if (starts.length == targets.length && targets.length == bodyRadiuses.length)
62
            nAgents = starts.length;
63
        else
64
            throw new RuntimeException("Lengths of arrays differ");
65
    }
66

  
67
    public TrajectoryCoordinationProblemImpl(Environment environment, int nAgents) {
68
        this.nAgents = nAgents;
69
        this.environment = environment;
70
        this.maxSpeeds = new int[nAgents];
71
        Arrays.fill(maxSpeeds, 1);
72

  
73
        starts = new Point[nAgents];
74
        targets = new Point[nAgents];
75
        bodyRadiuses = new int[nAgents];
76
    }
77

  
78
    public boolean isUniqueStart(Point point, int bodyRadius) {
79
        for (int i = 0; i < nAgents; i++) {
80
            if (starts[i] != null) {
81
                if (starts[i].distance(point) < bodyRadiuses[i] + bodyRadius) {
82
                    return false;
83
                }
84
            }
85
        }
86
        return true;
87
    }
88

  
89
    public boolean isUniqueTarget(Point point, int bodyRadius) {
90
        for (int i = 0; i < nAgents; i++) {
91
            if (targets[i] != null) {
92
                if (targets[i].distance(point) < bodyRadiuses[i] + bodyRadius) {
93
                    return false;
94
                }
95
            }
96
        }
97

  
98
        return true;
99
    }
100

  
101
    @Override
102
    public int nAgents() {
103
        return starts.length;
104
    }
105

  
106
    @Override
107
    public Point getStart(int i) {
108
        return starts[i];
109
    }
110

  
111
    @Override
112
    public Point[] getStarts() {
113
        return starts;
114
    }
115

  
116
    @Override
117
    public Point getTarget(int i) {
118
        return targets[i];
119
    }
120

  
121
    @Override
122
    public tt.euclid2i.Point[] getTargets() {
123
        return targets;
124
    }
125

  
126
    @Override
127
    public int getBodyRadius(int i) {
128
        return bodyRadiuses[i];
129
    }
130

  
131
    @Override
132
    public int[] getBodyRadiuses() {
133
        return bodyRadiuses;
134
    }
135

  
136
    @Override
137
    public int getMaxSpeed(int i) {
138
        return maxSpeeds[i];
139
    }
140

  
141
    @Override
142
    public int[] getMaxSpeeds() {
143
        return maxSpeeds;
144
    }
145

  
146
    @Override
147
    public Collection<Region> getObstacles() {
148
        return environment.getObstacles();
149
    }
150

  
151
    @Override
152
    public Environment getEnvironment() {
153
        return environment;
154
    }
155

  
156
    @Override
157
    public DirectedGraph<Point, Line> getPlanningGraph() {
158
        return planningGraph;
159
    }
160

  
161
	@Override
162
	public Point[] getDocks() {
163
		return docks;
164
	}
165

  
166
	@Override
167
	public List<RelocationTask> getRelocationTasks() {
168
		return relocationTasks;
169
	}
170
    
171
    
172

  
173

  
174
}
src/main/java/tt/jointeuclid2ni/probleminstance/TrajectoryCoordinationProblemXMLDeserializer.java
1
package tt.jointeuclid2ni.probleminstance;
2

  
3
import java.io.File;
4
import java.io.FileInputStream;
5
import java.io.FileNotFoundException;
6
import java.io.FileOutputStream;
7
import java.io.IOException;
8
import java.io.InputStream;
9
import java.io.StringWriter;
10
import java.util.ArrayList;
11
import java.util.Collection;
12
import java.util.LinkedList;
13
import java.util.List;
14

  
15
import javax.xml.parsers.DocumentBuilder;
16
import javax.xml.parsers.DocumentBuilderFactory;
17
import javax.xml.parsers.ParserConfigurationException;
18
import javax.xml.transform.OutputKeys;
19
import javax.xml.transform.Transformer;
20
import javax.xml.transform.TransformerException;
21
import javax.xml.transform.TransformerFactory;
22
import javax.xml.transform.dom.DOMSource;
23
import javax.xml.transform.stream.StreamResult;
24

  
25
import org.apache.commons.lang3.ArrayUtils;
26
import org.apache.log4j.Logger;
27
import org.jgrapht.DirectedGraph;
28
import org.jgrapht.EdgeFactory;
29
import org.jgrapht.graph.DirectedWeightedMultigraph;
30
import org.jgrapht.graph.SimpleDirectedWeightedGraph;
31
import org.w3c.dom.Document;
32
import org.w3c.dom.Element;
33
import org.w3c.dom.Node;
34
import org.w3c.dom.Text;
35
import org.w3c.dom.NodeList;
36
import org.xml.sax.SAXException;
37

  
38
import tt.euclid2i.Line;
39
import tt.euclid2i.Point;
40
import tt.euclid2i.Region;
41
import tt.euclid2i.probleminstance.Environment;
42
import tt.euclid2i.region.Circle;
43
import tt.euclid2i.region.Polygon;
44
import tt.euclid2i.region.Rectangle;
45

  
46
public class TrajectoryCoordinationProblemXMLDeserializer {
47

  
48
	private static Logger LOGGER = Logger.getLogger(EarliestArrivalProblem.class);
49

  
50
    private class Agents {
51

  
52
        private int size;
53
        private List<Point> starts;
54
        private List<Point> targets;
55
        private List<Integer> radiuses;
56
        private List<Integer> maxSpeeds;
57

  
58
        private Agents() {
59
            this.size = 0;
60
            this.starts = new ArrayList<Point>();
61
            this.targets = new ArrayList<Point>();
62
            this.radiuses = new ArrayList<Integer>();
63
            this.maxSpeeds = new ArrayList<Integer>();
64
        }
65

  
66
        public void add(Point start, Point target, int radius, int maxSpeed) {
67
            starts.add(start);
68
            targets.add(target);
69
            radiuses.add(radius);
70
            maxSpeeds.add(maxSpeed);
71
            size++;
72
        }
73
    }
74

  
75
    private Document doc;
76

  
77
    public static EarliestArrivalProblem deserialize(InputStream stream) {
78
        return new TrajectoryCoordinationProblemXMLDeserializer(stream).deserialize();
79
    }
80

  
81
    private TrajectoryCoordinationProblemXMLDeserializer(InputStream stream) {
82

  
83
        try {
84
            DocumentBuilderFactory docFactory = DocumentBuilderFactory.newInstance();
85
            DocumentBuilder docBuilder = docFactory.newDocumentBuilder();
86
            this.doc = docBuilder.parse(stream);
87
        } catch (ParserConfigurationException e) {
88
            e.printStackTrace();
89
        } catch (SAXException e) {
90
            e.printStackTrace();
91
        } catch (IOException e) {
92
            e.printStackTrace();
93
        }
94
    }
95

  
96
    public EarliestArrivalProblem deserialize() {
97
        Environment environment = parseEnvironment();
98
        Agents agents = parseAgents();
99
        DirectedGraph<Point, Line> graph = parseGraph();
100
        Point[] docks = parseDocks();
101
        List<RelocationTask> tasks = parseTasks();
102

  
103
        Point[] starts = agents.starts.toArray(new Point[agents.size]);
104
        Point[] targets = agents.targets.toArray(new Point[agents.size]);
105
        int[] radiuses = ArrayUtils.toPrimitive(agents.radiuses.toArray(new Integer[agents.size]));
106
        int[] maxSpeeds = ArrayUtils.toPrimitive(agents.maxSpeeds.toArray(new Integer[agents.size]));
107

  
108
        return new TrajectoryCoordinationProblemImpl(environment, starts, targets, radiuses, maxSpeeds, graph, docks, tasks);
109
    }
110

  
111
    private Point[] parseDocks() {
112
    	NodeList docksNL = doc.getElementsByTagName(EarliestArrivalProblemXMLConstants.DOCKS);
113
    	if(docksNL.getLength() == 0) {
114
    		return null;
115
    	}
116
    	
117
        assert docksNL.getLength() == 1;
118
        if (docksNL.item(0).getChildNodes().getLength() == 0) {
119
        	return null;
120
        }
121
        
122
        assert docksNL.item(0).getChildNodes().item(0).getNodeType() == Node.TEXT_NODE;
123
        String docksStr = docksNL.item(0).getTextContent();
124
        
125
        return stringToPointArray(docksStr);
126
	}
127
    
128
    private List<RelocationTask> parseTasks() {
129
    	
130
    	LinkedList<RelocationTask> tasks = new LinkedList<RelocationTask>();
131
    	
132
    	NodeList tasksNL = doc.getElementsByTagName(EarliestArrivalProblemXMLConstants.TASKS);
133
    	if(tasksNL.getLength() == 0) {
134
    		return null;
135
    	}
136
    	
137
    	Element tasksElem = (Element) tasksNL.item(0);
138

  
139
    	NodeList taskNL = tasksElem.getElementsByTagName(EarliestArrivalProblemXMLConstants.TASK);
140
    	
141
    	for (int i=0; i < taskNL.getLength(); i++) {
142
    		Element elem = (Element) taskNL.item(0);
143
    		assert elem.getNodeName().equals(EarliestArrivalProblemXMLConstants.TASK);
144
    		
145
    		int time = Integer.parseInt(elem.getAttribute("time"));
146
    		int agentId = Integer.parseInt(elem.getAttribute("agent"));
147
    		Point goal = stringToPoint(elem.getAttribute("goal"));
148
    		
149
    		tasks.add(new RelocationTaskImpl(time, agentId, goal));
150
    	} 	
151
    	
152
    	return tasks;
153
    	
154
	}
155

  
156
	private DirectedGraph<Point, Line> parseGraph() {
157
        long startTime = System.currentTimeMillis();
158
        DirectedWeightedMultigraph<Point, Line> graph = null;
159

  
160
        NodeList graphNL = doc.getElementsByTagName(EarliestArrivalProblemXMLConstants.GRAPH);
161

  
162
        if (graphNL.getLength() == 1) {
163

  
164
            graph = new DirectedWeightedMultigraph<Point, Line>(
165
                    new EdgeFactory<Point, Line>() {
166

  
167
                        @Override
168
                        public Line createEdge(Point sourceVertex,
169
                                               Point targetVertex) {
170
                            return new Line(sourceVertex, targetVertex);
171
                        }
172
                    }) {
173
						private static final long serialVersionUID = 1L;
174

  
175
						@Override
176
						public double getEdgeWeight(Line line) {
177
							return line.getDistance();
178
						}
179

  
180
            };
181

  
182
            NodeList verticesNL = doc.getElementsByTagName(EarliestArrivalProblemXMLConstants.VERTICES);
183
            assert verticesNL.getLength() == 1;
184
            NodeList nl = verticesNL.item(0).getChildNodes();
185
            assert nl.getLength() == 1 && nl.item(0).getNodeType() == Node.TEXT_NODE;
186
            String verticesListStr = ((Text) nl.item(0)).getData();
187

  
188
            Point[] vertices = stringToPointArray(verticesListStr);
189
            for (Point vertex : vertices) {
190
                graph.addVertex(vertex);
191
            }
192

  
193
            NodeList edgesNL = doc.getElementsByTagName(EarliestArrivalProblemXMLConstants.EDGES);
194
            assert edgesNL.getLength() == 1;
195
            assert edgesNL.item(0).getChildNodes().item(0).getNodeType() == Node.TEXT_NODE;
196
            String edgesListStr = edgesNL.item(0).getTextContent();
197

  
198
            String[] edgesStr = edgesListStr.split(";");
199
            for (String edgeStr : edgesStr) {
200
                if (!edgeStr.isEmpty()) {
201
                    String[] pointsStr = edgeStr.split(" ");
202

  
203
                    Point start = stringToPoint(pointsStr[0]);
204
                    Point end = stringToPoint(pointsStr[1]);
205

  
206
                    Line edge = graph.addEdge(start, end);
207
                }
208
            }
209

  
210
            LOGGER.debug("Graph (|V|=" + graph.vertexSet().size() + ", |E|=" + graph.edgeSet().size() + ") parsing took " + (System.currentTimeMillis() - startTime) + " ms");
211

  
212
            return graph;
213
        } else {
214
            return null;
215
        }
216
    }
217

  
218
    private Point[] stringToPointArray(String pointListStr) {
219

  
220
        String[] pointsStrArray = pointListStr.split(" ");
221
        LinkedList<Point> points = new LinkedList<Point>();
222
        for (String pointStr : pointsStrArray) {
223
            if (!pointStr.isEmpty()) {
224
                Point point = stringToPoint(pointStr);
225
                points.add(point);
226
            }
227
        }
228
        return points.toArray(new Point[points.size()]);
229
    }
230

  
231
    private Point stringToPoint(String verticeStr) {
232
        String[] xyStr = verticeStr.split(",");
233
        Point point = new Point(Integer.parseInt(xyStr[0]), Integer.parseInt(xyStr[1]));
234
        return point;
235
    }
236

  
237
    private Agents parseAgents() {
238
        Agents agents = new Agents();
239
        NodeList agentElements = doc.getElementsByTagName(EarliestArrivalProblemXMLConstants.AGENT);
240

  
241
        for (int i = 0; i < agentElements.getLength(); i++) {
242
            Element agent = (Element) agentElements.item(i);
243

  
244
            Point start, target;
245
            int radius, maxSpeed;
246
            
247
            if (agent.hasAttribute(EarliestArrivalProblemXMLConstants.START)) {
248
            	// use simple syntax
249
            	start = stringToPoint(agent.getAttribute(EarliestArrivalProblemXMLConstants.START));
250
            	target = stringToPoint(agent.getAttribute(EarliestArrivalProblemXMLConstants.TARGET));
251
            	radius = Integer.parseInt(agent.getAttribute(EarliestArrivalProblemXMLConstants.BODY_RADIUS));
... This diff was truncated because it exceeds the maximum size that can be displayed.

Also available in: Unified diff