3
$\begingroup$

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;
}
$\endgroup$
4
  • 2
    $\begingroup$ This sounds more like a programming problem than a research-level math problem. $\endgroup$ Jul 22, 2015 at 19:35
  • $\begingroup$ @PerAlexandersson First thanks for reading and for you comment. I put it here because I am not certain yet that a modification of the A^n counting algorithm is an appropriate strategy and was hoping for comment on that. I have found no other published algorithms that address this type of problem. $\endgroup$
    – mba12
    Jul 22, 2015 at 19:46
  • $\begingroup$ There must be a closed form solution to this somewhere ... I remember seeing something like this. Art of Computer Programming 4A? $\endgroup$ Jul 22, 2015 at 21:40
  • 1
    $\begingroup$ I would be inclined to use an adjacency matrix where, for each edge leading to a vertex in the bad set, you put a $t$ instead of a 1. Then calculate the $n$-th power of the matrix, and throw out all the terms where the power of $t$ is more than $M$. The sum of the coefficients of lower-order terms describes paths which visit bad vertices at most $M$ times. (I assume $M$ is the bound on the total number of visits to constrained vertices. If you want a bound on each separately, you would need a different variable for each.) $\endgroup$ Jul 23, 2015 at 4:37

0

Browse other questions tagged or ask your own question.