graphtreepartition.cc.svn-base

Probabilistic graphical models in matlab.

	VertexDescriptor candidate;
	
	// Follow subroutine for a given subgraph
	
	while(!gray_vertices.empty())
	{
		
		// It is *only* a candidate because of the backtrack mechanism
		
		GraphPartitionQueueOrder<Graph>::myTuple top_element = gray_vertices.top();
		
		candidate = top_element.get<0>();
		
		//unsigned int old_choices = gray_vertices.top().get<1>();
		
		//unsigned int new_choices = compute_possible_choices(g, color, candidate);
		
		gray_vertices.pop();
		
		/*
		 if ( old_choices != new_choices)
		 {
			 cout << "Update: for " << g[candidate]->get_random_variable()->get_index() << " , we now have " << new_choices << " choices now." << endl;
			 
			 gray_vertices.push( make_tuple(candidate, new_choices, top_element.get<2>(), top_element.get<3>(), top_element.get<4>() ) );
			 
			 continue;
		 }
		 */
		//cout << "Staying at " << new_choices << " choices." << endl;
		
		
		if (get(color, candidate) != Color::gray())
		{
			//cerr << "Candidate " << g[candidate]->get_random_variable()->get_index() << " was refused " << endl;
			continue;
		}
		
		++step;
		trapped_vertex = false;
		
		// Loop on the neighbors exploration
		
		for (tie (u, u_end) = adjacent_vertices(candidate, g); u != u_end; ++u)
		{
			// Red means already chosen (in fact, the parent of the candidate)
			// We never do anything with the parent
			
			if ( get(color,*u) == Color::red() )
			{
				continue;
			}
			
			if (free_edges[*u] == 1)
			{
				trapped_vertex = true; 
			}
			
			// Black means already not possible, we still add it to the backtrack_list
			// This is because we need to decrease the free edges
			// Note that black and grey have the same effect
			
			if ( get(color,*u) == Color::black() )
			{
				backtrack_list_black.push_back(*u);
				continue;
			}
			
			if ( get(color,*u) == Color::gray())
			{
				backtrack_list_black.push_back(*u);
				continue;
			}
			
			// Here check if it has one neighbor that is black (or later)
			
			backtrack_list_gray.push_back(*u);
		}
		
		// If trapped_vertex is set to true, we have to backtrack. We undo everything and don't accept the candidate.
		
		if (trapped_vertex)
		{
			backtrack_list_black.clear();
			backtrack_list_gray.clear();
			//cout << ". Refused. "  << endl;
		}
		
		// Else candidate is accepted and we make all the modifications.
		
		else
		{
			//cout << ". Accepted. "  << endl;
			put(color, candidate, Color::red());
			
			for (list<VertexDescriptor>::iterator it = backtrack_list_black.begin() ; it != backtrack_list_black.end(); ++it)
			{
				put(color, *it, Color::black());
				free_edges [*it] = free_edges [*it] -1;
				available_neighbors[*it].remove(candidate);
				
				// If we reach only one free edge, we need to transmit (propagate) that !!
				
				if ( free_edges [*it] == 1)
				{
					//cout << g[*it]->get_random_variable()->get_index() << " has reached 1 and now we escape" << endl;
					
					transmit_escape(*it, color, free_edges, available_neighbors, g);
				}
				
			}
			
			for ( list<VertexDescriptor>::iterator it = backtrack_list_gray.begin() ; it != backtrack_list_gray.end(); ++it)
			{
				put(color, *it, Color::gray());
			}
			
			for ( list<VertexDescriptor>::iterator it = backtrack_list_gray.begin() ; it != backtrack_list_gray.end(); ++it)
			{
				// Following is old code not used anymore
				
				/*
				unsigned int quantity(0);
				
				if (check_black_neighbor(g, color, *it))
				{
					quantity = 10;
				}
					
					if (check_gray_neighbor(g, color, *it))
					{
						quantity = 5;
					}
				*/
				
				
				gray_vertices.push(make_tuple (*it, compute_possible_choices(g, color, *it), out_degree(*it, g), step, 0));
				available_neighbors[*it].remove(candidate);
				free_edges [*it] = free_edges [*it] -1;
			}
			
			backtrack_list_black.clear();
			backtrack_list_gray.clear();
		}
		
    }
	
	return true;
}


