Graph Algorithms for Tulip Software
Tulip is an information visualization framework dedicated to the analysis and visualization of relational data. Tulip aims to provide the developer with a complete library, supporting the design of interactive information visualization applications for relational data that can be tailored to the problems he or she is addressing.
Find more info here.
This page contains Tulip plugins using Tulip API or Tulip Python API. They are implementation of well-known (or less-known) graph algorithms and network analysis methods.
Directory "TransportationNetworks" contains two transportation network construction algorithms.
- SPRouting: use iterative shortest-path routing of flow
- PhysariumSolver: use biologically inspired routing and edge length update.
The two algorithm only differ in the way flows are routed along the networks. For more details, check
Queyroi, F. (2018). Biological and Shortest-Path Routing Procedures for Transportation Network Design. arXiv preprint arXiv:1803.03528.
A plugin to enumerate all maximal cliques in the graph. It uses the algorithm of Eppstein et al. : vertices are ordered using their degeneracy value (the K-Cores plugin in Tulip) in order to speed up the enumeration.
Warning! This python plugin uses collections.OrderedDict. For python version prior to 2.7, you need to install the package: pip install ordereddict
An implementation of the Clique Percolation Method that finds an overlapping clustering of the graph. It does so by merging the k-cliques that share k-1 vertices (k is a parameter of the algorithm). We actually use the plugin CliqueEnum to find maximal cliques rather than enumerating all
A simple, fast and efficient graph clustering algorithm. For a weighted graph G=(V,E,w), it produces a partition of the vertices V.
The algorithm iteratively change vertices labels (that correspond to cluster). A vertex will take as label the label that occurs the most in its neighborhood. The algoithm will stop after a sufficient number of iterations.
For more details see:
Usha Nandini Raghavan, Réka Albert, and Soundar Kumara. Near linear time algorithm to detect community structures in large-scale networks. Physical Review E, 76(3) :036106, 2007.
and
Ian XY Leung, Pan Hui, Pietro Lìo, and Jon Crowcroft. Towards real-time community detection in large networks. Physical Review E, 79(6) :066107, 2009.
A variation of the famous K-Cores decomposition of the graph.
In the example, node labels corresponds to K-cores values and the hulls to the K-Peaks decomposition. The k-peak correspond to the maximal subgraph whose core value is k after the removal of nodes with a peak values above k. See for details
J. Abello and F. Queyroi (2014). Network decomposition into fixed points of degree peeling. Social Network Analysis and Mining, 4(1), 191.
Compute the Minimum Spanning Tree of the graph (Python script) using a Union-Find data structure.
Secret Santa is a way for people to exchange gifts but where each person only knows who he/she has to give a gift to. Traditionnaly Secret Santa assignments are done randomly: each participant pick the name of another participant.
But one can assume that not all assignments are possible. For example, one can want an assignment where parents can not be assigned to their own children or where colleagues in a company have to be assigned to people working in another department.
If we assume the the various possibilities are summed up in a graph G (an arc between A->B indicates that A can offer a gift to B) then the problem is to find a Vertex Cycle Cover of G. This problem can be solved using a maximum matching algorithm.
However, the Secret Santa has to be ... secret. Therefore, the Tulip Python plugin "SecretSanta" find a solution where the knowledge of a given assignment can not be used to infer another assignment. This is an implementation of the algorithm by Liberti and Raimondi (2008).