documentationfor yFiles for HTML 2.6

Graph Analysis

One of the key features of yFiles is its collection of sophisticated algorithms for analyzing graph structures.

The following table gives an overview of the available analysis algorithms classes:

Analysis Algorithms grouped by topic
Topic Algorithm Description
CentralityBetweennessCentralityCalculates a centrality value for nodes and edges based on how many shortest paths in the graph run through it.
DegreeCentralityCalculates a centrality value for nodes based on the number of their incoming and/or outgoing edges.
WeightCentralityCalculates a centrality value for nodes based on the added weights of their incoming and/or outgoing edges.
ClosenessCentralityCalculates a centrality value for nodes based on their shortest path distances to all other nodes.
GraphCentralityCalculates a centrality value for nodes based on the longest of their shortest path distances to all other nodes.
EigenvectorCentralityCalculates a centrality value for nodes by means of a dominant eigenvector of the graph’s adjacency matrix.
PageRankCalculates a rank value for nodes based on the rank of their predecessors.
ClusteringBiconnectedComponentClusteringPartitions the graph into clusters that consist of biconnected components.
EdgeBetweennessClusteringPartitions the graph into a specified number of clusters that consist of components that are isolated after iteratively removing edges with the highest betweenness centrality.
HierarchicalClusteringPartitions the graph into a hierarchy of clusters. Clusters are combined in a parent cluster based on the distances between the nodes in the child clusters.
KMeansClusteringPartitions the graph into K clusters that consist of the nodes closest to the clusters mean (or centroid).
LouvainModularityClusteringDetects the communities/clusters in the graph by applying the louvain modularity method.
LabelPropagationClusteringDetects the communities/clusters in the graph by propagating virtual labels.
ConnectivityConnectedComponentsPartitions the graph into components that consist of nodes which are all connected by undirected paths.
BiconnectedComponentsPartitions the graph into components that consist of nodes which are all connected by undirected paths even if one of the nodes in a component would be removed.
StronglyConnectedComponentsPartitions the graph into components that consist of nodes which are all connected by directed paths.
BipartitionPartitions the graph into two partitions of nodes so that all edges connect nodes in the first partition with nodes in the second partition.
IndependentSetsPartitions the graph into independent sets that consist of nodes that are not connected to each other.
KCoreComponentsCalculates the subgraph components where each node has at least an user-specified degree.
Path-relatedShortestPathFinds the shortest path between two nodes.
PathsFinds all simple paths between multiple start and end nodes.
SingleSourceShortestPathsFinds the shortest paths between one start and multiple end nodes.
AllPairsShortestPathsFinds the shortest paths between multiple start and end nodes.
CycleFinds a cyclic path in the graph if one exists.
CycleEdgesFinds all edges that are part of at least one simple cycle in the graph.
ChainsFinds all maximal paths in the graph where each inner node has only two attached edges.
LongestPathFinds the longest directed path in an acyclic graph.
ReachabilityFinds all nodes that are reachable from one or more start nodes by a path.
Tree-relatedTreeAnalysisAnalyzes a tree graph and calculates important properties of the tree structure.
SpanningTreeFinds a subset of edges that induce a tree connecting all nodes.
FeedbackEdgeSetFinds a subset of edges whose removal or reversal would make the graph acyclic.
Network FlowsMaximumFlowFinds the maximum flow from source to sink nodes through a network of edges where each edge has a specified maximum flow capacity.
MinimumCostFlowFinds the cheapest possible way of sending a certain amount of flow through a network of edges where each edge has a specified maximum flow capacity and flow costs.
TransitivityTransitiveClosureFinds all node pairs that are connected by a path but not by a single edge.
TransitiveReductionFinds all edges that could be removed so that their source and target nodes are still connected by a path.
TransitiveEdgesCreates the transitive edges that connect the selected nodes of a graph.
StructuralGraphStructureAnalyzerProvides methods that check structural properties of the graph.
CliqueSubstructuresDetects the cliques of the graph. A clique is a subset of node that are all adjacent to each other.
TreeSubstructuresDetects the subtrees of the graph.
StarSubstructuresDetects the stars of the graph. A star consists of a node that is connected to multiple nodes with degree one.
CycleSubstructuresDetects the isolated cycles of the graph where a most one edge connects the cycle with the remaining graph.
ChainSubstructuresDetects the chains of the graph.
OtherNeighborhoodFinds all nodes whose paths to one or multiple start nodes has at most a given number of edges.
BfsProvides layers that consist of nodes whose shortest path to one or multiple start nodes have the same number of edges.
NodeAggregationAggregates the nodes of a given graph and creates a hierarchical clustering structure subject to user-specified constraints.
RankAssignmentSolves the rank assignment problem using the simplex method. This method assigns a minimum rank to the nodes in a acyclic graph.
IntersectionsFinds intersections and overlaps between nodes, edges and labels in a graph.

Strictly speaking the analysis classes with an IGraph-based API provide a convenient wrapping of the actual algorithm implementations which work on the basic algorithms graph structure. How to work directly with these core algorithms is described in Graph Analysis: The Algorithms Graph API.