Graph Theory and Graphs

Are electronic schematics directed or indirected graphs?

Wires are no doubt undirected, but some components realize a control function so we tend to analize schematics in terms of cause and effect.

Definition of State Space Search

A state space is represented by a four-tuple [N,A,S,GD], where:

• N is the set of nodes or states of the graph. These correspond to the states in a problem-solving process.

• A is the set of arcs (or links) between nodes. These correspond to the steps in a problem-solving process.

• S, a nonempty subset of N, contains the start state(s) of the problem.

• GD, a nonempty subset of N, contains the goal state(s) of the problem. The states in GD are described using either:

  • 1. A measurable property of the states encountered in the search.
  • 2. A measurable property of the path developed in the search, for example, the sum of the transition costs for the arcs of the path.

A solution path is a path through this graph from a node in S to a node in GD.

Data-Driven and Goal-Driven Search

A state space may be searched in two directions: from the given data of a problem instance toward a goal or from a goal back to the data.

In data-driven search, sometimes called forward chaining, the problem solver begins with the given facts of the problem and a set of legal moves or rules for changing state. Search proceeds by applying rules to facts to produce new facts, which are in turn used by the rules to generate more new facts. This process continues until (we hope!) it generates a path that satisfies the goal condition.

An alternative approach is possible: take the goal that we want to solve. See what rules or legal moves could be used to generate this goal and determine what conditions must be true to use them. These conditions become the new goals, or subgoals, for the search. Search continues, working backward through successive subgoals until (we hope!) it works back to the facts of the problem. This finds the chain of moves or rules leading from data to a goal, although it does so in backward order. This approach is called goal-driven reasoning, or backward chaining, and it recalls the simple childhood trick of trying to solve a maze by working back from the finish to the start.

To summarize: data-driven reasoning takes the facts of the problem and applies the rules or legal moves to produce new facts that lead to a goal; goal-driven reasoning focuses on the goal, finds the rules that could produce the goal, and chains backward through successive rules and subgoals to the given facts of the problem.

In the final analysis, both data-driven and goal-driven problem solvers search the same state space graph; however, the order and actual number of states searched can differ. The preferred strategy is determined by the properties of the problem itself. These include the complexity of the rules, the shape of the state space, and the nature and availability of the problem data. All of these vary for different problems.

Implementing Graph Search

In solving a problem using either goal- or data-driven search, a problem solver must find a path from a start state to a goal through the state space graph. The sequence of arcs in this path corresponds to the ordered steps of the solution. If a problem solver were given an oracle or other infallible mechanism for choosing a solution path, search would not be required. The problem solver would move unerringly through the space to the desired goal, constructing the path as it went. Because oracles do not exist for interesting problems, a problem solver must consider different paths through the space until it finds a goal. Backtracking is a technique for systematically trying all paths through a state space. We begin with backtrack because it is one of the first search algorithms computer scientists study, and it has a natural implementation in a stack oriented recursive environment. We will present a simpler version of the backtrack algorithm with depth-first search.

Backtracking search begins at the start state and pursues a path until it reaches either a goal or a dead end. If it finds a goal, it quits and returns the solution path. If it reaches a dead end, it backtracks to the most recent node on the path having unexamined siblings and continues down one of these branches, as described in the following recursive rule:

If the present state S does not meet the requirements of the goal description, then generate its first descendant S_child1, and apply the backtrack procedure recursively to this node. If backtrack does not find a goal node in the subgraph rooted at S_child1, repeat the procedure for its sibling, S_child2. Continue until either some descendant of a child is a goal node or all the children have been searched. If none of the children of S leads to a goal, then backtrack fails back to the parent of S, where it is applied to the siblings of S, and so on.

The algorithm continues until it finds a goal or exhausts the state space. We now define an algorithm that performs a backtrack, using three lists to keep track of nodes in the state space:

• SL, for state list, lists the states in the current path being tried. If a goal is found, SL contains the ordered list of states on the solution path.
• NSL, for new state list, contains nodes awaiting evaluation, i.e., nodes whose descendants have not yet been generated and searched.
• DE, for dead ends, lists states whose descendants have failed to contain a goal. If these states are encountered again, they will be detected as elements of DE and eliminated from consideration immediately.

