graph.java

图像检索的代码b

package at.lux.fotoretrieval.lucene;

import java.util.*;
import java.text.DecimalFormat;

/*
 * This file is part of Caliph & Emir.
 *
 * Caliph & Emir is free software; you can redistribute it and/or modify
 * it under the terms of the GNU General Public License as published by
 * the Free Software Foundation; either version 2 of the License, or
 * (at your option) any later version.
 *
 * Caliph & Emir is distributed in the hope that it will be useful,
 * but WITHOUT ANY WARRANTY; without even the implied warranty of
 * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
 * GNU General Public License for more details.
 *
 * You should have received a copy of the GNU General Public License
 * along with Caliph & Emir; if not, write to the Free Software
 * Foundation, Inc., 59 Temple Place, Suite 330, Boston, MA  02111-1307  USA
 *
 * Copyright statement:
 * --------------------
 * (c) 2002-2004 by Mathias Lux ([e-mail]) and the Know-Center Graz
 * Inffeldgasse 21a, 8010 Graz, Austria
 * http://www.know-center.at
 */

/**
 * Date: 01.11.2004
 * Time: 11:56:22
 *
 * @author Mathias Lux, [e-mail]
 */
public class Graph implements Comparable {
    LinkedList<Node> nodes;
    LinkedList<Relation> relations;

    public Graph(List<Node> nodes, List<Relation> relations) {
        this.nodes = new LinkedList<Node>();
        this.relations = new LinkedList<Relation>();
        this.nodes.addAll(nodes);
        this.relations.addAll(relations);
    }

    /**
     * Creates a graph from its String representation
     *
     * @param graph as String like output from toString method
     */
    public Graph(String graph) {
        StringTokenizer st = new StringTokenizer(graph);
        this.nodes = new LinkedList<Node>();
        this.relations = new LinkedList<Relation>();
        Relation currentRelation = null;
        boolean nodesFinished = false;
        while (st.hasMoreTokens()) {
            String s = st.nextToken();
            try {
                int node = Integer.parseInt(s);
                if (!nodesFinished) {
                    nodes.add(new Node(node));
                } else if (currentRelation != null) {
                    if (currentRelation.getSource() < 0) {
                        currentRelation.setSource(node);
                    } else if (currentRelation.getTarget() < 0) {
                        currentRelation.setTarget(node);
                        relations.add(currentRelation);
                        currentRelation = null;
                    }
                } else {
                    System.err.println("Error parsing!");
                }
            } catch (NumberFormatException e) {
                nodesFinished = true;
                currentRelation = new Relation(-1, -1, s);
            }
        }
    }

    /**
     * Returns the power set of all possible subgraphs
     *
     * @return
     */
    public List<Graph> getPowerSet() {
        List<Graph> pws1 = getPowerSetOfNodes();
        List<Graph> resultList = new LinkedList<Graph>();
        for (Iterator<Graph> iterator = pws1.iterator(); iterator.hasNext();) {
            Graph graph =  iterator.next();
            resultList.addAll(graph.getPowerSetOfRelations());
        }

        // remove redundant entries:
        Collections.sort(resultList);
        Graph lastGraph = null;
        List<Graph> newResultList = new LinkedList<Graph>();
        for (Iterator<Graph> iterator = resultList.iterator(); iterator.hasNext();) {
            Graph graph = iterator.next();
            if (lastGraph != null && !graph.toString().equals(lastGraph.toString())) {
                newResultList.add(graph);
            }
            lastGraph = graph;
        }
        return resultList;
    }

    /**
     * Returns the power set of all possible subgraphs only taking the nodes into account
     *
     * @return
     */
    public List<Graph> getPowerSetOfNodes() {
        if (nodes.size() > 1) {
            LinkedList<Graph> powerSet = new LinkedList<Graph>();

            LinkedList<Node> nodeList = new LinkedList<Node>();
            LinkedList<Relation> relationList = new LinkedList<Relation>();
            LinkedList<Relation> removedRelationList = new LinkedList<Relation>();
            nodeList.addAll(nodes);
            Node first = nodeList.removeFirst();

            for (Iterator<Relation> iterator = relations.iterator(); iterator.hasNext();) {
                Relation relation = iterator.next();
                if (!relation.isSourceOrTarget(first.getNodeID())) {
                    relationList.add(relation);
                } else {
                    removedRelationList.add(relation);
                }
            }

            Graph g = new Graph(nodeList, relationList);
            // add all available from the smaller graphs powerset:
            List<Graph> pwSet = g.getPowerSet();
            powerSet.addAll(pwSet);
            // add all from the smaller graphs powerset in union with removed node:
            for (Iterator<Graph> iterator = pwSet.iterator(); iterator.hasNext();) {
                Graph graph = iterator.next().clone();
                for (Iterator<Relation> iterator1 = removedRelationList.iterator(); iterator1.hasNext();) {
                    Relation relation = iterator1.next();
                    for (Iterator<Node> iterator2 = graph.getNodes().iterator(); iterator2.hasNext();) {
                        Node node = iterator2.next();
                        if (relation.isSourceOrTarget(node.getNodeID()) ) {
                            if (!graph.getRelations().contains(relation)) {
                                graph.getRelations().add(relation);
                            } else {
//                                System.out.println("Oops! Relation was already there!");
                            }
                        }
                    }
                }
                // check if the node is not already inside :)
                boolean doNotAdd = false;
                for (Iterator<Node> iterator1 = graph.getNodes().iterator(); iterator1.hasNext();) {
                    Node node = iterator1.next();
                    if (node.getNodeID() == first.getNodeID()) {
                        doNotAdd = true;
//                        System.out.println("Oops!");
                    }
                }
                // add it if not already there
                if (!doNotAdd) {
                    graph.getNodes().add(first);
                }
                powerSet.add(graph);
            }
            return powerSet;
        } else {
            // if there is only one element:
            LinkedList<Node> nodeList = new LinkedList<Node>();
            nodeList.addAll(nodes);
            Graph gr = new Graph(nodes, new LinkedList<Relation>());
            LinkedList<Graph> graphs = new LinkedList<Graph>();
            // Graph with one element
            graphs.add(gr);
            // empty graph:
            graphs.add(new Graph(new LinkedList<Node>(), new LinkedList<Relation>()));
            return graphs;
        }
    }

