bcds.phison.clustering
Class GraphCondenser<V,E>

java.lang.Object
  bcds.phison.clustering.GraphCondenser<V,E>

public class GraphCondenser<V,E>
extends java.lang.Object

Given a directed graph and a clustering of its nodes, produces a new graph in which clusters are represented by a single node. To represent a given cluster in the new graph, a node of the original graph belonging to that cluster is arbitrarily chosen (that is, no new object nodes are created).

New edge objects are created to interconnect the clusters. For edge instantiation, the original graph's edge factory is used (getEdgeFactory is called).

In the original graph there can exist several links between a given pair of clusters, but in the condensed graph only one link is created. The edges of the original graph between two clusters can be retrieved by calling outgoingEdges.

Author:

Juan Segovia S.

Field Summary

SimGraph<V,E>

g A reference to the graph to be condensed.

Constructor Summary

GraphCondenser(SimGraph<V,E> g, java.util.Map<java.lang.Integer,java.util.List<V>> clusters)
Creates a new instance.

Method Summary

V	getSuperNode(int cluster_id) Returns the node that has been chosen as "representative" of a given cluster (cluster_id).
java.util.List<E>	outgoingEdges(int from, int to) Returns the ougtgoing edges present in the original graph corresponding to border nodes in the cluster from, going to border nodes in the cluster to.
SimGraph<V,E>	run() Performs the graph condensing and returns the new graph of clusters.

Methods inherited from class java.lang.Object

clone, equals, finalize, getClass, hashCode, notify, notifyAll, toString, wait, wait, wait

Field Detail

g

public final SimGraph<V,E> g

A reference to the graph to be condensed.

Constructor Detail

GraphCondenser

public GraphCondenser(SimGraph<V,E> g,
                      java.util.Map<java.lang.Integer,java.util.List<V>> clusters)

Creates a new instance. Nodes in the graph g as grouped as specified in clusters. All clusters must be are node-disjoint (each node can only appear in one cluster).

Method Detail

getSuperNode

public V getSuperNode(int cluster_id)

Returns the node that has been chosen as "representative" of a given cluster (cluster_id).

outgoingEdges

public java.util.List<E> outgoingEdges(int from,
                                       int to)

Returns the ougtgoing edges present in the original graph corresponding to border nodes in the cluster from, going to border nodes in the cluster to. NOTE that the edges returned are the ones of the original graph.

run

public SimGraph<V,E> run()

Performs the graph condensing and returns the new graph of clusters.