public class ConnectedComponents extends SinkAdapter implements DynamicAlgorithm, Iterable<ConnectedComponents.ConnectedComponent>
This algorithm computes the connected components for a given graph. Connected components are the set of its connected subgraphs. Two nodes belong to the same connected component when there exists a path (without considering the direction of the edges) between them. Therefore, the algorithm does not consider the direction of the edges. The number of connected components of an undirected graph is equal to the number of connected components of the same directed graph. See wikipedia for details.
This algorithm tries to handle the dynamics of the graph, trying not to recompute all from scratch at each change (kind of re-optimization). In this way, each instance of the algorithm is registered as a graph sink. Each change in the graph topology may affect the algorithm.
To start using the algorithm, you first need an instance of
Graph
, then you only have to instantiate the
algorithm class. Whether you specify a reference to the graph in the
constructor or you set it with the init(Graph)
method.
The computation of the algorithm starts only when the graph is specified with
the init(Graph)
method or with the appropriated constructor. In case
of a static graph, you may call the compute()
method. In case of a
dynamic graph, the algorithm will compute itself automatically when an event
(node or edge added or removed) occurs.
Finally you may ask the algorithm for the number of connected components at
any moment with a call to the getConnectedComponentsCount()
method.
import org.graphstream.algorithm.ConnectedComponents; import org.graphstream.graph.Graph; import org.graphstream.graph.implementations.DefaultGraph; public class CCTest { public static void main(String[] args) { Graph graph = new DefaultGraph("CC Test"); graph.addNode("A"); graph.addNode("B"); graph.addNode("C"); graph.addEdge("AB", "A", "B"); graph.addEdge("AC", "A", "C"); ConnectedComponents cc = new ConnectedComponents(); cc.init(graph); System.out.printf("%d connected component(s) in this graph, so far.%n", cc.getConnectedComponentsCount()); graph.removeEdge("AC"); System.out.printf("Eventually, there are %d.%n", cc .getConnectedComponentsCount()); } }
It is possible to get rid of connected components belong a size threshold
when counting the overall number of connected components. It is also possible
to define a ceiling size for the connected component. Above that size
ceiling, connected components will not be counted. Use the
getConnectedComponentsCount(int)
or
getConnectedComponentsCount(int, int)
methods.
You can tag each node with an integer that identifies the component it
pertains to using setCountAttribute(String)
. The argument of this
method is an arbitrary name that will be used as attribute on each node of
the graph. The value of this attribute will be an integer (counting from
zero) that is different for each connected component.
The getGiantComponent()
method gives you a list of nodes belonging
to the biggest connected component of the graph.
The cut attribute is a feature that can optionally simulate a given edge to
be invisible (as if the edge did not exist). In other words if an edge is
given such a cut attribute, it will be ignored by the algorithm when
counting. You can enable (or disable by passing null) the cut attribute by
specifying it with the setCutAttribute(String)
method, and by giving
the special edges the same attribute.
What is it useful for? Well you may want to simulate the removal of a given edge and see if it increases the number of connected components. You may not want to really remove and then re-add that edge in the graph, because such removal event may have consequences on other algorithms, viewer, writers...
Note that setting the cut attribute will trigger a new computation of the algorithm.
Modifier and Type | Class and Description |
---|---|
class |
ConnectedComponents.ConnectedComponent |
private static class |
ConnectedComponents.EdgeFilter |
Modifier and Type | Field and Description |
---|---|
protected FixedArrayList<ConnectedComponents.ConnectedComponent> |
components |
protected int |
connectedComponents
The number of connected components
|
private HashMap<Node,Integer> |
connectedComponentsMap
Map of connected components.
|
protected HashMap<Integer,Integer> |
connectedComponentsSize
Size of each connected component
|
protected String |
countAttribute
Optional attribute to set on each node of a given component.
|
protected String |
cutAttribute
Optional edge attribute that make it "invisible".
|
protected Graph |
graph
The Graph the algorithm is working on.
|
protected FixedArrayList<String> |
ids
Single IDs to identify the connected components.
|
protected boolean |
started
A token to decide whether or not the algorithm is started.
|
Constructor and Description |
---|
ConnectedComponents()
Construction of an instance with no parameter.
|
ConnectedComponents(Graph graph)
Constructor with the given graph.
|
Modifier and Type | Method and Description |
---|---|
protected int |
addIdentifier()
Allocate a new identifier for a connected component.
|
void |
compute()
Run the algorithm.
|
private int |
computeConnectedComponent(Node v,
int id,
Edge exception)
Goes recursively (depth first) into the connected component and assigns
each node an id.
|
void |
edgeAdded(String graphId,
long timeId,
String edgeId,
String fromNodeId,
String toNodeId,
boolean directed)
An edge was inserted in graph.
|
void |
edgeAttributeAdded(String graphId,
long timeId,
String edgeId,
String attribute,
Object value)
A edge attribute was added.
|
void |
edgeAttributeRemoved(String graphId,
long timeId,
String edgeId,
String attribute)
A edge attribute was removed.
|
void |
edgeRemoved(String graphId,
long timeId,
String edgeId)
An edge of graph was removed.The nodes the edge connects may already have
been removed from the graph.
|
int |
getConnectedComponentsCount()
Ask the algorithm for the number of connected components.
|
int |
getConnectedComponentsCount(int sizeThreshold)
Ask the algorithm for the number of connected components whose size is
equal to or greater than the specified threshold.
|
int |
getConnectedComponentsCount(int sizeThreshold,
int sizeCeiling)
Ask the algorithm for the number of connected components whose size is
equal to or greater than the specified threshold and lesser than the
specified ceiling.
|
List<Node> |
getGiantComponent()
Computes a list of nodes that belong to the biggest connected component.
|
void |
graphCleared(String graphId,
long timeId)
The whole graph was cleared.
|
void |
init(Graph graph)
Initialization of the algorithm.
|
Iterator<ConnectedComponents.ConnectedComponent> |
iterator() |
protected void |
markNode(Node node,
int id) |
void |
nodeAdded(String graphId,
long timeId,
String nodeId)
A node was inserted in the given graph.
|
void |
nodeRemoved(String graphId,
long timeId,
String nodeId)
A node was removed from the graph.
|
protected void |
remapMarks() |
protected void |
removeIdentifier(int identifier)
Remove a identifier that is no more used.
|
protected void |
removeMarks() |
void |
setCountAttribute(String countAttribute)
Enable (or disable by passing null for countAttribute) an optional
attribute that will be assigned to each node.
|
void |
setCutAttribute(String cutAttribute)
Enable (or disable by passing null) an optional attribute that makes
edges that have it invisible (as if the edge did not existed).
|
void |
terminate()
Terminate the dynamic algorithm.
|
edgeAttributeChanged, graphAttributeAdded, graphAttributeChanged, graphAttributeRemoved, nodeAttributeAdded, nodeAttributeChanged, nodeAttributeRemoved, stepBegins
clone, equals, finalize, getClass, hashCode, notify, notifyAll, toString, wait, wait, wait
forEach, spliterator
private HashMap<Node,Integer> connectedComponentsMap
protected int connectedComponents
protected HashMap<Integer,Integer> connectedComponentsSize
protected FixedArrayList<String> ids
protected FixedArrayList<ConnectedComponents.ConnectedComponent> components
protected boolean started
protected String cutAttribute
protected String countAttribute
public ConnectedComponents()
init(Graph)
method with a reference to
a graph so that the computation is able to start.
After the init(Graph)
method is invoked, the computation starts
as soon as and event is received or if the compute()
method is
invoked.public ConnectedComponents(Graph graph)
init(Graph)
method is invoked. This Constructor
will call the init(Graph)
method anyway.graph
- The graph who's connected components will be computed.public List<Node> getGiantComponent()
public int getConnectedComponentsCount()
public int getConnectedComponentsCount(int sizeThreshold)
sizeThreshold
- Minimum size for the connected component to be consideredpublic int getConnectedComponentsCount(int sizeThreshold, int sizeCeiling)
sizeThreshold
- Minimum size for the connected component to be consideredsizeCeiling
- Maximum size for the connected component to be considered (use
0 or lower values to ignore the ceiling)public Iterator<ConnectedComponents.ConnectedComponent> iterator()
iterator
in interface Iterable<ConnectedComponents.ConnectedComponent>
protected int addIdentifier()
protected void removeIdentifier(int identifier)
identifier
- The identifier to remove.public void setCutAttribute(String cutAttribute)
cutAttribute
- The name for the cut attribute or null if the cut attribute
option must be disabled.public void setCountAttribute(String countAttribute)
countAttribute
- The name of the attribute to put on each node (pass null to
disable this feature).protected void removeMarks()
protected void remapMarks()
public void init(Graph graph)
Algorithm
Algorithm.compute()
method to initialize or reset the algorithm according
to the new given graph.public void compute()
Algorithm
Algorithm.init(Graph)
method has to be called
before computing.compute
in interface Algorithm
Algorithm.init(Graph)
public void terminate()
DynamicAlgorithm
terminate
in interface DynamicAlgorithm
Algorithm.init(org.graphstream.graph.Graph)
private int computeConnectedComponent(Node v, int id, Edge exception)
v
- The considered node.id
- The id to assign to the given node.exception
- An optional edge that may not be considered (useful when
receiving a edgeRemoved(String, long, String)
event.public void edgeAdded(String graphId, long timeId, String edgeId, String fromNodeId, String toNodeId, boolean directed)
ElementSink
edgeAdded
in interface ElementSink
edgeAdded
in class SinkAdapter
graphId
- Identifier of the graph where the edge was added.edgeId
- Identifier of the added edge.fromNodeId
- Identifier of the first node of the edge.toNodeId
- Identifier of the second node of the edge.directed
- If true, the edge is directed.public void nodeAdded(String graphId, long timeId, String nodeId)
ElementSink
nodeAdded
in interface ElementSink
nodeAdded
in class SinkAdapter
graphId
- Identifier of the graph where the node was added.nodeId
- Identifier of the added node.public void edgeRemoved(String graphId, long timeId, String edgeId)
ElementSink
edgeRemoved
in interface ElementSink
edgeRemoved
in class SinkAdapter
graphId
- The graph where the edge will be removed.edgeId
- The edge that will be removed.public void nodeRemoved(String graphId, long timeId, String nodeId)
ElementSink
nodeRemoved
in interface ElementSink
nodeRemoved
in class SinkAdapter
graphId
- Identifier of the graph where the node will be removed.nodeId
- Identifier of the removed node.public void graphCleared(String graphId, long timeId)
ElementSink
graphCleared
in interface ElementSink
graphCleared
in class SinkAdapter
graphId
- The graph cleared.public void edgeAttributeAdded(String graphId, long timeId, String edgeId, String attribute, Object value)
AttributeSink
edgeAttributeAdded
in interface AttributeSink
edgeAttributeAdded
in class SinkAdapter
graphId
- Identifier of the graph where the change occurred.edgeId
- Identifier of the edge whose attribute changed.attribute
- The attribute name.value
- The attribute new value.public void edgeAttributeRemoved(String graphId, long timeId, String edgeId, String attribute)
AttributeSink
edgeAttributeRemoved
in interface AttributeSink
edgeAttributeRemoved
in class SinkAdapter
graphId
- Identifier of the graph where the attribute was removed.edgeId
- Identifier of the edge whose attribute was removed.attribute
- The removed attribute name.WebARTS Library Licensed Under the GNU - General Public License. Other Libraries licensed under their respective Open Source Licenses