Microsoft Technology Licensing, LLC

Lev Boris Nachmanson

George G Robertson

Bongshin Lee

Timothy Garry Dwyer

Roland Lucas Fernandez

Danyel Aharon Fisher

Alexander E Holroyd

Sergey Pupyrev

Gur Kimchi

Matthew Jay Kotler

Daniel Chaim Robbins

Murali R Krishnan

Xiaoji Chen

Nathalie Henry Riche

Jason Joseph Weber

Brian L Welcker

B Scott Ruble

Fabian Omar Winternitz

Christian Olaf Abeln

Stella Yick Chan

Kael R Rowan

Benjamin L Chronister

Edward Hart

Morten Holm-Peterson

Stuart Kent

Christian Pich

Mikkel Ronne Jakobsen

Olga Kulyk

Kipper V Jewsbury

Sergey Bereg

A graph processing module is described for producing a processed graph in three phases. In a bundling phase, the graph processing module selects edges that are used to constitute paths to produce a bundled graph. In an ordering phase, the graph processing module orders paths within the bundled graph to produce an ordered bundled graph. In a separating phase, the graph processing module separates paths in the ordered bundled graph. Among other features, the graph processing module performs the selecting operation by minimizing a cost function; this has the effect of promoting bundling in the bundled graph while discouraging the presence of overly long edges in the bundled graph. The graph processing module can perform the ordering operation by selecting the ordering of paths passing through each edge based on a consideration of ordering constraints within a common subpath associated with the edge.

Routing edges with ordered bundles

Large graph visualization embodiments are presented which generally render and display the more important elements for a current view. To this end, a measure of importance referred to as a zoom level is assigned to the vertices and rails of a graph. Each rail is a curve segment in the graph that represents an edge or a set of edges passing through it. The rendering and displaying of a graph (or a part thereof) is done quickly, even as a user moves about the graph, and the visualization of the large graph is not so dense and so full of detail that the user becomes disoriented. In general, this is accomplished by specifying a current viewport, or a current zoom level, or both. Furthermore, the visualization is stable in that the layout of vertices and rails will be the same for the same zoom level and viewport.

Visualizing large graphs

A graph processing module is described for producing a visualization of a layered graph. The graph processing module operates by: bundling edges in the layered graph to produce respective edge bundles; ordering the edges associated with the edge bundles to reduce edge crossings; straightening the edges; and separating the edges in the edges bundles with respect to each other. The graph processing module can operate on a layered graph produced by the Sugiyama algorithm or some other technique, reducing clutter in the layered graph and thus improving a user's understanding of the layered graph.

Visualizing a layered graph using edge bundling

The described implementations relate to unified application building. In one implementation unified application building tools can include a unifying component model configured to communicate with a set of components that are supported by different frameworks. The unified application building tools can also include a unification engine configured to bind events between individual components in a unified manner that is independent of an individual framework upon which individual components are supported.

Application building

A system and method for creating or editing a graph diagram. A system provides a mechanism to specify constraints on edge way points. Constraints may specify alignment with other way points, distribution of way points, spacing from other way points or nodes, or other types of constraints. A system may automatically determine edge way point constraints based on edge direction, edge type, target nodes or regions of nodes, or other characteristics of edges. The system enables a combination of constraints specified by a user and automatically determined by the system. Way points are positioned based on associated constraints, and edges are routed based on their associated way points.

Controlling edge routing using layout constraints

An edge routing system is described herein that uses a spatial decomposition to achieve faster routing, and more quickly generates a sparse visibility graph using a cone spanner. The system provides two approaches that can be used separately or in combination to achieve faster&#x2014;and hence more scalable and more interactive&#x2014;edge routing using approximate shortest paths. The first approach uses a spatial decomposition of the nodes in a graph, moving them slightly to obtain strictly disjoint convex hulls around groups of nodes, and then computing visibility graphs over these composite hulls rather than individual nodes. The second approach generates a sparse visibility-graph spanner to accelerate the process of producing the visibility graph. The system allows high quality obstacle avoiding edge routing for large diagrams in interactive diagramming applications where very fast refreshes of routing are used with many nodes moving at the same time.

Fast edge routing for interactive diagramming

A graph processing module is described for visualizing relationships among components, such as software components within a software system. The graph processing module generates group results based on grouping information which identifies groups of individual components. The graph processing module uses the group results to bias component-level analysis that it performs on the components. In one case, the component-level analysis can involve similarity analysis (e.g., using multidimensional scaling) to assess the similarity among components and importance analysis (e.g., using a network page ranking algorithm) to assess the relative importance of the components. The results of the component-level analysis can be presented for visualization. The biasing effects of the grouping results provide insight into the relationships among the components.

Visualizing relationships among components using grouping information

Various types of data can be collected into a data set and related content and/or related concepts across the data in the data set and/or across search histories can be displayed as a visual representation. The related content/concepts can be presented as a function of incremental revealing of relationships. After reviewing the visual representation, a user can customize the data set and relationships by specifically excluding a related data segment. The visual representation can be applied across multiple searches or other obtained data. Through interaction with the visual representation, a user can drill down into common linkages of the data to more narrowly focus on a subset of the data and/or to refocus a search result and/or to provide annotations.

Using visual techniques to manipulate data

A graph layout technique that creates a layered graph layout with a given aspect ratio. The present layered graph layout technique better utilizes the available space and, at the same time, creates an aesthetically pleasing drawing of a directed graph. In one embodiment it determines the layout of the new graph based on a modified Sugiyama technique combined with a modified Coffman-Graham scheduling algorithm. Given a directed graph and a desired aspect ratio, it uses a binary search and the Coffman-Graham scheduling algorithm to find a layout of the graph that has an aspect ratio that matches the given aspect ratio of the available space.

Layered graph layouts with a given aspect ratio

Growing community of inventors

Redmond, WA, United States of America

Lev Boris Nachmanson