# Tag Info

## Hot answers tagged graph-theory

8

The short answer is no, there is not a standard format. But there are some common ones, like Gmsh for input/output and VTK for output. Before making a decision you need to find out what do you want to do. If you want to have your (small) program for a while, then you can pick the format that best suit to your taste and needs. If you are planning to change ...

6

Arnold Neumaier's answer is discussed in more detail in section 3.2 of the paper "Approximating Spectral Densities of Large Matrices" by Lin Lin, Yousef Saad and Chao Yang (2016). Some other methods are also discussed but the numerical analysis at the end of the paper shows that the Lanczos method outperforms these alternatives.

5

No need for any advanced books, the easiest to implement answer is: Use a DFS (http://en.wikipedia.org/wiki/Depth-first_search), and store the cumulative sum of each subtree in the stack. For example, a possible DFS traversal in your example is: A->B->D->I->J->E->C->F->G->H. After computing the cumulative sum of the child of a node, add this value to ...

5

You don't need to check each pair of circles, so you can apply one of the neighour search algorithms. They restrict the distance calculations to the circles in the vicinity of each other by generating a list of potential neighbours based on a certain division of space. I would suggest to use the kd-tree method, which is efficient for circles with variable ...

4

If you have an array that stores the indices of the 3 neighbors of each cell, then you would only compute the midpoint of an edge of the neighbor cell has a higher index than the current cell, or if there is no neighbor at all. This way you have an easy tie breaker to decide which of the two cells is responsible for computing the edge midpoint.

4

75k x 75k double-precision entries is 45 gigabytes. That fits in memory, but barely; you need to be careful. The linear algebra routines in most languages rely on Lapack as a backend, which is a highly optimized linear algebra library written in Fortran. Most Lapack routines operate in-place: for instance, its QR routine xGEQRF does not allocate a second ...

4

This is a fun question! After academic searches and Wiki came up bare, I dug through the source code of SageMath. That gets us to this: #A graph is called *cactus graph* if it is connected and every pair of simple cycles have at most one common vertex. # Special cases if self.order() < 4: #Number of vertices return True # Every cactus graph is ...

4

Let's take an $n\times n$ mesh (with $N=n^2$ unknowns) and think about whether you can enumerate them in such a way that you end up with a bandwidth less than $m=n=\sqrt{N}$? You get this bandwidth with a 5-point stencil if you enumerate the first row left to right, then the next row left to right, etc. In that case, each degree of freedom $i$ couples with $... 3 Depth first search will put a node into the stack only once. The usual way to perform DFS involves marking a vertex as marked while pushing it into the stack and not pushing an already marked vertex again. A node will not enter the stack if and only if it is not part of the connected component involving the DFS start vertex. This only matters for graphs ... 3 The number of file formats for FEM is ridiculous, partly due to the fact that every software package implemented its own format in the past. (From xkcd.) I've created meshio to alleviate the pain of converting between formats, so if you use any format supported by meshio, you should be able to easily make a switch in the future. Out of all formats I know, ... 3 There is actually a standard for this: ISO/TS 10303 (start with parts 1380 to 1386). Prior to being hijacked by ISO, this initiative, which began back in the 1980s, was known as PDES/STEP. See https://www.pdesinc.org/index.html But I don't believe anybody much uses it unless they are working in an environment where it is a mandatory requirement. A large ... 3 You might try either Gmsh's MSH file format or GAMBIT neutral file format. 3 The fairly simple Lloyd's algorithm can be used to achieve this. The essence of the algorithm is you start with a given tesselation defined by a set of points and a distance metric. The points are then moved to the centroids, allowing the tesselation and the areas to be recomputed. This iterative process is then repeated until the movement is sufficiently ... 3 There are a handful of common metrics when analyzing graphs and networks. Clustering coefficient: given a vertex$i$in the graph and two neighbors$j$,$k$of$i$, what are the odds that$j$and$k$are also connected? Analogy: knowing that Gertrude Stein and Ernest Hemingway are both friends of mine, what are the chances that they're friends with each ... 3 If different nodes have different costs, for example because different rows of your matrix have different numbers of nonzero entries, then you need to attach weights to each node of your graph. Graph partitioning algorithms such as METIS allow you to do this, creating partitions where it is not the number of nodes that are about equal between partitions, but ... 3 Based on the provided description as well as the figure, you have an undirected graph with a single source and a sink at hand. The most famous option is to implement Dijkstra's algorithm. There are other options that are faster, but as long as your dealing with small instances and have no CPU time limit, I think you're good to go. In case you're interested, ... 3 If you have an algorithm that finds all cycles, then do the following steps: Take cycle 1, tag all edges that are part of it. Take cycle 2 and go through all edges that are part of it: If an edge is already tagged, then clearly that edge is part of another cycle and you don't have a cactus Otherwise, tag that edge Repeat with cycles 3...n 3 Pragmatically, an instance just means an input/output pair of an algorithm. I think a better example of a reduction would be transforming multiplication into repeated addition. For example, the single multiplication "instance",$4*7$, can be transformed into$7+(7+(7+7))$, three "instances" of the addition algorithm. Reduction is all about finding ways to ... 3 Despite my comment, I think you can find$\tilde{D}$that contains the noise term as well. You have this equation: $$-M^{T} \tilde{D} M \phi(t) = -M^{T} D M \phi(t) + W(t)$$ Where$W(t)$is the noise term vector. So: $$-M^{T} (\tilde{D}-D) M \phi(t) = W(t)$$ Take$\mathcal{D} = \tilde{D} - D$. Let's expand this equation:$$(M \phi(t))_{i} = \sum_{j=1}^{... 2 If you know the number of edges and triangles, you could raster through a list of your triangles and create a triangle-to-edge map$(\mathcal{O}(N_{tri}))$and simultaneously create the inverse map, which will give you the two triangles that share an edge. A naive search of that list for the right triangle-pair will be$\mathcal{O}(N_{edge})$, where$N_{edge}...

2

There are many methods to minimize a multi-dimensional function. Here is a list of some standard ones. If you want a good description along with some sample code you can check out Numerical Recipes. In particular checkout chapter 10 which covers minimization and maximization of functions. I've implemented their simplex method to solve 2D problems like yours ...

2

I think better approach is to use 'fzero()' function like this: then simply use (1) and (2) to find Y_B and Y_D use same trick for other triangles

2

If all you're looking for is an approximate solution, I would suggest starting with one of the well-known graph partitioning packages, for example METIS. It allows you to attach weights to nodes. Partition it into $P$ groups and check whether your minimal weight sum condition is satisfied. If yes, try partitioning into $P+1$ groups and check again. Then ...

2

You can avoid the explicit computation of $A^{-1}$ in the Newton iteration for the sign of $A$. Refer to chapter 5 from this book by Higham, more specifically equation 5.22.

2

The MATLAB code that you've computed finds the eigenvector of $A$ associated with the eigenvalue 1. We know for this particular problem that $A$ has 1 as an eigenvalue- this can be shown using the Perron-Frobenius Theorem. This code isn't using the inverse iteration algorithm. The inverse iteration algorithm can be used to find an eigenvalue and ...

2

If the main bottleneck is computing a list (well, in MATLAB, I guess it's a matrix) of unique edges, as long as you can find a hash table implementation, you should be able to find a(n average-case) linear time algorithm in the number of vertices (or elements, or edges, by Euler's formula, since your 2D mesh is a planar graph). On way to do this is to ...

2

Edges are represented as sets of vertices. With classical graphs, an edge can be represented by the set containing its 2 endpoints. With hypergraphs, they are represented by a set containing more than 2 nodes e.g. $e_i = \lbrace v_1, v_2, ... , v_n \rbrace$. Incidence matrices are straightforward, just look at the wikipedia page. About incidence matrices you ...

2

I usually use SageMath for research work connected with graphs. However, I was not able to find there a ready-made algorithm to find a minimum vertex cover for a hypergraph (see subsection with the corresponding name). Anyway, using Sage together with Python should simplify your life a lot as it will give access to a lot of convenient and tested data ...

2

Although I'm unfamiliar with "distance metrics", there's no shortage of information about graph laplacians on the web because of their practical applicability to matrix reordering and classification/clustering problems. The nullspace of the undirected graph laplacian is well known (a vector of 1's, or one such vector per connected component if the graph is ...

2

As far as I understand, you are looking for a family of algorithms that are used to reorder sparse matrices. Usually, it is used to reduce fill-in during sparse factorization; however, it's certainly not the only use. The first candidate would be (reverse) Cuthill-McKee algorithm. Also, take a look at Matlab sparse matrix reordering page that would ...

Only top voted, non community-wiki answers of a minimum length are eligible