`graph_library`¶

Module Contents¶

class graph_library.AnnotatedObject¶

Represents an annotated object. Any number of annotations can be attached as (key,value) pairs, i.e. each annotation is identified with a unique key.

set_annotation(self, key, value)¶

Annotate node with some (key,value) pair.

Parameters

key – key used to retrieve the annotation
value – actual annotation

get_annotation(self, key)¶

Retrieve a previously attached annotation identified with the given key.

Parameters: key – key specified when adding the annotation
Returns: retrieved annotation, if present, else None

remove_annotation(self, key)¶

Remove the annotation identified with the given key.

Parameters: key – key with which the annotation is identified
Returns: True if the annotation is successfully removed
Return type: bool

has_annotation(self)¶

Indicates whether this node has any annotations.

Returns: True if this node has annotations
Return type: bool

num_annotations(self)¶

Get the number of currently attached annotations.

Returns: number of annotations
Return type: int

get_annotations(self)¶

Get all attached annotations.

Returns: dictionary containing all anootations as (key, value) pairs
Return type: dict

class graph_library.Node(name)¶

Bases:graph_library.AnnotatedObject

Represents a node in a graph. Nodes are identified with a string label (name) which should be unique among all nodes in a graph. Nodes with the same name are considered equal and an error will be thrown when attempting to add equal nodes to any graph. An unlimited number of annotations can be added to a node, e.g. during execution of a specific algorithm.

__str__(self)¶

Returns: formatted string representation
Return type: str

__eq__(self, other)¶

Compares nodes for equality based on their name.

Parameters: other (Node) – other object to compare for equality
Returns: True if the given other object is also a node with the same name
Return type: bool

__hash__(self)¶

Hash code computation based on node name.

Returns: hash code
Return type: int

__repr__(self)¶

class graph_library.Edge(node1, node2, weight=None)¶

Bases:graph_library.AnnotatedObject

Represents an edge in a graph. The edge can be directed or undirected. It is assumed that for directed edges, the first node is the source node and the second node is the destination node. For undirected edges it does not mean anything whether a node is the first or second node. Edges may have a weight but they are not required to. Besides the weight, an unlimited number of additional annotations can also be added to any edge as (key,value) pairs. This class is not intended to be directly instantiated. Explicit directed or undirected edges can be created using one of the constructors of DirectedEdge or UnDirectedEdge

node1¶

Get first node. In case of a directed edge, this node is assumed to be the source node.

Returns: first node
Return type: Node

node2¶

Get second node. In case of a directed edge, this node is assumed to be the destination node.

Returns: second node
Return type: Node

get_nodes(self)¶

Get a list containing both nodes (arbitrary order).

Returns: list containing both nodes
Return type: list(Node)

contains(self, node)¶

Check whether this edge contains the given node.

Parameters: node (Node) – node
Returns: True if n is one of both nodes of this edge
Return type: bool

class graph_library.DirectedEdge(*args, **kwargs)¶

Bases:graph_library.Edge

Represents a directed edge. This type of edges can be added to a directed graph. An edge (a,b) is not equal to a corresponding edge (b,a).

is_directed(self)¶

Always returns true as this is a directed edge.

Returns: True
Return type: bool

get_source(self)¶

Get the source node of this edge.

Returns: source node
Return type: Node

get_destination(self)¶

Get the destination node of this edge.

Returns: destination node
Return type: Node

__str__(self)¶

Create a string representation of the directed edge, formatted as (source,destination).

Returns: string representation
Return type: str

class graph_library.UndirectedEdge(*args, **kwargs)¶

Bases:graph_library.Edge

Represents an undirected edge. This type of edges can be added to a undirected graph. Edges {a,b} and {b,a} are equal.

is_directed(self)¶

Always returns False as this is an undirected edge.

Returns: False
Return type: bool

__str__(self)¶

Create a string representation of the undirected edge, formatted as {a,b}.

Returns: string representation
Return type: str

class graph_library.Graph¶

contains_node(self, node)¶

Check whether a specific node is contained in the graph.

Parameters: node (Node) – node
Returns: True if the given node is contained in the graph
Return type: bool

get_node_from_name(self, name)¶

Get a graph node based on its name. If the graph does not contain any node with this name, None is returned.

Parameters: name – node name
Returns: the graph node with the given name; None if the graph does not contain a node with this name

:rtype Node

add_node(self, node)¶

Add a node to the graph. If a node with the same name is already contained in the graph, calling this method does not have any effect and False is returned.

Parameters: node (Node) – node to add to the graph
Returns: True if the node was successfully added
Return type: bool

remove_node(self, node)¶

Remove a node from the graph. All incident edges are also removed. If the given node is not contained in the graph False is returned and calling this method does not have any effect.

Parameters: node (Node) – node to be removed
Returns: True if the node has been successfully removed
Return type: bool

get_all_nodes(self)¶

Get all nodes contained in the graph.

Returns: list of all graph nodes
Return type: list(Node)

num_nodes(self)¶

Get the number of nodes (order) of the graph.

Returns: number of nodes
Return type: int

contains_edge(self, edge)¶

Check whether the graph contains a given edge.

Parameters: edge (Edge) – edge
Returns: True if the given edge is contained in the graph
Return type: bool

add_edge(self, edge)¶

get_edges(self, sourcenode, destnode)¶

contains_edge_between(self, sourcenode, destnode)¶

Check whether there is an edge from the given source node to the given destination node.

Parameters

