Graph Search Algorithm
Hello
I have a symmetric graph and a distance variable 1 or 2 etc:
| A | B | C | D
--
A | 0 | 2 | 4 | 1
B | 2 | 0 | 3 | 5
C | 4 | 3 | 0 | 1
D | 1 | 5 | 1 | 0
I wanted to find different Graph Edges that are on the same Set for a give distance variable. For the Distance Variable 1, the Set will be {A, D,C}. For Distance Variable 2, it will be {A, B, C, D}, the same for Distance variable 3, 4 and 5.
Please, I need some tips on how to go about it. What is the best algorithm to solve such problem? Is there any Java Graph API for that?
Thanks,
Jona_T
[625 byte] By [
Jona_Ta] at [2007-11-27 6:06:46]
> i wanted to find different Graph Edges that are on the same Set for a give distance variable
do you mean you want to find which node have edge with specified distance?
A B C D
A 0 2 4 1
B 2 0 3 5
C 4 3 0 1
D 1 5 1 0
eg.
edge with length (distance) = 1 owned by A, C, D
edge with length (distance) = 2 owned by A, B
edge ... = 3 owned by B, C
edge 4 owned by A, C
edge 5 owned by B, D
(but you said edge 2 owned by A, B, C, D C!@#$%^&*)
Hello,
No, what I want are nodes that a connected with one another given a given distance. The distance between the nodes should be less than or equal to the given distance. Some thing like a Clique finder.
Eg;
Given a Symmetric Matrix;
A B C D E
A 0 1 3 5 1
B 1 0 4 3 2
C 3 4 0 1 3
D 5 3 1 0 4
E 1 2 3 4 0
The Set for a distance less than or equal to 1 will be {A,B,E} , {C,D}.
The Set for a distance less than or equal to 2 will be {A,B,E} , {C,D}.
The Set for a distance less than or equal to 3 will be {A,B,C,D,E}
Thanks,
Jona_T
Message was edited by:
Jona_T
null
sorry, i don't understand... A B C D EA 0 1 3 5 1B 1 0 4 3 2C 3 4 0 1 3D 5 3 1 0 4E 1 2 3 4 0what does {A, B, E} means ? do {A, B, E}, {A, B}, {B, E}, and {A, E} are equal?
Hello,
{A,B,E} means that all the nodes are connected. From the last graph, if we transverse from the starting point (0,0) which is A and our distance 1, then node B is connected to A because the distance is 1. The same as node E. When I am at node B, I will check if is further connected to other node by taken the column index as the next row and search if we can get a node with a distance less than or equal the distance we are searching (threshold).
I wrote a small code but it is basically wrong:
public void getGraphSets(Double [][]adjaMatrix, Double []Elements, int thres) {
/* The symmetric matrix is stored in adjaMatrix, the nodes are store in Double [] Elements (here ,I am using double values instead of Chars), int thres is the given distance or threshold */
Set <Double> Indexes = new LinkedHashSet <Double>();
List <Double[]>StoreAll = new ArrayList<Double[]>();
//Double []SetNums = new Double[2];
int col2 = 0;
int row2 = 0;
int temp = 0;
int count = 0;
for(int row = 0; row < adjaMatrix.length; row++) {
for ( int col = 0; col < adjaMatrix[row].length; col++){
if( row < col) { //only the upper diagonal
if(adjaMatrix[row][col] <= thres ) {
Indexes.add(Elements[row]);
Indexes.add(Elements[col]);
temp = col;
for(row2 = temp; row2 < adjaMatrix.length; row2++) {
for(col2 = 0; col2 < adjaMatrix[row2].length; col2++) {
if(adjaMatrix[row2][col2] <= thres) { //check if there is further node connected
Indexes.add(Elements[col2]);
row2 = col2;
}
}
}
}
}
}
}
Indexes.clear();
}
Okay, it's more clear...
your code seems ok, but you clear the result instead of save/print it.
//...
// you already get your set, why you clear it without store it in a set list?
// maybe you try to save it to StoreAll variable, but will cause Generic prob
Indexes.clear();
//...
import java.io.RandomAccessFile;
import java.io.IOException;
import java.util.StringTokenizer;
import java.util.NoSuchElementException;
public class routing{
public static void main( String args[] ){
routing app = new routing( args[ 0 ] );
}
public routing( String inFile ){
try{
RandomAccessFile file = new RandomAccessFile( inFile, "rw" );
String tmp = file.readLine(); int i = 0;
while( tmp != null ){ tmp = file.readLine(); i++; }
file.seek( 0 ); tmp = file.readLine();
int graph[][]; graph = new int[ i ][ i ]; i = 0;
while( tmp != null ){
StringTokenizer sT = new StringTokenizer( tmp, " " ); int j = 0;
while( sT.hasMoreTokens() ){ graph[ i ][ j++ ] = Integer.parseInt( sT.nextToken() ); }
i++; tmp = file.readLine();
}
file.close();
dijkstra( graph );
}
catch( IOException io ){ System.err.println( io.toString() ); System.exit( 1 ); }
catch( RuntimeException re ){ System.err.println( re.toString() ); System.exit( 1 ); }
}
public void dijkstra( int graph[][] ){
int d[] = new int[ graph.length ];
int dC[] = new int[ graph.length ];
int p[] = new int[ graph.length ];
for( int i = 0; i < graph.length; i++ ){ d[ i ] = 100; dC[ i ] = 100; p[ i ] = -1; }
d[ 0 ] = 0; dC[ 0 ] = 0;
int i = 0, min = 200, pos = 0; //You can change the min to 1000 to make it the largest number
while( i < graph.length ){
//extract minimum
for( int j = 0; j < dC.length; j++ ){
if( min > d[ j ] && dC[ j ] != -1 ){
min = d[ j ]; pos = j;
}
}
dC[ pos ] = -1;
//relax
for( int j = 0; j < graph.length; j++ ){
if( d[ j ] > graph[ pos ][ j ] + d[ pos ] ){
d[ j ] = graph[ pos ][ j ] + d[ pos ];
p[ j ] = pos;
}
}
i++; min = 200;
}
for( int j = 0; j < p.length; j++ ){
System.out.print( p[ j ] + " " );
}
System.out.print( "\n" );
for( int j = 0; j < d.length; j++ ){
System.out.print( d[ j ] + " " );
}
System.out.print( "\n" );
}
}
you need disjktra algorithm...
disjktra? is it a shortest pathfinding algo like A*?he/she is looking for subgraph that connected with specified length (equal or less than distance) of edge.
hi Jona,
in this code: temp = col;
for(row2 = temp; row2 < adjaMatrix.length; row2++) {
for(col2 = 0; col2 < adjaMatrix[row2].length; col2++) {
if(adjaMatrix[row2][col2] <= thres) { //check if there is further node connected
Indexes.add(Elements[col2]);
row2 = col2;
}
}
}
looks like you try to forward the searching... but you do it only once forwarding. you need to change your iteration control.
perhaps its more easy to do forwarding in recursive:
i change your matrix from Double[][] to int[][], and just leave about the naming of nodes(Elements) first.
// return moved to result parameter for recursive purpose
private static void getConnected(List result, int[][] adjMtx, int src, int d) {
for (int i = src + 1; i < adjMtx[src].length; i++) {
if (adjMtx[src][i] <= d) {
if (!result.contains(src)) result.add(src);
if (!result.contains(i)) result.add(i);
getConnected(result, adjMtx, i, d);
}
}
}
public static List getGraphSet(int[][] adjMtx, int d) {
List setOfSet = new ArrayList();
for (int src = 0; src < adjMtx.length; src++) {
List aSet = new ArrayList();
getConnected(aSet, adjMtx, src, d);
if (aSet.size() > 0) setOfSet.add(aSet);
}
// TODO : discard subgraph
return setOfSet;
}
well then his question is too vague.. i still did'nt understand..
In the OP's graph every node is connected to every other.I don't know if this is a "well known" problem but, if we remove every link that is bigger than the threshold, then the problem reduces to finding the connected components of the graph.
Hello Shanidata and others,
The problem is finding a maximum connected subgraph. It is similar to finding clusters in a weighted graph if a threshold is given. The solution of Shadinata is quite close. The problem is in the method getGraphSet();
public static List getGraphSet(int[][] adjMtx, int d) {
List setOfSet = new ArrayList();
for (int src = 0; src < adjMtx.length; src++) {
List aSet = new ArrayList();
getConnected(aSet, adjMtx, src, d);
if (aSet.size() > 0) setOfSet.add(aSet); //the problem point
}
// TODO : discard subgraph
return setOfSet;
}
Assume I have the following matrix;
A B C D E
A 0 1 3 6 2
B 1 0 2 5 1
C 3 2 0 3 1
D 6 5 3 0 4
E 2 1 1 4 0
Given 1 as the threshold, I will only have one set or cluster , namely [A,B,C,E] but with the getGraphSet method above, I got, 3 sets, namely, [ [A, B, E], [B, E], [C, E]].
When the iterating through adjMtx, if we are at index = 0,
and getConnected is called; private static void getConnected(List <Integer> result, Integer[][] adjMtx, int src, int d)
it takes the column index (int src) of the element found as the new row index and makes recursive function call. The indexes of the Element found are stored in aSet. (The implementation is correct)
When the index of adjMtx is 1, we end up visiting some nodes (and storing their indexes) which we have visited before through recursive functions call.
If it is possible to differentiate nodes already visited and those not when iterating through adjMtx, then my problem will be solved.
Thanks,
Message was edited by:
Jona_T
fix 1:
private static void getConnected(List result, int[][] adjMtx, int src, int d) {
for (int i = 0; i < adjMtx[src].length; i++) {
if (adjMtx[src][i] <= d && src != i) {
if (!result.contains(src)) result.add(src);
if (!result.contains(i)) {
result.add(i);
getConnected(result, adjMtx, i, d);
}
}
}
}
result = [[ABEC] [BAEC] [CEBA] [EBAC]] (which actually same)
complete ver (using generic):
import java.util.*;
public class Graph1 {
// return moved to result parameter for recursive purpose
private static void getConnected(List<Integer> result, int[][] adjMtx, int src, int d) {
for (int i = 0; i < adjMtx[src].length; i++) {
if (adjMtx[src][i] <= d && src != i) {
if (!result.contains(src)) result.add(src);
if (!result.contains(i)) {
result.add(i);
getConnected(result, adjMtx, i, d);
}
}
}
}
public static List<List><Integer>> getGraphSet(int[][] adjMtx, int d) {
List<List><Integer>> setOfSet = new ArrayList<List><Integer>>();
for (int src = 0; src < adjMtx.length; src++) {
// check if source already in setOfSet
boolean alreadyExists = false;
for (List<Integer> e : setOfSet) {
if (e.contains(src)) {
alreadyExists = true;
break;
}
}
if (!alreadyExists) {
List<Integer> aSet = new ArrayList<Integer>();
getConnected(aSet, adjMtx, src, d);
if (aSet.size() > 0) setOfSet.add(aSet);
}
}
return setOfSet;
}
public static void main(String[] args) {
int[][] adjMtx = {
{0, 1, 3, 6, 2},
{1, 0, 2, 5, 1},
{3, 2, 0, 3, 1},
{6, 5, 3, 0, 4},
{2, 1, 1, 4, 0}
};
char[] names = { 'A', 'B', 'C', 'D', 'E' };
List<List><Integer>> l = getGraphSet(adjMtx, 1);
List<List><Character>> lc = new ArrayList<List><Character>>();
for (List<Integer> e : l) {
List<Character> lce = new ArrayList<Character>();
for (Integer eie : e) lce.add(names[eie]);
lc.add(lce);
}
System.out.println(lc);
}
}
?...
List < List < Integer > > prints List<List><Integer>> in this reply
Message was edited by:
j_shadinata
> List < List < Integer > > prints List<List><Integer>> in this reply
That's the forum's "self closing angle bracket" bug. If you want to write something like:List<List><Integer>> setOfSet = new ArrayList<List><Integer>>();
then you have to use < instead of <. This applies to every instance of < both inside the[code] tags and outside.
I thought of quite a different approach to this problem: building a forest (I think that's the term) from the adjacency entries. The forest is built from the bottom up. First the original graphs nodes are added (they constitute the leaves of the forest). Then each adjacency entry is added from the smallest to the biggest in the following fashion.
* The "top" ancestors (so far) of the leaves being connected are determined.
* If they are the same, the adjacency entry is added as the parent of this node
* If they are different, the adjacency entry is added as the common parent of both nodes.
While it is being built the forest keeps track of the currently parentless nodes.
Once the forest has been built it is an easy matter to determine the components for any given threshold: for each of the parentless nodes you work down its tree until you encounter a node whose value is less than or equal to the threshold. The leaves under this node constitute one of the components being sought.
The resulting code is more verbose than yours. (Not polished, and not even thoroughly checked). But such an approach might be useful if the components have to be determined for a large number of different thresholds: the forest only has to be constructed once.
[Edit] The middle step of the three listed is not necessary. In that case the adjacency infomation contributes nothing and can be discarded. This greatly reduces the size of the resulting data structure and allows for graphs with thousands of nodes to be analysed.
Hello,
Thanks for your efforts. I am sorry that I was not precise enough in my last reply.
The answer for the adjacency matrix should be [[ABEC]] which is a set or any of the permutation (the order of the char do not matter) , and not [[ABEC], [BAEC]] which are two sets. The Set [ABEC] and [BAEC] are the same subgraph, so, it will be either the later or the former.
I will work hard to see if I can correct the problem, but If you have a better idea on how to do it that will be fine.
Jona_T
see 14th reply and remove '>' at every List<List><Integer>> to List<List<Integer>>.This forum automatically add '>' when it meet with another '<'
Hello,
I removed the additional "<" and ran the program before my last reply. It still gave me 2 similar sets of different permutations instead of 1. Is there any way we can check if a permutation of a set already exits?
// check if source already in setOfSet
boolean alreadyExists = false;
for (List<Integer> e : setOfSet) {
if (e.contains(src)) { // Can we check for different permutations of the set, eg, [A,B,E,C] = [A,B,C,E] = [B,C,E,A] etc. ?
alreadyExists = true;
break;
}
}
Thanks a lot,
Jona_T
Hello Shadinata,Your program actually works. The problem was on my side and I have corrected it. By now you must have received your dukes.Thanks for the time spent.Jona_T
