From d4b646103a6cae433d58bf7e2f4953f81358835b Mon Sep 17 00:00:00 2001
From: Martin Poirier <theeth@yahoo.com>
Date: Mon, 4 Aug 2008 19:12:42 +0000
Subject: Option to hide embedding dots on display Merge internal and external
 filtering in a single loop (solve problems caused by order of filtering) Made
 graph length calculations work on cyclic graphs (it unrolls them)

---
 source/blender/blenlib/BLI_graph.h    |  2 +-
 source/blender/blenlib/intern/graph.c | 50 ++++++++++++++++-------------------
 2 files changed, 24 insertions(+), 28 deletions(-)

(limited to 'source/blender/blenlib')

diff --git a/source/blender/blenlib/BLI_graph.h b/source/blender/blenlib/BLI_graph.h
index 66cf2a22842..89f21b919e2 100644
--- a/source/blender/blenlib/BLI_graph.h
+++ b/source/blender/blenlib/BLI_graph.h
@@ -85,7 +85,7 @@ void BLI_ReflagSubgraph(BGraph *graph, int old_subgraph, int new_subgraph);
 #define SHAPE_RADIX 10 /* each shape level is encoded this base */
 
 int BLI_subtreeShape(BNode *node, BArc *rootArc, int include_root);
-float BLI_subtreeLength(BNode *node, BArc *rootArc);
+float BLI_subtreeLength(BNode *node);
 void BLI_calcGraphLength(BGraph *graph);
 
 void BLI_replaceNode(BGraph *graph, BNode *node_src, BNode *node_replaced);
diff --git a/source/blender/blenlib/intern/graph.c b/source/blender/blenlib/intern/graph.c
index aa899042a58..80d770e1034 100644
--- a/source/blender/blenlib/intern/graph.c
+++ b/source/blender/blenlib/intern/graph.c
@@ -397,57 +397,53 @@ int BLI_subtreeShape(BNode *node, BArc *rootArc, int include_root)
 	}
 }
 
-float BLI_subtreeLength(BNode *node, BArc *rootArc)
+float BLI_subtreeLength(BNode *node)
 {
 	float length = 0;
 	int i;
 
+	node->flag = 0; /* flag node as visited */
+
 	for(i = 0; i < node->degree; i++)
 	{
 		BArc *arc = node->arcs[i];
+		BNode *other_node = BLI_otherNode(arc, node);
 		
-		/* don't go back on the root arc */
-		if (arc != rootArc)
+		if (other_node->flag != 0)
 		{
-			length = MAX2(length, BLI_subtreeLength(BLI_otherNode(arc, node), arc));
+			float subgraph_length = arc->length + BLI_subtreeLength(other_node); 
+			length = MAX2(length, subgraph_length);
 		}
 	}
 	
-	if (rootArc)
-	{
-		length += rootArc->length;
-	}
-	
 	return length;
 }
 
 void BLI_calcGraphLength(BGraph *graph)
 {
-	if (BLI_isGraphCyclic(graph) == 0)
+	float length = 0;
+	int nb_subgraphs;
+	int i;
+	
+	nb_subgraphs = BLI_FlagSubgraphs(graph);
+	
+	for (i = 1; i <= nb_subgraphs; i++)
 	{
-		float length = 0;
-		int nb_subgraphs;
-		int i;
+		BNode *node;
 		
-		nb_subgraphs = BLI_FlagSubgraphs(graph);
-		
-		for (i = 1; i <= nb_subgraphs; i++)
+		for (node = graph->nodes.first; node; node = node->next)
 		{
-			BNode *node;
-			
-			for (node = graph->nodes.first; node; node = node->next)
+			/* start on an external node  of the subgraph */
+			if (node->flag == i && node->degree == 1)
 			{
-				/* start on an external node  of the subgraph */
-				if (node->flag == i && node->degree == 1)
-				{
-					length = MAX2(length, BLI_subtreeLength(node, NULL));
-					break;
-				}
+				float subgraph_length = BLI_subtreeLength(node);
+				length = MAX2(length, subgraph_length);
+				break;
 			}
 		}
-		
-		graph->length = length;
 	}
+	
+	graph->length = length;
 }
 
 /********************************* SYMMETRY DETECTION **************************************************/
-- 
cgit v1.2.3