| | |
- 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) |
| |
A 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 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>
| |