knapscak and graph optimization problems you might want to stop for minute and think about why graph is subclass of digraphrather than the other way around in many of the examples of subclassing we have looked atthe subclass adds attributes to the superclass for exampleclass weightededge added weight attribute to class edge heredigraph and graph have the same attributes the only difference is the implementation of the addedge method either could have been easily implemented by inheriting methods from the otherbut the choice of which to make the superclass was not arbitrary in we stressed the importance of obeying the substitution principleif client code works correctly using an instance of the supertypeit should also work correctly when an instance of the subtype is substituted for the instance of the supertype and indeed if client code works correctly using an instance of digraphit will work correctly if an instance of graph is substituted for the instance of digraph the converse is not true there are many algorithms that work on graphs (by exploiting the symmetry of edgesthat do not work on directed graphs some classic graph-theoretic problems one of the nice things about formulating problem using graph theory is that there are well-known algorithms for solving many optimization problems on graphs some of the best-known graph optimization problems areshortest path for some pair of nodesn and find the shortest sequence of edges (source node and destination node)such that the source node in the first edge is the destination node of the last edge is for all edges and in the sequenceif follows in the sequencethe source node of is the destination node of shortest weighted path this is like the shortest pathexcept instead of choosing the shortest sequence of edges that connects two nodeswe define some function on the weights of the edges in the sequence ( their sumand minimize that value this is the kind of problem solved by mapquest and google maps when asked to compute driving directions between two points cliques find set of nodes such that there is path (or often path not exceeding maximum lengthin the graph between each pair of nodes in the set min cut given two sets of nodes in grapha cut is set of edges whose removal eliminates all paths from each node in one set to each node in the other the minimum cut is the smallest set of edges whose removal accomplishes this this notion is quite similar to the notion of social cliquei group of people who feel closely connected to each other and are inclined to exclude those not in the clique seefor examplethe movie heathers