00001
00002
00003
00004
00005
00006
00007
00008
00009
00010
00011
00012
00013
00014
00015
00016
00017
00018
00019
00020
00021
#ifndef SH_MATCHING_H
00022
#define SH_MATCHING_H
00023
00024
#include <list>
00025
#include <vector>
00026
00027
#include "Vertex.h"
00028
#include "common.h"
00029
00030
class Edge ;
00031
class ProgressOutput ;
00032
00041 class Matching {
00042
public:
00048
Matching (
Graph* g,
ProgressOutput* po = NULL) ;
00049
00050
~Matching (
void) ;
00051
00055 bool isMatched (
Vertex *v)
const
00056
{
return VertexInformation[v->
getLabel()].isMatched() ; } ;
00057
00061 bool isMatched (VertexLabel vlbl)
const
00062
{
return VertexInformation[vlbl].isMatched() ; } ;
00063
00067 bool isExposed (
Vertex *v)
const
00068
{
return VertexInformation[v->
getLabel()].isExposed() ; } ;
00069
00073 bool isExposed (VertexLabel vlbl)
const
00074
{
return VertexInformation[vlbl].isExposed() ; } ;
00075
00080 const Edge*
getMatchingEdge (
Vertex *v)
const
00081
{
return VertexInformation[v->
getLabel()].getMatchingEdge() ; } ;
00082
00087 bool includesEdge (
const Edge* e)
const {
return includesEdge(*e) ; } ;
00088
bool includesEdge (
const Edge& e)
const ;
00089
00093 unsigned long getCardinality (
void)
const
00094
{
return Cardinality ; } ;
00095
00096 const std::list<Vertex*>&
getExposedVertices (
void)
const
00097
{
return ExposedVertices ; } ;
00098
00103
float getMatchedRate (
void) const ;
00104
00108
float getAvgEdgeWeight (
void) const ;
00109
00118 const std::list<
Vertex*> *getExposedVerticesLink (
void)
const
00119
{
return &
ExposedVertices ; } ;
00120
00128
void addEdge (
const Edge& e) ;
00129 void addEdge (
Edge* e) { addEdge(*e) ; } ;
00130
00137
void removeEdge (
const Edge& e) ;
00138
00142 const std::list<Edge*>&
getEdges (
void)
const
00143
{
return MatchingEdges ; } ;
00144
00154
Matching& augment (
const Edge** path,
unsigned long len) ;
00155
00156
Matching& augment (
const std::vector<Edge*>& path) ;
00157
00158
void printVerboseInfo (
void) const ;
00159
00160 private:
00165 class
VertexInfo {
00166
public:
00167 VertexInfo (std::list<Edge*>::iterator mit)
00168 { setMatched (mit) ; } ;
00169
00170 VertexInfo (std::list<Vertex*>::iterator eit)
00171 { setExposed (eit) ; } ;
00172
00173 bool isExposed (
void)
const
00174
{
return !Matched ; } ;
00175
00176 bool isMatched (
void)
const
00177
{
return Matched ; } ;
00178
00179 Edge *getMatchingEdge (
void)
const
00180
{
return *MatchedIterator ; } ;
00181
00182 std::list<Edge*>::iterator getMatchedIterator (
void)
const
00183
{
return MatchedIterator ; } ;
00184
00185 std::list<Vertex*>::iterator getExposedIterator (
void)
const
00186
{
return ExposedIterator ; } ;
00187
00188 void setMatched (std::list<Edge*>::iterator mit)
00189 { Matched =
true ; MatchedIterator = mit ; } ;
00190
00191 void setExposed (std::list<Vertex*>::iterator eit)
00192 { Matched =
false ; ExposedIterator = eit ; } ;
00193
00194
private:
00195 bool Matched ;
00197 std::list<Edge*>::iterator MatchedIterator ;
00199 std::list<Vertex*>::iterator ExposedIterator ;
00200 } ;
00201
00203 std::vector<VertexInfo>
VertexInformation ;
00204
00206 std::list<Vertex*>
ExposedVertices ;
00207
00209 std::list<Edge*>
MatchingEdges ;
00210
00212 unsigned long Cardinality ;
00213
00215 Graph*
TheGraph ;
00216
00218 ProgressOutput*
PrOut ;
00219
00223
void setCardinality (
unsigned long c) ;
00224
00225
public:
00226
bool check (
void) const ;
00227
bool check_MatchingEdges_vs_VertexInformation (
void) const ;
00228
bool check_ExposedVertices_vs_VertexInformation (
void) const ;
00229
bool check_VertexInformation_Integrity (
void) const ;
00230
00231
bool check_ValidAugPath (const std::vector<
Edge*>& path) const ;
00232 } ;
00233
00234 #endif