More merging goodness

	fix adjacency list inline instead of having to rebuild fully
	reweight joined graphs properly

3 files changed, 77 insertions, 26 deletions

diff --git a/source/blender/blenlib/BLI_graph.h b/source/blender/blenlib/BLI_graph.h
index dba02932e02..be5d1f5d10c 100644
--- a/source/blender/blenlib/BLI_graph.h
+++ b/source/blender/blenlib/BLI_graph.h
@@ -76,6 +76,7 @@ void BLI_flagArcs(BGraph *graph, int flag);
 int BLI_hasAdjacencyList(BGraph *rg);
 void BLI_buildAdjacencyList(BGraph *rg);
 void BLI_rebuildAdjacencyList(BGraph* rg);
+void BLI_rebuildAdjacencyListForNode(BGraph* rg, BNode *node);
 void BLI_freeAdjacencyList(BGraph *rg);
 
 int BLI_FlagSubgraphs(BGraph *graph);
diff --git a/source/blender/blenlib/intern/graph.c b/source/blender/blenlib/intern/graph.c
index fce9d0b6d95..32d9f3b91b7 100644
--- a/source/blender/blenlib/intern/graph.c
+++ b/source/blender/blenlib/intern/graph.c
@@ -90,12 +90,6 @@ static void addArcToNodeAdjacencyList(BNode *node, BArc *arc)
 	node->flag++;
 }
 
-void BLI_rebuildAdjacencyList(BGraph *rg)
-{
-	BLI_freeAdjacencyList(rg);
-	BLI_buildAdjacencyList(rg);
-}
-
 void BLI_buildAdjacencyList(BGraph *rg)
 {
 	BNode *node;
@@ -129,6 +123,38 @@ void BLI_buildAdjacencyList(BGraph *rg)
 	}
 }
 
+void BLI_rebuildAdjacencyListForNode(BGraph* rg, BNode *node)
+{
+	BArc *arc;
+
+	if (node->arcs != NULL)
+	{
+		MEM_freeN(node->arcs);
+	}
+	
+	node->arcs = MEM_callocN((node->degree) * sizeof(BArc*), "adjacency list");
+	
+	/* temporary use to indicate the first index available in the lists */
+	node->flag = 0;
+
+	for(arc = rg->arcs.first; arc; arc= arc->next)
+	{
+		if (arc->head == node)
+		{
+			addArcToNodeAdjacencyList(arc->head, arc);
+		}
+		else if (arc->tail == node)
+		{
+			addArcToNodeAdjacencyList(arc->tail, arc);
+		}
+	}
+
+	if (node->degree != node->flag)
+	{
+		printf("error in node [%p]. Added only %i arcs out of %i\n", node, node->flag, node->degree);
+	}
+}
+
 void BLI_freeAdjacencyList(BGraph *rg)
 {
 	BNode *node;
diff --git a/source/blender/src/reeb.c b/source/blender/src/reeb.c
index 71eb550fd21..b3fe465830a 100644
--- a/source/blender/src/reeb.c
+++ b/source/blender/src/reeb.c
@@ -328,7 +328,7 @@ ReebGraph * copyReebGraph(ReebGraph *rg)
 		copyArc(cp_rg, arc);
 	}
 	
-	BLI_rebuildAdjacencyList((BGraph*)cp_rg);
+	BLI_buildAdjacencyList((BGraph*)cp_rg);
 	
 	return cp_rg;
 }
