KiCad PCB EDA Suite
from_to_cache.cpp File Reference
#include <cstdio>
#include <memory>
#include <reporter.h>
#include <board.h>
#include <string_utils.h>
#include <pcb_expr_evaluator.h>
#include <connectivity/connectivity_data.h>
#include <connectivity/connectivity_algo.h>
#include <connectivity/from_to_cache.h>

Go to the source code of this file.

Enumerations

enum  PATH_STATUS { PS_OK = 0, PS_MULTIPLE_PATHS = -1, PS_NO_PATH = -2 }
 

Functions

static bool isVertexVisited (CN_ITEM *v, const std::vector< CN_ITEM * > &path)
 
static PATH_STATUS uniquePathBetweenNodes (CN_ITEM *u, CN_ITEM *v, std::vector< CN_ITEM * > &outPath)
 

Enumeration Type Documentation

◆ PATH_STATUS

Enumerator
PS_OK 
PS_MULTIPLE_PATHS 
PS_NO_PATH 

Definition at line 53 of file from_to_cache.cpp.

53  {
54  PS_OK = 0,
55  PS_MULTIPLE_PATHS = -1,
56  PS_NO_PATH = -2
57 };

Function Documentation

◆ isVertexVisited()

static bool isVertexVisited ( CN_ITEM v,
const std::vector< CN_ITEM * > &  path 
)
static

Definition at line 60 of file from_to_cache.cpp.

61 {
62  for( auto u : path )
63  {
64  if ( u == v )
65  return true;
66  }
67 
68  return false;
69 }

References path.

Referenced by uniquePathBetweenNodes().

◆ uniquePathBetweenNodes()

static PATH_STATUS uniquePathBetweenNodes ( CN_ITEM u,
CN_ITEM v,
std::vector< CN_ITEM * > &  outPath 
)
static

Definition at line 72 of file from_to_cache.cpp.

73 {
74  using Path = std::vector<CN_ITEM*>;
75  std::deque<Path> Q;
76 
77  Path pInit;
78  bool pathFound = false;
79  pInit.push_back( u );
80  Q.push_back( pInit );
81 
82  while( Q.size() )
83  {
84  Path path = Q.front();
85  Q.pop_front();
86  CN_ITEM* last = path.back();
87 
88  if( last == v )
89  {
90  outPath = path;
91  if( pathFound )
92  return PS_MULTIPLE_PATHS;
93  pathFound = true;
94  }
95 
96  for( auto ci : last->ConnectedItems() )
97  {
98  bool vertexVisited = isVertexVisited( ci, path );
99 
100  for( auto& p : Q )
101  if( isVertexVisited( ci, p ) )
102  {
103  vertexVisited = true;
104  break;
105  }
106 
107  if( !vertexVisited )
108  {
109  Path newpath( path );
110  newpath.push_back( ci );
111  Q.push_back( newpath );
112  }
113  }
114  }
115 
116  return pathFound ? PS_OK : PS_NO_PATH;
117 };
const CONNECTED_ITEMS & ConnectedItems() const
static bool isVertexVisited(CN_ITEM *v, const std::vector< CN_ITEM * > &path)

References CN_ITEM::ConnectedItems(), isVertexVisited(), path, PS_MULTIPLE_PATHS, PS_NO_PATH, and PS_OK.

Referenced by FROM_TO_CACHE::cacheFromToPaths().