141 lines
4.2 KiB
Java
141 lines
4.2 KiB
Java
/*
|
|
* ConnectedComponentsPair.java 2005-05-12
|
|
*
|
|
* Dirk Ansorge, FernUniversitaet Hagen
|
|
*
|
|
*/
|
|
|
|
package twodsack.util.graph;
|
|
|
|
import twodsack.set.*;
|
|
import twodsack.setelement.*;
|
|
import twodsack.util.collection.*;
|
|
import twodsack.util.collectiontype.*;
|
|
import twodsack.util.comparator.*;
|
|
import java.util.*;
|
|
|
|
|
|
/**
|
|
* An instance of the ConnectedComponentsPair class represents the connected components of a graph. The graph itself is an instance of the
|
|
* {@link twodsack.util.graph} class. A ConnectedComponentsPair instance consists of two lists. The first list is a LinkedList named
|
|
* compVertices, which has as elements MultiSet(s) of vertices belonging to one connected component. The second list is a LinkedList with
|
|
* the name compEdges, which consists of MultiSet(s) of edges belonging to the connected components. Both lists have always the same length
|
|
* and they are somehow connected: If there is only one entry in compVertices' element0, compEdges element0 cannot have an entry. But, for
|
|
* two entries in comVertices' element1, compEdges' element1 must have exactly one entry.
|
|
*/
|
|
public class ConnectedComponentsPair {
|
|
/*
|
|
* fields
|
|
*/
|
|
/**
|
|
* The list of connected components represented only by vertices.
|
|
*/
|
|
public LinkedList compVertices;
|
|
/**
|
|
* The list of connected components represented only by edges.
|
|
*/
|
|
public LinkedList compEdges;
|
|
|
|
/*
|
|
* constructors
|
|
*/
|
|
/**
|
|
* Constructs an 'empty' instance.
|
|
* All fields are initialized to empty LinkedList(s).
|
|
*/
|
|
public ConnectedComponentsPair() {
|
|
this.compVertices = new LinkedList();
|
|
this.compEdges = new LinkedList();
|
|
}
|
|
|
|
|
|
/**
|
|
* Constructs a new instance using the passed LinkedList(s).
|
|
*
|
|
* @param v the list of MultiSets for connected components for vertices
|
|
* @param e the list of MultiSets for connected components for edges
|
|
*/
|
|
public ConnectedComponentsPair(LinkedList v, LinkedList e) {
|
|
this.compVertices = v;
|
|
this.compEdges = e;
|
|
}
|
|
|
|
|
|
/*
|
|
* methods
|
|
*/
|
|
/**
|
|
* Prints the data of <i>this</i> to standard output.
|
|
*/
|
|
public void print() {
|
|
System.out.println("\nconnected components");
|
|
System.out.println("vertices:");
|
|
for (int i = 0; i < compVertices.size(); i++) {
|
|
System.out.println("component "+i);
|
|
Iterator it = ((MultiSet)compVertices.get(i)).iterator();
|
|
while (it.hasNext())
|
|
((Vertex)((MultiSetEntry)it.next()).value).print();
|
|
}//for i
|
|
System.out.println("\nedges:");
|
|
for (int i = 0; i < compEdges.size(); i++) {
|
|
System.out.println("component "+i);
|
|
Iterator it = ((MultiSet)compEdges.get(i)).iterator();
|
|
while (it.hasNext())
|
|
((Edge)((MultiSetEntry)it.next()).value).print();
|
|
}//for i
|
|
}//print
|
|
|
|
|
|
/**
|
|
* Converts the list of MultiSet(s) for vertices to an ElemMultiSetList.
|
|
*
|
|
* @return the converted list
|
|
*/
|
|
public ElemMultiSetList verticesToEMSList() {
|
|
ListIterator lit1 = compVertices.listIterator(0);
|
|
Iterator lit2;
|
|
MultiSet actCC;
|
|
ElemMultiSet actEL;
|
|
ElemMultiSetList retList = new ElemMultiSetList();
|
|
|
|
while (lit1.hasNext()) {
|
|
actCC = (MultiSet)lit1.next();
|
|
lit2 = actCC.iterator();
|
|
actEL = new ElemMultiSet(new ElemComparator());
|
|
while (lit2.hasNext()) actEL.add(((Vertex)((MultiSetEntry)lit2.next()).value).value);
|
|
retList.add(actEL);
|
|
}//while
|
|
|
|
return retList;
|
|
}//end method verticesToEMSList
|
|
|
|
|
|
/**
|
|
* Converts the list of MultiSet(s) for edges to a PairMultiSetList.
|
|
*
|
|
* @return the converted list
|
|
*/
|
|
public PairMultiSetList edgesToPairListList() {
|
|
ListIterator lit1 = compEdges.listIterator(0);
|
|
Iterator lit2;
|
|
MultiSet actCC;
|
|
PairMultiSet actPL;
|
|
PairMultiSetList retList = new PairMultiSetList();
|
|
Edge actEdge;
|
|
|
|
while (lit1.hasNext()) {
|
|
actCC = (MultiSet)lit1.next();
|
|
lit2 = actCC.iterator();
|
|
actPL = new PairMultiSet(new ElemPairComparator());
|
|
while (lit2.hasNext()) {
|
|
actEdge = (Edge)((MultiSetEntry)lit2.next()).value;
|
|
actPL.add(new ElemPair((Element)actEdge.first.value,(Element)actEdge.second.value));
|
|
}//while
|
|
retList.add(actPL);
|
|
}//while
|
|
|
|
return retList;
|
|
}//end method edgesToPairListList
|
|
|
|
}//end class ConnectedComponentsPair
|