I have a graph G with two classes of vertices. The first class represents no resource limitation entities and can be visited an unlimited number of times in any path traversal. The second class of vertices represent a cost constrained resource. A path may traverse any vertices in this subclass at most M times (i.e. resource limit met) after which all the vertices in the second class become unreachable for the remainder of that individual path traversal. There are no self loops but cycles are allowed.
I have come up with an inefficient modification of depth first search which enumerates all possible paths starting at each vertex that follows all possible paths of length n from that vertex given the above traversal constraints. With n > 15 or so the running time becomes unreasonable. I am essentially enumerating every possible path which respects the visitation constraint starting from each vertex and keeping count of the total across all starting vertices.
There is an efficient way to count all paths of length n in an adjacency matrix (A). Summing the number of paths found A^n quickly gives the total number of paths of length n. A nice explanation is found here:
https://stackoverflow.com/questions/17623876/matrix-multiplication-using-arrays
My modified DFS follows:
public long dfs(int depth, Digraph G, int v) {
if(depth == 1) {
return 1l;
}
long total = 0;
for (int w : G.adj(v)) {
if(class2ResourceCheck(w)) {
total += dfs(depth - 1, G, w);
class2ResourceRelease(w);
}
}
return total;
}
private boolean class2ResourceCheck(int c) {
boolean answer = true;
if(memberOfClass2(2)) {
if(vCount < resourceLimit) {
answer = true;
vCount++;
} else {
answer = false;
}
}
return answer;
}
I am exploring if it is possible to adapt the A^n counting algorithm to deal with the resource constraint issue. My thought is that I can maintain two versions of A. A is the normal A and A' is a version of A with the second class edges removed making them unreachable. i.e. A' = A(i,j) except A'(i,j) = 0 where either i or j are vertices in the second class.
During the matrix multiplication process I keep track of when resource constrained vertices are used in paths. When I need to remove the resource constrained vertices the math becomes:
(((A x A) x A) x A') x A'
Here's a first stab at what I've been experimenting with but I haven't found an algorithm whose output (and therefore correctness) matches the modified DFS above. Would appreciate any thoughts or insights into the problem, suggestions for alternative solutions, and whether this direction seems worth pursuing. Thanks.
public static int[][] multiplyByMatrix(int[][] m1) {
int[][] m2 = allVertices;
int m1ColLength = m1[0].length; // m1 columns length
int m2RowLength = m2.length; // m2 rows length
if(m1ColLength != m2RowLength) return null; // matrix multiplication is not possible
int mRRowLength = m1.length; // m result rows length
int mRColLength = m2[0].length; // m result columns length
int[][] mResult = new int[mRRowLength][mRColLength];
for(int i = 0; i < mRRowLength; i++) { // rows from m1
m2 = allVertices;
resetClass2Count();
for(int j = 0; j < mRColLength; j++) { // columns from m2
for(int k = 0; k < m1ColLength; k++) { // columns from m1
if(class2Check(j) >= 2) {
m2 = noClass2Vertices;
}
mResult[i][j] += m1[i][k] * m2[k][j];
class2PostRelease(j);
}
}
}
return mResult;
}