implementing an simple undirected Graph algorithm

[Mubo]

Hi guys,

these days Social Networking Sites are spreeding faster around the world and they getting more users into their networks daily.

My question ist.
How to implement an algorithm as simple undirected graph in social networking site and how to search and find special groups who know each other in order to place adverstisement on it, after determining how well connected they are.

Nodes/vertex represent one person und one edge connect to two people when they know eacht other. One edge has got edgeweight of integers from 1 to 100. Means it is a number written on the edge, which say about it´s weight. there is knowledgegrade which says one two people know each other well, edge which connects them has got very high grad integer.

I would be very grateful if you can help me how to start these algorithm.

[JamesCherrill]

One class for nodes(personName), one class for edges(node1, node2, weight) . Analysis class with methods to traverse the graph to find what you're looking for. Start with a really trivial case and work upwards. Just get stuck in and see how it goes.

[Mubo]

One class for nodes(personName), one class for edges(node1, node2, weight) . Analysis class with methods to traverse the graph to find what you're looking for. Start with a really trivial case and work upwards. Just get stuck in and see how it goes.

Thanks james.

Youre right. The one for edges(node1,node2, weight)

Public class Edge
{


public final int node1;

public final int node2;
public final int weight;

public Edge( int n1, int n2, int w )
{
	if (n1 < n2) {
		node1 = n1;
		node2 = n2;
	} else {
		node1 = n2;
		node2 = n1;
	}

	weight = w;
}

/**
 * comparig  edges if they are equal
 * two edges  are equal , when their endedges are equal
 */
public boolean equals( Object other )
{
	if (other instanceof Edge) {
		Edge o = (Edge) other;

		return ((node1 == o.node1 && node2 == o.node2)
			|| (node1 == o.node2 && node2 == o.node1))
			&& (weight == o.weight);
	} else {
		return false;
	}
}



public int hashCode()
{
	assert node1 < node2;

	return (node1 << 18) + (node2 << 4) + weight;
}

 
public String
toString()
{
	return "(" + node1 + "," + node2 + "," + weight + ")";
}

} // class Edge

but the other class muss determine how to find special groups and how is their knowlegegrad,
so the second class is called Group Finder {
and this is where i have to implement simplest heuristic algorithm for finding groups.
public GroupFinder( int numNodes, Set<Edge> edges ) {
}
public ArrayList<Integer> findGroup1() {
}
public ArrayList<Integer> findGroup3() {
}
i don't really know how to implement it efficiently,,,,,,, specially the set parameter,,,,,,,,,,,,,
so could please give the best way to go further
thanks james

[JamesCherrill]

Sorry man, I'm no graph expert. You seem to have a good class/data structure to work with now, but as for the most efficient algorithm - you'll need someone else to help. Sorry.

[VernonDozier]

Code tags please.

[code=JAVA] // code here

[/code]

You have a few tasks. One, set up your overall mathematical plan. That includes setting up a sample graph, making rules for what the graph represents, with specific English explanations of what the node/edge values mean, and what it means to be "connected". Sort of sounds like a "Six Degrees of Kevin Bacon" project? I'm not entirely sure. Or more likely one of those old "Friends And Families" phone plans that everyone hated, but were probably very interesting mathematically. Then you program it.

But you can't program it at all, not even to start, till you figure out the Graph Theory/mathematical part, and decide exactly what you want to do, which is a very large part of this project. I would get as far away from your Java IDE as you can for now. Right now your job is to doodle on paper and get the formulas. James is right. Start with the trivial case and work upwards.

Ignoring my own advice completely for the moment and looking at the code, I notice you have node as an integer in your code. There must be much more information to store in a node?

[JamesCherrill]

Re Nodes. Yes, more than just an int, I think this should be a proper class. In particular, I suspect it will be useful to have each Node hold a list of the Edges that connect to it. That way you will be able to navigate from Node to Node via the Edges. You can easily populate that list from the Edge constructor, provided that the Nodes are created before the Edges.