    /**
     * Returns the power set taking relations into account
     *
     * @return
     */
    public List<Graph> getPowerSetOfRelations() {
        if (relations.size() > 1) {
            LinkedList<Relation> rels = new LinkedList<Relation>(relations);
            Relation firstRel = rels.removeFirst();
            Graph g = new Graph(nodes, rels);

            List<Graph> tmpResults = g.getPowerSetOfRelations();
            LinkedList<Graph> results = new LinkedList<Graph>();
            for (Iterator<Graph> iterator = tmpResults.iterator(); iterator.hasNext();) {
                Graph graph = iterator.next();
                results.add(graph);
                LinkedList<Relation> tmp = new LinkedList<Relation>(graph.getRelations());
                tmp.add(firstRel);
                results.add(new Graph(graph.nodes, tmp));
            }
            return results;
        } else {
            LinkedList<Graph> result = new LinkedList<Graph>();
            if (relations.size() > 0) {
                // there is one single relation:
                // creating a graph without relation
                Graph g1 = new Graph(nodes, new LinkedList<Relation>());
                // adding the one with one relation
                result.add(this);
                // adding the one with zero relations
                result.add(g1);
            } else {
                result.add(this);
            }
            return result;
        }
    }

    public List<Node> getNodes() {
        return nodes;
    }

    public List<Relation> getRelations() {
        return relations;
    }

    public Graph clone() {
        LinkedList<Node> nList = new LinkedList<Node>();
        LinkedList<Relation> rList = new LinkedList<Relation>();
        for (Iterator<Node> iterator = nodes.iterator(); iterator.hasNext();) {
            nList.add(iterator.next().clone());
        }
        for (Iterator<Relation> iterator = relations.iterator(); iterator.hasNext();) {
            rList.add(iterator.next().clone());
        }
        return new Graph(nList, rList);
    }

    /**
     * Creates a String representations from a Graph
     *
     * @return
     */
    public String toString() {
        DecimalFormat df = (DecimalFormat) DecimalFormat.getInstance();
        df.setMinimumIntegerDigits(5);
        df.setMaximumFractionDigits(0);
        df.setGroupingUsed(false);
        StringBuilder sb = new StringBuilder(64);
        Collections.sort(nodes);
        Collections.sort(relations);
        for (Iterator<Node> iterator = nodes.iterator(); iterator.hasNext();) {
            Node n = iterator.next();
            sb.append(df.format(n.getNodeID()) + " ");
        }
        for (Iterator<Relation> iterator = relations.iterator(); iterator.hasNext();) {
            Relation relation = iterator.next();
            sb.append(relation.toString() + " ");
        }
        return sb.toString().trim();
    }

    /**
     * Returns true if the graph contains the same relations and nodes,
     * that is when the string representation is euqal.
     *
     * @param o
     * @return
     */
    public boolean equals(Object o) {
        if (o instanceof Graph) {
            Graph g = (Graph) o;
            if (g.toString().equals(toString())) {
                return true;
            } else {
                return false;
            }
        } else {
            return false;
        }
    }

    public float getSimilarity(Graph g) {
        float similarity = 1f;
        boolean matched = false;
        for (Iterator<Node> iterator = nodes.iterator(); iterator.hasNext();) {
            Node node = iterator.next();
            for (Iterator<Node> iterator1 = g.getNodes().iterator(); iterator1.hasNext();) {
                Node n = iterator1.next();
                if (node.equals(n)) {
                    similarity = similarity * node.getWeight() * n.getWeight();
                    matched = true;
                }
            }
        }
        if (!matched) similarity = 0f;
        else {
            float thisSize = (float) (nodes.size() + relations.size());
            float gSize = (float) (g.getNodes().size() + g.getRelations().size());
            similarity = similarity * (Math.min(thisSize, gSize)/Math.max(thisSize, gSize));
        }
        return similarity;
    }

    public int compareTo(Object o) {
        return toString().compareTo(((Graph) o).toString());
    }
}