Source code

001/* *********************************************************************** *
002 * project: org.matsim.*
003 * RandomGroupLevelSelector.java
004 *                                                                         *
005 * *********************************************************************** *
006 *                                                                         *
007 * copyright       : (C) 2013 by the members listed in the COPYING,        *
008 *                   LICENSE and WARRANTY file.                            *
009 * email           : info at matsim dot org                                *
010 *                                                                         *
011 * *********************************************************************** *
012 *                                                                         *
013 *   This program is free software; you can redistribute it and/or modify  *
014 *   it under the terms of the GNU General Public License as published by  *
015 *   the Free Software Foundation; either version 2 of the License, or     *
016 *   (at your option) any later version.                                   *
017 *   See also COPYING, LICENSE and WARRANTY file                           *
018 *                                                                         *
019 * *********************************************************************** */
020package org.matsim.contrib.socnetsim.framework.replanning.selectors.highestweightselection;
021
022import java.util.*;
023
024import org.apache.log4j.Logger;
025import org.matsim.api.core.v01.Id;
026import org.matsim.api.core.v01.population.Person;
027import org.matsim.api.core.v01.population.Plan;
028
029import org.matsim.contrib.socnetsim.framework.population.JointPlan;
030import org.matsim.contrib.socnetsim.framework.population.JointPlans;
031import org.matsim.contrib.socnetsim.framework.replanning.grouping.GroupPlans;
032import org.matsim.contrib.socnetsim.framework.replanning.grouping.ReplanningGroup;
033import org.matsim.contrib.socnetsim.framework.replanning.selectors.GroupLevelPlanSelector;
034import org.matsim.contrib.socnetsim.framework.replanning.selectors.IncompatiblePlansIdentifier;
035import org.matsim.contrib.socnetsim.framework.replanning.selectors.IncompatiblePlansIdentifierFactory;
036
037/**
038 * @author thibautd
039 */
040public class RandomGroupLevelSelector implements GroupLevelPlanSelector {
041        private static final Logger log = Logger.getLogger( RandomGroupLevelSelector.class );
042        private final Random random;
043        private final IncompatiblePlansIdentifierFactory incompFactory;
044
045        public RandomGroupLevelSelector(
046                        final Random random,
047                        final IncompatiblePlansIdentifierFactory incompFactory) {
048                this.random = random;
049                this.incompFactory = incompFactory;
050        }
051        
052        // /////////////////////////////////////////////////////////////////////////
053        // interface and abstract method
054        // /////////////////////////////////////////////////////////////////////////
055        @Override
056        public final GroupPlans selectPlans(
057                        final JointPlans jointPlans,
058                        final ReplanningGroup group) {
059                final IncompatiblePlansIdentifier incompatiblePlansIdentifier =
060                        incompFactory.createIdentifier( jointPlans , group );
061                final Map<Id, PersonRecord> personRecords =
062                        getPersonRecords(
063                                        jointPlans,
064                                        group );
065                final IncompatiblePlanRecords incompatibleRecords =
066                        new IncompatiblePlanRecords(
067                                        incompatiblePlansIdentifier,
068                                        personRecords );
069
070                final GroupPlans plans = searchForRandomCombination(
071                                incompatibleRecords,
072                                new ArrayList<>(
073                                        personRecords.values() ) );
074
075                if ( plans == null ) {
076                        throw new RuntimeException( "could not find combination for group "+group );
077                }
078
079                assert plans.getAllIndividualPlans().size() == group.getPersons().size() : plans.getAllIndividualPlans()+" != "+group.getPersons();
080
081                return plans;
082        }
083
084        private static Map<Id, PersonRecord> getPersonRecords(
085                        final JointPlans jointPlans,
086                        final ReplanningGroup group) {
087                final Map<Id, PersonRecord> map = new LinkedHashMap<Id, PersonRecord>();
088
089                final Map<JointPlan, Collection<PlanRecord>> recordsPerJp = new HashMap<>();
090                for (Person person : group.getPersons()) {
091                        final List<PlanRecord> plans = new ArrayList<>();
092                        for (Plan plan : person.getPlans()) {
093                                final JointPlan jp = jointPlans.getJointPlan( plan );
094
095                                final PlanRecord r = new PlanRecord(
096                                                        plan,
097                                                        jp,
098                                                        0 );
099                                plans.add( r );
100                                if ( jp != null ) {
101                                        Collection<PlanRecord> rs = recordsPerJp.get( jp );
102                                        if ( rs == null ) {
103                                                rs = new ArrayList<>();
104                                                recordsPerJp.put( jp , rs );
105                                        }
106                                        rs.add( r );
107                                }
108                        }
109                        final PersonRecord pr = new PersonRecord( person , plans );
110                        map.put(
111                                        person.getId(),
112                                        pr );
113                        for ( PlanRecord p : plans ) {
114                                p.person = pr;
115                        }
116                }
117
118                for (PersonRecord personRecord : map.values()) {
119                        for ( PlanRecord pr : personRecord.plans ) {
120                                if ( pr.jointPlan == null ) continue;
121                                pr.linkedPlans.addAll( recordsPerJp.get( pr.jointPlan ) );
122                                pr.linkedPlans.remove( pr );
123                        }
124                }
125
126                return map;
127        }
128
129        private GroupPlans searchForRandomCombination(
130                        final IncompatiblePlanRecords incompatibleRecords,
131                        final List<PersonRecord> persons) {
132                final Queue<AnswerNode> plansStack = getInitialNodes( persons.get(0).plans );
133
134                if ( log.isTraceEnabled() ) {
135                        log.trace( "search for random combination for persons "+persons );
136                }
137
138                while ( !plansStack.isEmpty() ) {
139                        final AnswerNode currentPlan = plansStack.remove();
140
141                        if ( log.isTraceEnabled() ) {
142                                log.trace( "examine "+currentPlan );
143                        }
144
145                        if ( currentPlan.type == AnswerNodeType.feasibility ) {
146                                currentPlan.resetFeasibilities();
147                                continue;
148                        }
149
150                        if ( currentPlan.record.isStillFeasible ) {
151
152                                final List<PersonRecord> actuallyRemainingPersons = remainingPersons(persons, currentPlan);
153
154                                if (!actuallyRemainingPersons.isEmpty()) {
155                                        final FeasibilityChanger feasibilityChanger = new FeasibilityChanger();
156                                        SelectorUtils.tagIncompatiblePlansAsInfeasible(
157                                                        currentPlan.record,
158                                                        incompatibleRecords,
159                                                        feasibilityChanger);
160                                        markPlansOfCotravelersAsInfeasible( currentPlan , feasibilityChanger );
161                                        markJointPlansAsInfeasible( currentPlan.record , feasibilityChanger );
162
163                                        final PersonRecord nextPerson = actuallyRemainingPersons.get(0);
164                                        plansStack.add( new AnswerNode( feasibilityChanger ) );
165                                        for (PlanRecord r : shuffle(nextPerson.plans)) {
166                                                // TODO: only add one plan per planComposition-incompatibility "branch"
167                                                if (!r.isStillFeasible) continue;
168
169                                                final AnswerNode newNode = new AnswerNode( r, currentPlan );
170                                                if ( log.isTraceEnabled() ) {
171                                                        log.trace( "add to stack: "+newNode );
172                                                }
173                                                assert !containsSamePersonTwice( newNode ) : "plans="+ plansStack +"\n       answer="+ newNode;
174                                                plansStack.add( newNode );
175
176                                        }
177                                }
178                                else {
179                                        final GroupPlans constructedPlan = new GroupPlans();
180                                        for ( AnswerNode p : currentPlan ) {
181                                                SelectorUtils.add( constructedPlan, p.record );
182                                        }
183                                        return constructedPlan;
184                                }
185                        }
186                }
187
188                return null;
189        }
190
191        private void markJointPlansAsInfeasible(
192                        final PlanRecord currentRecord,
193                        final FeasibilityChanger feasibilityChanger ) {
194                for ( PlanRecord otherRecord : currentRecord.person.plans ) {
195                        if ( currentRecord == otherRecord ) continue;
196                        for ( PlanRecord linked : otherRecord.linkedPlans ) {
197                                feasibilityChanger.changeIfNecessary( linked );
198                        }
199                }
200        }
201
202        private void markPlansOfCotravelersAsInfeasible(
203                        final AnswerNode currentPlan,
204                        final FeasibilityChanger feasibilityChanger ) {
205                final Collection<PlanRecord> linkedPlans = currentPlan.record.linkedPlans;
206                for ( PlanRecord linkedPlan : linkedPlans ) {
207                        for ( PlanRecord planOfCotraveler : linkedPlan.person.plans ) {
208                                if ( linkedPlan == planOfCotraveler ) continue;
209                                feasibilityChanger.changeIfNecessary( planOfCotraveler );
210                                markJointPlansAsInfeasible( planOfCotraveler , feasibilityChanger );
211                        }
212                }
213        }
214
215        private Queue<AnswerNode> getInitialNodes(List<PlanRecord> plans ) {
216                final Queue<AnswerNode> queue = Collections.asLifoQueue( new ArrayDeque<AnswerNode>() );
217                for ( PlanRecord p : plans ) queue.add( new AnswerNode( p , null ) );
218                return queue;
219        }
220
221        private boolean containsSamePersonTwice(AnswerNode answerStack) {
222                final Set<Id<Person>> ps = new HashSet<>();
223
224                for ( AnswerNode p : answerStack ) {
225                        if ( !ps.add( p.record.person.person.getId() ) ) return true;
226                        for ( PlanRecord l : p.record.linkedPlans ) {
227                                if ( !ps.add( l.person.person.getId() ) ) return true;
228                        }
229                }
230
231                return false;
232        }
233
234        private List<PersonRecord> remainingPersons(List<PersonRecord> persons, AnswerNode plansStack) {
235                final List<PersonRecord> rem = new ArrayList<>( persons );
236                for ( AnswerNode p : plansStack ) {
237                        rem.remove( p.record.person );
238                        for ( PlanRecord l : p.record.linkedPlans ) rem.remove( l.person );
239                }
240                return rem;
241        }
242
243        private <T> Collection<T> shuffle(List<T> plans) {
244                Collections.shuffle( plans , random );
245                return plans;
246        }
247
248        private enum AnswerNodeType {record, feasibility}
249
250        private static class AnswerNode implements Iterable<AnswerNode> {
251                private final PlanRecord record;
252                private final AnswerNode parent;
253                private final FeasibilityChanger feasibilityChanger;
254                private final AnswerNodeType type;
255
256                private AnswerNode(PlanRecord record, AnswerNode parent) {
257                        this.record = record;
258                        this.parent = parent;
259                        this.feasibilityChanger = null;
260                        this.type = AnswerNodeType.record;
261                }
262
263                private AnswerNode(FeasibilityChanger feasibilityChanger) {
264                        this.record = null;
265                        this.parent = null;
266                        this.feasibilityChanger = feasibilityChanger;
267                        this.type = AnswerNodeType.feasibility;
268                }
269
270                @Override
271                public Iterator<AnswerNode> iterator() {
272                        return new Iterator<AnswerNode>() {
273                                @Override
274                                public void remove() {
275                                        throw new UnsupportedOperationException();
276                                }
277
278                                AnswerNode current = AnswerNode.this;
279
280                                @Override
281                                public boolean hasNext() {
282                                        return current != null;
283                                }
284
285                                @Override
286                                public AnswerNode next() {
287                                        AnswerNode n = current;
288                                        current = current.parent;
289                                        return n;
290                                }
291                        };
292                }
293
294                public void resetFeasibilities() {
295                        if ( feasibilityChanger == null ) return;
296                        feasibilityChanger.resetFeasibilities();
297                }
298
299                @Override
300                public String toString() {
301                        final StringBuilder s = new StringBuilder( "AnswerNode{ " );
302                        for ( AnswerNode n : this ) s.append( n.record.toString() );
303                        if ( feasibilityChanger != null ) s.append( "; feasibilityChanging" );
304                        s.append( " } " );
305                        return s.toString();
306                }
307        }
308}