In defining the backtrack algorithm for the general case (a graph rather than a tree), it is necessary to detect multiple occurrences of any state so that it will not be reentered and cause (infinite) loops in the path. This is accomplished by testing each newly generated state for membership in any of these three lists. If a new state belongs to any of these lists, then it has already been visited and may be ignored.

This is the pseudocode for function backtrack:

function backtrack;
begin
  SL := [Start]; NSL := [Start]; DE := [ ]; CS := Start;     % initialize:
  while NSL ≠ [ ] do                 % while there are states to be tried
    begin
      if CS = goal (or meets goal description)
        then return SL;       % on success, return list of states in path.
      if CS has no children (excluding nodes already on DE, SL, and NSL)
        then begin
          while SL is not empty and CS = the first element of SL do
            begin
              add CS to DE;                    % record state as dead end
              remove first element from SL;                    %backtrack
              remove first element from NSL;
              CS := first element of NSL;
            end
          add CS to SL;
        end
        else begin
          place children of CS (except nodes already on DE, SL, or NSL) on NSL;
          CS := first element of NSL;
          add CS to SL
        end
      end;
      return FAIL;
end.

In backtrack, the state currently under consideration is called CS for current state. CS is always equal to the state most recently added to SL and represents the frontier of the solution path currently being explored. Inference rules, moves in a game, or other appropriate problem-solving operators are ordered and applied to CS. The result is an ordered set of new states, the children of CS. The first of these children is made the new current state and the rest are placed in order on NSL for future examination. The new current state is added to SL and search continues. If CS has no children, it is removed from SL (this is where the algorithm backtracks) and any remaining children of its predecessor on SL are examined.

As presented here, backtrack implements data-driven search, taking the root as a start state and evaluating its children to search for the goal. The algorithm can be viewed as a goal-driven search by letting the goal be the root of the graph and evaluating descendants back in an attempt to find a start state. If the goal description is of type 2, the algorithm must determine a goal state by examining the path on SL.

backtrack is an algorithm for searching state space graphs. The graph search algorithms that follow, including depth-first, breadth-first, and best-first search, exploit the ideas used in backtrack, including:

• 1. The use of a list of unprocessed states (NSL) to allow the algorithm to return to any of these states.
• 2. A list of bad states (DE) to prevent the algorithm from retrying useless paths.
• 3. A list of nodes (SL) on the current solution path that is returned if a goal is found.
• 4. Explicit checks for membership of new states in these lists to prevent looping.

Internal and External Properties

The properties of vertices and edges can be stored inside the the graph data structure or outside in some suitably addressable data structure, such as an array or an associative map.

Algorithms for Finding the Shortest Path

We want to find the shortest path from one vertex to all other vertices. We start with a weighted (undirected) graph

This graph could be represented using an adjacency list adj[][] (C/C++ syntax), where each entry adj[u] contains pairs of the form {v, w} - representing that vertex u is connected to vertex v with an edge weight of w and we are also given a source vertex src. We need to find the shortest path distances from the source vertex to all other vertices in the graph.

Note The given graph does not contain any negative edge.

Example:

Input: src = 0, adj[][] = [[[1, 4], [2, 8]],
                                                [[0, 4], [4, 6], [2,3]],
                                                [[0, 8], [3, 2], [1,3]],
                                                [[2, 2], [4, 10]],
                                                [[1, 6], [3, 10]]]

Topological Sort

One of the most useful algorithms on graphs is topological sort, in which the nodes of an acyclic graph are placed in a total order consistent with the edges of the graph; that is, if there is an edge (u,v), then u comes before v in the resulting total order. This is useful when you need to order a set of elements and some elements have no ordering constraint relative to other elements.

For example, suppose you have a set of tasks to perform, but some tasks have to be done before other tasks can start. In what order should you perform the tasks? This problem can be solved by representing the tasks as nodes in a graph with an edge from task₁ to task₂ if task₁ must be done before task₂. A topological sort of the graph will give an ordering in which all of these constraints are satisfied.

