Explore chapters and articles related to this topic
Introduction to graph theory
Published in Karthik Raman, An Introduction to Computational Systems Biology, 2021
This is the simplest representation of a graph, as a simple list of all edges. Although inefficient for computations, it happens to be the easiest way to store graphs in a file and exchange them in a human-readable format. Figure 2.5c illustrates the edge list for the directed graph in Figure 2.5b. Formats such as PSI-MI TAB (see Appendix C) are edge lists at their core. An edge list obviously contains |E| rows, two columns representing the interacting entities (node ‘IDs’) and a possible third column representing edge weights, if any. Additional columns may capture other attributes of the edges.
Graph centrality analysis of feature dependencies to unveil modeling intents
Published in Computer-Aided Design and Applications, 2018
Zhengrong Cheng, Yanan Xie, Yongsheng Ma
A part model contains a lot more information than just features, for example, geometric information like bodies, faces, edges, etc., and non-geometric information like annotations, colors, and layers. Here what we care about are features in the part. There is a feature manager in the part model called feature collection [21], which is responsible for creating different feature builders to construct features, and keeping track of features that have been created in the part. All features within a part can be obtained from the feature collection, as is shown in Fig. 4. In addition, since each feature has pointers to those features depending on it, we can trace down the feature dependencies to build the graph. The general algorithm to extract feature information and to construct the feature dependency graph is shown in Fig. 6. The general framework of current research is presented in Fig. 5. It starts with a constructed feature-based CAD model with all the model history and feature information. Then feature information is extracted from the model with API programming to construct the ADFDG based on the algorithm introduced in Fig. 6. In general, three representations are available for a graph, adjacency list, edge list, and adjacency matrix. This research uses adjacency list representation for ADFDG by using a data structure called map, which is a type of associative container that stores key-value pairs. Note that some feature operations are created automatically by the CAD system in the background during the model construction. The resulting graph might show more feature nodes than what could be seen in the part navigator, where only explicitly applied feature operations are presented. With the ADFDG at hand, visualization and centrality analysis of the graph could be carried out.
Fractality in water distribution networks: application to criticality analysis and optimal rehabilitation
Published in Urban Water Journal, 2021
Kegong Diao, David Butler, Bogumil Ulanicki
The WDNs are first mapped into undirected graphs (edges do not have a direction) in which the nodes represent the consumers, sources, and tanks and the edges represent the connecting pipes, pumps, and valves (Perelman and Ostfeld 2011). The graph is stored as an edge list used as the input for the box-covering algorithm.
Optimizing streaming graph partitioning via a heuristic greedy method and caching strategy
Published in Optimization Methods and Software, 2020
Qi Li, Jiang Zhong, Zehong Cao, Xue Li
There are many ways to save graph data, such as the adjacency list and the edge list. The size of the graph depends on the method used to save the graph data. The input graph size in this paper is calculated according to the adjacency list.