template <class Graph>
void partition_mrf_graph_into_chains (Graph & g)
{
	// Will work for graphs of size 2n (100*100...)
	
	const unsigned int top_left(0);
	const unsigned int bottom_left(1);
	const unsigned int bottom_right(2);
	const unsigned int top_right(3);
	
	// VERY UGLY
	
	unsigned int rows = mrf_rows;
	unsigned int columns = mrf_columns;
	
	// End hard coded
	
	typename graph_traits<Graph>::vertex_descriptor current_node = 0;
	
	unsigned int state = top_left;
	
	vector <bool> bool_vec(rows*columns, true);
	
	bool bool_cont = true;
	
	Graph & new_chain  = g.create_subgraph();
	
	add_vertex( current_node, new_chain);
	add_vertex( current_node+rows*columns, new_chain);
	bool_vec[current_node] = false;
	
	while (bool_cont)
	{
		
		switch (state)
		{
			case top_left:
			{
				
				++current_node;
				
				bool_cont = false;
				while (  (current_node % rows != 0) && bool_vec[current_node+1] )
				{
					bool_cont = true;
					add_vertex( current_node, new_chain);
					add_vertex( current_node+rows*columns, new_chain);
					bool_vec[current_node] = false;
					//cout << "Adding " << current_node << endl;
					++current_node;
				}
				
				--current_node;
				
				state = bottom_left;
			};
				
				break;
				
			case bottom_left:
			{
				current_node += rows;
				
				bool_cont = false;
				while (  current_node <  rows*(columns-1)  && bool_vec[current_node+rows] )
				{
					bool_cont = true;
					add_vertex( current_node, new_chain);
					add_vertex( current_node+rows*columns, new_chain);
					bool_vec[current_node] = false;
					//cout << "Adding " << current_node << endl;
					current_node += rows;
				}
				
				current_node -= rows;
				
				state = bottom_right;
			};
				
				break;
				
			case bottom_right:
			{
				--current_node;
				
				bool_cont = false;
				while ( (current_node %  rows) != 0 && bool_vec[current_node-1] )
				{
					bool_cont = true;
					add_vertex( current_node, new_chain);
					add_vertex( current_node+rows*columns, new_chain);
					bool_vec[current_node] = false;
					//cout << "Adding " << current_node << endl;
					--current_node;
				}
				
				++current_node;
				
				state = top_right;
			};
				break;
				
			case top_right:
			{
				current_node -= rows;
				
				bool_cont = false;
				while ( bool_vec[current_node-rows] )
				{
					bool_cont = true;
					add_vertex( current_node, new_chain);
					add_vertex( current_node+rows*columns, new_chain);
					bool_vec[current_node] = false;
					//cout << "Adding " << current_node << endl;
					current_node -= rows;
					//cout << "next 2 " << current_node-rows << ", " << bool_vec[current_node-rows] << endl;
				}
				
				current_node += rows;
				
				state = top_left;
			};
				break;
				
		}
	}
	
	//cout << "finished" << endl;
	
	Graph & second_chain = g.create_subgraph();
	
	for (unsigned int it = 0; it < bool_vec.size(); ++it)
	{
		if ( bool_vec[it])
		{
			add_vertex(it, second_chain);
			add_vertex(it+rows*columns, second_chain);
		}
	}	
}

template <class Graph>
void partition_simple_chain(Graph & g)
{
	typename graph_traits <Graph>::vertex_iterator u, u_end;
	
	Graph & chain = g.create_subgraph();
	
	for (tie (u, u_end) = vertices(g); u != u_end; ++u)
	{
		add_vertex(*u, chain);
	}
}

template <class Graph, class ColorMap, class ParentMap>
bool check_rv( Graph & g, typename graph_traits<Graph>::vertex_descriptor candidate, list < typename graph_traits<Graph>::vertex_descriptor> & backtrack_list_gray, ColorMap  & color, ParentMap & parent)
{
	typename graph_traits <Graph>::adjacency_iterator u, u_end;
	typedef typename property_traits<ColorMap>::value_type ColorValue;
	typedef color_traits<ColorValue> Color;
	
	for (tie (u, u_end) = adjacent_vertices(candidate, g); u != u_end; ++u)
	{
		if ( get(color,*u) == Color::red() )
		{
			continue;
		}
		
		if ( get(color, *u) == Color::black() )
		{
			//backtrack_list_black.push_back(*u);
			cout << "Something strange happened. It should never be black";
			continue;
		}
		
		if ( get(color, *u) == Color::gray())
		{
			//backtrack_list_black.push_back(*u);
			//This means we shouldn't choose this vertex at all
			return false;
		}
		
		//cout << "We grayed the Potential number " << g[*u]->index << endl; 
		
		backtrack_list_gray.push_back(*u);
	}
	
	return true;
}

