networks
index
/Users/ejones/multipath/networks.py

This module contains objects that help generate wireless networks to be fed
into ns2. It supports generating random topologies, shortest path routing via
Dijkstra's algorithm and outputting the network data in ns2 format.

 
Modules
       
math
random
sys

 
Classes
       
NS2ScriptBuilder
Network
__builtin__.list(__builtin__.object)
ListSubclassFifo
__builtin__.object
Node
Path
HeuristicPath2

 
class HeuristicPath2(Path)
    This Path subclass is used to make Dijkstra's algorithm run a bit faster.
 
 
Method resolution order:
HeuristicPath2
Path
__builtin__.object

Methods defined here:
append(self, node)
clone(self)

Data and other attributes defined here:
__dict__ = <dictproxy object at 0x2237d0>
dictionary for instance variables (if defined)
__weakref__ = <attribute '__weakref__' of 'HeuristicPath2' objects>
list of weak references to the object (if defined)

Methods inherited from Path:
__cmp__(self, other)
__init__(self, source)
__len__(self)
distance(self)
Returns the total distance of the path, computed as the
sum of the distances between each node.
isNodeDisjoint(self, other)
Returns True if this path does not share any nodes with the
other path. It returns False if it shares at least one node.
iterlinks(self)
last(self)
reverse(self)
Return a clone of this path in reverse order.
source(self)
unvisitedPaths(self)

Data and other attributes inherited from Path:
__slots__ = ('path', 'visited')
path = <member 'path' of 'Path' objects>
visited = <member 'visited' of 'Path' objects>

 
class ListSubclassFifo(__builtin__.list)
    list subclass that provides better performance for enqueue and
dequeue operations.
 
From: http://aspn.activestate.com/ASPN/Cookbook/Python/Recipe/68436
- Constant time enqueue and dequeue
- Has a higher constant than the list
- Only faster if you are dequeuing from lists with more than ~1000 items
 
 
Method resolution order:
ListSubclassFifo
__builtin__.list
__builtin__.object

Methods defined here:
__init__(self)
__iter__(self)
__len__(self)
dequeue(self)
dequeueEnd(self)
enqueue(self, elt)
peekAtEnd(self)

Data and other attributes defined here:
__slots__ = ('front',)
front = <member 'front' of 'ListSubclassFifo' objects>

Methods inherited from __builtin__.list:
__add__(...)
x.__add__(y) <==> x+y
__contains__(...)
x.__contains__(y) <==> y in x
__delitem__(...)
x.__delitem__(y) <==> del x[y]
__delslice__(...)
x.__delslice__(i, j) <==> del x[i:j]
 
Use of negative indices is not supported.
__eq__(...)
x.__eq__(y) <==> x==y
__ge__(...)
x.__ge__(y) <==> x>=y
__getattribute__(...)
x.__getattribute__('name') <==> x.name
__getitem__(...)
x.__getitem__(y) <==> x[y]
__getslice__(...)
x.__getslice__(i, j) <==> x[i:j]
 
Use of negative indices is not supported.
__gt__(...)
x.__gt__(y) <==> x>y
__hash__(...)
x.__hash__() <==> hash(x)
__iadd__(...)
x.__iadd__(y) <==> x+=y
__imul__(...)
x.__imul__(y) <==> x*=y
__le__(...)
x.__le__(y) <==> x<=y
__lt__(...)
x.__lt__(y) <==> x<y
__mul__(...)
x.__mul__(n) <==> x*n
__ne__(...)
x.__ne__(y) <==> x!=y
__repr__(...)
x.__repr__() <==> repr(x)
__rmul__(...)
x.__rmul__(n) <==> n*x
__setitem__(...)
x.__setitem__(i, y) <==> x[i]=y
__setslice__(...)
x.__setslice__(i, j, y) <==> x[i:j]=y
 
Use  of negative indices is not supported.
append(...)
L.append(object) -- append object to end
count(...)
L.count(value) -> integer -- return number of occurrences of value
extend(...)
L.extend(iterable) -- extend list by appending elements from the iterable
index(...)
L.index(value, [start, [stop]]) -> integer -- return first index of value
insert(...)
L.insert(index, object) -- insert object before index
pop(...)
L.pop([index]) -> item -- remove and return item at index (default last)
remove(...)
L.remove(value) -- remove first occurrence of value
reverse(...)
L.reverse() -- reverse *IN PLACE*
sort(...)
L.sort(cmpfunc=None) -- stable sort *IN PLACE*; cmpfunc(x, y) -> -1, 0, 1

Data and other attributes inherited from __builtin__.list:
__new__ = <built-in method __new__ of type object at 0xa5f444fc>
T.__new__(S, ...) -> a new object with type S, a subtype of T

 
class NS2ScriptBuilder
     Methods defined here:
