Project Manual
Contents
1. 1 Node2 2 5 The sofware will calculate and return the followings a Minimum Distance between the node pair b Maximum Flow between the node pair c If the node is connected to all other nodes of the network 6 By clicking on the CapRelEst the program will run a simulation and returns the capacity reliability estimation 7 Here is how the result look like for the sample graph at one of the runs Select Nodes Vertex from Node0 0 x Node12 12 Node0 0 Node1 1 Vertex to Node12 12 v Node10 1 Node2 2 Node7 7 Distance 14 0 o g T 3 amp 3 z z ib a Os Be Node3 3 Max Flow 3 SNode1 812 8 3 10 at mz Eeti wr 2 F fa w50 99 S gAs YNodeke g 4 gt 126 A 3 Ya Is Graph Connected Yes Node14 14 pe 2 4 og eq 8 Node6 6 a 4 st Se 146Ww 2 0 oj Node11 11 Node9 9 CapRelEst 0 267 11 7 How to install the project To run the program on Windows or Linux you need to have java run time environment JRE 1 6 installed To install the project download the binary files at the following address http www4 ncsu edu sazizza 787 project sna sna 1_ 0 source jar unzip the compressed file into a folder 7 1 Run on Windows Before running the project on windows set the JAVA HOME in windows En vironment Variables or open run bat with notepad and change the line pointing to your java home directory by removing REM from the2. the ability to visualize your work SNA s network visualization takes advantage of the great visual features of Jung library You can use the Visual Demo class in SNA as a user interface for implementing most of the algorithms discussed so far Here is a sample view of what SNA is able to provide Select Nodes Vertex from Node0 0 v Node12 12 Vertex to Node12 12 v Node10 16 Node7 7 Distance 14 0 Max Flow 3 Os g Node3 3 4 Node tga 8 he s at wr k aw 93 9 gAs Node ep w gt a amp w Cya Is Graph Connected Yes Nodet4 14 lt pe lt Vv HA 4 r Be 8 Node6 6 N s g 5 gt esw 0 oY Node11 11 Nodeg 9 Cap Rel Est 20 267 6 An extended example Implementation of all the methods and algorithms available through the software is provided here using an extended example As all the necessary commands have been discussed in the previous sections here we only introduce a case for which the creating is via reading from file and implementing the algorithm is by using the interface 1 Create a properties file in your project directory the name of the file can be exam1l properties The sample of the file for a 15 node graph is provided in the appendix 2 Run Visula Demo java file 3 From the first combo box choose the desired source origin node From the second combo box choose the desired sink destination node 10 Node0 0 Node1
3. SNA A tool for Stochastic Network Analysis CE737 Course Project Shahrzad Azizzadeh 5 5 2010 Abstract This document is the user manual to the SNA Stochastic Network Analysis tool It provides complete information on how to use the system as well as description of tools and algorithms which are provided in the software The Examples provided in this tutorial are all tested properly by the software Contents 1 Introduction 3 2 SNA s Technology Dependencies 4 3 SNA Network Basics 5 3 1 How to Create a network 00 4 5 3 1 1 Creating a network manually 5 3 1 2 Reading a network from fille 6 4 Working with algorithms 7 4 1 Connectivity 2 2 2 0 200 7 4 2 Shortest Paths sto Oe ek ee es 7 4 3 Max Blow spad amp ones ale OA ROS ee eee s 8 4 4 Capacity Reliability Estimation 2 8 5 Network Visulalization 9 6 An extended example 10 7 How to install the project 12 7 1 Run on Windows 2 00 020004 12 Ta Ruan ont DNX sa ea ee ey ae ea A SS eck Gite et ee 12 8 Appendix 1 A Sample Data set 12 1 Introduction SNA is a software for stochastic flow network analysis It enables the user to ac complish basic and more advanced network analysis under uncertain conditions The software is designed and implemented for audiences majoring in math and engineering Background on network and graph analysis will help in using the system but the manua
4. e or False e Graph Capacity If the data is not random provide it here e Graph Weight Edge weights go here Probability Distribution If the capacity data is probabilistic provide the distributions here e Demand Mean The mean of demand of the network e Demand Sigma The standard deviation of demand of the network Here is a sample set of data for properties file of a network with 5 nodes Graph_ Nodes Node0 Nodel Node2 Node3 Node4 Random_ Capacity True Graph_ Capacity Null 6 Null Null Null Null Null 3 3 Null Null Null Null 3 Null Null Null Null Null 6 Null Null Null Null Null Graph_ Weight Null 1 Null Null Null Null Null 1 2 Null Null Null Null 1 Null Null Null Null Null 4 Null Null Null Null Null Comment N Normal E Exponential V uniform Probability _ Distribution Null N 6 1 Null Null Null Null Null U 2 4 U 2 4 Null Null Null Null E 3 Null Null Null Null Null N 6 1 Null Null Null Null Null Demand_ Mean 2 5 Demand_ Sigma 0 5 4 Working with algorithms After creating a network using one of the methods introduced earlier you can try some algorithm on your network The following will show you how you can run these algotithms in the software 4 1 Connectivity There are a lot of explorations you can do using this tool connectivity of a pair of node connectivity of the over all network and etc As an example we
5. following statement For example change REM set JAVA_HOME C Program Files Java jdk1 6 0_ 18 to set JAVA HOME lt YOUR JAVA HOME DIRECTORY gt after modifying run bat file simply execute the file by double clicking or using Command Prompt 7 2 Run on Linux Make sure that JRE 1 6 is installed and java bin directory is added to system PATH variables then run sh by either one of these commands run sh sh run sh 8 Appendix 1 A Sample Data set Sample properties file data set for the discussed network Comments 15NodeConnectedNetwork N Normal E Exponential U uniform Probability Distribution Null U 0 3 N 10 1 5 Null Null Null Null Null Null Null Null Null Null Null Null U 0 3 Null N 8 1 Null Null Null Null Null Null Null Null Null Null Null Null Null Null Null N 18 2 Null Null Null Null Null Null Null Null Null Null Null Null Null Null Null N 3 0 5 Null N 3 0 5 Null N 12 2 Null Null Null Null Null Null Null Null Null Null Null E 3 1 Null N 2 0 25 Null Null Null Null Null Null Null Null Null Null Null Null Null Null E 3 1 Null Null Null Null Null Null Null Null Null Null Null Null Null Null Null N 3 0 5 N 3 0 5 Null Null Null Null Null Null Null Null Null Null Null Null Null Null Null N 3 1 Null Null Null Null Null Null Null Null Null Null N 3 0 5 N 5 1 Null U 3 6 Null N 6 12 2 Null N 7 2 N 8 1 Null Null Null Nu
6. have provided the code to investigate whether a given node of the network is connected to all the other nodes GraphGenerator lt Node CapacitatedLink gt gg PropertyFileGraphGenera tor getInstance CapacitatedNetworkGraph lt Node CapacitatedLink gt cng gg getGraph ConnectivityLabeler lt Node CapacitatedLink gt cl new ConnectivityLabeler lt Node CapacitatedLink gt System out println Is Graph Connected cl isConnected cng cng get Vertex fromNode 2 Ves No System out println Number of Nodes fromNode is disconnected from cl disconnectedNodesCount cng cng get Vertex fromNode Nodes System out println Number of Nodes fromNode is directly discon nected from cl disconnectedNodesDirectlyCount cng cng get Vertex fromNode Nodes 4 2 Shortest Path To calculate the shortest path between a pair of nodes using Dijkastra s algo rithm you can use the following sample code The transformer is used to return the links weight GraphGenerator lt Node CapacitatedLink gt gg PropertyFileGraphGenera tor getInstance CapacitatedNetworkGraph lt Node CapacitatedLink gt cng gg getGraph Transformer lt CapacitatedLink Double gt wTransformer new Transformer lt CapacitatedLink Double gt public Double transform CapacitatedLink link return link getWeight E DijkstraShortestPath lt Node CapacitatedLink gt spAlgorithm new DijkstraSh
7. l is complete enough to help the users not familiar with graph theory as well Stochastic network analysis is used to describe the behavior of many com plex systems including lifeline networks The analysis of the performance of such networks should be done under uncertainty Uncertainties stem from the natural variations in the availability of network components and due to failures degradations Also in real world networks usually partial information is pro vided about the demand in the system and it may also follow a distribution other than being a completely known value These issues reveal the need to a tool which gives the opportunity to perform network analysis under uncertainties In addition to the basic famous network analysis problems such as shortest path and connectivity analysis this tool estimates more advance network met rics such as capacity reliability of the system under uncertainties conditions Also this tool provides good visualization capabilities The software is based on two different yet interacting tools e Monte Carlo Simulation e Network Analysis tool The uncertainty analysis is done by means of Monte Carlo simulation The results of the simulations are passed to the network analysis tool as the input data The following figure depicts the high level architecture of SNA Node Capacitated Link Capacitated Network Graph Distance Shortest Path Simulator Random Factory Graph Pro
8. ll Null Null Null Null U 3 6 Null Null N 5 1 Null Null Null Null Null Null Null Null Null Null Null Null Null Null Null N 3 0 5 N 2 0 25 Null Null Null Null Null Null Null Null Null Null Null Null Null Null Null U 2 4 Null Null Null Null Null Null Null Null Null Null Null Null Null Null Null Null Null Null Null Null Null 2 Null Null Null Null Null Null Null Null Null Null Null Null Null N 18 2 Null Graph_ Capacity Null 1 2 Null Null Null Null Null Null Null Null Null Null Null Null 1 Null 2 Null Null Null Null Null Nu Graph_ Weight Null 1 2 Null Null Null Null Null Null Null Null Null Null Null Null 1 Null 2 Null Null Graph_ Nodes Node0 Nodel Node2 Node3 Node4 Node5 Node6 Node7 Node8 Node9 Node10 Node11 Node12 Node13 Node14 13
9. ort estPath lt Node CapacitatedLink gt cng wTransformer java util List lt CapacitatedLink gt path spAlgorithm getPath cng get Vertex fromNode cng get Vertex to Node Number distance spAlgorithm getDistance cng get Vertex fromNode cng get Vertex to Node System out println Distance from Node fromNode to toNode is distance System out println Path from Node fromNode to toNode is path 4 3 Max Flow To calculate the maximum flow passing through a pair of nodes considering the link capacities the sofware uses Edmonds Karp algorithm which is an imple mentation of Ford Folkerson method You can use the following sample code to calculate the max flow on your network between desired nodes GraphGenerator lt Node CapacitatedLink gt gg PropertyFileGraphGenera tor getInstance CapacitatedNetworkGraph lt Node CapacitatedLink gt cng gg getGraph Transformer lt CapacitatedLink Double gt cap Transformer new Transformer lt CapacitatedLink Double gt public Double transform CapacitatedLink link return link getCapacity Ah Map lt CapacitatedLink Double gt edgeFlowMap new HashMap lt CapacitatedLink Double gt This Factory produces new edges for use by the algorithm Factory lt CapacitatedLink gt edgeFactory new Factory lt CapacitatedLink gt public CapacitatedLink create return new CapacitatedLink 1 1 0 1 0 Aa
10. perty File Generator DBGraph Key Value 2 SNA s Technology Dependencies SNA depends on two java libraries Commons Math 2 1 API and Jung 2 0 Java Universal Network Graph e Commons Math API This library is used for generating random numbers from some of the famous probability distribution functions The library is available for free download at http commons apache org math download_ math cgi and the javadoc of the library is reachable at http commons apache org math api 2 1 index html e JUNG 2 0 Graph and network classes of SNA extend some of the classes of this library Also it is used for graph visualizations in SNA The library is available for free download at http jung sourceforge net doc index html and the javadoc of the library is reachable at http jung sourceforge net doc api index html 3 SNA Network Basics SNA is an object oriented software It represents a network as a directed graph which has been read through its incidence matrix Although SNA uses some of the classes and interfaces of JUNG and JGRAPHT libraries it introduces its own classes for a lot of objects needed for its specific purposes The structure of a network in SNA is briefly introduced in the following For a more complete list of the classes please see the SNA javadoc The following figure depicts the high level SNA network architecture Fields Id Name Methods Methods Demand Setter and ToString Compare
11. to getters Capacitated getVertex NetworkGraph getEdge Extends Capacitated Link Directed Sparse Multi Graph Fields Capacity Weight ld Name Methods Fields setters and getters 3 1 How to Create a network There are three alternatives for forming a network in SNA e Creating a network manually e Reading from a file e Generating a random network 3 1 1 Creating a network manually In SNA nodes should be of the defined Node class and links should be of the defined CapacitatedLink class The following command initiates a network named g CapacitatedNetworkGraph lt Node CapacitatedLink gt g new Capacitated NetworkGraph lt Node CapacitatedLink gt As class CapacitatedNetworkGraph of SNA extends the DirectedOrderedSparse Multigraph of Jung library it inherits its methods so you can add a node with the id i to your network by g add Vertex i You can also add an edge e to between nodes source and sink by g addEdge e source sink For a complete set of commands like setting the link distributions demand and etc please see the javadoc of SNA 3 1 2 Reading a network from file In this method creating the network begins by defining a properties file You need to determine the following to be able to form your network The names between are key values e Graph_Nodes Set of Graph Nodes e Random_ Capacity Your graph capacity data is random Tru
12. try EdmondsKarpMazFlow lt Node CapacitatedLink gt maxFlowAlgorithm new EdmondsKarpMaxFlow cng cng get Vertex fromNode cng get Vertex to Node cap Transformer edgeFlowMap edgeFactory maxFlowAlgorithm evaluate System out println Maximum Flow from Node fromNode to toNode is mazFlowAlgorithm getMazFlow catch IllegalArgumentException e System out println Maximum Flow from Node fromNode to toNode is No Flow 4 4 Capacity Reliability Estimation The capacity reliability estimation method has the following steps 1 Sampling from all the link capacities 2 Calculating the Max Flow of the network using the data provided in step 1 3 Sample the demand from its distribution 4 Comparing the demand and the maximum flow 5 For the desired number of iterations do steps 1 4 6 return the percentage of times the maximum flow the network is able to provide exceedes the demand You can use the following commands to run such a simulation for 1000 times for the flow between your hypothetical 0 and 4 nodes and get the results GraphGenerator graphGenerator PropertyFileGraphGenerator getInstance ReliabilityEvaluation re new ReliabilityEvaluation 1000 System out println Capacity Reliability Estimation re estimate graphGenerator 0 4 5 Network Visulalization By now you have created your desired graph and implemented some algorithms SNA also gives
Download Pdf Manuals
Related Search