diff options
author | Martin Poirier <theeth@yahoo.com> | 2008-07-16 01:07:13 +0400 |
---|---|---|
committer | Martin Poirier <theeth@yahoo.com> | 2008-07-16 01:07:13 +0400 |
commit | db5a83d083c1517316ff94a011c4a21e0ada7d34 (patch) | |
tree | 57f4c45185a2c8ac998134c820c083352505ec60 /source/blender/blenlib | |
parent | 08039ef38fa6d39f756860032659cc3678137ced (diff) |
More merging goodness
fix adjacency list inline instead of having to rebuild fully
reweight joined graphs properly
Diffstat (limited to 'source/blender/blenlib')
-rw-r--r-- | source/blender/blenlib/BLI_graph.h | 1 | ||||
-rw-r--r-- | source/blender/blenlib/intern/graph.c | 38 |
2 files changed, 33 insertions, 6 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; |