图（Graph）的表示

1.图的概念

图是一种重要的数据结构，在解决实际问题中也经常用到这种数据结构，其基本表示为G=(V, E)，V(vectex)是图的顶点，E(edge)表示图的边。我们的地图在计算机中就可以表示成一个Graph，不同的标志性地点为vectex，地点之间的路表示为edge，这样就可以方便操作实际中的地图去解决一些复杂的问题，比如找两个地点之间的最短路径，旅行商问题等等。

图分为有向图和无向图，有向图指的是各个顶点之间有一定的方向，一个顶点到另一个顶点需要按照给定的方向进行移动；而无向图指的是顶点之间没有固定方向。如下图所示，第一幅图为无向图，第二幅图为有向图。在有向图中，顶点1指向顶点2，说明1可以移向2，但是2不能移向1。

2.图的表示

图的表示就是表示清楚顶点信息和边的信息。有两种表示方法，邻接链表和邻接矩阵。如上面两张图可分别表示如下：

在计算机中，我们可以使用一些数据结构来简化图的表达，比如在Python中，我们可以用下面代码来表示一个图：

graph = {'A': set(['B', 'C']),
         'B': set(['A', 'D', 'E']),
         'C': set(['A', 'F']),
         'D': set(['B']),
         'E': set(['B', 'F']),
         'F': set(['C', 'E'])}

graph是一个字典，其中keys是所有的vertices，values是与该顶点连接的其他顶点。如果我们需要获取所有的顶点，那么可以利用字典的keys()方法：

graph.keys()

output: dict_keys(['A', 'B', 'C', 'D', 'E', 'F'])

获取与某个顶点相连的其他顶点，就可直接利用字典的取值方法：

graph['A']

output: {'B', 'C'}

但是如果图中的每一个边有权，我们称之为有权图时，利用上述的表示方法不能很方便地得到权重信息，为此我们可以封装一个类，定义获取边，权重等相关信息的函数。

# Fall 2012 6.034 Lab 2: Search
from functools import reduce

try:
    set()
except NameError:
    from sets import Set as set, ImmutableSet as frozenset

NAME="NAME"
NODE1="NODE1"
NODE2="NODE2"
VAL="LENGTH"

class Edge:
    def __init__(self, name, node1, node2, length):
        self.name = name
        self.node1 = node1
        self.node2 = node2
        self.length = length
    def __repr__(self):
        return 'Edge ' + self.name + \
               ' from ' + self.node1 + ' to ' + self.node2 + \
               ' with length ' + str(self.length)

