Generic Graph Theory Code

Graph-theoretic operations in Python.

base_graph_simple.py

base_gridgraph.py

Basic GridGraph class. Demo uses Pygame for rendering.

class base_gridgraph.GridGraph(cols=2, rows=2, dx=1.0, dy=1.0)

A regular rectangular grid with Manhattan/diagonal neighborhoods.

Parameters:
  • cols (int) – Number of node columns (in the horizontal dimension).
  • rows (int) – Number of node rows (in the vertical dimension).
  • dx (float) – Edge weight between horizontally adjacent nodes.
  • dy (float) – Edge weight between vertically adjacent nodes.
is_node(node)

Check for a valid node (even if it’s inactive).

is_not_inactive()

Check for an active node (does not check for validity).

Note

For performance reasons, this simply checks if the node with grid coordinates (x,y) is in the grid’s inactive list.

edge_cost(node0, node1)

Get the edge cost between two nodes. :returns: float :rtype: The edge cost, or INF if the nodes are not adjacent.

Raises:IndexError : If either node is invalid.
active_neighbors(node)

Get a list of active neighbors for the given node.

Parameters:node (2-tuple of int) – Grid coordinates of the given node.

Note

For performance reasons, this does not check if node is valid.

base_graph.py

Module for various type of graph nodes/edges. WORK IN PROGRESS!

base_graph.INVALID_NODE_ID = -1

Any reference to this index is treated as being a nonexistant node.

class base_graph.BaseGraphNode(node_id, **kwargs)

Base class for various types of graph nodes.

Parameters:
  • node_id (int) – ID to assign this node, to allow consistency with external information.
  • kwargs (any, optional) – Additional attributes can be set using keyword arguments. Each key (except node_id) sets an instance variable with the same name. There is no error-checking in the base class, but subclasses may override this.

Note

Subclasses should call the base __init__() method (via super) to set the node ID and any extra keyword arguments. The base class keeps a master directory of nodes by id, which can be accessed using the module function get_node(node_id).

base_graph.get_node(node_id)

A handle to the node with the given id; None for invalid nodes.

class base_graph.EasyGraphNode(node_id, **kwargs)

A BaseGraphNode with anonymous directed edges.

Adjacency is stored locally per node, using a dictionary keyed by node ID, Entries can then represent edge information (weight, label, etc.), but there is no way to access edges independently. To modify adjacency, use either the make_edges() or remove_edges() method on the source node.

Parameters:
  • node_id (int) – ID to assign this node, to allow consistency with external information.
  • kwargs (any, optional) – Additional attributes can be set using keyword arguments. Each key (except node_id) sets an instance variable with the same name.
get_id()

Returns the ID of this node.

ignore_me()

Sets this node to be treated as temporarily inactive.

Note

After calling this, existing references to this node will remain valid, but any future queries to node_from_id[] will return None. This gives the ability to temporarily ignore nodes without the overhead of deleting them. Provided that we keep an external reference, we can reactivate this node later, using unignore_me() below.

unignore_me()

Restore this node to being treated as active.

Note

After calling this, any information about this node (including edges to/from adjancent nodes) that existed before make_invalid() will once again be available.

make_edges(neighbor, label=1)

Create edge(s) from this node, with optional weight (default 1).

Parameters:
  • neighbor (int or list of int) – The ID of the node to connect to.
  • label (object or list of objects, optional) – The label/weight information for the edge(s) (default = 1). If a single label is given, all neighbors get that label. If a list is given, it must have the same length as neighbor.

Note

This will overwrite any previous edge to the given neighbor(s). This does not check if neighbor(s) is/are currently active or valid, so we can create edges to node id’s that do not yet exist.

remove_edges(neighbor)

Remove any existing edges to the given neighbor(s).

Parameters:neighbor (int or list of int) – The ID of the nodes to remove edges to.
neighbor_ids()

The set of IDs of active nodes adjacent to this one.

neighbor_nodes()

The set of active nodes adjacent to this one.

edges_from()

A dictionary of edges from this node, keyed by neighbor ID. Inactive neighbors are ignored.