Ignore:
Timestamp:
Sep 17, 2010, 6:04:18 PM (14 years ago)
Author:
gnappo
Message:

Individuazione del miglioramento del taglio: tentativi.

Location:
src/main/java/weka/clusterers/forMetisMQI
Files:
6 edited

Legend:

Unmodified
Added
Removed
  • src/main/java/weka/clusterers/forMetisMQI/GraphAlgorithms.java

    r14 r15  
    5757        static public Set<Set<Node>> metisMqi(UndirectedGraph g, int numberOfCluster, int sizeFinerGraph) {
    5858                Set<Set<Node>> clusters = new HashSet<Set<Node>>();
     59                Util.viewGraph(g);
    5960                for (int i = 0; i < numberOfCluster; i++) {
    6061                        Bisection partition = metis(g,sizeFinerGraph);
    6162                        Set<Node> cluster = MQI.mqi(partition);
    6263                        clusters.add(cluster);
     64                        System.out.println("CLUSTER "+ i + ": " + cluster);
    6365                }
    6466                return clusters;
  • src/main/java/weka/clusterers/forMetisMQI/MQI.java

    r14 r15  
    11package weka.clusterers.forMetisMQI;
    22
    3 import java.awt.Color;
    4 import java.awt.Dimension;
    5 import java.awt.Paint;
    63import java.util.Collection;
    74import java.util.HashMap;
     
    129import java.util.Stack;
    1310
    14 import javax.swing.JFrame;
    15 
    1611import org.apache.commons.collections15.Factory;
    1712import org.apache.commons.collections15.Transformer;
     
    2217import weka.clusterers.forMetisMQI.graph.Subgraph;
    2318import weka.clusterers.forMetisMQI.graph.UndirectedGraph;
     19import weka.clusterers.forMetisMQI.util.Util;
    2420import edu.uci.ics.jung.algorithms.flows.EdmondsKarpMaxFlow;
    25 import edu.uci.ics.jung.algorithms.layout.FRLayout;
    26 import edu.uci.ics.jung.algorithms.layout.KKLayout;
    27 import edu.uci.ics.jung.algorithms.layout.Layout;
    2821import edu.uci.ics.jung.graph.DirectedGraph;
    2922import edu.uci.ics.jung.graph.DirectedSparseGraph;
    30 import edu.uci.ics.jung.graph.Graph;
    31 import edu.uci.ics.jung.visualization.BasicVisualizationServer;
    32 import edu.uci.ics.jung.visualization.decorators.ToStringLabeller;
    3323
    3424public class MQI {
    3525       
    3626        static int i = -1;
     27       
     28        static private Set<Node> reversedLookup(Node sink, DirectedGraph<Node, Edge> g, Map<Edge, Number> edgeFlowMap) {
     29                Set<Node> result = new HashSet<Node>();
     30                Collection<Edge> inEdges = g.getInEdges(sink);
     31                Iterator<Edge> inEdgesIterator = inEdges.iterator();
     32                while (inEdgesIterator.hasNext()) {
     33                        Edge edge = inEdgesIterator.next();
     34                        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);
     40                        }
     41                }
     42                return result;
     43        }
     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);
     48                Set<Node> result = new HashSet<Node>();
     49                Set<Node> discardedNodes = new HashSet<Node>();
     50                result.add(sink);
     51                while (!stack.empty()) {
     52                        boolean founded = false;
     53                        Node currentNode = stack.pop();
     54                        discardedNodes.add(currentNode);
     55                        Collection<Edge> inEdges = g.getInEdges(currentNode);
     56                        Iterator<Edge> inEdgesIterator = inEdges.iterator();
     57                        while (inEdgesIterator.hasNext()) {
     58                                Edge edge = inEdgesIterator.next();
     59                                Node src = g.getSource(edge);
     60                                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);
     69                        }
     70                }
     71                return result;
     72        }
    3773       
    3874        static private Set<Node> BFSReversed(Node sink, DirectedGraph<Node, Edge> g, Map<Edge, Number> edgeFlowMap) {
     
    132168                boolean finished = false;
    133169                Bisection bisection = partition;
    134                 Set<Node> cluster = new HashSet<Node>(partition.getSubgraph().createInducedSubgraph().getVertices());
     170                Set<Node> cluster = new HashSet<Node>(partition.getSmallerNotEmptySubgraph().createInducedSubgraph().getVertices());
    135171                int maxFlowThreshold = Integer.MAX_VALUE;
    136172                while (!finished) {
     
    138174                        Node sink = new Node("T");
    139175                        DirectedGraph<Node, Edge> directedGraph = prepareDirectedGraph(bisection, source, sink);
     176//                      Util.viewGraph(directedGraph);
    140177                        Transformer<Edge, Number> capTransformer = new Transformer<Edge, Number>() {
    141178                                public Double transform(Edge e) {
     
    144181                        };
    145182                        Map<Edge, Number> edgeFlowMap = new HashMap<Edge, Number>();
     183                        i=-1;
    146184                        // This Factory produces new edges for use by the algorithm
    147                         i=-1;
    148185                        Factory<Edge> edgeFactory = new Factory<Edge>() {
    149186                                public Edge create() {
    150187                                        i++;
    151                                         return new Edge(Integer.toString(i), 1, 1);
     188                                        return new Edge("f" + Integer.toString(i), 1, 1);
    152189                                }
    153190                        };
     
    155192                                        directedGraph, source, sink, capTransformer, edgeFlowMap, edgeFactory);
    156193                       
    157                         maxFlowThreshold = bisection.getSmallerSubgraph().getVertexCount() * bisection.edgeCut() / 2;
     194                        maxFlowThreshold = bisection.getSmallerNotEmptySubgraph().getVertexCount() * bisection.edgeCut() / 2;
    158195                        alg.evaluate();
     196                        Util.viewFlowGraph(directedGraph, edgeFlowMap);
    159197                        System.out.println("MAX FLOW: " + alg.getMaxFlow() + " THRESHOLD: " + maxFlowThreshold);
    160198                        if(alg.getMaxFlow() < maxFlowThreshold) {
    161                                 Set<Node> sinkPartition = alg.getNodesInSinkPartition();
    162                                 System.out.println(sinkPartition);
    163                                 Set<Node> sourcePartition = alg.getNodesInSourcePartition();
    164                                 System.out.println(sourcePartition);
    165                                 bisection = prepareBisection(bisection.getSmallerSubgraph().createInducedSubgraph(), sourcePartition, sinkPartition);
    166 //                              bisection = new Bisection(new Subgraph(bisection.getSmallerSubgraph().createInducedSubgraph(), BFSReversed(sink, directedGraph, edgeFlowMap)));
     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);
     204                                cluster.remove(sink);
     205                                bisection = new Bisection(new Subgraph(bisection.getSmallerNotEmptySubgraph().createInducedSubgraph(), cluster));
    167206                                System.out.println("NEW BISECTION: " + bisection.toString());
    168                                 cluster = sinkPartition;
    169207                        } else
    170208                                finished = true;
  • src/main/java/weka/clusterers/forMetisMQI/graph/Bisection.java

    r12 r15  
    139139       
    140140        /**
    141          * Returns the smaller subgraph of this bisection.
     141         * Returns the smaller not empty subgraph of this bisection, null otherwise.
    142142         * @return
    143143         */
    144         public Subgraph getSmallerSubgraph() {
     144        public Subgraph getSmallerNotEmptySubgraph() {
     145                if(a.getVertexCount() > 0 && b.getVertexCount() == 0)
     146                        return a;
     147                if(b.getVertexCount() > 0 && a.getVertexCount() == 0)
     148                        return b;
    145149                if(a.getVertexCount() < b.getVertexCount())
    146150                        return a;
  • src/main/java/weka/clusterers/forMetisMQI/graph/Edge.java

    r11 r15  
    2828                        Edge e = (Edge) o;
    2929                        result = result && (e.getId().equals(id));
    30                         result = result && (e.getWeight() == weight);
    31                         result = result && (e.getCapacity() == capacity);
    3230                }
    3331                return result;
  • src/main/java/weka/clusterers/forMetisMQI/graph/Subgraph.java

    r13 r15  
    204204        @Override
    205205        public String toString() {
    206                 String out = "[";
     206                if(getVertexCount() == 0)
     207                        return "[]";
     208                StringBuffer out =new StringBuffer("[");
    207209                Iterator<Node> it = nodes.iterator();
    208210                while(it.hasNext()) {
    209211                        Node u = it.next();
    210                         out = out + u + ",";
    211                 }
    212                 out = out + "]";
    213                 return out;
     212                        out.append(u.toString() + ",");
     213                }
     214                out.setLength(out.length() - 1);
     215                out.append("]");
     216                return out.toString();
    214217        }
    215218       
  • src/main/java/weka/clusterers/forMetisMQI/util/Util.java

    r14 r15  
    9191                vv.getRenderContext().setVertexLabelTransformer(new ToStringLabeller<Node>());
    9292                vv.getRenderContext().setEdgeLabelTransformer(new ToStringLabeller<Edge>());
    93 
     93                JFrame frame = new JFrame("Simple Graph View");
     94                frame.setDefaultCloseOperation(JFrame.EXIT_ON_CLOSE);
     95                frame.getContentPane().add(vv);
     96                frame.pack();
     97                frame.setVisible(true);
     98        }
     99       
     100        public static void viewFlowGraph(Graph<Node, Edge> g, Map<Edge, Number> edgeFlowMap){
     101                class EdgeTransformer implements Transformer<Edge,String> {
     102                        Map<Edge,Number> edgeFlowMap = null;
     103                        public String transform(Edge edge){
     104                                return edgeFlowMap.get(edge) + "/" + edge.getCapacity();
     105                        }
     106                        public EdgeTransformer(Map<Edge,Number> edgeFlowMap) {
     107                                this.edgeFlowMap = edgeFlowMap;
     108                        }
     109                }
     110                Layout<Node, Edge> layout = new FRLayout<Node, Edge>(g);
     111                layout.setSize(new Dimension(800,600)); // sets the initial size of the space
     112                // The BasicVisualizationServer<V,E> is parameterized by the edge types
     113                BasicVisualizationServer<Node,Edge> vv =
     114                new BasicVisualizationServer<Node,Edge>(layout);
     115                vv.setPreferredSize(new Dimension(800,600)); //Sets the viewing area size
     116                vv.getRenderContext().setVertexLabelTransformer(new ToStringLabeller<Node>());
     117                vv.getRenderContext().setEdgeLabelTransformer(new EdgeTransformer(edgeFlowMap));
    94118                JFrame frame = new JFrame("Simple Graph View");
    95119                frame.setDefaultCloseOperation(JFrame.EXIT_ON_CLOSE);
Note: See TracChangeset for help on using the changeset viewer.