#174 FoldingTransformer breaks edge hash-keys

[Gert van Valkenhoef]

FoldingTransformer.foldHyperGraphEdges breaks finding of the edges in the edges HashMap, because it modifies edges (keys) after they have been added. The responsible code is in FoldingTransformer.populateTarget(), line 314-320:

Collection<T> e_coll = target.findEdge(v1, v2);
if (e_coll == null)
{
e_coll = new ArrayList<T>();
target.addEdge(e_coll, v1, v2);
}
e_coll.add(e);

This could be fixed e.g. by:

Collection<T> e_coll = target.findEdge(v1, v2);
if (e_coll == null)
{
e_coll = new ArrayList<T>();
}
else
{
target.removeEdge(e_coll);
}
e_coll.add(e);
target.addEdge(e_coll, v1, v2);

Unit test reproducing the bug is attached.

[Gert van Valkenhoef]

Failing unit test for FoldingTransformer

[Gert van Valkenhoef]

I'm sorry, I realize now that the code I posted as a possible fix won't work either. There is no guarantee that edges will be unique and the "fixed" code now highlights this error in logic -- something else is needed as the edge type, perhaps containing both a Pair<V> and a Collection<E>.

[Gert van Valkenhoef]

New proposal that actually works (but unfortunately requires an additional class). Small modifications to foldHypergraphEdges and foldHypergraphVertices as well as the unit test are required.

[code]
/**
* @param target
* @param e
* @param incident
*/
private static <S,T> void populateTarget(Graph<S, FoldedEdge<S, T>> target, T e,
ArrayList<S> incident)
{
for (int i = 0; i < incident.size(); i++)
{
S v1 = incident.get(i);
for (int j = i+1; j < incident.size(); j++)
{
S v2 = incident.get(j);
FoldedEdge<S, T> e_coll = target.findEdge(v1, v2);
if (e_coll == null)
{
e_coll = new FoldedEdge<S, T>(v1, v2);
target.addEdge(e_coll, v1, v2);
}
e_coll.getFolded().add(e);
}
}
}

/**
* An edge resulting from folding on a Hypergraph.
*/
public static class FoldedEdge<V, E> {
private Pair<V> d_vertices;
private Collection<E> d_folded;

/**
* The FoldedEdge is identified by it's pair of vertices, since the
* set of folded objects it corresponds to need not be unique.
*/
public FoldedEdge(V v1, V v2) {
d_vertices = new Pair<V>(v1, v2);
d_folded = new ArrayList<E>();
}

/**
* @return The vertices incident with this edge.
*/
public Pair<V> getVertices() {
return d_vertices;
}

/**
* @return The Collection of objects that were folded onto this edge.
*/
public Collection<E> getFolded() {
return d_folded;
}

@Override
public boolean equals(Object obj) {
if (obj instanceof FoldedEdge<?, ?>) {
FoldedEdge<?, ?> other = (FoldedEdge<?, ?>) obj;
return other.d_vertices.equals(d_vertices);
}
return false;
}

@Override
public int hashCode() {
return d_vertices.hashCode();
}
}
[/code]

[Gert van Valkenhoef]

By the way, could it happen that e.g. {A, B, C} and {A, B, D} map inconsistently? For example the first clique would include (A, B) and the second (B, A)? If these algorithms are producing undirected graphs (which I think they are?) why aren't the returned graphs explicitly undirected?

[Gert van Valkenhoef]

FoldingTransformer patch. Touches only Hypergraph related methods.

[Gert van Valkenhoef]

I attached a patch that uniquely identifies edges in the folded graph and forces the folded graph to be undirected (which appears to have been the assumption anyway).