__init__(self, network)
addFlow(self, paths, UDP=True, tcpType='SACKDelAck', rate=False)
getNsToTopologyIndex(self)
Returns a dictionary that maps the ns2 indexes back to topology indexes.
getScript(self)
ns2Footer(self)
ns2TCPAgent(self, type, rate)
ns2UDPAgent(self)

 
class Network
    Represents a collection of nodes.
 
  Methods defined here:
__init__(self, size, range=250)
size - A tuple of the (x, y) dimensions of the network terrain.
range - The maximum distance between connected nodes.
addNode(self, x, y)
drawScript(self, paths=None)
Returns a list of node coordinates in the format for my
network topology drawing program (drawnetwork).
findNeighbours(self)
Recalculates the neighbour lists for each node. It also
forgets any cached routing information.
findShortestPaths(self, source, destination, extraHopLimit=0)
Finds all the shortest paths from source index node to the
destination index nodes. It will also return paths with up to
extraHopLimit hops past the shortest path.
findShortestPathsHeuristic(self, source, destination, extraHopLimit=0)
Same as findShortestPaths, but it uses the heuristic path
so it runs much faster. I believe the results should be
the same, but I have not thought about it enough to be able to
be certain about it.
findShortestPathsOnly(self, source, destination, onlyDestination=True)
Yet another findShortestPaths, implementation, but this one
finds only the shortest paths. If onlyDestination is false, it
will find all the shortest paths that begin at source. This is
used to implement the route() function.
maximumConnectedSet(self)
pathToIndexes(self, path)
Converts a path object into a list of node indexes.
route(self, source, destination)
Yet another shortest paths implementation. This one finds
all the shortest paths that start at the given source. It also
uses extensive caching, and relies on the fact that the routing
is symmetric. The implementation relies on
findShortestPathsOnly.
routeAll(self, maxPaths=None)
Floyd-Warshall all pairs shortest path. O(n^3)
Implemented thanks to: http://ai-depot.com/BotNavigation/Path-AllPairs.html
Computes all the shortest paths in the network. It will
only do this computation once, and it is faster to do it for
the entire network at the same time than it is to do if for
each pair of nodes in order.
 
After calling this, paths can be found via:
self.nodes[source].routes[destination]
unconnectedNodes(self)

 
class Node(__builtin__.object)
    This class represents a single wireless node. The important
attributes are the x and y coordinates. The others are designed to be
internal attributes used for routing.
 
  Methods defined here:
__init__(self, x, y)
Creates a new Node located at the specified x and y coordinates.
distance(self, other)
Returns the distance from this node to another node.

Data and other attributes defined here:
__slots__ = ('x', 'y', 'neighbours', 'shortestPathLength', 'shortestPaths', 'routes')
neighbours = <member 'neighbours' of 'Node' objects>
routes = <member 'routes' of 'Node' objects>
shortestPathLength = <member 'shortestPathLength' of 'Node' objects>
shortestPaths = <member 'shortestPaths' of 'Node' objects>
x = <member 'x' of 'Node' objects>
y = <member 'y' of 'Node' objects>

 
class Path(__builtin__.object)
    Represents a path of connected nodes. The node instances can be
directly accessed via the self.path list.
 
  Methods defined here:
__cmp__(self, other)
__init__(self, source)
__len__(self)
append(self, node)
clone(self)
Returns a clone of this object with new instances for the 
first level variables (not a recursive copy).
distance(self)
Returns the total distance of the path, computed as the
sum of the distances between each node.
isNodeDisjoint(self, other)
Returns True if this path does not share any nodes with the
other path. It returns False if it shares at least one node.
iterlinks(self)
last(self)
reverse(self)
Return a clone of this path in reverse order.
source(self)
unvisitedPaths(self)

Data and other attributes defined here:
__slots__ = ('path', 'visited')
path = <member 'path' of 'Path' objects>
visited = <member 'visited' of 'Path' objects>

 
Functions
       
randomNetwork(size, numNodes=None, density=None)
Generates a random connected network, and computes the neighbour
information. The size must be specified as a tuple: (width, height).
One of numNodes or density must be set in order to compute the number
of nodes.
randomSquareCellNetwork(cellSize=None, numCells=None, area=None)
Returns a network with one node in each square cell. Exactly two of
the three keyword parameters must be specified. The missing value will
be computed from the other two. Note that these networks are not
guaranteed to be connected. If you need a connected network, check
that the result from maximumConnectedSet contains all the nodes in
this network.
 
Arguments:
 
cellSize -- A float that specifies the width and height of each cell.
        If numCells is specified, the cells will be exactly this size.
        If area is specified, the cells will be at most this size.
numCells -- A tuple specifying the number of cells in the (x,y)
        directions.
area -- A tuple specifying the (width, height) of the network area.
        
Two useful constants are defined in this module:
 
MAX_CELL_SIZE -- A node located in a cell of this size will cover the
        entire cell.
MIN_CELL_SIZE -- A node located in a cell of this size is guaranteed
        to connect to its four neighbours: up, down, left and right.

 
Data
        MAX_CELL_SIZE = 176.77669529663686
MIN_CELL_SIZE = 111.80339887498948
RANGE = 250.0