:mod:`graph_library` ==================== .. py:module:: graph_library Module Contents --------------- .. py:class:: 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. .. method:: set_annotation(self, key, value) Annotate node with some (key,value) pair. :param key: key used to retrieve the annotation :param value: actual annotation .. method:: get_annotation(self, key) Retrieve a previously attached annotation identified with the given key. :param key: key specified when adding the annotation :return: retrieved annotation, if present, else None .. method:: remove_annotation(self, key) Remove the annotation identified with the given key. :param key: key with which the annotation is identified :return: True if the annotation is successfully removed :rtype: bool .. method:: has_annotation(self) Indicates whether this node has any annotations. :return: True if this node has annotations :rtype: bool .. method:: num_annotations(self) Get the number of currently attached annotations. :return: number of annotations :rtype: int .. method:: get_annotations(self) Get all attached annotations. :return: dictionary containing all anootations as (key, value) pairs :rtype: dict .. py:class:: Node(name) Bases::class:`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. .. method:: __str__(self) :return: formatted string representation :rtype: str .. method:: __eq__(self, other) Compares nodes for equality based on their name. :param other: other object to compare for equality :type other: Node :return: True if the given other object is also a node with the same name :rtype: bool .. method:: __hash__(self) Hash code computation based on node name. :return: hash code :rtype: int .. method:: __repr__(self) .. py:class:: Edge(node1, node2, weight=None) Bases::class:`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 .. attribute:: node1 Get first node. In case of a directed edge, this node is assumed to be the source node. :return: first node :rtype: Node .. attribute:: node2 Get second node. In case of a directed edge, this node is assumed to be the destination node. :return: second node :rtype: Node .. method:: get_nodes(self) Get a list containing both nodes (arbitrary order). :return: list containing both nodes :rtype: list(Node) .. method:: contains(self, node) Check whether this edge contains the given node. :param node: node :type node: Node :return: True if n is one of both nodes of this edge :rtype: bool .. py:class:: DirectedEdge(*args, **kwargs) Bases::class:`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). .. method:: is_directed(self) Always returns true as this is a directed edge. :return: True :rtype: bool .. method:: get_source(self) Get the source node of this edge. :return: source node :rtype: Node .. method:: get_destination(self) Get the destination node of this edge. :return: destination node :rtype: Node .. method:: __str__(self) Create a string representation of the directed edge, formatted as (source,destination). :return: string representation :rtype: str .. py:class:: UndirectedEdge(*args, **kwargs) Bases::class:`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. .. method:: is_directed(self) Always returns False as this is an undirected edge. :return: False :rtype: bool .. method:: __str__(self) Create a string representation of the undirected edge, formatted as {a,b}. :return: string representation :rtype: str .. py:class:: Graph .. method:: contains_node(self, node) Check whether a specific node is contained in the graph. :param node: node :type node: Node :return: True if the given node is contained in the graph :rtype: bool .. method:: 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. :param name: node name :return: the graph node with the given name; None if the graph does not contain a node with this name :rtype Node .. method:: 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. :param node: node to add to the graph :type node: Node :return: True if the node was successfully added :rtype: bool .. method:: 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. :param node: node to be removed :type node: Node :return: True if the node has been successfully removed :rtype: bool .. method:: get_all_nodes(self) Get all nodes contained in the graph. :return: list of all graph nodes :rtype: list(Node) .. method:: num_nodes(self) Get the number of nodes (order) of the graph. :return: number of nodes :rtype: int .. method:: contains_edge(self, edge) Check whether the graph contains a given edge. :param edge: edge :type edge: Edge :return: True if the given edge is contained in the graph :rtype: bool .. method:: add_edge(self, edge) .. method:: get_edges(self, sourcenode, destnode) .. method:: contains_edge_between(self, sourcenode, destnode) Check whether there is an edge from the given source node to the given destination node. :param sourcenode: source node :type sourcenode: Node :param destnode: destination node :type destnode: Node :return: True if both nodes are contained in the graph, with an edge between them :rtype: bool .. method:: 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. :param edge: edge to be removed :type edge: Edge :return: True if the edge has been successfully removed :rtype: bool .. method:: 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. :param sourcenode: source node :type sourcenode: Node :param destnode: destination node :type destnode: Node :return: removed edge if it was present; else None :rtype: Edge .. method:: get_all_edges(self) Get a list containing all edges from the graph. :return: list of all edges :rtype: list(Edge) .. method:: num_edges(self) Get the number of edges (size) of the graph. :return: number of edges :rtype: int .. method:: 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. :param node: given node :type node: Node :return: list of neighbours of n :rtype: list(Node) .. method:: get_outgoing_edges(self, node) Get a list of outgoing edges from a given node n. :param node: given node :type node: Node :return: list of outgoing edges :rtype: list(Edge) .. method:: 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. :param node: node :type node: Node :return: out degree of the given node :rtype: int .. method:: get_incoming_edges(self, node) Get a list of incoming edges in a given node n. :param node: given node :type node: Node :return: list of incoming edges :rtype: list(Edge) .. method:: 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. :param node: node :type node: Node :return: in degree of the given node :rtype: int .. py:class:: SimpleGraph Bases::class:`graph_library.Graph` .. method:: 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. :param edge: edge to be added to the graph :type edge: Edge :return: True if the edge is successfully added :rtype: bool .. method:: get_edge_between(self, source, dest) Get the edge that goes from the given source node to the given destination node, if any. :param source: source node :type source: Node :param dest: destination node :type dest: Node :return: 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 :rtype: Edge .. py:class:: DirectedGraph(graph=None) Bases::class:`graph_library.SimpleGraph` Represents a directed graph. .. method:: 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. :param source: source node :type source: Node :param destination: destination node :type destination: Node :return: added edge, None if edge between nodes already present :rtype: DirectedEdge .. py:class:: UnDirectedGraph(graph=None) Bases::class:`graph_library.SimpleGraph` .. method:: 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. :param source: source node :type source: Node :param destination: destination node :type destination: Node :return: added edge, None if edge between nodes already present :rtype: UnDirectedEdge .. method:: get_incident_edges(self, node) Get the list of incident edges of a given node n. :param node: given node :type node: Node :return: list of incident edges :rtype: list(UnDirectedEdge) .. method:: get_degree(self, node) Get the degree of a node in the graph. The degree corresponds to the number of incident edges. :param node: node :type node: Node :return: degree of the given node :rtype: int .. py:class:: DirectedMultiGraph(graph=None) Bases::class:`graph_library.Graph` .. method:: 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. :param source: source node :type source: Node :param destination: destination node :type destination: Node :return: added edge, None if edge between nodes already present :rtype: DirectedEdge .. py:class:: UndirectedMultiGraph(graph=None) Bases::class:`graph_library.Graph` .. function:: set_weights(graph, weights) .. function:: 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 .. function:: 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