sourcenode (Node) – source node
destnode (Node) – destination node

Returns

True if both nodes are contained in the graph, with an edge between them

Return type

bool

remove_edge(self, edge)¶

Remove an edge from the graph. If the edge is not present or either the source or destination nodes are not contained in the graph, False is returned and calling this method does not have any effect.

Parameters: edge (Edge) – edge to be removed
Returns: True if the edge has been successfully removed
Return type: bool

remove_edge_between(self, sourcenode, destnode)¶

Remove the edge from the given source node to the given destination node. If such edge is not present or either the source or destination nodes are not contained in the graph, None is returned and calling this method does not have any effect. Else, the removed edge is returned.

Parameters

sourcenode (Node) – source node
destnode (Node) – destination node

Returns

removed edge if it was present; else None

Return type

Edge

get_all_edges(self)¶

Get a list containing all edges from the graph.

Returns: list of all edges
Return type: list(Edge)

num_edges(self)¶

Get the number of edges (size) of the graph.

Returns: number of edges
Return type: int

get_neighbours(self, node)¶

Get all neighbours of a given node n. A node m is defined to be a neighbour of n if there is an edge from n to m.

Parameters: node (Node) – given node
Returns: list of neighbours of n
Return type: list(Node)

get_outgoing_edges(self, node)¶

Get a list of outgoing edges from a given node n.

Parameters: node (Node) – given node
Returns: list of outgoing edges
Return type: list(Edge)

get_out_degree(self, node)¶

Get the out degree of a node in the graph. The out degree corresponds to the number of outgoing edges.

Parameters: node (Node) – node
Returns: out degree of the given node
Return type: int

get_incoming_edges(self, node)¶

Get a list of incoming edges in a given node n.

Parameters: node (Node) – given node
Returns: list of incoming edges
Return type: list(Edge)

get_in_degree(self, node)¶

Get the in degree of a node in the graph. The in degree corresponds to the number of incoming edges.

Parameters: node (Node) – node
Returns: in degree of the given node
Return type: int

class graph_library.SimpleGraph¶

Bases:graph_library.Graph

add_edge(self, edge)¶

Add an edge to the graph. The nodes of the edge should already be present in the graph, else an assertion is thrown. If the graph already contains an edge with the same source and destination, calling this method does not have any effect and False is returned.

Parameters: edge (Edge) – edge to be added to the graph
Returns: True if the edge is successfully added
Return type: bool

get_edge_between(self, source, dest)¶

Get the edge that goes from the given source node to the given destination node, if any.

Parameters

source (Node) – source node
dest (Node) – destination node

Returns

the edge between the given nodes, if both nodes are contained in the graph and connected with an edge in the given direction; else None is returned

Return type

Edge

class graph_library.DirectedGraph(graph=None)¶

Bases:graph_library.SimpleGraph

Represents a directed graph.

add_edge_between(self, source, destination)¶

Adds an edge from the given source to destination node. Both nodes should already be contained in the graph, else an assertion is thrown. If an edge is already present from the given source to destination node, None is returned and the graph is not modified, else the newly added edge is returned.

Parameters

source (Node) – source node
destination (Node) – destination node

Returns

added edge, None if edge between nodes already present

Return type

DirectedEdge

class graph_library.UnDirectedGraph(graph=None)¶

Bases:graph_library.SimpleGraph

add_edge_between(self, source, destination)¶

Adds an edge from the given source to destination node. Both nodes should already be contained in the graph, else an assertion is thrown. If an edge is already present from the given source to destination node, None is returned and the graph is not modified, else the newly added edge is returned.

Parameters

source (Node) – source node
destination (Node) – destination node

Returns

added edge, None if edge between nodes already present

Return type

UnDirectedEdge

get_incident_edges(self, node)¶

Get the list of incident edges of a given node n.

Parameters: node (Node) – given node
Returns: list of incident edges
Return type: list(UnDirectedEdge)

get_degree(self, node)¶

Get the degree of a node in the graph. The degree corresponds to the number of incident edges.

Parameters: node (Node) – node
Returns: degree of the given node
Return type: int

class graph_library.DirectedMultiGraph(graph=None)¶

Bases:graph_library.Graph

add_edge_between(self, source, destination)¶

Adds an edge from the given source to destination node. Both nodes should already be contained in the graph, else an assertion is thrown. The newly added edge is returned.

Parameters

source (Node) – source node
destination (Node) – destination node

Returns

added edge, None if edge between nodes already present

Return type

DirectedEdge

class graph_library.UndirectedMultiGraph(graph=None)¶: Bases:graph_library.Graph

graph_library.set_weights(graph, weights)¶

graph_library.directed_graph_from_dict(data, weights=None)¶: Creates a directed graph from a dictionary. The keys of the dictionary correspond to the nodes of the graph and the value for a key correspond to the incident nodes of the node that key represents :param data: the dictionary containing the neighbour information :type data: dict :param weights: the weights for each edge :type weights: dict :return: the corresponding undirected graph :rtype: DirectedGraph

graph_library.undirected_graph_from_dict(data, weights=None)¶: Creates an undirected graph from a dictionary. The keys of the dictionary correspond to the nodes of the graph and the value for a key correspond to the incident nodes of the node that key represents :param data: the dictionary containing the neighbour information :type data: dict :param weights: the weights for each edge :type weights: dict :return: the corresponding undirected graph :rtype: UnDirectedGraph

graph_library¶

Module Contents¶

`graph_library`¶