Coverage details for edu.uci.ics.jung.algorithms.transformation.FoldingTransformer

LineHitsSource
1 /*
2  * Copyright (c) 2003, the JUNG Project and the Regents of the University
3  * of California
4  * All rights reserved.
5  *
6  * This software is open-source under the BSD license; see either
7  * "license.txt" or
8  * http://jung.sourceforge.net/license.txt for a description.
9  */
10 /*
11  * Created on Apr 21, 2004
12  */
13 package edu.uci.ics.jung.algorithms.transformation;
14  
15 import java.util.HashMap;
16 import java.util.HashSet;
17 import java.util.Iterator;
18 import java.util.Map;
19 import java.util.Set;
20  
21 import org.apache.commons.collections.BidiMap;
22 import org.apache.commons.collections.Predicate;
23  
24 import edu.uci.ics.jung.graph.ArchetypeVertex;
25 import edu.uci.ics.jung.graph.Edge;
26 import edu.uci.ics.jung.graph.Element;
27 import edu.uci.ics.jung.graph.Graph;
28 import edu.uci.ics.jung.graph.Hypergraph;
29 import edu.uci.ics.jung.graph.KPartiteGraph;
30 import edu.uci.ics.jung.graph.Vertex;
31 import edu.uci.ics.jung.graph.decorators.NumberEdgeValue;
32 import edu.uci.ics.jung.graph.impl.DirectedSparseEdge;
33 import edu.uci.ics.jung.graph.impl.DirectedSparseGraph;
34 import edu.uci.ics.jung.graph.impl.UndirectedSparseEdge;
35 import edu.uci.ics.jung.graph.impl.UndirectedSparseGraph;
36 import edu.uci.ics.jung.utils.GraphUtils;
37 import edu.uci.ics.jung.utils.PredicateUtils;
38 import edu.uci.ics.jung.utils.TypedVertexGenerator;
39 import edu.uci.ics.jung.utils.UserData;
40 import edu.uci.ics.jung.utils.VertexGenerator;
41 import edu.uci.ics.jung.utils.UserDataContainer.CopyAction;
42  
43 /**
44  * A class for creating a "folded" graph based on a k-partite graph or a
45  * hypergraph.
46  *
47  * <p>A "folded" graph is derived from a k-partite graph by identifying
48  * a partition of vertices which will become the vertices of the new graph, copying
49  * these vertices into the new graph, and then connecting those vertices whose
50  * original analogues were connected indirectly through elements
51  * of other partitions. (See <code>fold(KPartiteGraph, Predicate, NumberEdgeValue)</code>
52  * for more details.)</p>
53  *
54  * <p>A "folded" graph is derived from a hypergraph by creating vertices based on
55  * either the vertices or the hyperedges of the original graph, and connecting
56  * vertices in the new graph if their corresponding vertices/hyperedges share a
57  * connection with a common hyperedge/vertex. (See <code>fold(Hypergraph,
58  * boolean, NumberEdgeValue)</code> for more details.)</p>
59  *
60  * @author Danyel Fisher
61  * @author Joshua O'Madadhain
62  */
63 public class FoldingTransformer
64 {
65     /**
66      * Used in <code>fold()</code> as a user data key to the data attached to
67      * the edges in the folded graph.
68      */
69     public static final String FOLDED_DATA = "edu.uci.ics.jung.graph.KPartiteFolder:Folded Data";
70  
71     protected boolean parallel;
722    protected CopyAction copy_action = UserData.REMOVE;
73     
74     /**
75      * Specifies whether the graph being folded is undirected or not.
76      * Set by <code>checkGraphConstraints</code>.
77      */
78     private boolean undirected;
79     
80     /**
81      * Creates an instance of this Folder. See the discussion of fold for notes
82      * on the "parallel" argument.
83      *
84      */
852    public FoldingTransformer(boolean parallel) {
862        this.parallel = parallel;
872    }
88  
89     /**
90      * Specifies whether the folded graphs create parallel edges or a decorated
91      * single edge.
92      * @param parallel
93      */
94     public void setParallel(boolean parallel) {
950        this.parallel = parallel;
960    }
97     
98     /**
99      * Specifies the copy action used to attach data to edges.
100      * @param copy_action
101      */
102     public void setCopyAction(CopyAction copy_action)
103     {
1040        this.copy_action = copy_action;
1050    }
106  
107     /**
108      * Equivalent to <code>fold(g, p, null)</code>.
109      */
110     public Graph fold(KPartiteGraph g, Predicate p)
111     {
1122        return fold(g, p, null);
113     }
114  
115     /**
116      * <p>
117      * Converts <code>g</code> into a unipartite graph whose vertex set is the
118      * vertices whose partition is specified by <code>p</code>. For vertices
119      * <code>a</code> and <code>b</code> in this partition, the resultant
120      * graph will include the edge <code>(a,b)</code> if the original graph
121      * contains edges <code>(a,c)</code> and <code>(c,b)</code> for at least
122      * one vertex <code>c</code>.
123      * </p>
124      *
125      * <p>
126      * If <code>parallel</code> is true, then each such connecting vertex
127      * <code>c</code> will be represented by a single edge in the resultant
128      * graph, and the resultant graph may therefore contain parallel edges.
129      * Otherwise, each edge <code>(a,b)</code> in the resultant graph will be
130      * annotated with the set of vertices <code>c</code> that connected
131      * <code>a</code> to <code>b</code> in the original graph, and the
132      * graph's edge requirements will be set to refuse parallel edges.
133      * </p>
134      *
135      * <p>In either case, if the original graph contains both a directed edge from
136      * <code>a</code> to <code>b</code>, and a directed edge from <code>b</code>
137      * <code>a</code>, then a self-loop will be created from <code>a</code>
138      * to itself in the folded graph. Undirected edges do not result in
139      * self-loops.
140      * </p>
141      *
142      * <p>
143      * If <code>g</code> is neither strictly directed nor strictly undirected,
144      * this method throws <code>IllegalArgumentException</code>. Parallel edges
145      * in the original graph have no effect on the resultant graph: only one edge
146      * <code>(a,c)</code> and one edge <code>(c,b)</code> are necessary to
147      * induce a connection between <code>a</code> and <code>b</code> in the folded
148      * graph, and any additional such edges are ignored.</p>
149      *
150      * <p>If <code>nev</code> is null,
151      * adds the connecting element as a decoration on the corresponding edge in the new
152      * graph; otherwise, sets the weight of each edge to the number of parallel
153      * paths between the corresponding vertices in the original graph that are
154      * encountered in the folding process.</p>
155      *
156      * @param g the graph to fold
157      * @param p the predicate which specifies the partition to fold into
158      * @return the folded graph
159      * @throws IllegalArgumentException
160      */
161     public Graph fold(KPartiteGraph g, Predicate p, NumberEdgeValue nev)
162     {
1632        checkGraphConstraints(g);
164  
1652        Graph newGraph = createGraph();
166  
167         // get vertices for the specified partition, copy into new graph
1682        Set vertices = PredicateUtils.getVertices(g, p);
1692        for (Iterator iter = vertices.iterator(); iter.hasNext();) {
1706            ArchetypeVertex v = (ArchetypeVertex) iter.next();
1716            v.copy(newGraph);
172         }
173  
1742        for (Iterator iter = vertices.iterator(); iter.hasNext();) {
1756            Vertex v = (Vertex) iter.next();
1766            Vertex v_new = (Vertex) v.getEqualVertex(newGraph);
1776            Set succs = v.getSuccessors();
178  
1796            for (Iterator s_iter = succs.iterator(); s_iter.hasNext();) {
18010                Vertex s = (Vertex) s_iter.next();
18110                Set s_succs = s.getSuccessors();
182  
18310                for (Iterator t_iter = s_succs.iterator(); t_iter.hasNext();) {
18413                    Vertex t = (Vertex) t_iter.next();
185  
186                     // if t is in the partition of interest
187                     // and has not been covered (undirected graphs only)
18813                    if (!vertices.contains(t)) continue;
189  
19013                    Vertex t_new = (Vertex) t.getEqualVertex(newGraph);
19113                    addEdge(newGraph, v_new, s, t_new, nev);
192  
193                 }
194             }
195         }
1962        return newGraph;
197     }
198  
199 // /**
200 // * Equivalent to <code>fold(h, use_vertices, null)</code>.
201 // */
202 // public Graph fold(Hypergraph h, boolean use_vertices)
203 // {
204 // return fold(h, use_vertices, null);
205 // }
206 //
207 // public Graph fold(Hypergraph h, boolean use_vertices, NumberEdgeValue nev)
208 // {
209 // return fold(h, null, use_vertices, nev, new BidirectionalHashMap());
210 // }
211     
212     /**
213      * Creates a <code>Graph</code> which is a "folded" version of <code>h</code>.
214      *
215      * <p>If <code>use_vertices</code> is true, the vertices of the new graph
216      * correspond to the vertices of <code>h</code>, and <code>a</code>
217      * is connected to <code>b</code> in the new graph if the corresponding vertices
218      * in <code>h</code> are connected by a hyperedge. Thus, each hyperedge with
219      * <i>k</i> vertices in <code>h</code> would induce a <i>k</i>-clique in the new graph.</p>
220      *
221      * <p>If <code>use_vertices</code> is false, then the vertices of the new
222      * graph correspond to the hyperedges of <code>h</code>, and <code>a</code>
223      * is connected to <code>b</code> in the new graph if the corresponding hyperedges
224      * in <code>h</code> share a vertex. Thus, each vertex connected to <i>k</i>
225      * hyperedges in <code>h</code> would induce a <i>k</i>-clique in the new graph.</p>
226      *
227      * <p>If <code>nev</code> is null,
228      * adds the connecting element as a decoration on the corresponding edge in the new
229      * graph; otherwise, sets the weight of each edge to the number of parallel
230      * paths between the corresponding vertices in the original graph that are
231      * encountered in the folding process.</p>
232      */
233     public Graph fold(Hypergraph h, Graph target, boolean use_vertices, NumberEdgeValue nev, BidiMap map)
234     {
2350        undirected = true;
236         
2370        if (target == null)
2380            target = createGraph();
239  
2400        VertexGenerator vg = GraphUtils.getVertexGenerator(target);
2410        if (vg == null)
2420            vg = new TypedVertexGenerator(target);
243         
2440        Map m = new HashMap();
245         Set vertices;
246         Set edges;
247         
248         // vertices and hyperedges are duals of one another; we can treat
249         // them equivalently for this purpose
2500        if (use_vertices)
251         {
2520            vertices = h.getVertices();
2530            edges = h.getEdges();
254         }
255         else
256         {
2570            vertices = h.getEdges();
2580            edges = h.getVertices();
259         }
260         
261         // create vertices:
262         // for each "vertex", create a new vertex and import user data
2630        for (Iterator iter = vertices.iterator(); iter.hasNext(); )
264         {
2650            Element av = (Element)iter.next();
2660            Vertex v = vg.create();
2670            v.importUserData(av);
2680            target.addVertex(v);
2690            m.put(av, v);
2700            map.put(v, av);
271         }
272         
273         // create edges:
274         // for each "hyperedge", create an edge between each incident vertex pair
2750        for (Iterator iter = edges.iterator(); iter.hasNext(); )
276         {
2770            Element he = (Element)iter.next();
2780            Set elts = he.getIncidentElements();
2790            Vertex[] v_array = new Vertex[elts.size()];
2800            int i = 0;
2810            for (Iterator e_iter = elts.iterator(); e_iter.hasNext(); )
2820                v_array[i++] = (Vertex)(m.get(e_iter.next()));
2830            for (i = 0; i < v_array.length; i++)
2840                for (int j = i + 1; j < v_array.length; j++)
2850                    addEdge(target, v_array[i], he, v_array[j], nev);
286         }
287         
2880        return target;
289     }
290  
291     
292     /**
293      * Creates a new edge from <code>firstEnd</code> to <code>secondEnd</code>
294      * in <code>newGraph</code>. Note that
295      * <code>firstEnd</code> and <code>secondEnd</code> are both parts of
296      * <code>newGraph</code>, while
297      * <code>intermediate</code> is part of the original graph. If <code>parallel</code> is set,
298      * adds a new edge from <code>firstEnd</code> to <code>secondEnd</code>.
299      * If <code>parallel</code> is not set, then (as appropriate) adds an edge
300      * or creates one from <code>firstEnd</code> to <code>secondEnd</code>.
301      */
302     protected void addEdge(Graph newGraph, Vertex firstEnd,
303             Element intermediate, Vertex secondEnd, NumberEdgeValue nev)
304     {
30513        if( undirected && firstEnd == secondEnd ) return;
3068        if (parallel) {
307             Edge v_t;
3084            if (undirected)
3090                v_t = new UndirectedSparseEdge(firstEnd, secondEnd);
310             else
3114                v_t = new DirectedSparseEdge(firstEnd, secondEnd);
3124            if (nev != null)
3130                nev.setNumber(v_t, new Integer(1));
314             else
3154                v_t.addUserDatum(FOLDED_DATA, intermediate, copy_action);
3164            newGraph.addEdge(v_t);
317         } else {
3184            Edge v_t = firstEnd.findEdge(secondEnd);
3194            if (v_t == null) {
3201                if (undirected)
3211                    v_t = new UndirectedSparseEdge(firstEnd, secondEnd);
322                 else
3230                    v_t = new DirectedSparseEdge(firstEnd, secondEnd);
3241                if (nev != null)
3250                    nev.setNumber(v_t, new Integer(0));
326                 else
3271                    v_t.addUserDatum(FOLDED_DATA, new HashSet(), copy_action);
3281                newGraph.addEdge(v_t);
329             }
3304            if (nev != null)
3310                nev.setNumber(v_t, new Integer(nev.getNumber(v_t).intValue() + 1));
332             else
333             {
3344                Set folded_vertices = (Set) v_t.getUserDatum(FOLDED_DATA);
3354                folded_vertices.add(intermediate);
336             }
337         }
3388    }
339  
340     /**
341      * Returns a base graph to use.
342      */
343     protected Graph createGraph()
344     {
345         Graph newGraph;
3462        if (undirected)
3471            newGraph = new UndirectedSparseGraph();
348         else
3491            newGraph = new DirectedSparseGraph();
350         
3512        if (parallel)
3521            newGraph.getEdgeConstraints().remove(Graph.NOT_PARALLEL_EDGE);
353  
3542        return newGraph;
355     }
356  
357     /**
358      * Checks for, and rejects, mixed-mode graphs, and sets the <code>undirected</code>
359      * class variable state.
360      */
361     protected void checkGraphConstraints(KPartiteGraph g) {
3622        undirected = PredicateUtils.enforcesUndirected(g);
3632        if (!undirected && !PredicateUtils.enforcesDirected(g))
3640                throw new IllegalArgumentException(
365                         "Graph must be strictly "
366                                 + "directed or strictly undirected (no mixed graphs allowed)");
3672    }
368  
369 }

this report was generated by version 1.0.5 of jcoverage.
visit www.jcoverage.com for updates.

copyright © 2003, jcoverage ltd. all rights reserved.
Java is a trademark of Sun Microsystems, Inc. in the United States and other countries.