template <class Graph, class ColorMap, class ParentMap>
bool	check_potential( Graph & g, typename  graph_traits<Graph>::vertex_descriptor candidate, list < typename graph_traits<Graph>::vertex_descriptor> & backtrack_list_gray, list < typename graph_traits<Graph>::vertex_descriptor> & backtrack_list_black, ColorMap  & color, ParentMap & parent, vector <unsigned int> & free_edges)
{
	typename graph_traits <Graph>::adjacency_iterator u, u_end;
	typedef typename property_traits<ColorMap>::value_type ColorValue;
	typedef color_traits<ColorValue> Color;
	
	bool non_trapped_vertex(true);
	
	for (tie (u, u_end) = adjacent_vertices(candidate, g); u != u_end; ++u)
	{
		if ( get(color,*u) == Color::red() )
		{
			continue;
		}
		
		if (free_edges[*u] == 1)
		{
			//non_trapped_vertex = false; 
		}
		
		if ( get(color,*u) == Color::black() )
		{
			//backtrack_list_black.push_back(*u);
			//cout << "Something strange happened (or not)" << endl;
			continue;
		}
		
		if ( get(color,*u) == Color::gray())
		{
			backtrack_list_black.push_back(*u);
			
			continue;
		}
		
		//cout << "We grayed the Variable number " << g[*u]->get_random_variable()->get_index() << endl; 
		
		backtrack_list_gray.push_back(*u);
	}
	
	return non_trapped_vertex;
}


typedef iterator_property_map < vector < default_color_type >::iterator, property_map < SubDiscreteFactorGraph, vertex_index_t>::type > DiscreteFactorGraphColorMap;
typedef iterator_property_map < vector < graph_traits <SubDiscreteFactorGraph>::vertex_descriptor >::iterator, property_map < SubDiscreteFactorGraph, vertex_index_t>::type > DiscreteFactorGraphParentMap;

bool get_phantom_potential(MessageNode < DiscreteRandomVariable, graph_traits <DiscreteFactorGraph>::vertex_descriptor> * uncasted )
{
	typedef graph_traits <DiscreteFactorGraph>::vertex_descriptor VertexDescriptor;
	
	PotentialMessageNode < DiscreteRandomVariable, DiscretePotential, VertexDescriptor > * ptr = dynamic_cast < PotentialMessageNode < DiscreteRandomVariable, DiscretePotential, VertexDescriptor > * > (uncasted);
	
	if (!ptr)
	{
		return false;
	}
	
	else
	{
		return ptr->get_phantom();
	}
}

//unsigned int teton = 0;

template <>
bool get_tree(DiscreteFactorGraph & g, DiscreteFactorGraphColorMap color, DiscreteFactorGraphParentMap parent)
{
	
	//cout << "We use the correct get_tree" << endl;
	
	typedef DiscreteFactorGraph Graph;
	
	typedef  graph_traits <Graph>::vertex_descriptor VertexDescriptor;
	typedef  property_traits<DiscreteFactorGraphColorMap>::value_type ColorValue;
	typedef color_traits<ColorValue> Color;
	
	graph_traits <Graph>::vertex_iterator v, v_end;
	
	priority_queue<GraphPartitionQueueOrder <Graph>::myTuple ,vector <GraphPartitionQueueOrder <Graph>::myTuple >, GraphPartitionQueueOrder <Graph> > gray_vertices ( (GraphPartitionQueueOrder <Graph> (g)) );
	
	graph_traits <Graph>::adjacency_iterator u, u_end;
	
	list <VertexDescriptor> backtrack_list_black;
	list <VertexDescriptor> backtrack_list_gray;
	
	vector <unsigned int> free_edges;
	
	unsigned int a(0);
	unsigned int b(0);
	
	VertexDescriptor vertex_with_lowest_degree = VertexDescriptor();