CycleNode.java

/*-
 *  Copyright 2020 Beuth Hochschule für Technik Berlin, Hochschule für Technik Stuttgart
 * 
 *  This file is part of CityDoctor2.
 *
 *  CityDoctor2 is free software: you can redistribute it and/or modify
 *  it under the terms of the GNU Lesser General Public License as published by
 *  the Free Software Foundation, either version 3 of the License, or
 *  (at your option) any later version.
 *
 *  CityDoctor2 is distributed in the hope that it will be useful,
 *  but WITHOUT ANY WARRANTY; without even the implied warranty of
 *  MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
 *  GNU Lesser General Public License for more details.
 *
 *  You should have received a copy of the GNU Lesser General Public License
 *  along with CityDoctor2.  If not, see <https://www.gnu.org/licenses/>.
 */
package de.hft.stuttgart.citydoctor2.math.graph;

import java.util.ArrayList;
import java.util.Deque;
import java.util.HashSet;
import java.util.LinkedList;
import java.util.List;
import java.util.Set;
import java.util.concurrent.atomic.AtomicInteger;

import de.hft.stuttgart.citydoctor2.datastructure.LinearRing;

/**
 * A node in the cycle graph
 * 
 * @author Matthias Betz
 *
 */
public class CycleNode {

	private final LinearRing value;

	private int index = -1;
	private int lowlink = 0;
	boolean onStack = false;

	private boolean visited = false;

	private Set<CycleNode> children;

	public CycleNode(LinearRing value) {
		children = new HashSet<>();
		this.value = value;
	}

	public Set<CycleNode> getChildren() {
		return children;
	}

	public LinearRing getValue() {
		return value;
	}

	public boolean addChild(CycleNode node) {
		return children.add(node);
	}

	int getIndex() {
		return index;
	}

	void collectNodes(Set<CycleNode> nodes) {
		if (nodes.add(this)) {
			for (CycleNode node : children) {
				node.collectNodes(nodes);
			}
		}
	}

	void strongConnect(Deque<CycleNode> s, AtomicInteger counter, List<List<LinearRing>> components) {
		index = counter.get();
		lowlink = counter.getAndIncrement();
		s.push(this);
		onStack = true;

		for (CycleNode node : children) {
			if (node.index == -1) {
				node.strongConnect(s, counter, components);
				lowlink = Math.min(lowlink, node.lowlink);
			} else if (node.onStack) {
				lowlink = Math.min(lowlink, node.index);
			}
		}

		if (lowlink == index) {
			List<LinearRing> comps = new LinkedList<>();
			CycleNode w = null;
			do {
				w = s.pop();
				w.onStack = false;
				comps.add(w.getValue());
			} while (this != w);
			components.add(comps);
		}
	}

	public boolean containsChild(CycleNode node) {
		return children.contains(node);
	}

	public int countEdges(CycleNode parent) {
		int edgeCount = 1;
		visited = true;
		for (CycleNode node : children) {
			if (!node.visited && node != parent) {
				edgeCount += node.countEdges(this);
			}
		}
		return edgeCount;
	}

	public void resetVisit() {
		visited = false;
		for (CycleNode node : children) {
			if (node.visited) {
				node.resetVisit();
			}
		}
	}

	public boolean hasMoreThan2CycleDepth(CycleNode parent) {
		visited = true;
		boolean result = false;
		for (CycleNode node : children) {
			if (node.visited && node != parent) {
				return true;
			} else if (!node.visited) {
				result = result || node.hasMoreThan2CycleDepth(this);
			}
		}
		return result;
	}

	public List<LinearRing> getConnectedRings() {
		List<LinearRing> result = new ArrayList<>();
		getConnectedRings(result);
		return result;
	}

	private void getConnectedRings(List<LinearRing> rings) {
		visited = true;
		rings.add(value);
		for (CycleNode node : children) {
			if (!node.visited) {
				node.getConnectedRings(rings);
			}
		}
	}

}