Of course, it is impossible to topologically sort a graph with a cycle in it. So to topologically sort a graph, it must be a DAG. But the interesting thing is that the condition of being a DAG is not only necessary for the existence of a topological sort, it is also sufficient. That is, all DAGs have at least one topological sort.

We can obtain a linear-time algorithm for topological sort from DFS. The key observation is that a node finishes (is marked black) only after all of its descendants have been marked black. Therefore, a node that is marked black later must come earlier when topologically sorted. A a postorder traversal generates nodes in the reverse of a topological sort:

[...]

Minimum Spanning Tree*

(From https://www.w3schools.com/dsa/dsa_theory_mst_minspantree.php)

Ordered Sets of Arcs/Edges

In choosing the data structures suitable for implementing a graph, we must decide whether we want the arcs or edges to be ordered, that is whether it makes sense to maintain that a given edge is the j_th edge of all that leave the i_th node, or at least whether for each arc a_n its successor a_n+1 can be found, as long as a_n is not the last arc leaving a node.

Depth-first search algorithms in particular require that arcs be next-able when they backtrack to a previous, unexhausted node to resume digging.

Ordered, Directed or Tuple Hypergraphs

In a tuple hypergraph the edges are not sets (unordered) but tuples (ordered). This enables modelling the sentences in a natural language, thus extending the expressive power of semantic networks.

Semantic networks are good for representing binary relationships between objects. In Andrew knows Philip, Andrew and Philip represent entities, and know might be represented as a weight in a graph. We would also succeed in representing sentences like Anne knows Italy, or Anne lives in Italy, if it is understood that the weight of the latter is live(s) in. But the model cannot represent sentences like Mary writes novels on a computer because here write(s) is being used as a ternary relationship. This relationship could be expressed through an edge consisting of an entity and a tuple of two entities (a pair), or through a tuple of three entities. And so on.

Variations

• A hypergraph may be a std::multimap<Node&, std::set<Node&> >,
• hyperarcs might be arrays of nodes: typedef std::vector<Node&> hyperarc;

Formal Mapping Between Graphs and Hypergraphs

Both graphs and hypergraphs have nodes. They differ in whether they connect their nodes through edges or through hyperedges. The way to map between a graph and a hypergraph relies on the concept of typed graphs:

• a graph node's children are hyperedge nodes, that is nodes whose children are non-hyperedge nodes...
• ...

A weighted graph can model the hyperedges in a phypergraph like this:

• Either a graph have two types of nodes, one representing objects or nodes in a hypergraph and the other representing relationships between object nodes,
• or ...

Predicators

Imagine a universe of entities (objects, persons, words etc.). Programmatically, these might be held in an array (std::vector), a linked list, an std::set etc.

On top of this we might want to build a layer of first-order predicators, that is predicates that take 0 to n references to entities in the bottom layer, as in cry(John). Programmatically, predicators would have a container objects such as an array or even a linked list (since growing a list never invalidates pointers to its members).

Next, a layer of second order predicators would hold predicates on first order predicators, for example cause(cry(John), wakeup(Peter)).

And so on. Note that predicates of different order would all have a container for their predicates, whereas atomic entities would not. But what about predicates that take arguments of mixed-order, as in know(I, sleep(Peter))? May be we would want to derive both predicates and entities from an ancestor Entity class and resolve types polymorphically should the need arise.

Hypergraphs and the Entity-Relationship Model

Ordered or tuple hypergraphs can be used to represent simple and compound sentences in a language. The texts or sentences of a language are made up of entities (noun phrases) and relationships or predications on entities and relationships themselves.

A linguistical hypergraph would have two kinds of nodes: entity nodes and relationship nodes...

Terminology And Concepts

A flow network if often what we call a directed graph with a flow flowing through it.

The capacity c of an edge tells us how much flow is allowed to flow through that edge. Each edge also has a flow value that tells how much the current flow is in that edge. For instance 3/7 might represent a flow of 3 and a capacity of 7. The flow cannot be greater than the capacity.

In its simplest form, a flow network has one source vertex s where the flow comes out, and one sink vertex t where the flow goes in. The other vertices just have flow passing through them.

For all vertices except s and t, there is a conservation of flow, which means that the same amount of flow that goes into a vertex, must also come out of it.

The maximum flow is found by algorithms such as Ford-Fulkerson, or Edmonds-Karp, by sending more and more flow through the edges in the flow network until the capacity of the edges are such that no more flow can be sent through. Such a path where more flow can be sent through is called an augmented path.

Residual Network

The Ford-Fulkerson and Edmonds-Karp algorithms are implemented using something called a residual network. This will be explained in more detail on the next pages.

The residual network is set up with the residual capacities on each edge, where the residual capacity of an edge is the capacity on that edge, minus the flow. So when flow is increased in an edge, the residual capacity is decreased with the same amount.

For each edge in the residual network, there is also a reversed edge that points in the opposite direction of the original edge. The residual capacity of a reversed edge is the flow of the original edge. Reversed edges are important for sending flow back on an edge as part of the maximum flow algorithms.

Multiple Source and Sink Vertices

The Ford-Fulkerson and Edmonds-Karp algorithms expects one source vertex and one sink vertex to be able to find the maximum flow.

If the graph has more than one source vertex, or more than one sink vertex, the graph should be modified to find the maximum flow.

To modify the graph so that you can run the Ford-Fulkerson or Edmonds-Karp algorithm on it, create an extra super-source vertex if you have multiple source vertices, and create an extra super-sink vertex if you have multiple sink-vertices.

From the super-source vertex, create edges to the original source vertices, with infinite capacities. And create edges from the sink vertices to the super-sink vertex similarly, with infinite capacities.

The Ford-Fulkerson or Edmonds-Karp algorithm is now able to find maximum flow in a graph with multiple source and sink vertices, by going from the super source S, to the super sink T.

The Max-flow Min-cut Theorem

To understand what this theorem says we first need to know what a cut is.

We create two sets of vertices: one with only the source vertex inside it called S, and one with all the other vertices inside it (including the sink vertex) called T. Now, starting in the source vertex, we can choose to expand set S by including adjacent vertices and excluding them from T, and continue to include adjacent vertices as much as we want as long as we do not include the sink vertex.

Expanding set S will shrink set T, because any vertex belongs either to set S or set T.

In such a setup, with any vertex belonging to either set S or set T, there is a cut between the sets. The cut consists of all the edges stretching from set S to set T.

If we add all the capacities from edges going from set S to set T, we get the capacity of the cut, which is the total possible flow from source to sink in this cut.

The minimum cut is the cut we can make with the lowest total capacity, which will be the bottleneck.

The max-flow min-cut theorem says that finding the minimum cut in a graph, is the same as finding the maximum flow, because the value of the minimum cut will be the same value as the maximum flow.

Ford-Fulkerson Algorithm

(From https://www.w3schools.com/dsa/dsa_algo_graphs_fordfulkerson.php)

The Ford-Fulkerson algorithm works by looking for a path with available capacity from the source to the sink (called an augmented path), and then sends as much flow as possible through that path. The Ford-Fulkerson algorithm continues to find new paths to send more flow through until the maximum flow is reached.

Note: The Ford-Fulkerson algorithm is often described as a method instead of as an algorithm, because it does not specify how to find a path where flow can be increased. This means it can be implemented in different ways, resulting in different time complexities. But we will call it an algorithm here, and use Depth-First-Search to find the paths.

Edmonds-Karp Algorithm

(From https://www.w3schools.com/dsa/dsa_algo_graphs_edmondskarp.php)

The Edmonds-Karp algorithm is very similar to the Ford-Fulkerson algorithm, except the Edmonds-Karp algorithm uses Breadth First Search (BFS) to find augmented paths to increase flow.

The Edmonds-Karp algorithm works by using Breadth-First Search (BFS) to find a path with available capacity from the source to the sink (called an augmented path), and then sends as much flow as possible through that path. It continues to find new paths to send more flow through until the maximum flow is reached.