class Graph:
    def __init__(self, nodes=None, edgesdict=None, heuristic=None,
                 edges=None):
        '''specify EITHER edgesdict OR edges'''

        if edges:
            self.edges = edges
        elif edgesdict:
            try:
                self.edges = [Edge(e['NAME'], e['NODE1'], e['NODE2'], e['LENGTH'])\
                              for e in edgesdict]
            except KeyError:
                self.edges = [Edge(e['name'], e['node1'], e['node2'], e['length'])\
                              for e in edgesdict]
        else:
            self.edges = []
        self.nodes = nodes
        if not nodes:
            self.nodes = list(set([edge.node1 for edge in self.edges] + 
                                  [edge.node2 for edge in self.edges]))
        # heuristic is a dictionary where heuristic[G][S] is the
        #  heuristic distance from S to G
        self.heuristic = heuristic
        if not heuristic:
            self.heuristic = {}
        self.validate()
    
    def validate(self):
        for name in self.nodes:
            assert isinstance(name, str), str(type(name))+": "+str(name)
        assert len(self.nodes) == len(set(self.nodes)), "no duplicate nodes"
        edgenames = [edge.name for edge in self.edges]
        assert len(edgenames) == len(set(edgenames)), "no duplicate edges"
        for edge in self.edges:
            assert isinstance(edge.name, str), type(edge.name)
            assert edge.node1 in self.nodes
            assert edge.node2 in self.nodes
            assert edge.length > 0, "positive edges only today"
        for start in self.nodes:
            for end in self.nodes:
                assert self.get_heuristic(start,end) >= 0

    def get_connected_nodes(self, node):
        """
        gets a list of all node id values connected to a given node.
        'node' should be a node name, not a dictionary.
        The return value is a list of node names.
        """
        assert node in self.nodes, "No node "+str(node)+" in graph "+str(self)
        result = [x.node2 for x in self.edges if x.node1 == node]
        result += [x.node1 for x in self.edges if x.node2 == node]
        return sorted(result)

    def get_edge(self, node1, node2):
        """
        checks the list of edges and returns an edge if
        both connected nodes are part of the edge, or 'None' otherwise.
        'node1' and 'node2' are names of nodes, not 'NODE' dictionaries.
        """
        assert node1 in self.nodes, "No node "+str(node1)+" in graph "+str(self)
        assert node2 in self.nodes, "No node "+str(node2)+" in graph "+str(self)
        node_names = ( node1, node2 )
        for edge in self.edges:
            if ((edge.node1, edge.node2) == node_names or 
                (edge.node2, edge.node1) == node_names):
                return edge
        return None

    def are_connected(self, node1, node2):
        """
        checks if two edges are connected.
        'node1' and 'node2' are names of nodes, not 'NODE' dictionaries.
        """
        return bool(self.get_edge(node1, node2) )

    def get_heuristic(self, start, goal):
        """ Return the value of the heuristic from the start to the goal"""
        assert start in self.nodes, "No node "+str(start)+" in graph "+str(self)
        assert goal in self.nodes, "No node "+str(goal)+" in graph "+str(self)
        if goal in self.heuristic:
            if start in self.heuristic[goal]:
                return self.heuristic[goal][start]
            else:
                return 0 # we have checked that everything is positive
        else: 
            return 0 # we have checked that everything is positive
    
    def is_valid_path(self, path):
        def is_valid_path_reducer(elt_a, elt_b):
            if elt_a == False or not self.are_connected(elt_a, elt_b):
                return False
            else:
                return elt_b
        return (reduce(is_valid_path_reducer, path) != False)

    def add_edge(self, node1, node2, length, name=None):
        if node1 not in self.nodes:
            self.nodes.append(node1)
        if node2 not in self.nodes:
            self.nodes.append(node2)
        if name == None:
            name = ("%s %s" % (node1, node2))
        self.edges.append(Edge(name, node1, node2, length))

    def set_heuristic(self, start, goal, value):
        if goal not in self.heuristic:
            self.heuristic[goal] = {}
        self.heuristic[goal][start] = value

    def __str__(self):
        return "Graph: \n  edges="+str(self.edges)+"\n  heuristic="+str(self.heuristic)

根据init方法的定义，一个图可以如下定义：

AGRAPH = Graph(nodes = ['S', 'A', 'B', 'C', 'G'],
               edgesdict = [{'NAME': 'eSA', 'LENGTH': 3, 'NODE1': 'S', 'NODE2': 'A'},
                            {'NAME': 'eSB', 'LENGTH': 1, 'NODE1': 'S', 'NODE2': 'B'},
                            {'NAME': 'eAB', 'LENGTH': 1, 'NODE1': 'A', 'NODE2': 'B'},
                            {'NAME': 'eAC', 'LENGTH': 1, 'NODE1': 'A', 'NODE2': 'C'},
                            {'NAME': 'eCG', 'LENGTH': 10, 'NODE1': 'C', 'NODE2': 'G'}],
               heuristic = {'G':{'S': 12,
                                 'A': 9,
                                 'B': 12,
                                 'C': 8,
                                 'G': 0}})

heuristic是启发式的距离，在A*算法中会使用到这个属性，这里不做过多的描述。我们只需明白图的表示可以很灵活多样，但关键在于把需要的信息表达清楚即可，特别是顶点和边的信息。对于不同问题，我们可以使用不同的数据结构和算法对图进行表示。

参考资料：

1.算法导论第三版

2.MIT Artificial Intelligence open course Assignment lab2 code