The Stack Overflow podcast is back! Listen to an interview with our new CEO.

Tag Info

Hot answers tagged graph-theory

15

If your graph is undirected (as I suspect), the matrix is symmetric, and you cannot do anything better than the Lanczsos algorithm (with selective reorthogonalization if necessary for stability). As the full spectrum consists of 100000 numbers, I giess you are mainly interested in the spectral density. To get an approximate spectral density, take the ...

11

Boost Graph Library and LEMON As Daniel mentions in his comprehensive answer, the most full-featured general C++ library is the Boost Graph Library. There is a new distributed-memory extension capable of doing some basic algorithms such as breadth-first and depth-first search, minimum spanning trees, and connected components search, but I am not very ...

8

Since you're already using C++ and your matrices are symmetric positive definite, I would perform an unpivoted $LDL^T$ factorization of $Q$ and also of $12I-Q-J$. Here I'm assuming that $12I-Q-J$ is also positive definite, otherwise the $LDL^T$ will require pivoting for numerical stability (it's also possible that even though it's not positive definite, ...

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 ...

7

Say, we are given $n$ points $x_1, \ldots, x_n$ in the plane. Let's assume them to be ordered by their x-coordinates. I.e. $x_1$ is leftmost and $x_n$ is rightmost. Let's think a bit about the minimal bitonic tour on all vertices. We can be sure that the edge $(x_{n-1}, x_n)$ will be contained in such a tour, so it suffices to find the length of a minimal ...

6

According to this ticket, Boost Graph Library added this feature around 3 years ago. The appropriate function (or set of functions) appears to be this function (mcgregor_common_subgraphs), which uses the McGregor algorithm.

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.

6

When I was in the same position as you, I was very happy to find Knuth's Stanford Graphbase (SGB). He supplies not only a library for working with graphs, but also some data sets to play with. My favorite one was the 5-letter English words dataset. You can use your programming language of choice to generate an undirected graph where two words are neighbors ...

5

Without some information about the construction of these $12\times 12$ positive definite real symmetric matrices, the suggestions to be made are of necessity fairly limited. I downloaded the Armadillo package from Sourceforge and took a look at the documentation. Try to improve performance of separately computing $\det(Q)$ and $\det(12I - Q - J)$, where $J$...

5

I'd also like to mention STINGER, a dynamic graph data structure designed for parallelism. According to the website, it is designed for the following objectives: Portability: Algorithms written for STINGER can easily be translated/ported between multiple languages and frameworks Productivity: STINGER should provide a common abstract data structure ...

5

Perhaps, the Boost Graph Library is what you are looking for. It has a parser to read graphs specified in GraphViz's DOT format. While i don't really know about memory overhead, it does provide a variant for parallelization. Another graph library is LEMON but i don't really know it and if it has support for parallelization, it's not advertised. It's ...

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

The phrase "community detection" is loosely defined as partitioning the vertices of a graph into "communities" such that each has members more densely linked to one another than to members of other "communities". Our first task is to ascertain what this should mean in the case of a bipartite graph, which by definition consists of two "modes" such that ...

4

If by "good introduction" you mean "just the basics", then you might want to look at the first chapter of "Graphs, Networks and Algorithms". Lucky you, springer gives the first chapter as a free preview: here NB: I wanted to add this as a comment to @Jean-VictorCôté's answer but it seems I'm not reputable enough...

4

A good book for you may be: Dieter Jungnickel, "Graphs, Networks and Algorithms", Third Edition, Springer, 2008

4

If you're ok with thinking about things that are not eigenvalues but functions that in some sense still tell you something about the spectrum, then I think you should check out some of the work by Mark Embree at Rice University.

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 ...

3

Creating lattice (and other periodic) structures is a major issue in molecular simulations. Therefore, if you can translate your points into something that can be parsed by a viewer such as VMD or PyMol, you should be able to generate a view that can tell you if everything is working as expected. (This assumes, of course, that you build more than one ...

3

In structural mechanics the number of eigenvalues of a matrix $K$ in a given range $(\alpha,\beta)$ is computed via the "Sturm sequence check", i. e. computing the $LDL^T$ factorizations of $K-\alpha I$ and $K-\beta I$ and counting the difference in the number of negative pivots. If you have reasonably large bins, can be applied to your problem, and should ...

3

Start with equal edge weight, so $A$ is a boolean matrix. Think about what happens when you apply $A$ to the $k$th column of the identity, $\mathbf e_k$. Are the nonzeros in $A \mathbf e_k$ upstream or downstream of node $k$? What happens when you apply $A$ again, $A(A \mathbf e_k)$? What happens when there are two length-2 paths from node $i$ to node $k$? ...

3

There's benchmark code for max cardinality matching: you could use that and even randomly generated bipartite graphs to establish ground truth and test out your algorithms.

3

Not minimal but fairly good :) I've collected some online resources. Pick the one you like: http://karussell.wordpress.com/2012/02/19/free-online-graph-theory-books-and-resources/

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

You might try either Gmsh's MSH file format or GAMBIT neutral file format.

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 ...

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