# Tag Info

Accepted

### Finding a shortest path in a graph

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

### Factorize laplacian in terms of first derivative matrix

@lightxbulb's answer gives the correct factorization already, but since you mention failed attempts with the Cholesky factorization, let me describe a method to discover the factorization numerically, ...
• 11.5k
Accepted

### Software for finding a minimum vertex cover for a hypergraph

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 ...
• 8,672
Accepted

### Can a Depth first traversal of a graph visit node more than once?

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

### What is a common file/data format for a mesh (for FEM)?

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

### What is a common file/data format for a mesh (for FEM)?

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 ...
• 3,126

### What is a common file/data format for a mesh (for FEM)?

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:...
• 311

### PageRank using Inverse Iteration Method by Cleve Moler

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 ...
• 18.8k

### Hypergraph matching -> adjacency matrix?

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 ...
• 121
Accepted

### Moore-Penrose pseudoinverse of singular rank degenerate matrix

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/...
• 4,936
Accepted

### What is an instance (precisely) in computational complexity?

When considering a problem in a Computational Complexity context, an instance for the problem is just an input to the problem encoded in a manner that works with the underlying model of computation. ...
• 4,258
Accepted

### Find shortest path around a cylinder represented by 3d triangular mesh

OK, after thinking about it for a while, I came up with an answer. Step 1: Find the caps of the cylinder, in other words two closed disjoint paths along the graph's borders. Step 2: Find a path ...
• 253

### How to reorder/cluster adjacency matrix to maximize the interaction along the super diagonal?

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 ...
• 8,672
Accepted

### Newman algorithm yielding different result to what is given in his paper

It's a bit late, but I have a very simple answer: there is nothing wrong with the code I was simply missing the extra optimisation that Newman recommends in his paper. The results are perfectly in-...

### Developing a meshfree contouring algorithm

Maybe this is not a full answer to your question. However, I am currently developing my own unstructured mesh generator and found this toolbox quite helpful. Perhaps there are some algorithms which ...
• 1,379
I mean I think you clearly showed the graph $G$ can induce a metric, namely define $d_G(u,v)$ as the shortest path from $u \in V(G)$ to $v \in V(G)$ and you can readily show the three properties you ...