Grasshopper

algorithmic modeling for Rhino

Hi

I am quite new to graph theory and Spiderweb. I was wondering if there is a way for me to evaluate the betweenness of a graph.

I created directly a dual graph from a series of spaces (no lines are provided), so if I created a graph from cells I already have my dual graph (if I am no wrong). Also, from my understanding, betweenness implies the calculus of n^3 shortest path (where n is the number of nodes).

Thank you in advance.

Claudio

Views: 974

Replies to This Discussion

Hallo Claudio,

1. Betweenness Measurment

please find attached an example based on the betweenness formular given at: 

https://en.wikipedia.org/wiki/Betweenness_centrality

However I would like to point out that this might not be the betweenness formulated by SpaceSyntax so please double check, also SpiderWeb operates on directed graphs so this is also different to SpaceSyntax / depthmap but more general. 

However this has some inpacts on results especialy when working on a grid.

2. Graph generation

If you create a graph from cells than you get a graph where every cell is represented by a vertex the edges show which cell is connected to which other cell....

3. Computational Complexity

Yes V^3 seams about right, as in this case DIJKSTRA is implemented with a complexity of V^2 (so not optimal as described here: https://de.wikipedia.org/wiki/Dijkstra-Algorithmus) and than you have to do it for every node.

However why bother? Are you planning on running the city of London with SpiderWeb? Don't download Depthmap X. Depending on the Graphtype you use in SpiderWeb graphs are limited to around 65.000 vertices anyway. SpiderWeb is intendet for generative not for analytical purposes.

Hope that helps.

Richard

Attachments:

Richard

Many thanks for your reply, it is very helpful. I actually used the cross reference but I wasn't entirely sure my algorithm was consistent with the concept of betweenness in centrality, even if I checked wiki and UNA help to better get into that.

Then, YES!, I am using Spiderweb for performing generative design. I am running Octopus on a hutong-like urban fabric superblock in order to understand how internal courtyards can contribute to public space when connected to the streets through openings. If many courtyards are connected together, they can create alternative routes (therefore, their betweenness increases).

In fact, only courtyards' betweenness is evaluated as a fitness criteria (I am still wondering if this is meaningful in order to achieve my purpose, but at the moment my logic says 'yes'). Other fitness criteria are volume and courtyard irradiation. At the moment I am not providing enough entrances, therefore my fitness landscape has very tight local optimums which are very hard to be achieved.

So, yes, I didn't mean to run only one analysis on a huge network (e.g. London), but to create and quickly evaluate different design possibilities on a small graph (my graph spans between 200 and 300 vertices - please see attached).

Thank you.

Claudio

Attachments:

HAllo Claudio,

if you are using the ShortestPath between component and are using only starting / endpoints of the courtyards than the betweenness is only for the paths between between these starting points. For complete betweenness you would need to include also the other vertices and as SpaceSyntax say a walking distance radius around your  development.

And something is wrong with your color assignment if it should represent betweenness because a blue next to a red which is not a dead end makes no sense... maybe you could post that part of the script.

How does betweeness add to your fitness? Just wondering maybe there is a faster version to approximate it which would work better with your Octopus ....

Hello Richard

I attached that part of the script. As you can see, the evaluation is made in two steps. Firstly, all the (private) courtyards which are not connected to the streets are separated from those which are connected (public courtyards).

Then, 'betweenness' is calculated throughout the public spaces, but only the values referred to the public courtyards are being fed into the Octopus' fitness criteria. However, I included the street in the calculus since, from my understanding, all the possible paths have to be considered. In fact, if an alternative route is open throughout the courtyards, their 'walk-on values' should increase because of it can be the shortest path for some of these combinations.

Yes, the script is a bit heavy and requires time to be processed (mean evaluation time is about 7 seconds). However, my lack of experience makes me not seeing an alternative criteria atm. Suggestions would be helpful.

Thank you again for your help.

Claudio

Attachments:

Hello Claudio,

Can't really say but something was wrong with your computation. Added a correct Version with some simplifications (improvement of speed). As you can see in the image most of your courtyards have a low betweenness which is not surprising as they are dead ends...

The four crossings at the center show the highest values. I think you have to do two things:

1. Extend the Graph into the surrounding area, at least 1 * Walking distance e.g. 500m, otherwise this will make no sense. 

2. Adapt your fitness function, if you are only summing up the total betweenness values a solution with more (much more) courtyards will be better than a solution with less courtyards.

As for Speed:

The only way to speed it up is to use VB/C# Script component. SpiderWeb.dll can be imported. For more information see:

http://www.gbl.tuwien.ac.at/_docs/GrasshopperScriptum/lib/002_Spide...

http://www.gbl.tuwien.ac.at/_docs/SpiderWebLibraryDoc/index.html

Attachments:

Richard

Many thanks for your help.

The first point actually avoids high differences between the streets. In fact it looked pretty weird to have a gap bigger than 50% between central and peripherical ones.

The second point, well, it was pretty obvious. Thank you for pointing it out. I'll definitely take a look at implementing the dll in C#.

Thank you.

Claudio

denanda,

maybe you could do a post showing final result here...

if you have questions regarding the c# implementation or vb.net please ask.

RSS

About

Translate

Search

Photos

  • Add Photos
  • View All

Videos

  • Add Videos
  • View All

© 2024   Created by Scott Davidson.   Powered by

Badges  |  Report an Issue  |  Terms of Service