java - graph algorithm for (economic) share graph -

-

hi graph theory experts :)

i'm facing algorithmic problem cannot solve myself.

i have find indirect shares each company each other in directed graph containing direct shares (see image simple example).

i have start directed graph nodes companies , edges direct shares between these companies. algorithm has append indirect shares between nodes edges (this includes adding new edges graph during algorithm).

an indirect share defined product of intermediate direct shares. if there nodes a, b , c in graph, there 1 indirect share, 1 c.

indirect(a, c) = 100% * 80% = 1 * 0.8 = 0.8 = 80%

now need algorithm computes shares whole graph. there no specific starting point in graph, , may contain variety of circles of each size (in example there 1 "direct" circle between c , d) , multiple paths between pair of nodes (like paths c e).

it helpful if me out pseudo code or description of possible algorithm. searched algorithms in graph theory books , on internet, can find standard algorithms finding shortest path, paths, or visiting nodes of graph. cannot find mechanism calculate kind of mathematical combination of graph edge weights.

example share graph

let operationalise ownership looking @ happens if given company receives $1, , money received passed on shareholders according ownership. reckon proportion of ownership final proportion of money received when passing of money around has died down.

it easiest account first of total money received each company, , give set of linear equations solution tell total amount of money received every company when $1 sent in first instance company a.

suppose example , b own 1/2 of each other. = 1 + b/2 , b = a/2, total amount of money received a, , b total amount of money received b - because $1 , 1/2 of whatever b sees, , b 1/2 of sees. solves = 1 + a/4 or = 4/3 , b = 2/3. if follow each step of distribution receives 1 , sends 1/2 b, sends 1/4 a, sends 1/8 b sends 1/16 a... gets 1 + 1/4 + 1/16 + ... = 4/3.

so sees total of 4/3 , b sees total of 2/3 - , b have pass on 1/2 of receive, ends 2/3 , b ends 1/3, makes sense - incoming $1 accounted for.

if take distribution of money indicative of ownership, owns 2/3 of itself, , b owns other 1/3.


Comments

Post a Comment

Popular posts from this blog

SVG stroke-linecap doesn't work for circles in Firefox? -

-
i've got problem svg stroke-linecap attribute. i've got circular progress bar in angularjs , set outer circle (blue one) have rounded "ends". @ fiddle . <svg ... height="130" width="130"> <!-- ngif: background --> <circle ... ng-if="background" fill="#fff" class="ng-scope" stroke-width="13" stroke="#cc3399" r="57.5" cy="65" cx="65" stroke-linecap="round" /> <!-- end ngif: background --> <circle ... fill="none" stroke-dashoffset="36.12831551628261" stroke-dasharray="361.28315516282623" stroke-width="13" stroke="#432db3" stroke-linecap="round" r="57.5" cy="65" cx="65" transform="rotate(-89.9, 65, 65)" /> </svg> how can that? ...
Read more

routes - Laravel 4 Wildcard Routing to Different Controllers -

-
realizing i'm going take beating this, have several questions "best practices" when constructing laravel route. do laravel routes run "first come first serve" top bottom? if route found, pass control controller (or perform action) , terminate? i have part of application acts url shortner. so, route looks this: route::get('/{id}', array('as' => 'home.text', 'uses' => 'homecontroller@text'), function($id){ //make sure id exists before pushing controller. if (storage::where('shortcode','=', $id)->count() > 0) { // route found } }); how can improved? one, i'm not sure how pass processing on controller conditionally.. sort of controller::make() ..? 3) there better way in laravel check if record exists versus doing mode::where('column','=','value')->count() 4) have legacy urls http://url.com/?...
Read more

cross browser - XSLT namespace-alias Not Working in Firefox or Chrome -

-
i transforming xhtml xhtml, need xslt stylesheet part of resulting document (the stylesheet contained in <script type"text/template"> element. using the xsl:namespace-alias instruction, works fine in ie, fails in both chrome , firefox. here relevant code: <xsl:output doctype-system="about:legacy-compat" omit-xml-declaration="yes" indent="yes" method="html" media-type="application/xhml" encoding="utf-8"/> <xsl:namespace-alias stylesheet-prefix="wxsl" result-prefix="xsl" /> <xsl:template match="head"> <!-- code omitted clarity --> <script type="text/template"> <wxsl:stylesheet version="1.0" xmlns:xsl="http://www.w3.org/1999/xsl/transform" xmlns="http://www.w3.org/1999/xhtml" xmlns:xhtml="http://www.w3.org/1999/xhtml" xmlns:eli="local"> ...
Read more