Changeset 20 for src/main/java


Ignore:
Timestamp:
Sep 30, 2010, 5:33:45 PM (14 years ago)
Author:
gnappo
Message:

Aggiunto metodo per stampare i grafi in formato utile per kmetis; modificato politica di azione di mqi, ora agisce sulla partizione piu` grande.

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

Legend:

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

    r18 r20  
    8181         */
    8282        static public Set<Set<Node>> metisMqi(UndirectedGraph g, int numberOfCluster, int sizeFinerGraph) {
    83                 System.out.println("VERTEX: " + g.getVertexCount());
    84                 System.out.println("EDGE: " + g.getEdgeCount());
     83                System.out.println("Vertex count: " + g.getVertexCount());
     84                System.out.println("Edges count: " + g.getEdgeCount());
    8585                Iterator<Node> iNodes = g.getVertices().iterator();
    8686                int degreeCounter = 0;
     
    9595//              Util.viewGraph(g);
    9696                for (int i = 0; i < numberOfCluster; i++) {
    97                         Bisection partition = metis(g,sizeFinerGraph);
    98                         System.out.println("Partizione iniziale (Metis)");
    99 //                      System.out.println("Edge-cut: " + partition.edgeCut() / 2);
     97//                      Bisection partition = metis(g,sizeFinerGraph);
     98                        Bisection partition = new Bisection(g);
     99                        System.out.print("Partizione iniziale: ");
     100                        System.out.print("V1: " + partition.getSubgraph().getVertexCount());
     101                        System.out.print(" V2: " + partition.getComplement().getVertexCount());
     102                        System.out.println(" EC: " + partition.edgeCut() * 0.5);
    100103                        System.out.println("Conductance: " +
    101104                                        ((double)partition.edgeCut() / 2) / Math.min(partition.getSubgraph().totalDegree(),partition.getComplement().totalDegree()));
     
    107110                        Bisection mqiBisection = new Bisection(new Subgraph(g,cluster));
    108111                        System.out.println("Partizione raffinata (MQI)");
    109 //                      System.out.println("Edge-cut: " + mqiBisection.edgeCut() / 2);
    110112                        double newConductance = ((double)mqiBisection.edgeCut() / 2) / Math.min(mqiBisection.getSubgraph().totalDegree(),mqiBisection.getComplement().totalDegree());
    111113                        System.out.println("Conductance: " + newConductance);
     
    117119                        }
    118120                       
     121                        System.out.println();
    119122                        Iterator<Node> clustersNode = cluster.iterator();
    120123                        while(clustersNode.hasNext()){
  • src/main/java/weka/clusterers/forMetisMQI/MQI.java

    r18 r20  
    8181
    8282        static private DirectedGraph<Node, Edge> prepareDirectedGraph(
    83                         Bisection partition, Node source, Node sink, boolean forConductance) {
    84                 Subgraph A = null;
    85                 Subgraph B = null;
    86                 if (partition.getSubgraph().getVertexCount() < partition
    87                                 .getComplement().getVertexCount()) {
    88                         A = partition.getSubgraph();
    89                         B = partition.getComplement();
    90                 } else {
    91                         A = partition.getComplement();
    92                         B = partition.getSubgraph();
    93                 }
     83                        Bisection bisection, Node source, Node sink, boolean forConductance) {
     84                Subgraph A = bisection.getLargerSubgraph();
     85                Subgraph B = bisection.getSmallerSubgraph();
    9486                int a = 0;
    9587                if (!forConductance)
     
    9890                        Iterator<Node> aIterator = A.iterator();
    9991                        while(aIterator.hasNext()) {
    100                                 a += partition.getGraph().degree(aIterator.next());
    101                         }
    102                 }
    103                 int c = partition.edgeCut() / 2;
     92                                a += bisection.getGraph().degree(aIterator.next());
     93                        }
     94                }
     95                int c = bisection.edgeCut() / 2;
    10496
    10597                DirectedGraph<Node, Edge> g = new DirectedSparseGraph<Node, Edge>();
     
    109101                        g.addVertex(u);
    110102                }
    111 
    112103                nodes = A.iterator();
    113104                int id = 0;
     
    153144                        if(forConductance)
    154145                                //FIXME: CONTROLLAMI
    155                                 g.addEdge(new Edge(Integer.toString(id), 1, c * partition.getGraph().degree(u)), u, sink);
     146                                g.addEdge(new Edge(Integer.toString(id), 1, c * bisection.getGraph().degree(u)), u, sink);
    156147                        else
    157148                                g.addEdge(new Edge(Integer.toString(id), 1, c), u, sink);
     
    173164                boolean finished = false;
    174165                Bisection bisection = partition;
    175                 Set<Node> cluster = new HashSet<Node>(partition.getSmallerNotEmptySubgraph()
     166                Set<Node> cluster = new HashSet<Node>(partition.getLargerSubgraph()
    176167                                .createInducedSubgraph().getVertices());
    177168                int maxFlowThreshold = Integer.MAX_VALUE;
     
    200191
    201192                        if (!forConductance)
    202                                 maxFlowThreshold = bisection.getSmallerNotEmptySubgraph()
     193                                maxFlowThreshold = bisection.getLargerSubgraph()
    203194                                                .getVertexCount()
    204195                                                * bisection.edgeCut() / 2;
    205196                        else {
    206                                 Iterator<Node> aIterator = bisection.getSmallerNotEmptySubgraph().iterator();
     197                                Iterator<Node> aIterator = bisection.getLargerSubgraph().iterator();
    207198                                maxFlowThreshold = 0;
    208199                                while(aIterator.hasNext())
     
    212203                        }
    213204                        alg.evaluate();
    214 //                       Util.viewFlowGraph(directedGraph, edgeFlowMap);
    215 //                      System.out.println("MAX FLOW: " + alg.getMaxFlow() + " THRESHOLD: "
    216 //                                      + maxFlowThreshold);
     205//                      Util.viewFlowGraph(directedGraph, edgeFlowMap);
     206                        System.out.println("MAX FLOW: " + alg.getMaxFlow() + " THRESHOLD: "
     207                                        + maxFlowThreshold);
    217208                        if (alg.getMaxFlow() < maxFlowThreshold) {
    218209                                Set<Node> dfsResult = DFSReversed(sink, directedGraph,
    219210                                                edgeFlowMap, new HashSet<Node>());
    220211                                dfsResult.remove(sink);
    221 //                              if (dfsResult.size() > 0) {
    222                                         cluster = dfsResult;
    223                                         bisection = new Bisection(new Subgraph(
    224                                                         bisection.getGraph(), cluster));
    225 //                                      System.out
    226 //                                                      .println("NEW BISECTION: " + bisection.toString());
    227 //                              } else
    228 //                                      finished = true;
     212                                cluster = dfsResult;
     213                                bisection = new Bisection(new Subgraph(
     214                                        bisection.getGraph(), cluster));
    229215                        } else
    230216                                finished = true;
  • src/main/java/weka/clusterers/forMetisMQI/graph/Bisection.java

    r18 r20  
    139139        }
    140140       
     141        public Subgraph getLargerSubgraph() {
     142                if(a.getVertexCount() < b.getVertexCount())
     143                        return b;
     144                else
     145                        return a;
     146        }
     147       
    141148        /**
    142          * Returns the smaller not empty subgraph of this bisection, null otherwise.
     149         * Returns the smaller subgraph of this bisection, null otherwise.
    143150         * @return
    144151         */
    145         public Subgraph getSmallerNotEmptySubgraph() {
    146                 if(a.getVertexCount() > 0 && b.getVertexCount() == 0)
    147                         return a;
    148                 if(b.getVertexCount() > 0 && a.getVertexCount() == 0)
    149                         return b;
     152        public Subgraph getSmallerSubgraph() {
    150153                if(a.getVertexCount() < b.getVertexCount())
    151154                        return a;
  • src/main/java/weka/clusterers/forMetisMQI/graph/UndirectedGraph.java

    r17 r20  
    11package weka.clusterers.forMetisMQI.graph;
    22
     3import java.io.PrintStream;
    34import java.util.ArrayList;
    45import java.util.Collection;
     6import java.util.HashMap;
    57import java.util.Iterator;
    68import java.util.List;
     9import java.util.TreeMap;
    710
    811import weka.clusterers.forMetisMQI.Random;
     
    109112        }
    110113       
     114        public void printForMetis(PrintStream output) {
     115                TreeMap<Integer,Node> map = new TreeMap<Integer,Node>();
     116                HashMap<Node,Integer> reverseMap = new HashMap<Node,Integer>();
     117                Iterator<Node> nodesIterator = getVertices().iterator();
     118                int id = 1;
     119                while(nodesIterator.hasNext()) {
     120                        Node node = nodesIterator.next();
     121                        map.put(id, node);
     122                        reverseMap.put(node,id);
     123                        id++;
     124                }
     125                output.println(getVertexCount() + " "+ getEdgeCount());
     126                Iterator<Integer> mappedIterator = map.keySet().iterator();
     127                while(mappedIterator.hasNext()) {
     128                        id = mappedIterator.next();
     129                        Iterator<Node> neighbors = getNeighbors(map.get(id)).iterator();
     130                        while(neighbors.hasNext()){
     131                                output.print(reverseMap.get(neighbors.next()));
     132                                if(neighbors.hasNext()) output.print(" ");
     133                        }
     134                        output.println();
     135                }
     136        }
     137       
    111138        public String toString() {
    112139                StringBuffer sb = new StringBuffer("Vertices:");
Note: See TracChangeset for help on using the changeset viewer.