NWFInstance {{ /** * Checks if a solution is valid with respect to this nwfInstance. * * @author liangyu 1st April * @param SolutionI solution, Config config * @return 1, if valid; 0 if invalid. */ public double valid(SolutionI solution, Config config) { /** * Cast the SolutionI object to a NWFSolution object, * if cannot be casted, return 0; */ double retVal = 0; NWFSolution nwfSolution = null; if (solution instanceof NWFSolution) { nwfSolution = (NWFSolution) solution; } else { return retVal; } String source = nwfSolution.getSource().getV(); String sink = nwfSolution.getSink().getV(); if (areAllNodeFlowBalanced(nwfSolution.getG(), source, sink) && areAllEdgeFlowValid(nwfSolution.getG())) { retVal = 1; } else { retVal = 0; } return retVal; } /** * check whether all the nodes are flow balanced * @param g * @return */ private boolean areAllNodeFlowBalanced( EdgeLabeledGraph g, String source, String sink) { Iterator> i = g.getAdjs().iterator(); for (;i.hasNext();) { // keep the element in the iterator in a tmp variable, // or else it causes some problem in the next step. Adjacency tmpA = i.next(); Node n = tmpA.getSource(); // node not source,not sink if (!(n.getV().equals(source)) && !(n.getV().equals(sink))) { // it works well, tested. int outFlowValue = getNodeOutFlowValue(tmpA); // get the rest list of adjacency List> tempList = g.getAdjs().remove(tmpA); int inFlowValue = getNodeInFlowVaue(n, tempList); if (!(outFlowValue == inFlowValue)) { return false; } } } return true; } /** * for a perticular node, get the in flow value * @param n * @param tempList * @return */ private int getNodeInFlowVaue(Node n, List> tempList) { int inFlowValue = 0; Iterator> i = tempList.iterator(); for (;i.hasNext() ;) { Adjacency tmp = i.next(); Iterator> i1 = tmp.getSuccessors().iterator(); for (;i1.hasNext() ;) { NodeAndLabel tmp1 = i1.next(); if (n.getV().equals(tmp1.getN().getV())) { inFlowValue += tmp1.getLabel2().getV(); } } } return inFlowValue; } /** * for a particular node, get the outside flow value * @param adj * @return */ private int getNodeOutFlowValue(Adjacency adj) { int outFlowValue = 0; Iterator> i = adj.getSuccessors().iterator(); for (;i.hasNext() ;) { NodeAndLabel tmp = i.next(); outFlowValue += tmp.getLabel2().getV(); } return outFlowValue; } private boolean areAllEdgeFlowValid( EdgeLabeledGraph g) { Iterator> i = g.getAdjs().iterator(); for (; i.hasNext();) { Adjacency tmpA = i.next(); if (areAllEdgeFlowValidHelper(tmpA.getSuccessors())) { return true; } // if find any edgeflow is invalid, just terminate // this loop, and return false; break; } return false; } private boolean areAllEdgeFlowValidHelper( List> successors) { Iterator> i = successors.iterator(); for (; i.hasNext();) { NodeAndLabel tmpN = i.next(); if (tmpN.getLabel2().getV() > tmpN.getLabel1().getV()) { return false; } } return true; } /** * Calculate the quality of a solution with respect to this * nwfInstance. * * @return double quality * @param SolutionI solution * @author liangyu 1st April */ public double quality(SolutionI solution) { double quality = 0; NWFSolution nwfSolution = null; /* not long avaiable if (valid(solution) != 1) { System.out.println("solution is invalid," + "no quality will be get for it"); } */ nwfSolution = (NWFSolution) solution; int flowValue = getValueAtSource(nwfSolution, "flow"); int capValue = getValueAtSource(nwfSolution, "cap"); quality = (double)flowValue / capValue; return quality; } /** * getValueAtSource function, it will call the helper function * getValueAtSourceHelper. * * @param Flow f * @param String string, two options: * "cap" means the value we want to get is the capacity * "flow" means the value we want to get is the flow * @return int value */ private int getValueAtSource(NWFSolution nwfSolution, String string) { int value = 0; String source = nwfSolution.getSource().getV(); Iterator> adj1 = nwfSolution.getG().getAdjs().iterator(); for (; adj1.hasNext();) { Adjacency tmpA = adj1.next(); if (tmpA.getSource().getV().equals(source)) { value = getValueAtSourceHelper(tmpA, string); } } return value; } /** * getValueAtSourceHelper Function * * @param adj2 * @param string * @return */ private int getValueAtSourceHelper( Adjacency adj2, String string) { int result = 0; // get every NodeAndLabel element from the list Iterator> inl = adj2.getSuccessors().iterator(); for (; inl.hasNext();) { NodeAndLabel tmpN = inl.next(); if (string.equals("cap")) { result = result + tmpN.getLabel1().getV(); } else if (string.equals("flow")) { result = result + tmpN.getLabel2().getV(); } } return result; } }} NWFInstanceSet {{ /** * Check if an instance belongs to this nwfInstanceSet. * * @param InstanceI instance * @return Option * @author liangyu 1st April */ public Option belongsTo(InstanceI instance) { NWFInstance i = (NWFInstance)instance; if(!i.equals(getSingleton())){ return new Some("The instance " + i.print() + " is different from " + getSingleton().print() + "."); } return new None(); } public Option valid(Config config) { NWFInstance i = getSingleton(); int n = countNode(i); if (n <=0 ) { return new Some("The Instance set has a n <= 0"); } else { return new None(); } } private int countNode(NWFInstance i) { EdgeLabeledGraph g = i.getG(); List> adjs = g.getAdjs(); return adjs.length(); } }} // the configuration for the networkflow playground NWFConfig {{ private static NWFConfig DEFAULT_NWF_CONFIG; static{ // I just limit the node to 10 at most. try{ DEFAULT_NWF_CONFIG = NWFConfig.parse( "nwf_config[\n" + "maxN: 10\n" + "]" ); }catch(Exception ex){ ex.printStackTrace(); } } public static NWFConfig getDefaultDomainConfig(){ return NWFConfig.DEFAULT_NWF_CONFIG; } public static Config getDefaultConfig(){ return new Config(SCGConfig.getDefaultSCGConfig(), getDefaultDomainConfig()); } }}