public class FoldingTransformer
extends java.lang.Object
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.)
Modifier and Type | Field and Description |
---|---|
protected UserDataContainer.CopyAction |
copy_action |
static java.lang.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 and Description |
---|
FoldingTransformer(boolean parallel)
Creates an instance of this Folder.
|
Modifier and Type | Method and Description |
---|---|
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,
org.apache.commons.collections.BidiMap map)
Creates a
Graph which is a "folded" version of h . |
Graph |
fold(KPartiteGraph g,
org.apache.commons.collections.Predicate p)
Equivalent to
fold(g, p, null) . |
Graph |
fold(KPartiteGraph g,
org.apache.commons.collections.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.
|
public static final java.lang.String FOLDED_DATA
fold()
as a user data key to the data attached to
the edges in the folded graph.protected boolean parallel
protected UserDataContainer.CopyAction copy_action
public FoldingTransformer(boolean parallel)
public void setParallel(boolean parallel)
parallel
- public void setCopyAction(UserDataContainer.CopyAction copy_action)
copy_action
- public Graph fold(KPartiteGraph g, org.apache.commons.collections.Predicate p)
fold(g, p, null)
.public Graph fold(KPartiteGraph g, org.apache.commons.collections.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.
g
- the graph to foldp
- the predicate which specifies the partition to fold intojava.lang.IllegalArgumentException
public Graph fold(Hypergraph h, Graph target, boolean use_vertices, NumberEdgeValue nev, org.apache.commons.collections.BidiMap map)
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.
protected void addEdge(Graph newGraph, Vertex firstEnd, Element intermediate, Vertex secondEnd, NumberEdgeValue nev)
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
.protected Graph createGraph()
protected void checkGraphConstraints(KPartiteGraph g)
undirected
class variable state.