Questions tagged [graph-theory]
A field of combinatorics relating to the study of vertices and the edges that connect them
83
questions
14
votes
6
answers
1k
views
Approximate spectrum of a large matrix
I want to compute the spectrum (all the eigenvalues) of a large sparse matrix (hundreds of thousands of rows). This is hard.
I am willing to settle for an approximation. Are there approximation ...
- 3,058
13
votes
6
answers
6k
views
What is a common file/data format for a mesh (for FEM)?
I'm developing an FEM simulation. For early testing, I will use simple self-written mesher and visualisation of the mesh graph. But I want to prepare my program to use data generated by an existing ...
- 1,453
11
votes
3
answers
7k
views
I am looking for a parallel dynamic graph library in C++
Hello scicomp community,
I have worked in the area of graph algorithms using frameworks such as NetworkX (Python), JUNG and YFiles (Java). I am now entering the area of parallel and high perfomance ...
- 243
11
votes
3
answers
1k
views
Testing if two 12x12 matrices have the same determinant
I am given a $12 \times 12$ matrix $Q$ that is symmetric, invertible, positive definite and dense. I need to test if $$\det(Q) = \det(12I-Q-J) \; \; (1)$$ where $J$ is the all ones matrix.
I am ...
- 458
11
votes
1
answer
5k
views
Algorithms for community detection for bipartite graphs?
Are there any algorithms for community detection for bipartite graphs (2-mode networks) implemented in igraph, networkX, R or Python etc.? In particular, is there such an implementation in which one ...
- 211
9
votes
2
answers
2k
views
Is there an algorithm or graph theory that allows me to not need to store an intermediate matrix when calculating AT*Y1*A + BT*Y2*B?
I have a system of conductors for which there are two dense matrices of the (complex) mutual admittances, $Y_A$ and $Y_B$, which are symmetric. Then, an equivalent nodal admittance matrix $Y_N$ is ...
8
votes
1
answer
811
views
C++ library for graphs with maximum common subgraph solver
I'm looking for a convenient, free C++ library for graphs that include a solver for the maximum common subgraph (MCS) problem.
I'm aware of the
Boost Graph Library
and
LEMON
, but neither includes an ...
- 1,032
8
votes
1
answer
803
views
Where to find data sets for testing minimum vertex cover algorithm for bipartite graphs?
I'm playing with simple implementations of algorithms to find minimum vertex cover/maximum cardinality matching in bipartite graphs. However, I seem to have trouble googling for some test data sets ...
- 183
7
votes
2
answers
1k
views
Finding the distribution (histogram) of eigenvalues for large sparse matrices
Are there any existing programs that are able to compute the (approximate) distribution of eigenvalues for very large (symmetric) sparse matrices?
Note that I do not need the eigenvalues themselves, ...
- 2,600
6
votes
2
answers
438
views
Efficient algorithm to decide if a graph is a cactus?
A cactus is a connected graph in which every edge belongs to at most one simple cycle.
How should one modify the Depth First Search algorithm to obtain an efficient algorithm that determines if a ...
- 63
6
votes
1
answer
12k
views
Concave polygon 'hull' finding
I implemented an algorithm to find the alpha shape of a set of points. The alpha shape is a concave hull for a set of points, whose shape depends on a parameter alpha deciding which points make up the ...
- 343
6
votes
1
answer
792
views
how to visualize lattice with periodic, helical, etc. boundary conditions?
I am trying to write a special hexagonal lattice generator, with several kinds of boundary conditions, such as helical BC, periodic BC, and I find it hard to verify whether it works correctly. I tried ...
- 279
6
votes
1
answer
174
views
Is there a way to inspect the graph of a sparse matrix with PETSc?
I am currently trying to code the CA-CG method within the PETSc framework. A mandatory step in this process is the implementation of the "matrix powers kernel" algorithm for a generic sparse matrix.
...
- 205
5
votes
3
answers
464
views
What is a good introduction to graph theory / algorithm
By good I mean minimal and essential.
One whose concepts form a minimum spanning tree, and whose words are precious :)
(A small pdf would be perfect)
- 153
5
votes
3
answers
207
views
Where do I find data to start a graph data structure to practice on?
I am interested in learning firsthand about graph data structures but have no data to put into the database. Can anyone recommend a source for a beginner to find graph data? (Preferably a source that ...
- 51
5
votes
3
answers
861
views
Minimization of non-linear function
Problem Summary
I am trying to estimate the (x,y) coordinates of each node in a graph, where I know the distances between connected nodes. For example
Given this ...
- 191
5
votes
1
answer
87
views
Optimal partitioning of a graph
Consider a planar graph, where each node is associated with a weight. I would like to partition the graph such that the sum of the node weights in each group satisfy a minimum requirement. However, I ...
- 51
5
votes
0
answers
111
views
Graph optimization for parallel processing
Consider the following example structure of overlapping images marked A,B,C,D. The possible overlaps are marked by gray color:
The structure can be represented by a weighted undirected graph (images ...
- 393
5
votes
0
answers
2k
views
Two-chordless cycle extraction from a failed comparability graph recognition
I have implemented a comparability graph recognition algorithm from M.C. Golumbic's "Algorithmic graph theory and perfect graphs" book. It is hinted in Fekete, Schepers, and van der Veen's "Exact ...
- 580
4
votes
2
answers
523
views
Moore-Penrose pseudoinverse of singular rank degenerate matrix
I am trying to attain the Moore-Penrose pseudoinverse of a very large, very sparse, rank-degenerate, singular, and square matrix. ($75000 \times 75000$, near rank). The matrix is a graph Laplacian and ...
- 143
4
votes
1
answer
269
views
Which optimization method can be used to do the following?
I've the following system of equations for studying information flow in the below graph,
$$ \frac{d \phi}{dt} = -M^TDM\phi + \text{noise effects} \hspace{1cm} (1)$$
Here, M is the incidence ...
- 459
4
votes
1
answer
351
views
Efficiently generate a random subgraph (Gs) with maximum degree K, using only edges from an existing graph G
I am looking find a way of efficiently generating a random, undirected subgraph $G_s$ with $N$ vertices, using a subset of edges from an exisiting undirected graph $G$, also of size $N$, where the ...
- 41
4
votes
1
answer
3k
views
Find / Detect / Enumerate all Cliques or Independent Sets
What are generally best choices for enumerating all k-cliques (or independent sets of size k)?
The graphs I am looking at probably won't have more than ~ 100 nodes.
Presently I code in Python with ...
- 141
4
votes
1
answer
204
views
Generating lattice clusters/graphs in parallel
I'm trying to generate all graphs with n or fewer vertices that can be embedded in some lattice, eg square, triangular, Kagome. Do there exist algorithms to both enumerate and draw these graphs? What ...
- 405
3
votes
2
answers
1k
views
How to calculate efficiently mesh edges midpoints?
I have a 2D mesh of triangles used in Finite Element method to discretize the domain. I want to calculate the midpoints of all the edges because I want to use $\mathbb{P}^2$ elements. I am using ...
- 33
3
votes
2
answers
200
views
Find shortest path around a cylinder represented by 3d triangular mesh
Suppose I have a 3d triangular mesh with the topology of a finite cylinder. Let $C$ be a vertex on that mesh.
How can I find the shortest path from $C$ to itself that goes around the cylinder? By ...
- 243
3
votes
1
answer
205
views
Software for finding a minimum vertex cover for a hypergraph
A hypergraph $H = (V,E)$ consists of a finite set of vertices, say $V=\{1, \dots, n\}$ and a set of hyperedges $E \subseteq \mathcal{P}(V)$. We call $H$ a $k$-hypergraph if all $|e| = k$ for all $e\in ...
- 133
3
votes
1
answer
160
views
multiplications of graph adjacency matrix
Suppose $A$ is a directed graph adjacency matrix. Is there any good interpration of the $(i,j)-$entry of the matrix $(A^{32}\cdot (A^T)^{32})$ ?
- 241
3
votes
1
answer
147
views
Sparse Matrix Reordering
Matrix reorderings are important for many direct solvers. Sometimes the objective is to reduce the bandwith or the generated fill in by LU Decomposition. I am interested in a reordering which reduces ...
- 168
3
votes
1
answer
69
views
Minimizing expression DAGs
Say I have an expression involving adds, subtractions, and multiplications. I know that it is safe to assume commutativity, associativity, distributivity, etc., and would like to automatically ...
- 3,879
3
votes
1
answer
291
views
Optimal Scheduling of Parallel Tasks with Known Dependencies
This is maybe a trivial question, but I am stuck with the problem.
Suppose we have a general graph:
$$G=(V,E)$$
Each edge represents a task, each vertex represents a data for the task (hence each ...
- 393
3
votes
0
answers
230
views
Factorize laplacian in terms of first derivative matrix
I am trying to factorize the following Laplacian matrix in terms of $ D^TD$, D is the first derivative matrix.
The tridiagonal form of the secon derivative matrix using Neumann boundary condition is ...
- 459
3
votes
0
answers
76
views
Absorbing BC's / PML on a graph
The wave equation,
$$\ddot{u} = c^2 \Delta u,$$
can be generalized to abstract graphs by using the negative graph Laplacian in place of the physical Laplacian.
Is there a graph-theoretic analog of ...
- 3,043
3
votes
0
answers
134
views
The traveling salesman problem - Using Space Renormalization
Image attached is where I am at the moment. Blue dots=points/cities, Black x's represent central points in each box that contains at least one city, and pink dots represent the midpoint of these ...
- 299
2
votes
1
answer
130
views
Bounds for the optimal bandwidth of 2D/3D FEM stiffness matrices
is anyone here aware of whether there exist bounds on the optimal bandwidths of 2D/3D FEM stiffness matrices?
Edit: more specifically, I would like to have bounds on the minimum bandwidth after ...
- 91
2
votes
2
answers
492
views
Find connected circles
I have a problem as follows:
We have a set of circles (we know the radius r and the center point c in Rd of each circle)
We ...
- 23
2
votes
1
answer
99
views
graph theory operations to explore structure of a graph
I'm analyzing experimental data, and I've produced graphs that look similar to the attached sketch. When I look at the graph, I see structure in the connections (connections tend to be local, there is ...
- 135
2
votes
1
answer
267
views
Algorithm to equalize the area of random tessellation of various polygons
I am looking for an algorithm that I can apply for a random tessellation of polygons with different areas. The algorithm can relax the geometry of the polygons to a condition that all of them would ...
- 21
2
votes
2
answers
766
views
PageRank using Inverse Iteration Method by Cleve Moler
I was trying to understand how to use the inverse interation method to compute the page rank as an exercise.
In this chapter (page 4) about page rank (by Cleve Moler), the author suggests to use the ...
user9925
2
votes
2
answers
2k
views
Depth of a Binary Search Tree
I wrote a function to search a Binary Search Tree, but I have logic problems: When I insert some values, and I have a tree of 2 levels, and the final level (2 in this case) is not full (full is that ...
- 153
2
votes
1
answer
139
views
Developing a meshfree contouring algorithm
I would like to find the contours of a scalar function $u(x,y)$ available as a discrete set of function values $u_i = u(x_i,y_i)$ over a scattered set of points $(x_i,y_i), i=1,...,N$.
In my case, the ...
- 342
2
votes
1
answer
1k
views
How can I determine if there is a closed-loop path in a graph?
Assuming I have a computer representation of a graph presented in the figure below:
How can I find out whether there are some close-loops inside the graph, like the one marked in red (or more ...
- 123
2
votes
1
answer
132
views
k-splittable flow problem
The maximum k-splittable s-t flow problem(MkSF) that aims to find a maximum k-splittable flow between a given source and sink node is NP-hard. We do not require the paths to be disjoint, not even ...
- 555
2
votes
1
answer
810
views
Evolutionary algorithm - Traveling Salesman -fitness function
I'm trying to solve this problem using genetic algorithms and am having difficulty choosing the fitness function. My problem is a little different than the original Traveling Salesman Problem, since ...
- 21
2
votes
2
answers
207
views
Finding two shortest path that are 'distant' in the graph
The problem is as follows:
We are given a graph with each edge length 1 and two pairs of vertices (a,b) and (c,d).
How to find shortest paths between from a to b and from c to d, with assumption that ...
- 121
2
votes
0
answers
171
views
Mesh partitioning with METIS
I am trying to use METIS-5.1.0 edition in order to partion a FE mesh. For demostration purposes I created 2x2 rectangle mesh and tried to partition it. However, I notice a weird behaviour in my code. ...
- 471
2
votes
0
answers
111
views
Algorithm for optimizing graph interconnectivity
I have a partiuclar kind of graph problem and (not having a background in graph algorithms) I would like to know how this kind of problem is called in the literature and what algorithms exist for ...
- 435
1
vote
1
answer
2k
views
Efficient way to compute the cumulative weights of all subtrees rooted at each node in a tree?
I have a tree data structure (rooted, unbalanced, with unbounded branching factor), where each individual node has an associated 'weight'. For every node $n$ in the tree, I'd like to compute the ...
- 237
1
vote
2
answers
824
views
How can I find the maximum equal-split flow of a network
I am working on a program currently that works out the maximum flow through a network using the Ford-Fulkerson algorithm, and that works fine, however, I need the final flow to meet the constraint ...
1
vote
1
answer
84
views
Newman algorithm yielding different result to what is given in his paper
Summary
I am trying to implement Newman's algorithm for community detection, outlined in this paper. I am testing my implementation against one of the datasets used in that paper to benchmark the ...
- 31