China
Africa
Explore chapters and articles related to this topic
Big Graph Analytics: Techniques, Tools, Challenges, and Applications
Published in Mohiuddin Ahmed, Al-Sakib Khan Pathan, Data Analytics, 2018
Dhananjay Kumar Singh, Pijush Kanti Dutta Pramanik, Prasenjit Choudhury
A graph is basically a collection of nodes where each node might point to the other nodes. The graphs can be directed like one-way streets or can be undirected like two-way streets in the city. Suppose we want to go through this graph, and specifically suppose we want to do something, like figure out if there is a path from one node to another. There are two common ways of doing this: Breadth-first search (BFS): The BFS is a level-by-level graph traversal algorithm that performs searching on unweighted, undirected graph from the given start vertex and assigns the distance to each vertex.Depth-first search (DFS): The DFS is typically a recursive graph traversal algorithm that explores as deeply as possible using one neighbor before backtracking to other neighbors. DFS does not go through all the edges. The vertices and edges, which depth first search has visited, form a tree (graph spanning tree).
Connectivity
Published in Kenneth H. Rosen, Graphs, Algorithms, and Optimization, 2005
There is an easier, more efficient way of finding the blocks of a graph than using fundamental cycles. It was discovered by Hopcroft and Tarjan. It uses a depth-first search (DFS) to construct a spanning tree. With a depth-first search the fundamental cycles take a very simple form – essentially we find them for free, as they require no extra work. The basic form of the depth-first search follows. It is a recursive procedure, usually organized with several global variables initialized by the calling procedure. The example following uses a global counter DFCount, and two arrays DFNum[v] and Parent[v]. Each vertex v is assigned a number DFNum[v], being the order in which the DFS visits the vertices of G, and a value Parent[v], being the vertex u from which DFS(v) was called. It is the parent of v in the rooted spanning tree constructed. Initially all DFNum[·] values are set to 0.
Graph Algorithms I
Published in R. Balakrishnan, Sriraman Sridharan, Discrete Mathematics, 2019
R. Balakrishnan, Sriraman Sridharan
Intuitively, during the traversal of the graph, each vertex is marked only once and each edge xy is traversed exactly twice – once from x and once from y. Hence the complexity of the dfs algorithm is O(n + m) = O(max (n, m)) by the sum rule of the complexity. Here, m denotes the number of edges of the graph G.
Integrated job-shop scheduling in an FMS with heterogeneous transporters: MILP formulation, constraint programming, and branch-and-bound
Published in International Journal of Production Research, 2023
Amir Ahmadi-Javid, Maryam Haghi, Pedram Hooshangi-Tabrizi
The suggested algorithm uses the Depth-First Search (DFS) and backtracking strategies. According to the DFS strategy, the algorithm starts from the root (partial sequence of zero operations) and explores as far as possible along each branch before backtracking. At each level, a node with the smallest lower bound is chosen to keep the searching procedure. After reaching to the deepest level of the search tree, the search backtracks and returns to the most recent node and continues to explore other sub-nods. The DFS strategy helps us to find a very quick feasible solution. Besides, it needs less memory to explore the tree. At each node of the tree, a lower bound for the associated partial sequence is calculated and a dominance rule can be also applied to fathom the nodes and reduce the dimension of the search space.
A Combined Graph Theory–Machine Learning Strategy for Planning Optimal Radial Topology of Distribution Networks
Published in Electric Power Components and Systems, 2022
Sravan Kumar Gunturi, Dipu Sarkar, Lilika Sumi, Abhinandan De
The DFS algorithm traverses extensively deeper into the graph whenever it is possible. The exploration starts from a random node and designates as the ‘parent’ and noted as visited once. Next, search the other nodes that are attached directly to this parent. For the first accessible associated node, the algorithm bounds to that node, mark it as visited once and begins a new search for the next pertinent node. If we find no node, the current node is marked as visited twice and returns to the parent node. After reaching the parent node, it starts to the second connected node, performs the same search technique repeatedly and returns to the parent node. Just after all the connected nodes from the current parent node are marked as visited twice, then the search ends. While examining connected nodes at each stage, if a node with the mark of already visited twice is seen even before the present search ended well, it is indicated that a loop must be present.
Detection and clustering of mixed-type defect patterns in wafer bin maps
Published in IISE Transactions, 2018
Jinho Kim, Youngmin Lee, Heeyoung Kim
The connected-path filtering method basically searches all possible defective-die-connected paths between two defective dies (vertices) and detects paths that are longer than a pre-specified threshold. To illustrate this, Figure 4(a) shows a simulated example of a WBM of approximately 400 dies that has a linear defective pattern (red: defective dies, green: good dies). Figure 4(b) shows its adjacency matrix, which indicates whether there exists an edge connecting two specific vertices (1 if there is an edge). Based on the adjacency matrix, the geodesic distances of all possible connected paths between two defective dies are calculated. For example, Table 1 shows the geodesic distances from the vertex (3, 7) to all other defective die vertices; a negative distance means that there is no path connecting the two vertices. To calculate the distances of all possible connected paths between two defective dies, we used the depth-first search (DFS) algorithm (Tarjan, 1972). The DFS algorithm is an algorithm that searches tree or graph structures while traversing connected nodes in graph data. The DFS algorithm computes all distances from a specific vertex to all other vertices and is usually used to find the shortest path in the graph. Details of the DFS algorithm for the connected-path filtering are provided in the Appendix.