From: Matthias Kramm <kramm@quiss.org>
Date: Tue, 1 Dec 2009 01:50:37 +0000 (-0800)
Subject: added graph_find_components() to graph library
X-Git-Tag: version-0-9-1~224
X-Git-Url: http://git.asbjorn.biz/?p=swftools.git;a=commitdiff_plain;h=062138c37383ec48082037f0610b7c8da41f6d0d

added graph_find_components() to graph library
---

diff --git a/lib/graphcut.c b/lib/graphcut.c
index 641fa61..93ff79c 100644
--- a/lib/graphcut.c
+++ b/lib/graphcut.c
@@ -625,6 +625,33 @@ halfedge_t*graph_add_edge(node_t*from, node_t*to, weight_t forward_weight, weigh
     return e1;
 }
 
+static void do_dfs(node_t*n, int color)
+{
+    int t;
+    n->tmp = color;
+    halfedge_t*e = n->edges;
+    while(e) {
+	if(e->fwd->node->tmp<0)
+	    do_dfs(e->fwd->node, color);
+	e = e->next;
+    }
+}
+
+int graph_find_components(graph_t*g)
+{
+    int t;
+    int count = 0;
+    for(t=0;t<g->num_nodes;t++) {
+	g->nodes[t].tmp = -1;
+    }
+    for(t=0;t<g->num_nodes;t++) {
+	if(g->nodes[t].tmp<0) {
+	    do_dfs(&g->nodes[t], count++);
+	}
+    }
+    return count;
+}
+
 #ifdef MAIN
 int main()
 {
diff --git a/lib/graphcut.h b/lib/graphcut.h
index b085770..39b96c0 100644
--- a/lib/graphcut.h
+++ b/lib/graphcut.h
@@ -38,6 +38,7 @@ struct _halfedge {
 
 struct _node {
     halfedge_t*edges;
+    int tmp;
     int nr;
 };
 
@@ -49,6 +50,7 @@ struct _graph {
 graph_t* graph_new(int num_nodes);
 halfedge_t*graph_add_edge(node_t*from, node_t*to, weight_t forward_weight, weight_t backward_weight);
 weight_t graph_maxflow(graph_t*graph, node_t*pos1, node_t*pos2);
+int graph_find_components(graph_t*g);
 void graph_delete(graph_t*);
 
 #endif