*/
public boolean fuse() {
//create walker for first stage
// if the walker sees a node of degree 2 it adds it to the current
// set of nodes, else it starts a new set
m_walker = new GraphWalker() {
public int visit(Graphable element, GraphTraversal traversal) {
Node node = (Node)element;
//if the node is not of degree 2, start a new set
if (node.getDegree() != 2) {
finish();
}
else {
//add node to current set
m_nodes.add(node);
m_ndegree2--;
}
return(GraphTraversal.CONTINUE);
}
public void finish() {
//no need to recreate if empty
if (!m_nodes.isEmpty()) {
m_sets.add(m_nodes);
m_nodes = new ArrayList();
}
}
};
//perform a topological depth first traversal
m_traversal = new BasicGraphTraversal(
m_graph, m_walker, new DepthFirstTopologicalIterator()
);
//initialise set and node collections
m_sets = new ArrayList();
m_nodes = new ArrayList();
m_ndegree2 = m_graph.getNodesOfDegree(2).size();
if (m_ndegree2 == 0) return(true); // nothing to fuse
m_traversal.init();
//reset edge visited flags
m_graph.visitNodes(
new GraphVisitor() {
public int visit(Graphable component) {
component.setVisited(false);
return 0;
}
}
);
//perform the traversal
m_traversal.traverse();
//if all nodes of degree 2 have been visited, we are finished
if (m_ndegree2 > 0) {
//if there are still nodes of degree 2 that havent been visited, it means
// that the graph has a cycle and that the remaining degree 2 nodes are
// internal to the cycle, so the strategy for the second stage is to
// find all unvisited nodes of degree 2 that are not visited and start
// a no bifurcation traversal from them
Iterator sources = m_graph.queryNodes(
new GraphVisitor() {
public int visit(Graphable component) {
Node node = (Node)component;
if (!node.isVisited() && node.getDegree() == 2) {
//check for adjacent node of degree > 2
for (Iterator itr = node.getRelated(); itr.hasNext(); ) {
Node rel = (Node)itr.next();
if (rel.getDegree() > 2) return(Graph.PASS_AND_CONTINUE);
}
}
return(Graph.FAIL_QUERY);
}
}
).iterator();
//if the query returned no nodes, it means that all the cycle is
// disconnected from the rest of graph, so just pick any node of degree 2
if (!sources.hasNext()) {
sources = m_graph.queryNodes(
new GraphVisitor() {
public int visit(Graphable component) {
if (!component.isVisited()) return(Graph.PASS_AND_STOP);
return(Graph.FAIL_QUERY);
}
}
).iterator();
}
//create stage 2 walker, simple add any nodes visited nodes to the
// current node set
m_walker = new GraphWalker() {
public int visit(Graphable element, GraphTraversal traversal) {
m_ndegree2--;
m_nodes.add(element);
return(GraphTraversal.CONTINUE);
}