edu.uci.ics.jung.algorithms.transformation
Class FoldingTransformer

java.lang.Object
  extended by edu.uci.ics.jung.algorithms.transformation.FoldingTransformer

public class FoldingTransformer
extends Object

A class for creating a "folded" graph based on a k-partite graph or a hypergraph.

A "folded" graph is derived from a k-partite graph by identifying a partition of vertices which will become the vertices of the new graph, copying these vertices into the new graph, and then connecting those vertices whose original analogues were connected indirectly through elements of other partitions. (See fold(KPartiteGraph, Predicate, NumberEdgeValue) for more details.)

A "folded" graph is derived from a hypergraph by creating vertices based on either the vertices or the hyperedges of the original graph, and connecting vertices in the new graph if their corresponding vertices/hyperedges share a connection with a common hyperedge/vertex. (See fold(Hypergraph, boolean, NumberEdgeValue) for more details.)

Author:
Danyel Fisher, Joshua O'Madadhain

Field Summary
protected  UserDataContainer.CopyAction copy_action
           
static String FOLDED_DATA
          Used in fold() as a user data key to the data attached to the edges in the folded graph.
protected  boolean parallel
           
 
Constructor Summary
FoldingTransformer(boolean parallel)
          Creates an instance of this Folder.
 
Method Summary
protected  void addEdge(Graph newGraph, Vertex firstEnd, Element intermediate, Vertex secondEnd, NumberEdgeValue nev)
          Creates a new edge from firstEnd to secondEnd in newGraph.
protected  void checkGraphConstraints(KPartiteGraph g)
          Checks for, and rejects, mixed-mode graphs, and sets the undirected class variable state.
protected  Graph createGraph()
          Returns a base graph to use.
 Graph fold(Hypergraph h, Graph target, boolean use_vertices, NumberEdgeValue nev, BidiMap map)
          Creates a Graph which is a "folded" version of h.
 Graph fold(KPartiteGraph g, Predicate p)
          Equivalent to fold(g, p, null).
 Graph fold(KPartiteGraph g, Predicate p, NumberEdgeValue nev)
           Converts g into a unipartite graph whose vertex set is the vertices whose partition is specified by p.
 void setCopyAction(UserDataContainer.CopyAction copy_action)
          Specifies the copy action used to attach data to edges.
 void setParallel(boolean parallel)
          Specifies whether the folded graphs create parallel edges or a decorated single edge.
 
Methods inherited from class java.lang.Object
clone, equals, finalize, getClass, hashCode, notify, notifyAll, toString, wait, wait, wait
 

Field Detail

FOLDED_DATA

public static final String FOLDED_DATA
Used in fold() as a user data key to the data attached to the edges in the folded graph.

See Also:
Constant Field Values

parallel

protected boolean parallel

copy_action

protected UserDataContainer.CopyAction copy_action
Constructor Detail

FoldingTransformer

public FoldingTransformer(boolean parallel)
Creates an instance of this Folder. See the discussion of fold for notes on the "parallel" argument.

Method Detail

setParallel

public void setParallel(boolean parallel)
Specifies whether the folded graphs create parallel edges or a decorated single edge.

Parameters:
parallel -

setCopyAction

public void setCopyAction(UserDataContainer.CopyAction copy_action)
Specifies the copy action used to attach data to edges.

Parameters:
copy_action -

fold

public Graph fold(KPartiteGraph g,
                  Predicate p)
Equivalent to fold(g, p, null).


fold

public Graph fold(KPartiteGraph g,
                  Predicate p,
                  NumberEdgeValue nev)

Converts g into a unipartite graph whose vertex set is the vertices whose partition is specified by p. For vertices a and b in this partition, the resultant graph will include the edge (a,b) if the original graph contains edges (a,c) and (c,b) for at least one vertex c.

If parallel is true, then each such connecting vertex c will be represented by a single edge in the resultant graph, and the resultant graph may therefore contain parallel edges. Otherwise, each edge (a,b) in the resultant graph will be annotated with the set of vertices c that connected a to b in the original graph, and the graph's edge requirements will be set to refuse parallel edges.

In either case, if the original graph contains both a directed edge from a to b, and a directed edge from b a, then a self-loop will be created from a to itself in the folded graph. Undirected edges do not result in self-loops.

If g is neither strictly directed nor strictly undirected, this method throws IllegalArgumentException. Parallel edges in the original graph have no effect on the resultant graph: only one edge (a,c) and one edge (c,b) are necessary to induce a connection between a and b in the folded graph, and any additional such edges are ignored.

If nev is null, adds the connecting element as a decoration on the corresponding edge in the new graph; otherwise, sets the weight of each edge to the number of parallel paths between the corresponding vertices in the original graph that are encountered in the folding process.

Parameters:
g - the graph to fold
p - the predicate which specifies the partition to fold into
Returns:
the folded graph
Throws:
IllegalArgumentException

fold

public Graph fold(Hypergraph h,
                  Graph target,
                  boolean use_vertices,
                  NumberEdgeValue nev,
                  BidiMap map)
Creates a Graph which is a "folded" version of h.

If use_vertices is true, the vertices of the new graph correspond to the vertices of h, and a is connected to b in the new graph if the corresponding vertices in h are connected by a hyperedge. Thus, each hyperedge with k vertices in h would induce a k-clique in the new graph.

If use_vertices is false, then the vertices of the new graph correspond to the hyperedges of h, and a is connected to b in the new graph if the corresponding hyperedges in h share a vertex. Thus, each vertex connected to k hyperedges in h would induce a k-clique in the new graph.

If nev is null, adds the connecting element as a decoration on the corresponding edge in the new graph; otherwise, sets the weight of each edge to the number of parallel paths between the corresponding vertices in the original graph that are encountered in the folding process.


addEdge

protected void addEdge(Graph newGraph,
                       Vertex firstEnd,
                       Element intermediate,
                       Vertex secondEnd,
                       NumberEdgeValue nev)
Creates a new edge from firstEnd to secondEnd in newGraph. Note that firstEnd and secondEnd are both parts of newGraph, while intermediate is part of the original graph. If parallel is set, adds a new edge from firstEnd to secondEnd. If parallel is not set, then (as appropriate) adds an edge or creates one from firstEnd to secondEnd.


createGraph

protected Graph createGraph()
Returns a base graph to use.


checkGraphConstraints

protected void checkGraphConstraints(KPartiteGraph g)
Checks for, and rejects, mixed-mode graphs, and sets the undirected class variable state.