Ignore:
Timestamp:
Sep 18, 2010, 12:37:10 PM (14 years ago)
Author:
gnappo
Message:

Corretta la creazione del grafo per il calcolo del flusso massimo (errore logico); implementata DFS ricorsiva sul grafo.

File:
1 edited

Legend:

Unmodified
Added
Removed

  • src/main/java/weka/clusterers/forMetisMQI/MQI.java

    r15 r16  
    2323
    2424public class MQI {
    25        
     25
    2626        static int i = -1;
    27        
    28         static private Set<Node> reversedLookup(Node sink, DirectedGraph<Node, Edge> g, Map<Edge, Number> edgeFlowMap) {
     27
     28        static private Set<Node> DFSReversed(Node currentNode,
     29                        DirectedGraph<Node, Edge> g, Map<Edge, Number> edgeFlowMap, Set<Node> marked) {
     30                Collection<Edge> inEdges = g.getInEdges(currentNode);
    2931                Set<Node> result = new HashSet<Node>();
    30                 Collection<Edge> inEdges = g.getInEdges(sink);
     32                result.add(currentNode);
    3133                Iterator<Edge> inEdgesIterator = inEdges.iterator();
    3234                while (inEdgesIterator.hasNext()) {
    3335                        Edge edge = inEdgesIterator.next();
    3436                        Node src = g.getSource(edge);
    35                         Edge reverseEdge = g.findEdge(src, sink);
    36                         if ((reverseEdge != null)
    37                                         && ((Integer) edgeFlowMap.get(reverseEdge) < reverseEdge
    38                                                         .getCapacity())) {
    39                                 result.add(src);
     37                        Edge reverseEdge = g.findEdge(src, currentNode);
     38                        if (reverseEdge != null && !marked.contains(src)) {
     39                                int flow = (Integer) edgeFlowMap.get(reverseEdge);
     40                                int capacity = reverseEdge.getCapacity();
     41                                if (flow < capacity) {
     42                                        marked.add(src);
     43                                        result.addAll(DFSReversed(src, g, edgeFlowMap, marked));
     44                                }
    4045                        }
    4146                }
    4247                return result;
    4348        }
    44        
    45         static private Set<Node> DFSReversed(Node sink, DirectedGraph<Node, Edge> g, Map<Edge, Number> edgeFlowMap) {
    46                 Stack<Node> stack = new Stack<Node>();
    47                 stack.push(sink);
     49
     50
     51
     52        static private Set<Node> BFSReversed(Node sink,
     53                        DirectedGraph<Node, Edge> g, Map<Edge, Number> edgeFlowMap) {
    4854                Set<Node> result = new HashSet<Node>();
    49                 Set<Node> discardedNodes = new HashSet<Node>();
     55                Set<Node> visitedNodes = new HashSet<Node>();
     56                Stack<Node> nodesToVisit = new Stack<Node>();
    5057                result.add(sink);
    51                 while (!stack.empty()) {
    52                         boolean founded = false;
    53                         Node currentNode = stack.pop();
    54                         discardedNodes.add(currentNode);
     58                nodesToVisit.push(sink);
     59                while (!nodesToVisit.empty()) {
     60                        Node currentNode = nodesToVisit.pop();
     61                        visitedNodes.add(currentNode);
    5562                        Collection<Edge> inEdges = g.getInEdges(currentNode);
    5663                        Iterator<Edge> inEdgesIterator = inEdges.iterator();
    … …  
    5966                                Node src = g.getSource(edge);
    6067                                Edge reverseEdge = g.findEdge(src, currentNode);
    61                                 if ((reverseEdge != null) && !discardedNodes.contains(src)
    62                                                 && ((Integer) edgeFlowMap.get(reverseEdge) < reverseEdge
    63                                                                 .getCapacity()) && !founded) {
    64                                         founded=true;
    65                                         stack.push(src);
    66                                         result.add(src);
    67                                 }
    68                                 discardedNodes.add(src);
     68                                if (reverseEdge != null) {
     69                                        int flow = (Integer) edgeFlowMap.get(reverseEdge);
     70                                        int capacity = reverseEdge.getCapacity();
     71                                        if (flow < capacity) {
     72                                                if (!nodesToVisit.contains(src)
     73                                                                && !visitedNodes.contains(src)) {
     74                                                        nodesToVisit.push(src);
     75                                                }
     76                                                result.add(src);
     77                                        }
     78                                }
    6979                        }
    7080                }
    7181                return result;
    7282        }
    73        
    74         static private Set<Node> BFSReversed(Node sink, DirectedGraph<Node, Edge> g, Map<Edge, Number> edgeFlowMap) {
    75                 Set<Node> result = new HashSet<Node>();
    76                 Set<Node> visitedNodes = new HashSet<Node>();
    77                 Stack<Node> nodesToVisit = new Stack<Node>();
    78                 result.add(sink);
    79                 nodesToVisit.push(sink);
    80                 while(!nodesToVisit.empty()) {
    81                         Node currentNode = nodesToVisit.pop();
    82                         visitedNodes.add(currentNode);
    83                         Collection<Edge> inEdges = g.getInEdges(currentNode);
    84                         Iterator<Edge> inEdgesIterator = inEdges.iterator();
    85                         while(inEdgesIterator.hasNext()) {
    86                                 Edge edge = inEdgesIterator.next();
    87                                 Node src = g.getSource(edge);
    88                                 Edge reverseEdge = g.findEdge(src, currentNode);
    89                                 if((reverseEdge != null) && ((Integer)edgeFlowMap.get(reverseEdge) < reverseEdge.getCapacity())) {
    90                                         if(!nodesToVisit.contains(src) && !visitedNodes.contains(src)) {
    91                                                 nodesToVisit.push(src);
    92                                         }
    93                                         result.add(src);
    94                                 }
    95                         }
    96                 }
    97                 return result;
    98         }
    99        
    100         static private DirectedGraph<Node,       Edge> prepareDirectedGraph(Bisection partition, Node source, Node sink) {
     83
     84        static private DirectedGraph<Node, Edge> prepareDirectedGraph(
     85                        Bisection partition, Node source, Node sink) {
    10186                Subgraph A = null;
    10287                Subgraph B = null;
    103                 if(partition.getSubgraph().getVertexCount() < partition.getComplement().getVertexCount()) {
     88                if (partition.getSubgraph().getVertexCount() < partition
     89                                .getComplement().getVertexCount()) {
    10490                        A = partition.getSubgraph();
    10591                        B = partition.getComplement();
    106                 }
    107                 else {
     92                } else {
    10893                        A = partition.getComplement();
    10994                        B = partition.getSubgraph();
    … …  
    11196                int a = A.getVertexCount();
    11297                int c = partition.edgeCut() / 2;
    113                
    114                
    115                 DirectedGraph<Node,Edge> g = new DirectedSparseGraph<Node, Edge>();
    116                 Iterator<Node> nodes =  A.iterator();
    117                 while(nodes.hasNext()) {
     98
     99                DirectedGraph<Node, Edge> g = new DirectedSparseGraph<Node, Edge>();
     100                Iterator<Node> nodes = A.iterator();
     101                while (nodes.hasNext()) {
    118102                        Node u = nodes.next();
    119103                        g.addVertex(u);
    120104                }
    121                
    122                 nodes =  A.iterator();
     105
     106                nodes = A.iterator();
    123107                int id = 0;
    124                 while(nodes.hasNext()) {
     108                while (nodes.hasNext()) {
    125109                        Node u = nodes.next();
    126110                        Iterator<Node> neighbors = A.getNeighbors(u).iterator();
    127                         while(neighbors.hasNext()) {
     111                        while (neighbors.hasNext()) {
    128112                                Node v = neighbors.next();
    129                                 g.addEdge(new Edge(Integer.toString(id),A.getWeight(u, v),a),u,v);
     113                                g.addEdge(new Edge(Integer.toString(id), A.getWeight(u, v), a),
     114                                                u, v);
    130115                                id++;
    131116                        }
    132117                }
    133                
     118
    134119                g.addVertex(source);
    135120                g.addVertex(sink);
     121
    136122               
    137                
    138                 nodes =  B.iterator();
    139                 while(nodes.hasNext()) {
     123                //build the edges from source to each node of A which previously was connected
     124                //with a node of B.
     125                nodes = B.iterator();
     126                while (nodes.hasNext()) {
    140127                        Node u = nodes.next();
    141128                        Iterator<Node> neighbors = B.getGraph().getNeighbors(u).iterator();
    142                         while(neighbors.hasNext()) {
     129                        while (neighbors.hasNext()) {
    143130                                Node v = neighbors.next();
    144                                 if(A.contains(v)) {
    145                                         g.addEdge(new Edge(Integer.toString(id),1,a),source,v);
    146                                         id++;
    147                                 }
    148                         }
    149                 }
    150                
    151                 nodes =  A.iterator();
    152                 while(nodes.hasNext()) {
    153                         Node u = nodes.next();
    154                         g.addEdge(new Edge(Integer.toString(id),1,c),u,sink);
     131                                if (A.contains(v)) {
     132                                        Edge e = g.findEdge(source, v);
     133                                        if(e != null) {
     134                                                e.setCapacity(e.getCapacity() + a);
     135                                        } else {
     136                                                g.addEdge(new Edge(Integer.toString(id), 1, a), source, v);
     137                                                id++;
     138                                        }
     139                                }
     140                        }
     141                }
     142
     143                nodes = A.iterator();
     144                while (nodes.hasNext()) {
     145                        Node u = nodes.next();
     146                        g.addEdge(new Edge(Integer.toString(id), 1, c), u, sink);
    155147                        id++;
    156148                }
    157149                return g;
    158150        }
    159        
     151
    160152        /**
    161          * Given a partion of a graph, execute the Max-Flow Quotient-cut Improvement algorithm,
    162          * to find an improved cut and then returns the cluster which yields the best quotient cut.
     153         * Given a partion of a graph, execute the Max-Flow Quotient-cut Improvement
     154         * algorithm, to find an improved cut and then returns the cluster which
     155         * yields the best quotient cut.
     156         *
    163157         * @param partition
    164158         * @return
    … …  
    168162                boolean finished = false;
    169163                Bisection bisection = partition;
    170                 Set<Node> cluster = new HashSet<Node>(partition.getSmallerNotEmptySubgraph().createInducedSubgraph().getVertices());
     164                Set<Node> cluster = new HashSet<Node>(partition
     165                                .getSmallerNotEmptySubgraph().createInducedSubgraph()
     166                                .getVertices());
    171167                int maxFlowThreshold = Integer.MAX_VALUE;
    172168                while (!finished) {
    173169                        Node source = new Node("S");
    174170                        Node sink = new Node("T");
    175                         DirectedGraph<Node, Edge> directedGraph = prepareDirectedGraph(bisection, source, sink);
    176 //                      Util.viewGraph(directedGraph);
     171                        DirectedGraph<Node, Edge> directedGraph = prepareDirectedGraph(
     172                                        bisection, source, sink);
    177173                        Transformer<Edge, Number> capTransformer = new Transformer<Edge, Number>() {
    178174                                public Double transform(Edge e) {
    … …  
    181177                        };
    182178                        Map<Edge, Number> edgeFlowMap = new HashMap<Edge, Number>();
    183                         i=-1;
     179                        i = -1;
    184180                        // This Factory produces new edges for use by the algorithm
    185181                        Factory<Edge> edgeFactory = new Factory<Edge>() {
    … …  
    190186                        };
    191187                        EdmondsKarpMaxFlow<Node, Edge> alg = new EdmondsKarpMaxFlow<Node, Edge>(
    192                                         directedGraph, source, sink, capTransformer, edgeFlowMap, edgeFactory);
    193                        
    194                         maxFlowThreshold = bisection.getSmallerNotEmptySubgraph().getVertexCount() * bisection.edgeCut() / 2;
     188                                        directedGraph, source, sink, capTransformer, edgeFlowMap,
     189                                        edgeFactory);
     190
     191                        maxFlowThreshold = bisection.getSmallerNotEmptySubgraph()
     192                                        .getVertexCount()
     193                                        * bisection.edgeCut() / 2;
    195194                        alg.evaluate();
    196                         Util.viewFlowGraph(directedGraph, edgeFlowMap);
    197                         System.out.println("MAX FLOW: " + alg.getMaxFlow() + " THRESHOLD: " + maxFlowThreshold);
    198                         if(alg.getMaxFlow() < maxFlowThreshold) {
    199 //                              bisection = prepareBisection(bisection.getSmallerNotEmptySubgraph().createInducedSubgraph(), sourcePartition, sinkPartition);
    200                                 cluster = BFSReversed(sink, directedGraph, edgeFlowMap);
    201 //                              System.out.println("DFSReversed: " + DFSReversed(sink, directedGraph, edgeFlowMap));
    202 //                              bisection = new Bisection(new Subgraph(bisection.getSmallerNotEmptySubgraph().createInducedSubgraph(), DFSReversed(sink, directedGraph, edgeFlowMap)));
    203 //                              cluster = reversedLookup(sink, directedGraph, edgeFlowMap);
     195//                      Util.viewFlowGraph(directedGraph, edgeFlowMap);
     196                        System.out.println("MAX FLOW: " + alg.getMaxFlow() + " THRESHOLD: "
     197                                        + maxFlowThreshold);
     198                        if (alg.getMaxFlow() < maxFlowThreshold) {
     199                                cluster = DFSReversed(sink, directedGraph, edgeFlowMap, new HashSet<Node>());
    204200                                cluster.remove(sink);
    205                                 bisection = new Bisection(new Subgraph(bisection.getSmallerNotEmptySubgraph().createInducedSubgraph(), cluster));
     201                                 bisection = new Bisection(new Subgraph(bisection.getGraph(),
     202                                 cluster));
    206203                                System.out.println("NEW BISECTION: " + bisection.toString());
    207204                        } else
    … …  
    210207                return cluster;
    211208        }
    212        
    213         private static Bisection prepareBisection(UndirectedGraph g, Set<Node> sourcePartition, Set<Node> sinkPartition) {
    214                 Bisection b = null;
    215                 Subgraph sourceSubgraph = new Subgraph(g, sourcePartition);
    216                 Subgraph sinkSubgraph = new Subgraph(g, sinkPartition);
    217                 Subgraph subgraph = null;
    218                 if(sourceSubgraph.getVertexCount() > sinkSubgraph.getVertexCount())
    219                         subgraph =sourceSubgraph;
    220                 else
    221                         subgraph = sinkSubgraph;
    222                 b = new Bisection(subgraph);
    223                 return b;
    224         }
    225        
     209
    226210}
Note: See TracChangeset for help on using the changeset viewer.