@@ -1063,30 +1063,51 @@ void sortArcs(ReebGraph *rg)
 
 void reweightArc(ReebArc *arc, ReebNode *start_node, float start_weight)
 {
-	float delta_weight = arc->tail->weight - arc->head->weight;
+	ReebNode *node;
+	float old_weight;
+	float end_weight = start_weight + (arc->tail->weight - arc->head->weight);
+	int i;
 	
 	if (arc->tail == start_node)
 	{
 		flipArc(arc);
 	}
 	
+	node = arc->tail;
+	
+	for (i = 0; i < node->degree; i++)
+	{
+		ReebArc *next_arc = node->arcs[i];
+		
+		if (next_arc != arc) /* prevent backtracking */
+		{
+			reweightArc(next_arc, node, end_weight);
+		}
+	}
+	
+	old_weight = arc->head->weight; /* backup head weight, other arcs need it intact, it will be fixed by the source arc */
+	
 	arc->head->weight = start_weight;
-	arc->tail->weight = start_weight + delta_weight;
+	arc->tail->weight = end_weight;
 	
 	reweightBuckets(arc);
 	resizeArcBuckets(arc);
 	fillArcEmptyBuckets(arc);
 	
-	/* recurse here */
+	arc->head->weight = old_weight;
 } 
 
 void reweightSubgraph(ReebGraph *rg, ReebNode *start_node, float start_weight)
 {
-	ReebArc *arc;
-	
-	arc = start_node->arcs[0];
-	
-	reweightArc(arc, start_node, start_weight);
+	int i;
+		
+	for (i = 0; i < start_node->degree; i++)
+	{
+		ReebArc *next_arc = start_node->arcs[i];
+		
+		reweightArc(next_arc, start_node, start_weight);
+	}
+	start_node->weight = start_weight;
 }
 
 int joinSubgraphsEnds(ReebGraph *rg, float threshold, int nb_subgraphs)
@@ -1144,6 +1165,7 @@ int joinSubgraphsEnds(ReebGraph *rg, float threshold, int nb_subgraphs)
 						fillArcEmptyBuckets(start_arc);
 						
 						NodeDegreeIncrement(rg, end_node);
+						BLI_rebuildAdjacencyListForNode((BGraph*)rg, (BNode*)end_node);
 						
 						BLI_removeNode((BGraph*)rg, (BNode*)start_node);
 					}
@@ -1163,16 +1185,20 @@ int joinSubgraphs(ReebGraph *rg, float threshold)
 	int nb_subgraphs;
 	int joined = 0;
 	
-	BLI_rebuildAdjacencyList((BGraph*)rg);
+	BLI_buildAdjacencyList((BGraph*)rg);
 	
 	nb_subgraphs = BLI_FlagSubgraphs((BGraph*)rg);
 	
-	joined |= joinSubgraphsEnds(rg, threshold, nb_subgraphs);
-	
-	if (joined)
+	if (nb_subgraphs > 1)
 	{
-		removeNormalNodes(rg);
-		BLI_rebuildAdjacencyList((BGraph*)rg);
+		joined |= joinSubgraphsEnds(rg, threshold, nb_subgraphs);
+		
+		if (joined)
+		{
+			verifyNodeDegree(rg);
+			removeNormalNodes(rg);
+			BLI_buildAdjacencyList((BGraph*)rg);
+		}
 	}
 	
 	return joined;
@@ -1682,7 +1708,7 @@ void filterGraph(ReebGraph *rg, short options, float threshold_internal, float t
 	if (options & SKGEN_FILTER_SMART)
 	{
 		filterSmartReebGraph(rg, 0.5);
-		BLI_rebuildAdjacencyList((BGraph*)rg);
+		BLI_buildAdjacencyList((BGraph*)rg);
 		filterCyclesReebGraph(rg, 0.5);
 	}
 	
@@ -1698,7 +1724,7 @@ void finalizeGraph(ReebGraph *rg, char passes, char method)
 {
 	int i;
 	
-	BLI_rebuildAdjacencyList((BGraph*)rg);
+	BLI_buildAdjacencyList((BGraph*)rg);
 
 	sortNodes(rg);
 	
@@ -3162,9 +3188,7 @@ ReebGraph *BIF_ReebGraphMultiFromEditMesh(void)
 	/* Filtering might have created degree 2 nodes, so remove them */
 	removeNormalNodes(rg);
 	
-	joinSubgraphs(rg, 1.5);
-	
-	BLI_rebuildAdjacencyList((BGraph*)rg);
+	joinSubgraphs(rg, 1.0);
 	
 	/* calc length before copy, so we have same length on all levels */
 	BLI_calcGraphLength((BGraph*)rg);