    public void run(Graph graph) {
        clearCachedData();
        Collection<Trip> trips = _dao.getAllTrips();
        HashMap<StopPattern, TripPattern> patterns = new HashMap<StopPattern, TripPattern>();
        int index = 0;
        HashMap<String, HashMap<Stop, TreeSet<EncodedTrip>>> tripsByBlockAndStart = new HashMap<String, HashMap<Stop, TreeSet<EncodedTrip>>>();
        for (Trip trip : trips) {
            if (index % 100 == 0)
                _log.debug("trips=" + index + "/" + trips.size());
            index++;
            List<StopTime> stopTimes = _dao.getStopTimesForTrip(trip);
            if (stopTimes.size() < 2) {
                _log
                        .warn("Trip "
                                + trip
                                + " has fewer than two stops.  We will not use it for routing.  This is probably an error in your data");
                continue;
            }
            StopPattern stopPattern = stopPatternfromTrip(trip, _dao);
            TripPattern tripPattern = patterns.get(stopPattern);
            String blockId = trip.getBlockId();
            boolean simple = false;
            if (tripPattern == null) {
                tripPattern = makeTripPattern(graph, trip, stopTimes);
                patterns.put(stopPattern, tripPattern);
                if (blockId != null && !blockId.equals("")) {
                    addTripToInterliningMap(tripsByBlockAndStart, trip, stopTimes, tripPattern,
                            blockId);
                }
            } else {
                int insertionPoint = tripPattern.getDepartureTimeInsertionPoint(stopTimes.get(0)
                        .getDepartureTime());
                if (insertionPoint < 0) {
                    _log.warn("duplicate first departure time for trip " + trip.getId()
                            + ".  This will be handled correctly but inefficiently.");
                    createSimpleHops(graph, trip, stopTimes);
                } else {
                    StopTime st1 = null;
                    int i;
                    for (i = 0; i < stopTimes.size() - 1; i++) {
                        StopTime st0 = stopTimes.get(i);
                        st1 = stopTimes.get(i + 1);
                        int dwellTime = st0.getDepartureTime() - st0.getArrivalTime();
                        int runningTime = st1.getArrivalTime() - st0.getDepartureTime();
                        try {
                            tripPattern.addHop(i, insertionPoint, st0.getDepartureTime(),
                                    runningTime, st1.getArrivalTime(), dwellTime,
                                    trip.getId());
                        } catch (TripOvertakingException e) {
                            _log
                                    .warn("trip "
                                            + trip.getId()
                                            + " overtakes another trip with the same stops.  This will be handled correctly but inefficiently.");
                            for (i = i - 1; i >= 0; --i) {
                                tripPattern.removeHop(i, insertionPoint);
                            }
                            createSimpleHops(graph, trip, stopTimes);
                            simple = true;
                            break;
                        }
                    }
                }
                if (!simple) {
                    if (blockId != null && !blockId.equals("")) {
                        addTripToInterliningMap(tripsByBlockAndStart, trip, stopTimes, tripPattern,
                                blockId);
                    }
                }
                tripPattern.setTripFlags(insertionPoint, (trip.getWheelchairAccessible() != 0) ? TripPattern.FLAG_WHEELCHAIR_ACCESSIBLE : 0);
            }
        }
        HashMap<TripPattern, HashMap<TripPattern, PatternInterlineDwell>> dwellEdges = new HashMap<TripPattern, HashMap<TripPattern, PatternInterlineDwell>>();
        for (HashMap<Stop, TreeSet<EncodedTrip>> blockStops : tripsByBlockAndStart.values()) {
            for (Stop stop : blockStops.keySet()) {
                TreeSet<EncodedTrip> tripsStartingAt = blockStops.get(stop);
                for (EncodedTrip eTrip : tripsStartingAt) {
                    Trip trip = eTrip.trip;
                    List<StopTime> stopTimes = _dao.getStopTimesForTrip(trip);
                    StopTime lastStopTime = stopTimes.get(stopTimes.size() - 1);
                    Stop lastStop = lastStopTime.getStop();
                    TreeSet<EncodedTrip> possiblePosts = null;
                    if (blockStops.containsKey(lastStop)) {
                        possiblePosts = blockStops.get(lastStop);
                    } else {
                        continue;
                    }
                    EncodedTrip[] postArray = possiblePosts.toArray(new EncodedTrip[0]);
                    int postIndex = 0;
                    int arrivalTime = lastStopTime.getArrivalTime();
                    EncodedTrip post;
                    do {
                        post = postArray[postIndex];
                        ++postIndex;
                    } while (postIndex < postArray.length
                            && postArray[postIndex].getFirstStop(_dao).getDepartureTime() < arrivalTime);
                    if (post == null || post.getFirstStop(_dao).getDepartureTime() < arrivalTime) {
                        continue;
                    }
                    PatternInterlineDwell dwell = null;
                    HashMap<TripPattern, PatternInterlineDwell> edges = dwellEdges
                            .get(eTrip.pattern);
                    if (edges != null) {
                        dwell = edges.get(post.pattern);
                    }
                    if (dwell == null) {
                        Vertex arrive = graph.addVertex(id(lastStop.getId()) + "_"
                                + id(trip.getId()) + "_A", lastStop.getLon(), lastStop.getLat());
                        Vertex depart = graph.addVertex(id(lastStop.getId()) + "_"
                                + id(post.trip.getId()) + "_D", lastStop.getLon(), lastStop
                                .getLat());
                        dwell = new PatternInterlineDwell(arrive, depart, trip);
                        graph.addEdge(dwell);
                        if (edges == null) {
                            edges = new HashMap<TripPattern, PatternInterlineDwell>();
                            dwellEdges.put(eTrip.pattern, edges);
                        }
                        edges.put(eTrip.pattern, dwell);
                    }
                    int departureTime = post.getFirstStop(_dao).getArrivalTime();
                    int dwellTime = departureTime - arrivalTime;
                    dwell.addTrip(trip.getId(), post.trip.getId(), dwellTime);
                }
            }
        }
        loadTransfers(graph);
        deleteUselessDwells(graph);
        clearCachedData();
    }

    public void run(Graph graph) {
        clearCachedData();
        Collection<Trip> trips = _dao.getAllTrips();
        HashMap<StopPattern, TripPattern> patterns = new HashMap<StopPattern, TripPattern>();
        int index = 0;
        HashMap<String, HashMap<Stop, TreeSet<EncodedTrip>>> tripsByBlockAndStart = new HashMap<String, HashMap<Stop, TreeSet<EncodedTrip>>>();
        for (Trip trip : trips) {
            if (index % 100 == 0)
                _log.debug("trips=" + index + "/" + trips.size());
            index++;
            List<StopTime> stopTimes = _dao.getStopTimesForTrip(trip);
            if (stopTimes.size() < 2) {
                _log
                        .warn("Trip "
                                + trip
                                + " has fewer than two stops.  We will not use it for routing.  This is probably an error in your data");
                continue;
            }
            StopPattern stopPattern = stopPatternfromTrip(trip, _dao);
            TripPattern tripPattern = patterns.get(stopPattern);
            String blockId = trip.getBlockId();
            boolean simple = false;
            if (tripPattern == null) {
                tripPattern = makeTripPattern(graph, trip, stopTimes);
                patterns.put(stopPattern, tripPattern);
                if (blockId != null && !blockId.equals("")) {
                    addTripToInterliningMap(tripsByBlockAndStart, trip, stopTimes, tripPattern,
                            blockId);
                }
            } else {
                int insertionPoint = tripPattern.getDepartureTimeInsertionPoint(stopTimes.get(0)
                        .getDepartureTime());
                if (insertionPoint < 0) {
                    _log.warn("duplicate first departure time for trip " + trip.getId()
                            + ".  This will be handled correctly but inefficiently.");
                    simple = true;
                    createSimpleHops(graph, trip, stopTimes);
                } else {
                    StopTime st1 = null;
                    int i;
                    for (i = 0; i < stopTimes.size() - 1; i++) {
                        StopTime st0 = stopTimes.get(i);
                        st1 = stopTimes.get(i + 1);
                        int dwellTime = st0.getDepartureTime() - st0.getArrivalTime();
                        int runningTime = st1.getArrivalTime() - st0.getDepartureTime();
                        try {
                            tripPattern.addHop(i, insertionPoint, st0.getDepartureTime(),
                                    runningTime, st1.getArrivalTime(), dwellTime,
                                    trip.getId());
                        } catch (TripOvertakingException e) {
                            _log
                                    .warn("trip "
                                            + trip.getId()
                                            + " overtakes another trip with the same stops.  This will be handled correctly but inefficiently.");
                            for (i = i - 1; i >= 0; --i) {
                                tripPattern.removeHop(i, insertionPoint);
                            }
                            createSimpleHops(graph, trip, stopTimes);
                            simple = true;
                            break;
                        }
                    }
                }
                if (!simple) {
                    if (blockId != null && !blockId.equals("")) {
                        addTripToInterliningMap(tripsByBlockAndStart, trip, stopTimes, tripPattern,
                                blockId);
                    }
                    tripPattern.setTripFlags(insertionPoint, (trip.getWheelchairAccessible() != 0) ? TripPattern.FLAG_WHEELCHAIR_ACCESSIBLE : 0);
                }
            }
        }
        HashMap<TripPattern, HashMap<TripPattern, PatternInterlineDwell>> dwellEdges = new HashMap<TripPattern, HashMap<TripPattern, PatternInterlineDwell>>();
        for (HashMap<Stop, TreeSet<EncodedTrip>> blockStops : tripsByBlockAndStart.values()) {
            for (Stop stop : blockStops.keySet()) {
                TreeSet<EncodedTrip> tripsStartingAt = blockStops.get(stop);
                for (EncodedTrip eTrip : tripsStartingAt) {
                    Trip trip = eTrip.trip;
                    List<StopTime> stopTimes = _dao.getStopTimesForTrip(trip);
                    StopTime lastStopTime = stopTimes.get(stopTimes.size() - 1);
                    Stop lastStop = lastStopTime.getStop();
                    TreeSet<EncodedTrip> possiblePosts = null;
                    if (blockStops.containsKey(lastStop)) {
                        possiblePosts = blockStops.get(lastStop);
                    } else {
                        continue;
                    }
                    EncodedTrip[] postArray = possiblePosts.toArray(new EncodedTrip[0]);
                    int postIndex = 0;
                    int arrivalTime = lastStopTime.getArrivalTime();
                    EncodedTrip post;
                    do {
                        post = postArray[postIndex];
                        ++postIndex;
                    } while (postIndex < postArray.length
                            && postArray[postIndex].getFirstStop(_dao).getDepartureTime() < arrivalTime);
                    if (post == null || post.getFirstStop(_dao).getDepartureTime() < arrivalTime) {
                        continue;
                    }
                    PatternInterlineDwell dwell = null;
                    HashMap<TripPattern, PatternInterlineDwell> edges = dwellEdges
                            .get(eTrip.pattern);
                    if (edges != null) {
                        dwell = edges.get(post.pattern);
                    }
                    if (dwell == null) {
                        Vertex arrive = graph.addVertex(id(lastStop.getId()) + "_"
                                + id(trip.getId()) + "_A", lastStop.getLon(), lastStop.getLat());
                        Vertex depart = graph.addVertex(id(lastStop.getId()) + "_"
                                + id(post.trip.getId()) + "_D", lastStop.getLon(), lastStop
                                .getLat());
                        dwell = new PatternInterlineDwell(arrive, depart, trip);
                        graph.addEdge(dwell);
                        if (edges == null) {
                            edges = new HashMap<TripPattern, PatternInterlineDwell>();
                            dwellEdges.put(eTrip.pattern, edges);
                        }
                        edges.put(eTrip.pattern, dwell);
                    }
                    int departureTime = post.getFirstStop(_dao).getArrivalTime();
                    int dwellTime = departureTime - arrivalTime;
                    dwell.addTrip(trip.getId(), post.trip.getId(), dwellTime);
                }
            }
        }
        loadTransfers(graph);
        deleteUselessDwells(graph);
        clearCachedData();
    }
