The following code implementation counts the number of triangles present in a graph G.
For graph representation JUNG API is used but can be extended/ changed to use any other notation by simple means.
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 |
import java.util.Collection; import java.util.HashSet; import java.util.Iterator; import edu.uci.ics.jung.graph.Graph; public class TriangleFinder { private Graph<Integer, String> g; /** * @return The number of triangles in the graph. */ public int countTriangles() { int count = 0; Collection<Integer> c = g.getVertices(); Collection<Integer> neighb; Collection<Integer> neighbNeighb; Collection<Integer> visitedVertices = new HashSet<Integer>(); Collection<Integer> tempVisitedVertex = new HashSet<Integer>(); for (Iterator<Integer> iterator = c.iterator(); iterator.hasNext();) { Integer vertex = (Integer) iterator.next(); neighb = g.getNeighbors(vertex); neighb.removeAll(visitedVertices); for (Iterator<Integer> iterator2 = neighb.iterator(); iterator2 .hasNext();) { Integer vertexN = (Integer) iterator2.next(); neighbNeighb = g.getNeighbors(vertexN); neighbNeighb.removeAll(tempVisitedVertex); neighbNeighb.removeAll(visitedVertices); neighbNeighb.retainAll(neighb); count += neighbNeighb.size(); tempVisitedVertex.add(vertexN); } visitedVertices.add(vertex); tempVisitedVertex = new HashSet<Integer>(); } return count; } /** * @return the g */ public Graph<Integer, String> getG() { return g; } /** * @param g * the g to set */ public void setG(Graph<Integer, String> g) { this.g = g; } } |
Please post comments for any explanation/ help required. 🙂
Very good site you have here but I was wanting to know if you knew
of any message boards that cover the same topics discussed here?
I’d really like to be a part of community where I can get opinions
from other experienced people that share the same interest.
If you have any recommendations, please let me know.
Kudos!